Indexing: Primary, Clustering, Secondary and Multilevel Indexes

An index is an auxiliary file that speeds up search on a field, the indexing field or search key. Each index entry is a pair $\langle K, P \rangle$: a key value and a pointer to a data block or record. Index entries are much smaller than data records, so many fit in a block, and a search through the index reads far fewer blocks than a search through the data file.

The calculations here start from the block size, the record and field sizes and the number of records, and find the number of index entries, index blocks, levels of a multilevel index, or block accesses for a search. The single-level and multilevel calculations here lead directly to B-Trees and B+ Trees.

Index blocking factor. With key size $V$ and pointer size $P$, an entry has $V + P$ bytes and $\text{bfr}_i = \lfloor B / (V + P) \rfloor$ entries fit in a block of $B$ bytes.

Dense and sparse.

Three single-level ordered indexes (Elmasri and Navathe's names):

A file has at most one physical order, so it has at most one primary or clustering index (not both), but any number of secondary indexes.

Terminology warning. Korth, Silberschatz and Sudarshan call any index on the field that orders the file a clustering (or primary) index and every other index nonclustering (or secondary). In Elmasri and Navathe "primary" means ordering key and "clustering" means ordering non-key. The Elmasri and Navathe meanings are the ones used in the definitions and examples; when a question uses one of these words, check from its wording whether the field is a key and whether it orders the file.

Why levels are logarithmic in the fan-out. Each level reduces the number of blocks by a factor of $\text{fo}$, since one entry of level $j + 1$ points to one block of level $j$. After $t$ levels $r_1 / \text{fo}^t \le 1$, with at least one nonempty index level, so $t = \max(1,\lceil \log_{\text{fo}} r_1 \rceil)$. For $r_1=1$, this gives one index level and two uncached reads including the data block. For ordinary successful binary search of $b_i\ge1$ index blocks, the worst-case index probes satisfy $W(0)=0$ and $W(b_i)=1+W(\lfloor b_i/2\rfloor)$, since the larger remaining half has $\lfloor b_i/2\rfloor$ blocks. Thus $W(b_i)=\lfloor\lg b_i\rfloor+1$, followed by one data-block read: $\lfloor\lg b_i\rfloor+2$ uncached reads in total. The shortcut $\lceil\lg b_i\rceil$ agrees with the index-probe count only when $b_i$ is not a power of two; at a power of two, including 1, it undercounts by one.

Why a sparse index needs a sorted file. The entry for block $j$ says only that keys in block $j$ lie between its anchor and the next anchor. That is true only if the file is sorted on the indexing field.

Counting entries.

The data file is the one from File Organization: $r = 30000$ records of $R = 100$ bytes, $B = 1024$, unspanned, so $\text{bfr} = 10$ and $b = 3000$ data blocks. Key size $V = 9$ bytes, pointer size $P = 6$ bytes, so each entry is 15 bytes and $\text{bfr}_i = \lfloor 1024 / 15 \rfloor = 68$.

Example 1: primary index. The file is sorted on the key. Entries: $3000$ (one per block). Index blocks: $\lceil 3000 / 68 \rceil = 45$. Search: $\lceil \lg 45 \rceil + 1 = 7$ accesses, against $\lceil \lg 3000 \rceil = 12$ with binary search on the data file.

Example 2: secondary index on a key field. The file is not sorted on this field. Entries: $30000$. Index blocks: $\lceil 30000 / 68 \rceil = 442$. Search: $\lceil \lg 442 \rceil + 1 = 10$ accesses, against about $1500$ for a uniformly located existing key (exactly $1500.5$ for equally occupied blocks) for a linear scan. For both 45 and 442 the rounding conventions $\lceil \lg b \rceil$ and $\lfloor \lg b \rfloor + 1$ agree.

Example 3: multilevel version of Example 2 (Figure 2). Level 1: 442 blocks. Level 2: $\lceil 442 / 68 \rceil = 7$ blocks. Level 3: 1 block. So $t = 3 = \lceil \log_{68} 30000 \rceil$, and a search reads $3 + 1 = 4$ blocks.

Example 4: multilevel version of Example 1. Level 1: 45 blocks; level 2: 1 block. $t = 2$, search cost $3$.

Example 5: clustering index. The file is sorted on a non-key field with 20 distinct values. Entries: 20, all in one index block. A search reads the index block, then the first block containing the value, then the following blocks while the value continues.

Example 6: dense against sparse (Figure 1). Four data blocks with keys 5 to 60 in steps of 5, three per block. The sparse index has the four anchors 5, 20, 35, 50; the dense index has all 12 keys. To find 40 with the sparse index, take the largest anchor $\le 40$, namely 35, and scan that block.

Example 7: clustering index with numbers. Same file, sorted on a non-key field with 20 distinct values, each held by $30000 / 20 = 1500$ records. The 20 entries fit in one index block.

The two layouts give the same answer in this uniform, exactly divisible example; layout and starting offset matter for other run sizes.

Example 8: secondary index on a non-key field, with indirection. Same file, a non-ordering field with 1000 distinct values, 30 records each. One entry per value: 1000 entries, $\lceil 1000 / 68 \rceil = 15$ index blocks. Each entry points to a block of 30 record pointers ($30 \times 6 = 180$ bytes, one block).

The data-block term dominates: an index on a field with many records per value saves little over a scan when those records are scattered.

Common misconceptions.