4.2 B+ Tree Indexing: Pages, Key Ordering, and Execution Cost
As query volume grows, archivists no longer want to manually flip through pages to locate records, your task is to design an index that’s both efficient for disk pages and capable of continuous updates.
B+ trees are well-suited for database indexing not just because their lookup height approaches logarithmic growth, but because they integrate key features (high fan-out, ordered leaf nodes, page splitting, and concurrency control) into a durable, on-disk structure that can evolve over time.
Logical Structure
root/internal pages: separator keys + child pointers
/ \
internal pages: ... ...
/ \
leaf pages: [k, payload] <-> [k, payload] <-> ...Common characteristics:
- The tree remains balanced, with all leaves at the same depth;
- Internal nodes use separator keys for navigation;
- Leaves store entries in key order;
- Adjacent leaves are linked as siblings or otherwise connected to enable efficient range scans;
- Nodes are typically managed at the database page level.
"The B+ tree stores only values in leaf nodes" is a conceptual model. In practice, internal pages contain more than just separator and child pointers, additional components such as headers, high keys, sibling links, prefix compression, or concurrency metadata are included. Similarly, leaf payloads vary depending on whether the index is clustered, secondary, or heap-based.
Fan-out and Height
Fan-out is not page_size / key_size: an internal entry requires child pointer, line pointer, header, and alignment, and keys may be variable-length or prefix-compressed.
If the average fan-out is f, the leaf capacity is l, and there are N rows, the height remains small in magnitude:
leaf_pages ≈ ceil(N / l)
internal levels ≈ log_f(leaf_pages)However, the rule "a three-level tree requires three disk I/O operations" no longer holds: root and internal pages often reside in cache, and leaf pages may also be cached. Moreover, a single lookup might still involve heap or clustered lookup, visibility checks, overflow reads, or lock waits.
Point lookup
node = root
while node is internal:
choose child range containing search_key
node = fetch(child_page)
search leaf for matching key entriesA non-unique index may return multiple entries. The MVCC engine must additionally verify whether the corresponding row versions are visible in the current snapshot.
SQL:
CREATE INDEX idx_quests_adventurer
ON quests (adventurer_id);
SELECT quest_id, status, reward_cents
FROM quests
WHERE adventurer_id = 42;Whether the optimizer selects an index depends on table size, selectivity, correlation, statistics, required columns, and the cache/cost model. Building an index does not guarantee its usage.
Range scan
CREATE INDEX idx_items_type_value_id
ON vault_items (item_type_id, value_cents DESC, item_id DESC);
SELECT item_id, name, value_cents
FROM vault_items
WHERE item_type_id = 1
AND value_cents BETWEEN 50000 AND 200000
ORDER BY value_cents DESC, item_id DESC;The engine first locates the lower and upper boundaries, then scans the matching entries in leaf order. If the index order also satisfies an ORDER BY clause, an additional sort operation is avoided; however, name may still access the base table when it is not present in the key or payload.
The cost of a range scan increases with the number of matching entries and heap locality. When returning a large portion of table rows, a sequential scan might actually be cheaper.
Composite key order
Index (a, b, c) orders first by a, then by b within the same a values, and finally by c. Common effective access patterns include:
a = ?;a = ? AND b = ?;a = ? AND b BETWEEN ...;- Some engines support skip scan or similar extensions to handle missing leading columns, but such behavior cannot be relied upon as a general guarantee.
"The rule of placing all equality columns at the front and range columns at the end" is a common starting point, not a complete rule. Additional considerations must include ORDER BY, covering indexes, selectivity, write cost, compression, and other query characteristics.
Insert and Page Split
- Locate the target leaf node;
- Insert the entry if there is available space in the page;
- If space is insufficient, allocate space from a sibling page and redistribute the entries;
- Update the parent node's separator value;
- The parent may also split, and a root split increases the tree height.
A real implementation must handle concurrent readers and writers. Mechanisms such as B-link trees, high-key and sibling links, latch coupling, optimistic traversal, and Write-Ahead Logging (WAL) ensure that searches can still find the correct page during a split operation.
Random key distribution does not mean "split every time," and sequential keys do not imply zero cost: right-side hotspots, page latch contention, append patterns, and replication all require measurement. Random UUIDs may reduce data locality, increase working set size, and trigger more splits, though the impact depends on key encoding, fill factor, storage engine, and workload characteristics. Absolute conclusions should never be drawn without considering the specific product context and data scale.
Delete, Merge, and Bloat
Deleting typically begins by marking or removing a leaf entry. Immediate merging of low-occupancy pages can cause structural oscillation, so the engine may defer cleanup, space reuse, or compacting until maintenance or rebuild phases.
MVCC prevents the reclamation of old row or index versions until no active snapshot references them. PostgreSQL relies on operations like VACUUM to clean up dead tuples; InnoDB employs its own purge mechanism. Long-running transactions delay cleanup, thereby increasing storage and cache pressure.
Clustered vs. Heap-Organized
InnoDB
InnoDB tables typically use the primary key to organize their clustered index, with the leaf nodes containing the actual row data. Secondary indexes have leaf nodes that store the secondary key values along with the primary key columns, resulting in:
- The primary key width being duplicated into secondary indexes;
- Secondary index lookups often requiring a subsequent query to the clustered index to retrieve the primary key;
- If the required columns are already included in the secondary index entry, additional lookups may be avoided.
When no explicit primary key is defined, the selection of the clustered key follows product-specific rules. Developers should refer to the official MySQL version documentation for authoritative guidance and should not rely on hidden IDs as part of application contracts.
PostgreSQL
PostgreSQL stores ordinary tables in a heap-organized structure, where B-tree leaf nodes point to heap tuple identifiers. Index-only scans still require visibility information; even when an index contains all the columns needed for a query, it does not guarantee that no access to the heap is required.
PostgreSQL CLUSTER supports reorganizing a table based on a specific index in a single operation, but unlike InnoDB's clustered index, it does not maintain a persistent physical ordering of data.
Covering/index-only
"Coverage" refers to the relationship between a query and an index, not an inherent label of the index. An engine may adopt an index-only strategy only when all the predicate conditions, join operations, and output columns required by a query can be satisfied directly from the index.
CREATE INDEX idx_quests_cover
ON quests (adventurer_id, status)
INCLUDE (reward_cents);INCLUDE is a feature available in products like PostgreSQL; MySQL uses a different index syntax and leaf payload structure. Including additional columns in the index increases both index size and write overhead. The actual query plan must be evaluated to confirm whether the performance benefits justify the cost.
Look at the Plan, Not Guess the Plan
PostgreSQL:
EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT quest_id, status, reward_cents
FROM quests
WHERE adventurer_id = 42;ANALYZE will actually execute the query. Before running write statements, expensive queries, or production data, you must verify side effects and load impact. Focus on comparing estimated versus actual rows, loops, heap fetches, buffers, and execution time.
SQLite:
EXPLAIN QUERY PLAN
SELECT item_id, name, value_cents
FROM vault_items
WHERE item_type_id = 1
ORDER BY value_cents DESC, item_id DESC;The plan vocabulary and cost units across different systems cannot be directly compared.
Index review
- What are the predicate, join, order, and output clauses in a query?
- Does the leading key order align with key access patterns?
- Are the selectivity or cardinality estimates reliable?
- Is the index redundant with existing indexes?
- How many indexes will row writes maintain?
- What are the index size, cache residency, and potential bloat?
- Is a unique constraint critical to correctness, rather than performance alone?
- Does range or pagination support have a stable tie-breaker?
- Is the actual execution plan stable under representative parameter values?
Lesson Summary
A B+ tree maps ordered keys to a page hierarchy, but the cost of queries is not simply equal to the tree height. Factors such as leaf payload size, heap locality, MVCC visibility, cache behavior, and result cardinality all influence actual I/O operations. The next lesson explains how WAL (Write-Ahead Logging) enables dirty pages to be written back lazily while still ensuring consistency after a crash.