Slide 16.10: Internal structure of index set blocks Slide 16.12: Loading a simple prefix B+ tree Home

Internal Structure of Index Set Blocks (Cont.)

---

A Variable-Order B-Tree (Cont.)
The purpose of the index set is to guide us downward through the levels of the simple prefix B⁺ tree, leading us to the sequence set block we want to retrieve. The following figure shows one structure of an index set block:

• Separator count: It is used to find the middle element in the index to the separators for a binary search.
• Total length of separators: The list of merged separators varies in length from block to block. It is used to find how long the list is; so the beginning of the index could be found.
• Relative block numbers (RBN): They reference fixed-length blocks.

The following two steps show how to use this block structure as a road map to find the record in the sequence set for Beck:

1. Perform a binary search of the separators through this index, finally concluding that the key Beck falls between the separators Ba and Bro.
2. The next block we need to retrieve has the RBN stored in the B02 position of the RBN vector. The figure below gives a conceptual relationship of separators and RBNs.
   
   
   The next block could be another index set block or the sequence set block we are looking for.