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:
- Perform a binary search of the separators through this index, finally concluding that the key Beck falls between the separators Ba and Bro.
- 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.