B-tree Indexes — A Deep Dive (Summary)

This summary outlines the essentials of B-tree indexes: their purpose, structure, core algorithms, practical considerations for disk- and memory-oriented database systems, concurrency and recovery concerns, common implementations, alternatives, optimizations, tuning guidance, and future directions.

What B-trees provide

Ordered, balanced, block-oriented indexing designed to minimize I/O by packing many keys per page (high fanout).
Support for exact lookups, range scans, ordered traversal (ORDER BY), and efficient updates (local splits/merges, logarithmic height).
Typical tree height is very small (4–6 levels) for large datasets because fanout is in the hundreds for typical page/key sizes.

History & variants

Introduced by Bayer & McCreight (1972).
Major practical variants:
- B+ tree — common DBMS form: internal nodes hold keys only; records live in linked leaves.
- B* tree — aims for higher minimum fill (≈2/3) via sibling redistribution.
- B-link tree — adds right-sibling pointers/high-keys to improve concurrency/split safety.

Structure, invariants & node layout

Order m: node ≤ m children, internal nodes (except root) ≥ ⌈m/2⌉ children; all leaves same depth; keys sorted inside nodes.
B+ specifics: all records in leaves, leaves linked for fast scans.
Typical page layout: header (type, counts, sibling/parent pointers), key array (often prefix-compressed), pointer array (children or record pointers), slot directory for variable-length entries, optional checksums/LSN.

Core algorithms (high level)

Search: traverse from root, binary-search keys in each node to pick child, end at leaf to find key or range start. I/O ≈ tree height (often cached).
Insert: insert into leaf; if overflow, split leaf and promote separator; propagate splits up, possibly creating new root. Splits are local and typically one new page write + parent update.
Delete: remove from leaf; if underfull, try redistribute from sibling or merge and propagate parent adjustments; root may shrink.
Within-node search is O(log m) (binary search) or linear for small nodes; overall lookup cost O(h · log m) but dominated by page I/O.

Complexity & I/O cost

Fanout m ≈ floor(B / (K+P)), where B = page size, K = avg key size, P = pointer size. Large m keeps height h ≈ log_m n small.
Point lookup: O(h) page reads (often 1–5 worst-case). Range scan of k entries: O(h + k/(entries per leaf page)).
Space: minimum occupancy ≈ 50% (66% for B*), bounding storage overhead.

Disk/memory layout & optimizations

Align nodes with disk pages (4K/8K/16K). Larger pages increase fanout but enlarge write units.
Prefix compression in internal nodes to increase fanout; leaf compression for space savings when keys share prefixes.
Variable-length keys use slot directories; very large values are stored out-of-line (overflow/TOAST).
Buffer pool and caching of upper levels dramatically reduce average I/O.

Practical database aspects

Clustered (primary) index: table rows stored in leaf pages ordered by key (only one per table). Excellent for range scans on the clustering key.
Secondary indexes: store key + pointer to row (or to clustered key); non-covering queries may require an extra lookup.
Compound indexes are lexicographic; usefulness depends on leading columns. Covering indexes avoid table fetches.
Bulk-loading: building leaves from sorted input (bottom-up) avoids many splits and is faster than many individual inserts.
Fill factor controls initial leaf fullness to reduce splits; periodic reindexing/vacuuming removes fragmentation and dead entries.

Concurrency & recovery

Concurrency strategies: lock coupling (hand-over-hand), latches for short-term safety, optimistic (validate-and-retry) traversals, and latch-free variants.
B-link trees and sibling pointers allow more localized locking and safer split behavior under concurrency.
MVCC interactions (e.g., PostgreSQL HOT updates) reduce index churn by avoiding unnecessary index updates for certain updates; vacuuming reclaims dead index entries.
Durability via WAL: structural changes (splits/merges) are logged and ordered so recovery can reestablish consistency.

Representative implementations

PostgreSQL: optimized B+-tree, MVCC-aware, HOT updates, vacuuming, prefix compression options.
InnoDB (MySQL): clustered B+ tree (default primary), 16KB pages, adaptive hashing.
SQLite: file-format B-tree storing tables and indexes.
Oracle and modern filesystems (Btrfs, XFS extent trees) use B-tree variants for metadata/extent management.

B-tree vs alternatives (trade-offs)

Hash indexes: O(1) equality lookups but no ordering/ranges.
LSM-trees: superior write throughput (append/compaction model) but higher read amplification, less efficient range scans, compaction overhead.
In-memory trees (ART, radix): cache-friendly and fast in RAM but not optimized for block storage.
Learned indexes: promising smaller structures by modeling key distribution but still experimental for dynamic/update-heavy workloads.
Choose B-tree when range queries, low-latency reads, and mixed read/write workloads dominate; LSM when write throughput and append-friendly workloads dominate.

Advanced optimizations

Prefix/truncation compression, sibling pointers (B+), B-link enhancements, variable-length key management.
Hot-spot mitigation for monotonically increasing keys: partitioning, randomized keys, or multi-root/hash sharding.
Cache-aware layout, prefetching, and SIMD-accelerated searches for within-node speedups.

Future trends

Persistent memory (NVM/PMEM) enables byte-addressable durable structures and new concurrency/crash-consistency designs.
Hybrid/learned index ideas may reduce space and probes but require robust update/repair strategies.
Hardware shifts (NVMe, SSDs) and cloud/distributed databases influence page-size, compaction, and replication strategies.

Tuning checklist (practical recommendations)

Prefer B-trees for range-heavy and mixed workloads; consider LSM for write-heavy, append-dominant workloads.
Choose page size to suit storage and workload; keep upper levels cached.
Set fillfactor to balance split frequency vs space usage when heavy inserts follow index creation.
Avoid unpartitioned monotonically increasing keys under high concurrent inserts; use partitioning or other mitigations.
Use covering indexes where possible to avoid extra lookups; bulk-load sorted data for large imports.
Monitor bloat and rebuild/reindex as needed; benchmark compression trade-offs for CPU vs I/O savings.

Conclusion

B-tree (especially B+ tree) indexes are a mature, versatile choice for ordered indexing on block storage, offering predictable, low-height search costs, efficient range scans, and local updates. They remain the default in many RDBMS and filesystems due to their balance of simplicity, robustness, and support for mixed workloads. For deeper dives I can provide detailed delete pseudocode, an insertion simulation with I/O counts, workload-specific numerical comparisons with LSM, or an annotated implementation sketch in C/C++/Rust—tell me which you prefer.

B-tree indexes

Resources for