Slide 16.5: The content of the index: separators instead of keys Slide 16.7: Simple prefix B+ tree maintenance Home

The Simple Prefix B⁺ Tree

---

The figure shows a B-tree index set for the sequence set in the previous slide. The B-tree index is called the index set. Taken together with the sequence set, it forms a file structure called a simple prefix B⁺ tree:

• The modifier simple prefix indicates the index set contains shortest separators or prefix of the keys instead of the actual key copies.
• The last separator is not needed in a prefix tree as the last key is not needed for an interior node of B-trees. Hence, the extra key is dropped.

Note that the index set is a B-tree, and a node containing N separators branches to N+1 children. To search for the record with the key EMBRY, the following steps are taken:

1. Start at the root, comparing EMBRY with the separator E.
2. Since EMBRY comes after E, branch to the right, retrieving the node containing the separators F and FOLKS.
3. Since EMBRY comes before even the first of these separators, follow the branch that is to the left of the F separator, which leads to Block 4, the correct block in the sequence set.