B-tree indexes

May 10, 2026··

18 min read

B-tree Indexes — A Deep Dive

B-tree indexes are among the foundational data structures of modern database systems, filesystems, and storage engines. They provide efficient, balanced, disk-oriented ordered indexing that supports exact-match lookups, ordered range scans, and efficient updates. This article gives a comprehensive treatment: history, structure and invariants, algorithmic details, practical implications for disk and memory, concurrency and recovery, real-world implementations, trade-offs versus alternatives (notably LSM-trees), tuning and deployment guidance, and future directions.

Table of contents

Introduction and motivation
Brief history and lineage
B-tree family: B-tree, B+ tree, B* tree, B-link tree
Structure, invariants, and node layout
Algorithms: search, insert (split), delete (merge/redistribute)
Complexity, fanout, and I/O cost analysis
Disk/memory-oriented considerations and storage layout
Practical aspects in databases
- Primary vs secondary (clustered) indexes
- Compound keys, covering indexes, partial and expression indexes
- Bulk loading, fill factor and maintenance
- Prefix/truncation compression, overflow handling
Concurrency, locking, and recovery
- Lock coupling, optimistic concurrency, latch-free variants
- MVCC interactions and HOT updates
- Write-ahead logging (WAL) and crash recovery
Implementation examples in popular systems
- PostgreSQL, InnoDB (MySQL), SQLite, Oracle, filesystems (Btrfs)
B-tree vs alternatives (hash, LSM, radix/ART, learned indexes)
Advanced topics and optimizations
- Cache-awareness, prefix compression, key ordering
- B+ tree sibling pointers, B-link trees
- Variable-length keys, overflow pages
Future trends: NVM/PMEM, learned/hybrid indexes, hardware changes
Practical recommendations / tuning checklist
Example pseudocode and SQL examples
Further reading and seminal references

Introduction and motivation

When datasets exceed memory and must be stored on block-addressable storage (disks, SSDs), index structures must minimize I/O. B-tree indexes are balanced trees designed so each node matches a block (page) on disk. By maximizing fanout (number of children per internal node), they keep tree height small, reducing the number of I/Os per lookup. They support:

Exact lookup (equality)
Range queries (scans)
Ordered traversal (ORDER BY)
Efficient insert/delete/updates (logarithmic height; local splits/merges)

Because the structure stores keys in sorted order and groups many keys per node, B-tree indexes are particularly good for range queries and for workloads requiring low read latency.

Brief history and lineage

1970s: B-trees were introduced by Rudolf Bayer and Edward McCreight in 1972 as a balanced tree optimized for secondary storage (Bayer & McCreight, "Organization and Maintenance of Large Ordered Indexes").
Variants emerged:
- B+ tree: stores all data/values in leaves linked sequentially; internal nodes store only keys. Widely used in DBMS and filesystems.
- B* tree: variant designed to keep nodes fuller by redistributing keys among siblings before splitting.
- B-link tree (Lehman and Yao, 1981): adds right-sibling pointers and high keys to enable lock-free/less-blocking concurrency during splits.

Since their inception, B-tree families have become the default indexing structure in most relational databases, key-value stores, and many filesystems.

B-tree family: B-tree, B+ tree, B* tree, B-link tree

B-tree (general): internal nodes store keys and child pointers; keys separate child subranges. Leaves may also store records/pointers.
B+ tree: all actual records (or pointers to records) are stored in leaves. Internal nodes contain only keys and child pointers. Leaves are often doubly or singly linked to support fast ordered scans. This is the most common form for database indexes.
B* tree: an optimization that tries to keep nodes at least 2/3 full instead of 1/2; on insert, siblings are used to redistribute before splitting.
B-link tree: a B+ tree with right sibling pointers at every level and additional high-key info to make concurrent splits safe without global coordination; used in concurrent implementations.

Key practical note: when people say "B-tree index" in modern DBMS, they most often mean a B+ tree implementation.

Structure, invariants, and node layout

Basic B-tree invariants (B-tree of order m):

Each node can have at most m children (i.e., up to m-1 keys).
Each internal node (except root) must have at least ⌈m/2⌉ children.
All leaves are at the same depth (tree is height-balanced).
Keys within a node are sorted.

For B+ tree specifics:

Internal nodes contain only separators and child pointers.
Leaf nodes contain key-pointer pairs (pointers to rows or the row itself in clustered indexes).
Leaf nodes are linked sequentially for efficient range scans.

Node layout commonly includes:

Header (node type, item count, pointers to parent/left/right sibling)
Array of keys (or key prefixes)
Array of pointers (child pointers in internals, record pointers in leaves)
Optional free space and slot directory (for variable-length keys)
Checksums/LSNs for recovery

For disk-oriented layout, nodes usually align with page sizes (e.g., 4 KB, 8 KB) to allow efficient I/O.

Algorithms

B-tree operations are straightforward conceptually but have practical subtleties for disk storage, concurrency, and variable-length keys. Below are the core algorithms in brief, followed by annotated pseudocode.

Search (lookup)

Start at root.
At each internal node, binary-search (or linear scan for small node) the key array to find the child pointer whose subrange contains the search key.
Move to that child and repeat until a leaf node is reached.
In leaf: search keys for equality (or locate starting position for range scan).

I/O cost ~= number of levels visited (one page read per visited node if not cached).

Insert (high level)

Find the leaf where the key should go.
Insert the key into the leaf in sorted order.
If the leaf overflows (exceeds max entries), split it into two nodes:
- For B+ tree, promote the smallest key of the new right node to the parent as the separator.
If parent overflows due to new separator, recursively split parent.
If root splits, create a new root and increase tree height by 1.

Splits are local operations typically involving one page read/write and one new page write.

Delete (high level)

Find leaf containing key and remove it.
If the leaf becomes underfull (fewer entries than min), try to borrow (redistribute) an entry from a sibling.
If redistribution is not possible (sibling at minimum), merge with sibling and remove separator from parent.
If parent underflows, recursively borrow/merge upward. If root ends up with a single child, shrink root (height--).

Pseudocode (simplified)

Search pseudocode:

JavaScript

function BTreeSearch(node, key):
    if node.isLeaf:
        return node.findKey(key)  // return pointer or NOT_FOUND
    else:
        i = node.findChildIndexForKey(key)
        child = node.childPointers[i]
        return BTreeSearch(child, key)

Insert pseudocode (simplified, non-concurrent, B+ semantics):

JavaScript

function BTreeInsert(tree, key, value):
    leaf = findLeaf(tree.root, key)
    insertIntoLeaf(leaf, key, value)
    if leaf.isOverflow():
        newLeaf, separator = splitLeaf(leaf)
        insertIntoParent(leaf.parent, separator, leaf, newLeaf)

function insertIntoParent(parent, key, leftChild, rightChild):
    if parent == null:
        // create new root
        newRoot = Node(keys=[key], children=[leftChild, rightChild])
        tree.root = newRoot
        return
    parent.insertKeyAndChild(key, rightChild)
    if parent.isOverflow():
        newParent, separator = splitInternal(parent)
        insertIntoParent(parent.parent, separator, parent, newParent)

Delete pseudocode sketch omitted here for brevity because it requires many cases (borrow left/right, merge, propagate). Implementations must carefully manage sibling pointers and parent separators.

Complexity, fanout, and I/O cost analysis

Let:

B = page size (bytes)
P = pointer size (bytes) — often 8 bytes on 64-bit
K = average key size (bytes)
E = space per entry ≈ K + P (for internal nodes might be separator keys + child pointers)
m ≈ floor(B / E) ≈ approximate maximum children per internal node (fanout)

Height bound:

Each internal node has at least t = ceil(m/2) children (except root).
For n keys (or n records), approximate height h satisfies: n ≤ m^h => h ≥ log_m n (very loose) More precise lower bound for height: h ≤ floor(log_{t} ((n + 1) / 2)) (when counting nodes vs keys; constants omitted)

Practical consequence: because m is large (hundreds), h remains small: Example:

B = 4096 bytes, P = 8 bytes, K = 16 bytes → E ≈ 24 → m ≈ 170.
For n = 1 billion (~1e9), h ≈ log_{170}(1e9) ≈ ln(1e9)/ln(170) ≈ 20.7/5.14 ≈ 4.0. So only 4-5 levels are typical—meaning many lookups need only 4-5 random page reads in the worst case. With caching (root and upper internal nodes cached), average reads are often 1-2.

I/O cost:

Point lookup: O(h) page reads (often 1-5).
Range scan of k contiguous entries: O(h + k / (B / E_leaf)) page reads because sequential leaf pages are read.
Insert/delete: O(h) reads/writes plus occasional splits/merges (local writes).

CPU complexity:

Within-node search: binary search on keys (O(log m)), or linear scan for small m. Many implementations use binary search or SIMD-accelerated search.

Space efficiency:

Minimum fill factor typically 50% (or 66% for B* tree), so storage overhead due to sparsity is bounded.

Disk/memory-oriented considerations and storage layout

B-tree designs optimize for blocks/IOs:

Node = disk page (4KB, 8KB, etc.)
Pack many keys into a node to maximize fanout and minimize height.
Keep internal nodes small and few; typically root and upper levels stay cached in memory.

Leaf layout options:

Fixed-length entries: straightforward slot array; faster but wasteful for variable-length keys.
Variable-length keys with slot array: compact storage using variable-length items at the end of the page and a slot table of offsets.

Important techniques:

Prefix compression in internal nodes: store only separator prefixes sufficient to distinguish children to reduce internal node size and increase fanout.
Sibling pointers in leaves: allow fast in-order traversal and simplified concurrency.
Overflow/indirection: for very large values, store a pointer to a blob stored elsewhere (e.g., TOAST in PostgreSQL).

Buffer management:

Strong interaction with the DB buffer pool or OS page cache impacts effective I/O cost.
LRU or clock replacement policies target keeping upper levels and hot leaf pages in memory.

Page size choice:

Larger page size increases fanout and reduces height but increases cost for random modifications because more unrelated records share a page and writes are larger. On SSDs with low latency, smaller pages can be advantageous for write amplification considerations.

Practical aspects in databases

Primary (clustered) vs secondary indexes

Clustered index: when the table rows are stored physically in leaf pages of the B+ tree ordered by the primary key (InnoDB). The leaf contains the entire row. Only one clustered index per table.
Secondary index: leaf entries store indexed key plus pointer to the row (either physical row location, rowid, or the clustered key). Secondary index lookups may require a second read (to retrieve the row) unless the index is covering.

Implication:

Range scans on clustering key are very efficient.
Secondary index lookups for non-covering queries may require an extra fetch.

Compound keys and ordering

Compound (multi-column) indexes preserve lexicographic ordering by columns (first column major).
Leading column(s) are important: an index on (a, b, c) is useful for queries constrained on a or a and b, but not directly for queries only constrained on b.

Covering indexes

If the index includes all columns required by the query (SELECT columns are subset of index columns), the DB can satisfy the query from the index alone without visiting the table.

Bulk loading

Bulk load is much faster if the B-tree can be built bottom-up: sort the data and create leaf pages filled to capacity; then build internal levels. This avoids many splits and random writes.

Fill factor and maintenance

Fill factor controls how full pages are when created (e.g., CREATE INDEX ... WITH (fillfactor = 70) in PostgreSQL). Lower fill factor reduces split frequency at insertion time at the cost of increased space use.
Rebuilding/reorganizing: Over time fragmentation can occur (lots of splits, deletions), requiring REINDEX or VACUUM-like operations to compact leaves.

Prefix compression and key truncation

Internal nodes often store only minimum separator keys or key prefixes to reduce space.
Leaf nodes may use prefix compression to save space if adjacent keys share prefixes (common with string keys).

Variable-length keys and overflow pages

For very large indexed values (e.g., TEXT, BLOB), many systems store a pointer to a TOAST/overflow page containing the large value, keeping index entries small.

Concurrency, locking, and recovery

Real-world DBMS must support concurrent operations and crash recovery. B-tree concurrency management is a subtle and critical area.

Locking strategies

Lock coupling (hand-over-hand): acquire lock on a node, move to child, acquire child lock, then release parent. Ensures safe traversal but can be heavy.
Optimistic (latch-free) search: read without locks, validate, and retry if node changed.
Latches: short-term locks for in-memory concurrency (mostly protecting a page’s data structure).
Transactional locks (predicate locks, range locks) for serializability may be used at a higher level.

B-link trees and concurrency

B-link tree uses sibling pointers and high keys to permit searches to proceed rightward even during splits, reducing the need for strict locking. Particularly helpful for highly concurrent systems.

MVCC and HOT (Heap Only Tuple) updates

MVCC systems (PostgreSQL) often avoid index page updates for certain updates by using HOT updates: if a row is updated but remains on the same page and indexed columns didn't change, the index entry need not be updated.
Index maintenance must interact with transaction visibility and garbage collection: obsolete index entries must be removed eventually (vacuuming).

Write-ahead logging and recovery

Most DBMS use WAL: before modifying a page on disk, a log record is appended describing the change. On crash, WAL is replayed to reach a consistent state.
Recovery must ensure index consistency: log all structural changes (splits, merges) in a way that can be applied idempotently.
Some systems use logical logging plus physical page-image logging for complex operations.

Atomicity of splits/merges

Splits often require creating new siblings and updating parent pointers. Implementations ensure recovery/consistency by ordering writes and logging such that incomplete splits can be detected and corrected during recovery.

Implementation examples in popular systems

PostgreSQL: default index type is a B-tree (actually a highly optimized variant of a B+ tree). Uses page-based nodes, MVCC-aware index maintenance, HOT updates to avoid index changes for many updates, vacuum to remove dead index tuples. CREATE INDEX syntax, unique support, and expression/partial indexes are provided.
InnoDB (MySQL): uses a clustered B+ tree for primary keys; secondary indexes store primary key as pointer. InnoDB pages are typically 16KB; supports adaptive hashing and page compression.
SQLite: uses a B-tree variant for its internal storage engine; the database is essentially a B-tree file with table and index B-trees.
Oracle: uses B-tree indexes for most indexing needs; clustering and various index options available.
Filesystems: B-tree and B+ tree variants are used in many modern filesystems (Btrfs, XFS extent trees) to manage extents and metadata.

B-tree vs alternatives

Hash indexes (equality-only):
- Pros: O(1) average lookup for equality.
- Cons: no ordering, no range queries, often less resilient to skew, and more sensitive to bucket overflow.
LSM-tree (Log-Structured Merge tree):
- Pros: high write throughput, append-only writes, good for write-heavy workloads and SSDs when writes are batched.
- Cons: point queries may require searching multiple levels (mitigated by Bloom filters), range queries less efficient due to multiple sorted runs, compaction overhead, higher read amplification.
Adaptive Radix Tree (ART), radix tries:
- Pros: excellent in-memory performance, cache-aware, prefix compression-friendly.
- Cons: not optimized for block-based storage; persistence requires different design.
Learned Indexes (ML-based):
- Pros: potential for smaller index structure and fewer probes by learning key distribution.
- Cons: complexity, adaptability, worst-case behavior, updates and dynamic workloads still a research area.

When to prefer B-tree:

Balanced point and range workloads
Low-latency random read workloads
Workloads with many scans (ORDER BY, range queries)
Mixed read-write where up-to-date lookups are needed without compaction

When to prefer LSM:

High write throughput, mostly append-like workloads
Workloads that can tolerate compaction pauses or background compaction
Key-value workloads with mostly point reads + writes and large datasets on SSDs

Advanced topics and optimizations

Prefix compression: store only minimal distinguishing prefixes in internals to increase fanout. Leaves can also compress.
Key ordering and collation: multi-byte collation and variable-length encoding complicate comparisons and prefix policies (e.g., locale-specific ordering).
Partial and expression indexes: index only rows matching a predicate or index expressions computed from columns (PostgreSQL supports this).
Hot spot management: split policies, fill factors, and partitioning mitigate hot page contention for high-concurrency inserts to monotonic keys.
- Example: for monotonically increasing keys (timestamps, serial IDs), insertions hit the rightmost leaf generating contention; mitigations include partitioning, using UUIDs (but with trade-offs), or hashing to multiple trees.
Cache-friendly layouts: clustering internal nodes in memory, prefetching, and mapping multiple nodes into a single cacheline-friendly structure improve performance.
Recovery-friendly designs: write operations are logged in careful order to ensure that crashes leave the index in a consistent state.

Future trends: NVM/PMEM, learned/hybrid indexes, hardware changes

Persistent memory (NVDIMMs, Intel Optane DCPMM) changes assumptions: latency closer to DRAM, byte-addressable persistence. This enables in-place durable B-tree variants (e.g., Masstree-like adaptations) without page-I/O overhead.
New concurrency primitives and persistent atomic writes allow lock-free persistent B-tree variants but require careful design for crash-consistent recovery.
Learned indexes propose using machine learning models to predict key positions rather than traversing trees. Hybrid structures combining learned models with B-tree-like corrections show promise but are not yet universally adopted.
As SSDs and NVMe devices reduce random I/O cost, designs may favor smaller page sizes or different compaction strategies.
Cloud-native databases and distributed indexes introduce replication and consensus layers (Raft/Paxos) impacting index update patterns.

Practical recommendations / tuning checklist

Choose B-tree for workloads with range queries, ordered traversal, mixed reads/writes.
Align node/page size with storage and OS block size; consider 4K/8K/16K depending on DB defaults and workload.
Monitor index bloat and rebuild or reindex periodically if high fragmentation exists.
Set reasonable fillfactor if you expect many inserts post-index creation to reduce split frequency (e.g., fillfactor 70–90).
Avoid monotonically increasing keys for high-concurrency insert workload; consider partitioning, randomized keys, or batched inserts.
Use covering indexes to avoid lookups from secondary to primary data pages.
Bulk load large data sets using sorted input to build B-tree bottom-up.
Keep upper levels cached (size very small) to minimize I/O cost for lookups.
When using compressed pages or prefix compression, benchmark because CPU trade-offs may negate I/O savings for certain workloads.

Example SQL and execution plan snippets

PostgreSQL create index (simple):

SQL

CREATE INDEX idx_users_email ON users (email);

Compound and partial:

SQL

CREATE INDEX idx_orders_user_date ON orders (user_id, order_date);
CREATE INDEX idx_active_users_email ON users(email)
  WHERE active = true;

Explain plan snippet (conceptual) might show index scan:

Plain Text

Index Scan using idx_users_email on users (cost=...)
  Index Cond: (email = '[email protected]')

Bulk loading via sorted input:

Sort data on indexed key (external sort)
Fill leaf pages sequentially and write them to disk
Build internal levels from leaf pages' separators

Example: Insert split walkthrough (ASCII)

Assume leaf node can hold 4 keys for illustration. Node contains keys [10, 20, 30, 40] and we insert 25.

Before insert: leaf = [10,20,30,40] (full)

Insert 25 -> overflow -> split into left=[10,20] right=[25,30,40] (splitting policy varies) Promote separator = 25 to parent internal node.

Parent updates: if parent overflows, continue splitting upward.

Conclusion

B-tree indexes are a mature, well-understood, and highly-tuned solution for ordered indexing over block-addressable storage. Their balance between high fanout, small height, efficient range scans, and predictable update cost makes them ideal for many database workloads. Despite competition from LSM-trees in write-heavy systems and emerging learned indexes, B-trees remain the default in many RDBMS and filesystems because of their simplicity, robustness, and strong support for mixed workloads.

When designing or tuning a system, consider access patterns (reads vs writes, range queries), concurrency requirements, and hardware (SSD vs HDD vs persistent memory). Use B-tree-specific optimizations—fill factor, bulk load, prefix compression, sibling pointers—to match workload characteristics.

If you'd like, I can:

Provide detailed pseudocode for delete with all redistribution/merge cases,
Show a simulated insertion sequence with page I/O counts,
Compare numerical performance estimates for B-tree vs LSM for a concrete workload,
Or provide an annotated implementation sketch (in C/C++/Rust) of a simple B+ tree page format. Which would you prefer?