Slide 16.4: Adding a simple index to the sequence set Slide 16.6: The simple prefix B+ tree Home

The Content of the Index:
Separators Instead of Keys

---

The purpose of the index is to assist us when we are searching for a record with a specific key. Actually, we do not need to have keys in the index set. Our real need is for separators. The following figure shows one possible set of separators for the sequence set in the previous slide.

There are many potential separators capable of distinguishing between two blocks.

For example, all of the strings shown between Blocks 3 and 4 in the above figure are potential candidates of the separator. After a string comparison between the key and any of these separators,

• if the key precedes the separator, we look for the key in Block 3, or
• if the key follows the separator, we look in Block 4.

A separator may be the same as the second key; for example, the separator, FOLKS, of Blocks 5 and 6 is the same as the first key contained in Block 6.

The table on the right is then used to solve any ambiguity.

Relation of search key and separator Decision Key < separator Go left Key = separator Go right Key > separator Go right