Slide 16.10: Internal structure of index set blocks

Slide 16.9: Simple prefix B+ tree maintenance (cont.)
Slide 16.11: Internal structure of index set blocks (cont.)
Home

Internal Structure of Index Set Blocks

Index Set Block Size
The physical size of a node (block) for the index set is usually the same as the physical size of a block in the sequence set because

The choice of the block size of sequence set and index set is based on the same reasons, for example, there is a good fit among this block size, characteristics of the disk drive, and the amount of memory available.
A common block size makes it easier to implement a buffering scheme.
The index set blocks and sequence set blocks are often mingled within the same file to avoid seeking between two separate files while accessing the simple prefix B⁺ tree.

A Variable-Order B-Tree
For maximum flexibility, we sometimes want an index set block being large and to hold a variable number of variable-length separators. Once a block is loaded into memory for use, a binary search rather than sequential search should be applied to its list of separators. For example, suppose the following set of separators is placed into a block:

As,  Ba,  Bro,  C,  Ch,  Cra,  Dele,  Edi,  Err,  Fa,  Fle

We could merge these separators and build an index for them.

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

Perform a binary search on the index to the separators, retrieving first the middle separator, Cra, which starts in position 10.
The search finds that Beck falls between the separators Ba and Bro.