Database Reference
In-Depth Information
Search for
data with key
value 60
Data File
Random Index
Sorted Index
Address
Key
Data
Key
Address
Key
Address
01
48
……….
48
01
3
15
06
34
………..
34
06
8
12
11
21
……….
21
11
21
11
12
8
……….
8
12
34
6
15
3
………..
3
15
48
1
23
81
……….
81
23
60
44
60
44
44
60
……….
81
23
Figure 12-13
Primary index search.
file, with an index file with index records arranged in a random manner, or with an
index file with index records arranged in the order of the primary key values. Figure
12-13 shows these three options with key values and addresses.
Suppose your intention is to search for a data record with key value 60. It
takes seven I/O operations to search the data file directly. When you arrange the
index records randomly in the index file, it takes the same number of I/O
operations. However, when you arrange the index records sequentially in the index
file in the order of the key values, the I/O performance is slightly better, at six I/O
operations.
How can we improve the performance even more? Suppose you start your
search on the index file at the middle of the index file, that is, at the record with
index value 34. Compare the key value of 60 you are searching for with the value
34 at the middle of the index file. Because the value 60 is greater than 34, then
key value 60 must be in the second half of the index file. Then go to the middle of
the second half and get the index record. In our example, this index record happens
to be the one with value 60 and, therefore, our search is over with just two I/O
operations.
Step back and observe how we are able to improve the performance in this type
of search. We divide the index entries in a binary fashion and compare the search
value with the index value at the middle of the file. Immediately we are able to
determine in which half of the file the key value lies. We then proceed to that half
and compare the key value with the index at the middle of the selected half. This
process of binary divisions continues and speeds up the search process. This tech-
nique, known as binary search, cuts the number of searches to find the desired index
record.
Binary Search
The binary search method utilizes a binary search tree. The index entries are logi-
cally arranged in the form of an inverted tree, where the root is at the top. The root
Search WWH ::
Custom Search