Slide 16.3: Maintaining a sequence set (cont.) Slide 16.5: The content of the index: separators instead of keys Home

Adding a Simple Index to the Sequence Set

---

The previous two slides show how to maintain a set of records so we can access them sequentially in order by key. This slide tries to find an efficient way to locate some specific block containing a particular record, given the record's key. The following figure gives a sequence of blocks showing the range of keys in each block.

The figure on the right shows a simple, single-level index for these blocks. The largest key in the block is the key of the whole block.

The combination of this kind of index with the sequence set of blocks provides complete indexed sequential access.

• If we need to retrieve a specific record, we consult the index and then retrieve the correct block.
• If we need sequential access, we start at the first block and read through the linked list of blocks until we have read them all.

For efficient processing, this simple index must be held in memory entirely; otherwise, binary searching and updating require many disk seeks. B-trees are an excellent structure for handling indexes that are too large to fit entirely in memory. The resulting hybrid structure is a B⁺ tree which

• organizes the index to the sequence set as a B-tree, and
• is a B-tree index plus a sequence set that holds the records.