Indexing: dense/sparse indexes, B+ trees, hashing and selection cost

So far we have written the SQL query and discussed what the result would be. This week the question changes: how long does the database take to find that result? The answer depends on the layout on disk and on the indexes. The exam has three kinds of questions on this topic: cost calculation (in ms), inserting into a B+ tree and drawing the final tree, and a “which plan is cheaper?” comparison.

Golden rules:

1. The unit of cost is disk access. CPU is ignored. Reading a block = transfer ($t_T$), jumping to another place = seek ($t_S$).
2. Seek is much more expensive than transfer. On this page we always use $t_S = 4$ ms, $t_T = 0.1$ ms.
3. An index does not always help. If many records match, a secondary index can be slower than a plain scan.
4. In a B+ tree, when a leaf splits the key is copied up, and when an internal node splits it is moved up.

Storage: blocks, records, files

The disk reads and writes data in fixed-size blocks. A record is not read on its own; the whole block that contains it comes into memory. So the important numbers are:

$f_r = \left\lfloor \frac{\text{block size}}{\text{record size}} \right\rfloor \qquad b_r = \left\lceil \frac{n_r}{f_r} \right\rceil$

Example: block 4096 bytes, record 200 bytes. $f_r = \lfloor 20.48 \rfloor = 20$. With 10000 records, $b_r = 500$ blocks.

File organizations:

• Heap file: records are written wherever there is free space, with no order. Insertion is cheap, search is expensive.
• Sequential (sorted) file: records are sorted on a search key. Binary search and range queries are possible, but insertion needs overflow blocks to keep the order.

Index concepts

An index is like the index at the back of a book: it holds “key value → location of the record” pairs. The attribute(s) on which we build the index are called the search key. Note: the search key does not have to be the primary key of the table.

In a sparse index, if you search for stu_id = 'S4471', you find the largest entry in the index that is less than or equal to S4471, go to that block, and move forward in order. This works only if the file is sorted. A secondary index cannot be sparse, because records are scattered and you cannot say “continue after this block”.

With numbers: 10000 records, 500 blocks, 100 entries fit in an index block. A dense index has 10000 entries, that is 100 blocks. A sparse index has 500 entries, that is 5 blocks. Sparse is smaller, while dense can answer some queries without going to the data at all (for example, “does this key exist?”).

Multilevel index

When an index grows, it becomes a file that itself has to be searched on disk. The solution: build another sparse index on top of the index, and continue until the top level fits in a single block. This is called a multilevel index. One block is read from each level, then the data block. The B+ tree is the balanced, updatable form of this idea.

B+ tree

The B+ tree is the default index of databases. Its parameter is $n$: the maximum number of pointers in a node. A node holds at most $n - 1$ keys.

Properties:

• All leaves are at the same depth. The tree is always balanced.
• The real record pointers are only in the leaves. The keys in internal nodes only guide the way.
• The leaves are chained from left to right (the last pointer points to the next leaf). For a range query, you find the first leaf and walk along the chain.

The height bound, for $K$ distinct keys:

$h \le \left\lceil \log_{\lceil n/2 \rceil} K \right\rceil$

Real numbers: 4 KB block, 32-byte key, 8-byte pointer. From the inequality $(n-1)\cdot 32 + n \cdot 8 \le 4096$ we get $n = 103$. If we take roughly $n = 100$, for a million keys $h \le \lceil \log_{50} 10^6 \rceil = \lceil 3.53 \rceil = 4$. Searching among a million records reads at most 4 nodes. With binary search this number is around 20.

Search: start at the root. In a node, follow the pointer to the left of the first key greater than the searched value; if equal or greater, move right. When you reach a leaf, look for the key there.

Insertion and splits (step by step)

$n = 4$ (at most 3 keys). In an overflowing leaf, the first $\lceil n/2 \rceil = 2$ keys stay on the left and the rest go to a new leaf, and the first key of the new leaf is copied to the parent. In an overflowing internal node, the first $\lceil (n+1)/2 \rceil = 3$ pointers stay on the left, and the key in between is moved to the parent (it does not stay in the lower node).

Let us insert 10, 20, 30, 40, 50, 25, 35, 5, 45, 55 in order. Levels are separated by /, with the rightmost leaves last:

insert 10 -> [10]
insert 20 -> [10 20]
insert 30 -> [10 20 30]
insert 40 -> [30] / [10 20] [30 40]                    the leaf overflowed, 30 was copied
insert 50 -> [30] / [10 20] [30 40 50]
insert 25 -> [30] / [10 20 25] [30 40 50]
insert 35 -> [30 40] / [10 20 25] [30 35] [40 50]       the right leaf split, 40 goes up
insert 5  -> [20 30 40] / [5 10] [20 25] [30 35] [40 50]
insert 45 -> [20 30 40] / [5 10] [20 25] [30 35] [40 45 50]
insert 55 -> [40] / [20 30] [50] / [5 10] [20 25] [30 35] [40 45] [50 55]

Let us unpack the last step: [40 45 50 55] overflows, becoming [40 45] and [50 55], and 50 goes to the root. The root becomes [20 30 40 50], with 5 children, exceeding the limit $n = 4$. The internal node splits: the left has 3 pointers ([20 30]), 40 is moved to the new root, and the right is [50]. The tree grew by one level. A B+ tree grows upward, not downward. That is why the leaves always stay at the same depth.

PITFALL · where is 40? In the final tree 40 is both in the root and in a leaf [40 45]. This is correct: a value copied in a leaf split stays in the leaf too. But the 40 that goes up in an internal node split is not written again in the second level. Whoever writes [20 30 40] / [50] loses points.

Deletion (briefly)

In deletion, if a leaf falls below the minimum occupancy, it first borrows from a sibling (redistribution); if that is not possible it is merged with the sibling (merge/coalesce) and a key is deleted from the parent. A merge can propagate up to the root; if the root is left with a single child, the root is deleted and the tree gets one level shorter.

Indexing with hashing

Static hashing: $m$ buckets and a hash function $h$. A record is written to bucket number $h(k)$. An equality search reads a single bucket; for a range query hashing is useless because neighboring values are scattered.

With $h(k) = k \bmod 4$ for 12, 7, 21, 30, 16, 9, 43:

If a bucket fills up, an overflow bucket is chained. As the chain grows, search slows down. As data grows, $m$ stays fixed, so static hashing degrades.

Extendable hashing solves this: it keeps a directory that looks at the first $i$ bits of the hash value. When a bucket overflows, only that bucket is split in two; if needed, the directory size is doubled ($i$ increases by one). There is no need to rehash the whole file.

Selection costs

The methods used for $\sigma_{A = v}(r)$ or $\sigma_{A \ge v}(r)$. The numbering A1, A2 changes with the edition of the book; in the exam it is enough to know the name of the method and its formula. $h_i$: the height of the B+ tree. In the examples, $b_r = 500$, $h_i = 3$.

The logic is always the same: in the index tree every level is a random read (seek + transfer). In a primary index the data is sorted, so the matching records are in consecutive blocks: one seek, then $b$ transfers. In a secondary index each matching record may be somewhere else, and each needs a separate seek.

PITFALL · secondary index + many matches. With 40 matches, a secondary index costs 176.3 ms and a plain scan 54 ms. As the number of matching records grows, a secondary index quickly gets expensive. The answer “if there is an index, it is always used” is wrong.

To see this in a real system, let us look at SQLite’s plan on our sample database (the takes table):

EXPLAIN QUERY PLAN SELECT * FROM takes WHERE course_id = 'MA101';
CREATE INDEX idx_takes_course ON takes(course_id);
EXPLAIN QUERY PLAN SELECT * FROM takes WHERE course_id = 'MA101';

SCAN takes
SEARCH takes USING INDEX idx_takes_course (course_id=?)

Without the index, the table is scanned from start to end (SCAN). After the index, a search is made in the B+ tree (SEARCH). The result is the same three rows in both cases: S1, S3, S4. An index changes the path, not the result.

Common mistakes