Slide 1.10: AVL trees and B-trees
Slide 1.12: Hashing
Home

A Short History of File Structure Design (Cont.)

1970s (B-Trees) (Cont.)
The figure below shows a B-tree with 3 keys/node. Keys in internal nodes are surrounded by pointers, or record offsets, to keys that are less than or greater than, the key value.

For example, all keys less than 22 are to the left and all keys greater than 22 are to the right.

1970s (B+ Trees)
However, it is no longer could a file be accessed sequentially with efficiency by using a B-tree. This problem was solved almost immediately by adding a linked list structure at the bottom level of the B-tree. The combination of a B-tree and a sequential linked list is called a B+ tree, which is defined as follows:
a B-tree in which keys are stored in the leaves.
The figure below shows a B+ tree where all keys are stored at the leaf level, with their associated data values. Duplicates of the keys appear in internal parent nodes to guide the search. The left pointer designates all keys less than the value, while the right pointer designates all keys greater than or equal to the value.

For example, all keys less than 22 are on the left, and all keys greater than or equal to 22 are on the right.