Databases Reference
In-Depth Information
Notice the following about the index records in the tree:
The index records contain salesperson number key values copied from certain of
the salesperson records.
■
Each key value in the tree is associated with a pointer that is the address of either
a lower-level index record or a cylinder containing the salesperson records.
■
Each index record, at every level of the tree, contains space for the same number
of key value/pointer pairs (four in this example). This index record capacity is
arbitrary, but once it is set, it must be the same for every index record at every
level of the index.
■
Each index record is at least half full (in this example each record actually
contains at least two key value/pointer pairs).
■
How are the key values in the index tree constructed and how are the pointers
arranged? The lowest level of the tree contains the highest key value of the
salesperson records on each of the 10 data cylinders. That's why there are 10 key
values in the lowest level of the index tree. Each of those 10 key values has a
pointer to the data cylinder from which it was copied. For example, the leftmost
index record on the lowest level of the tree contains key values 140, 192, and 253,
which are the highest key values on cylinders 1, 2, and 3, respectively. The root
index record contains the highest key value of each of the index records at the next
(which happens to be the last in this case) level down. Looking down from the root
index record, notice that 253 is the highest key value of the first index record at the
next level down, and so on for key values 477 and 641 in the root.
Let's say that you want to perform a direct access for the record for salesperson
361. A stored search routine would start at the root and scan its key values from left
to right, looking for the first key value greater than or equal to 361, the key value for
which you are searching. Starting from the left, the first key value in the root greater
than or equal to 361 is 477. The routine would then follow the pointer associated
with key value 477 to the second of the three index records at the next level. The
search would be repeated in that index record, following the same rules. This time,
key value 368 is the first one from the left that is higher than or equal to 361. The
routine would then follow the pointer associated with key value 368 to cylinder 5.
Additional search cues within the cylinder could then point to the track and possibly
even the position on the track at which the record for salesperson 361 is to be found.
There are several additional points to note about this B
+
-tree arrangement:
The tree index is small and can be kept in main memory indefinitely for a
frequently accessed file.
■
The file and index of Figure 8.14 fit the definition of an indexed-sequential file,
because the file is stored in sequence by salesperson numbers and the index is
built over the Salesperson Number field.
■
The file can be retrieved in sequence by salesperson number by pointing from
the end of one cylinder to the beginning of the next, as is typically done, without
even using the tree index.
■
B
-tree indexes can be and are routinely used to also index non-key, non-unique
fields, although the tree can be deeper and/or the structures at the end of the tree
can be more complicated.
+
■
In general, the storage unit for groups of records can be (as in the above example)
but need not be the cylinder or any other physical device sub-unit.
■
Search WWH ::
Custom Search