Maintaining indexes through change

Fast reads send bills to writes

Indexes answer reads quickly, but they cost something on every write. Each insert, update, and delete must keep every relevant index consistent with the heap's versioned reality. A Postgre-like database cannot treat an index as an optional cache to rebuild whenever convenient. Query plans depend on indexes being trustworthy access paths even while transactions overlap and crashes remain possible.

An insert creates a heap tuple version and adds entries to the indexes on the indexed columns. The heap tuple has a physical identifier, and each index entry stores the key plus that identifier. The order matters with respect to WAL and visibility, but the link is simple: the heap owns the row version, and the index owns routes to find it. A reader may find an index entry before the inserting transaction commits, so heap visibility checks decide whether it counts.

Updates split the story

An update is often more expensive than it looks. If an indexed column changes, the new tuple version needs new index entries. The old entries cannot necessarily vanish right away, because old snapshots may still see the old tuple version. If no indexed column changes and the new version fits on the same heap page, a heap-only update can avoid adding new index entries. That optimization preserves read paths and reduces write amplification.

Deletion is usually deferred

Deletes are delayed too. A delete marks the heap tuple version as no longer visible to future snapshots once the deleting transaction commits. The index entry may remain until cleanup. During that window, an index scan can find a dead entry, visit the heap, and discard it. This sounds inefficient, but it keeps deletes from having to coordinate immediate removal across every old reader. Cleanup becomes a separate maintenance concern.

The hardest index maintenance problem is the page split. A B-tree leaf page eventually fills. To insert another key, the database allocates a new page, moves some entries, links the pages, and inserts a separator into the parent. If the parent is full, the split propagates upward. If the root splits, the tree grows taller. All of this must happen while concurrent readers can still search safely and concurrent writers may target nearby keys.

Structure changes while readers walk it

A stop-the-world split would be easy to trust and hard to live with. It locks the entire index, rearranges pages, and resumes work. The approach is simple but unacceptable for a busy server. A concurrent split uses page-level locks, right-links, high keys, and ordered steps, so a reader that lands on an old page can move right if the key range it wants shifted. The structure changes, but the search invariant holds.

WAL is part of index maintenance too. A page split is not a private memory event. If the server crashes after some split pages reach disk and others do not, recovery must restore a consistent tree. The log records for index changes must describe enough to redo the operation. Otherwise the index might point to missing heap tuples, drop keys, or break its ordering. Crash safety matters as much for indexes as for heap pages.

Unique indexes add concurrency tension. Suppose two transactions insert the same key. Neither should ignore the other, because one may commit and one may abort. The index must detect the possible conflict and coordinate with transaction status. A transaction may wait to see whether the other commits. If the other aborts, the key may be allowed. If it commits, the waiting transaction must fail. Uniqueness therefore depends on coordination between the index and the transaction manager.

Bulk index creation takes a different path. Building an index by inserting one entry at a time can be much slower than scanning the heap, sorting keys, and constructing pages in order. Concurrent builds still have to account for writes that happen while the build runs. The database may need multiple phases to capture a consistent set of entries without blocking ordinary work for too long.