B+tree deletion, bulk loading, composite keys, and hash indexes

This lesson sits in the index layer, the same place as week 6. On journey 1, our running query SELECT name FROM emp WHERE salary > 75000 ORDER BY name reaches us from the executor (week 9): a scan operator asks the access method for the rows matching salary > 75000. The access method (a B+tree on salary) descends to a leaf and walks linked leaves for the range, handing back row ids. Below us, every page we touch is fetched from the buffer pool (week 4), which reads it from the heap file (week 2). Week 6 taught the read and insert paths. This week closes the index layer: what happens on delete, how the index is first built, why column order matters, and the hash alternative that the optimizer (week 11) will sometimes prefer.

There is a connection to journey 2 hiding here. When our UPDATE account SET balance = balance - 100 WHERE id = 42 runs under MVCC (week 13), the old tuple version becomes dead and its index entries must eventually disappear. That is index deletion. The mechanism below is the textbook baseline; the lazy, two-stage version PostgreSQL actually runs is the realworld note.

Deletion: removing a key without breaking balance

The algorithm

1. Descend to the target leaf as in a search, and remove the entry.
2. If the leaf still has at least ceil(m/2) - 1 keys, stop. Most deletes end here.
3. On underflow, look at an adjacent sibling. If the sibling has more than the minimum, redistribute: move one entry across and update the separator in the parent. Tree shape is unchanged.
4. If no sibling can spare an entry (every neighbor is exactly at minimum), merge: fuse the underflowing node with a sibling into one node and remove the now-unused separator from the parent.
5. A merge removes a key from the parent, which can make the parent underflow. So merge and redistribute propagate upward, exactly like split propagation. If the root is left with a single child, that child becomes the new root and the tree loses a level.

Simulator: a B+tree that shrinks, and a hash that grows

Two structures, one screen. On the left, delete keys from a B+tree (order 4, so minimum 2 keys per leaf) and watch underflow resolve as redistribute or merge, with the tree height counter ticking down on a root collapse. On the right, insert keys into an extendible hash table and watch global and local depth climb and the directory double. The button that matters most is the range query: press it and the hash side lights up every bucket it must scan, while the B+tree descends once and walks its linked leaves. That contrast is the whole point of the lesson.

Bulk loading: build it bottom up, not one key at a time

The algorithm

1. Sort all the entries by key (an external merge sort if they do not fit in memory, the same one from week 10).
2. Pack the sorted entries left to right into leaves up to a target density, the fillfactor, linking each leaf to the next. Stop short of full so later inserts have room before they split.
3. Build the parent level by taking the first key of each leaf as a separator. Repeat upward until one node remains: that is the root.

Composite keys: lexicographic order and the leftmost prefix

An index on (a, b) is keyed on the pair, sorted the way a dictionary sorts: compare a first, and only when two rows tie on a does b break the tie. That single fact decides every query the index can and cannot accelerate.

One more axis pairs with composite keys: clustering. A clustered index defines the physical row order of the table, so there is at most one per table, and a range scan on it reads the heap in mostly sequential order. An unclustered (secondary) index has its own order; its leaves hold the key plus a row pointer, so a range scan reads index leaves in order but then jumps to scattered heap pages, close to one random read per matching row. How well the index order matches the heap order is the clustering factor, and it is what makes a secondary range scan cheap or ruinous [PG docs].

The hash alternative: O(1) points, but no order

Three ways to grow a hash table

# extendible hash insert, the case that matters
def insert(key):
    b = bucket_for(directory, low_bits(hash(key), global_depth))
    if b.has_room():
        b.add(key); return
    if b.local_depth == global_depth:
        global_depth += 1          # the directory doubles
        directory = double(directory)
    split(b)                       # b.local_depth += 1, redistribute by the new bit
    insert(key)                    # retry

The trade-off in one table

Check yourself