Similarly, at the next level there are two values and three pointers in each index entry. Each time we drop to another level, we narrow our search for a particular record. For example, if we continue to fol-low the leftmost pointer from the top entry and then follow the rightmost pointer from there, we can access all the records whose key field value is greater than 27 and less than or equal to 45. We have eliminated all that were greater than 45 at the first level.
B-trees are, by definition, balanced. That is, all of the data records are exactly the same distance from the top entry in the index set. This aspect of B-trees ensures performance efficiency, although the algo-rithms for inserting and deleting records are more complex than those for ordinary trees (which can be unbalanced), because several index entries may need to be modified when records are added or deleted to keep all records the same distance from the top index entry.
Summary of Data Structures
Figure H-11 summarizes the techniques for maintaining ordered flat files. Three supporting data struc-tures are possible. Sequential lists can be used, but the data must be duplicated in order to maintain several orders. Because sequential lists are not used in database processing, we will not consider them further. Both linked lists and indexes can be used without data duplication. B-trees are special applica-tions of indexes.