Index splits, maintenance, and storage costs

Start with the guided lesson. These sections develop the mechanisms and tradeoffs beyond that first example.

Insertion and splitting

Insertion finds the target leaf and checks whether it has room. If not, the engine allocates a sibling, redistributes entries, updates links and routing metadata, and possibly splits a parent. The root may gain a new level. Each publication step must remain safe for concurrent readers and recoverable after a crash.

A useful conceptual sequence is to prepare the new node before making it reachable, then publish links and parent information under the chosen concurrency protocol. Real algorithms vary. Some use sibling links and boundary keys so a reader can recover from a concurrent split. Others use latch coupling or optimistic validation. The exact search algorithm must agree with the exact split protocol.

The storage engine must log enough information to reconstruct a split or ensure another recoverable representation. Writing only a new child page without publishing it safely can leak space. Publishing a pointer before the child is valid can expose corruption. Tree structure is both a concurrency invariant and a persistence invariant.

Deletion, merging, and reclamation

Deleting a logical entry does not necessarily free a page immediately. Readers may still hold references, and old transactions may require an older version. Underfilled pages can be merged or left partially empty depending on policy. Aggressive merging saves space but adds structural writes and can oscillate under changing insert/delete workloads.

Reclamation needs proof that no valid reader can use the old node. Pins, epochs, generations, or other mechanisms establish that boundary. A page identifier reused too early can produce an ABA-like problem in which an old reference points to a new unrelated page occupying the same identity. Lesson 23 examines concurrent reclamation directly.

Maintenance policy affects long-term performance. A tree after repeated random updates can have different occupancy and locality from a freshly bulk-loaded tree. A short benchmark over a pristine structure may miss that evolution. Capacity planning should include realistic update history and background maintenance.

Unique enforcement and visibility

A unique index must prevent two concurrent transactions from both committing the same protected identity. Finding no currently visible entry is insufficient if another in-progress transaction has reserved it. The engine needs a protocol for conflicting uncommitted entries, waiting, aborting, or validation.

Visibility also affects index-only reads. An index entry may refer to a row version that is not visible to the current snapshot. Engines use different metadata and maintenance techniques to decide whether base-record inspection is needed. An index is an access path into transactional state, not a substitute for transaction semantics.

The application pays for every maintained index during writes. Updating a key can remove an old entry and insert a new one. Large included values increase copying and log work. More indexes can reduce read latency while lowering write throughput and increasing recovery or backup volume. The correct set follows actual query patterns and their importance.

Derive fanout from an entry budget

Tree height follows from bytes as well as row count. Suppose an illustrative internal page has 8,000 usable bytes. Each separator-plus-child entry averages 40 bytes, giving approximate fanout 200. If long keys increase that entry to 80 bytes, fanout falls toward 100. The same number of rows can then require more internal pages and possibly another level. Prefix compression can recover fanout when neighboring separators share bytes, at the cost of decoding and more complex split logic.

The root is a special case because it may have few children after a split, and leaves need payload or record references. A rough four-level tree at fanout 200 should therefore not be described as exactly holding 1.6 billion rows. The leaf capacity and occupancy must also be modeled. For example, 10 million leaf entries at 200 entries per leaf require about 50,000 leaves before accounting for free-space policy and skew.

Upper levels can be small enough to remain hot in memory. With 50,000 leaves and fanout 200, the next level needs about 250 pages, followed by roughly two pages and a root under a simple balanced approximation. Most storage misses may therefore occur at leaves or base records. The access pattern matters: a uniformly random lookup across a large leaf set differs from repeated access to one small tenant’s range.

An insertion trace with explicit separator semantics

Define an illustrative B+ tree convention: each internal separator is the smallest key in its right child, and equality routes right. A leaf containing [10, 20, 30, 40] overflows when inserting 35 under a four-entry limit. After insertion, split it into [10, 20] and [30, 35, 40]; the parent receives separator 30. Searches for 30 must route to the right leaf. A different convention can work, but search and split must use the same rule.

before: parent -> [10, 20, 30, 40]
insert 35
prepare: left [10, 20]   right [30, 35, 40]
publish separator: parent [30]
                           /  \
                 keys < 30    keys >= 30

This diagram depicts a completed structural change. Concurrent execution needs additional steps. A reader descending through an old parent must still find the right leaf if the split becomes visible before the parent update. One family of algorithms uses sibling links and upper-bound keys to let such a reader move right. Another holds a chain of latches that prevents an incompatible observation. Mixing a search algorithm from one family with publication rules from another is unsafe.

Crash recovery introduces a separate ordering. A new leaf must be recoverably initialized before an enduring reference can expose it. Parent and sibling updates must be replayable or otherwise atomic under the chosen log protocol. If a crash leaves an incomplete structural operation, recovery must restore reachability and ordering. The database cannot rely on a future ordinary insertion eventually repairing missing keys.

Secondary indexes multiply mutation work

Consider a row with a primary key and three secondary indexes: owner, item kind, and last-modified time. Changing only the owner may update the row and the owner index while leaving kind untouched. An engine may still create row versions or maintain other metadata. Changing a primary or clustering key can affect every secondary entry that stores that key as its row reference.

A covering index storing a large description can avoid table fetches for selected reads, but every description change now rewrites another copy. If a description averages 2 KiB and changes 5,000 times per second, that one included payload represents about 10 MiB per second of additional logical bytes before logging, replication, splits, and compression. The read benefit must justify that sustained maintenance cost.

Unused indexes can still impose writes, memory pressure, and recovery work. “Index usage count” needs interpretation before deletion because rare but critical maintenance or incident queries may depend on an index. The correct question is whether the access path supports a required workload sufficiently valuable to justify its cost. This is an engineering decision, not an instruction to maximize or minimize index count indiscriminately.

Bulk construction and incremental maintenance

Building an ordered index from a sorted stream can fill leaves efficiently and construct upper levels from their boundaries. Inserting the same entries one at a time may perform many searches and splits. Bulk construction can therefore produce a denser, more sequential structure with less work. The result’s performance may differ from an old index shaped by years of random updates.

Online construction adds a correctness problem: writes continue while the initial data is scanned. The builder needs a snapshot plus a way to incorporate concurrent changes, or another protocol proving the final structure represents the accepted state. Declaring the index usable before catching up can omit committed rows. Dropping the old access path before the replacement is validated risks availability.

Operationally, an index is never only a search routine. It has construction, mutation, cleanup, recovery, and retirement phases. Capacity estimates should include temporary construction space and maintenance headroom. Lesson 41 returns to how those phases can coexist with a live application without turning a performance optimization into an outage.