How Database Indexes Work — Inside B+ Trees and LSM-Trees

Why Indexes Matter

A full table scan checks $O(n)$ rows. Rows are packed into pages; at a few hundred rows per page, a million-row table occupies thousands of pages, and finding a single row means reading all of them and checking every row.

With a suitable index, a lookup takes $O(\log n)$. Each B+ tree node has many children (high fan-out), so even in a million-row table a lookup reaches the target row in about 3–4 disk accesses.

The two core data structures behind database indexes are the B+ tree, which favors reads, and the LSM-Tree, which favors writes. Which one fits depends on whether reads or writes dominate and how often queries scan ranges.

B+ Tree Fundamentals

From B-Tree to B+ Tree

The B-tree is a self-balancing search tree that Rudolf Bayer and Edward McCreight presented in 1970. Because each node holds multiple keys, one disk read lets a search compare many keys, which suits data stored on disk.

The B+ tree changes the B-tree in two ways:

1. Data is stored only in leaf nodes — internal nodes hold only keys (routing information)
2. Leaf nodes are linked together — enabling efficient range scans

B+ Tree Properties

A B+ tree of order $m$ has these properties:

• Each internal node has at most $m$ children
• Each internal node has at least $\lceil m/2 \rceil$ children (except the root)
• An internal node with $k$ keys has $k+1$ children
• Leaf nodes hold at most $m-1$ keys
• Leaf nodes hold at least $\lceil (m-1)/2 \rceil$ keys
• All leaves are at the same depth (perfectly balanced)

Search Algorithm

A search descends from the root to a leaf:

Search(node, key):
  if node is leaf:
    return binary_search(node.keys, key)
  
  // Internal node: pick the right child
  i = 0
  while i < len(node.keys) and key >= node.keys[i]:
    i += 1
  return Search(node.children[i], key)

Keys within each node are sorted, so binary search finds the next child in $O(\log m)$. The tree height is $O(\log_m n)$, giving an overall complexity of $O(\log_m n \cdot \log_2 m) = O(\log n)$.

In practice, $m$ is in the hundreds (a node is one disk page, 4–16 KB), so even a million-row table needs a tree of height only 3–4.

Insertion and Splits

Insertion follows these steps:

1. Use the search algorithm to find the leaf where the key belongs
2. Insert the key into the leaf (maintaining sorted order)
3. If the leaf overflows (keys > $m-1$), split it:
   • Divide the leaf into two
   • Copy a separator key (for a leaf split, the first key of the new right leaf) into the parent node
   • If the parent also overflows, split the parent too (splits propagate upward recursively)
4. If the root splits, create a new root above it (the tree height increases by one)

The demo below runs this process one step at a time:

Here is the split pseudocode:

Insert(tree, key, value):
  leaf = find_leaf(tree.root, key)
  insert_into_leaf(leaf, key, value)
  
  if leaf.num_keys > MAX_KEYS:
    split_leaf(leaf)
 
SplitLeaf(leaf):
  mid = ceil(leaf.num_keys / 2)
  new_leaf = new LeafNode()
  
  // Move upper half to new leaf
  new_leaf.keys = leaf.keys[mid:]
  leaf.keys = leaf.keys[:mid]
  
  // Update linked list
  new_leaf.next = leaf.next
  leaf.next = new_leaf
  
  // Copy separator key to parent
  promote_key = new_leaf.keys[0]
  insert_into_parent(leaf.parent, promote_key, new_leaf)

Range Scan Efficiency

The B+ tree's greatest strength is range scanning. Because leaf nodes are linked, a scan finds the start point and then follows the list:

RangeScan(tree, low, high):
  leaf = find_leaf(tree.root, low)
  results = []
  
  while leaf != null:
    for key in leaf.keys:
      if key > high:
        return results
      if key >= low:
        results.append(leaf.data[key])
    leaf = leaf.next
  
  return results

Leaf nodes are often laid out contiguously on disk, so this scan can use sequential reads.

Deletion and Merging

When a deletion drops a leaf's key count below the minimum ($\lceil (m-1)/2 \rceil$), the tree redistributes or merges:

1. Redistribution: borrow a key from an adjacent sibling
2. Merge: combine with a sibling and remove the separator key from the parent

Merges can propagate upward to the root, potentially reducing the tree height by one.

Clustered vs Non-Clustered Indexes

Clustered Index

In a clustered index, the actual row data is stored in the B+ tree's leaf nodes, so rows are stored in index order.

MySQL's InnoDB uses this approach. The primary key becomes the clustered index, and the entire table is stored as this B+ tree:

-- In InnoDB, the primary key becomes the clustered index
CREATE TABLE users (
  id INT PRIMARY KEY,      -- B+ tree key
  name VARCHAR(100),        -- Stored in leaf nodes
  email VARCHAR(200),       -- Stored in leaf nodes
  KEY idx_email (email)     -- Secondary index
);

Secondary indexes (indexes other than the primary key) store primary key values in their leaves, so a secondary index lookup takes two steps:

1. Search the secondary index B+ tree to get the primary key value
2. Search the clustered index (primary key B+ tree) to get the actual row data

Non-Clustered Index

PostgreSQL stores table rows in a heap (pages that hold rows in no particular order). Its default B-tree indexes are structured much like B+ trees, and their leaf entries hold row pointers (TID: tuple ID) into the heap.

PostgreSQL index structure:
  B+ tree leaf: [key → TID (block_number, offset)]
  Heap page:    [row data stored within pages]

With this design, each read of a row from the heap can cause random I/O. Whether a query can use an Index-Only Scan, which answers from the index alone, therefore has a large effect on performance.

Disk I/O and Page Structure

Why Node Size = Page Size

Disk I/O reads and writes whole pages (blocks). When a B+ tree node is the size of a page (typically 4–16 KB), one I/O reads all the keys in a node and nothing it reads is wasted.

Page size = 16KB, key size = 8B, pointer size = 8B:
  Keys per node ≈ 16384 / (8 + 8) ≈ 1000
  → Fan-out ≈ 1000
 
A height-3 B+ tree can index:
  1000 × 1000 × 1000 = 1 billion rows
  → 1 billion rows searchable in just 3 disk accesses

Buffer Pool

Databases cache frequently accessed pages in an in-memory buffer pool. The root and upper internal nodes are almost always cached, so a lookup usually needs only 1–2 disk reads to reach the leaf.

LSM-Tree — Write-Optimized Approach

The B+ Tree Write Cost Problem

B+ trees excel at reads, but writes are expensive. Even a single key insertion must read a page at a random disk location, modify it, and write it back (a Read-Modify-Write cycle: one read plus one write). A split updates several pages. As a result, the bytes written to disk exceed the size of the logical change; this is called write amplification.

LSM-Tree Design Philosophy

The LSM-Tree (Log-Structured Merge-Tree) was proposed by Patrick O'Neil et al. in 1996. It converts all writes to sequential writes, which raises write throughput.

Write Path

1. Append the write to the WAL (Write-Ahead Log) for durability
2. Insert the key into the Memtable (an in-memory sorted structure, typically a skip list or red-black tree)
3. When the Memtable reaches a threshold size, flush it to disk as an SSTable (Sorted String Table). An SSTable is a file of sorted key-value pairs and is never modified after it is written (immutable)

Read Path

A read searches multiple levels, starting with the newest data:

Read(key):
  // 1. Search Memtable first (most recent data)
  result = memtable.get(key)
  if result != null: return result
  
  // 2. Search L0 SSTables newest-first
  for sstable in L0_tables (newest first):
    result = sstable.get(key)  // Bloom filter + binary search
    if result != null: return result
  
  // 3. Search L1 and beyond
  for level in [L1, L2, ...]:
    result = level.get(key)    // Each level is sorted, so binary search
    if result != null: return result
  
  return NOT_FOUND

Each SSTable has a Bloom filter that can tell, without reading the data, that a key is not in the file. The probability that it wrongly reports a key as present (the false positive rate) is typically set below 1%.

Compaction

As SSTables accumulate, each read has more files to check and slows down. Periodic compaction merges SSTables to counter this:

Compaction(level_n, level_n1):
  // Merge level_n SSTables with overlapping range in level_n+1
  for sstable in level_n.tables:
    overlapping = find_overlapping(level_n1, sstable.key_range)
    merged = merge_sort(sstable, overlapping)
    // Write as new SSTables to level_n+1
    write_new_sstables(level_n1, merged)
    // Delete old SSTables
    delete(sstable, overlapping)

The two main compaction strategies are:

Write Amplification in LSM-Trees and B+ Trees

In LSM-Trees, compaction causes write amplification. With leveled compaction, each time data moves down a level, the overlapping data already in the lower level is rewritten with it. Each level is $T$ times larger than the one above (the size ratio), so the rewritten data is roughly $T$ times the data moved down. Because this repeats at every level, write amplification grows with the number of levels $L$ and the size ratio $T$, and is often summarized as $O(L \times T)$ in the worst case. With a size ratio of 10 and 4 levels, a key can be rewritten tens of times in the worst case.

B+ tree write amplification comes from updating whole pages for small logical changes. An isolated 100-byte change can dirty a 16 KB page, but the actual amplification depends on the WAL format, page flushing, group commit, and buffer pool batching, so it varies with the workload.

B+ Tree vs LSM-Tree — When to Use Which

The speed ratings in the table below are relative: each compares the two structures on the same operation.

Selection Guidelines

• Read-heavy with frequent range scans → B+ tree / B-tree family indexes (MySQL/InnoDB, PostgreSQL's default B-tree)
• Write-heavy with logs and event data → LSM-Tree (RocksDB, Cassandra)
• Mixed workloads → Consider tuning or hybrid configurations

Real-World Database Adoption

MySQL (InnoDB)

Because InnoDB's primary key B+ tree is the table itself, a lookup through a secondary index must then search the clustered index with the primary key value it found. The EXPLAIN output for such a query looks like this:

-- Check the query plan with EXPLAIN
EXPLAIN SELECT * FROM users WHERE email = 'test@example.com';
-- type: ref, key: idx_email → using secondary index
-- SELECT * is not covered by idx_email, so InnoDB looks up the clustered record by primary key

PostgreSQL

PostgreSQL combines a heap table with B-tree indexes. With the HOT (Heap-Only Tuples) optimization, an update that changes no indexed column and fits the new tuple version on the same heap page does not need to update the indexes.

Besides its default B-tree, PostgreSQL offers other index types, including GiST (Generalized Search Tree), GIN (Generalized Inverted Index), and BRIN (Block Range Index).

RocksDB

RocksDB is an LSM-Tree–based storage engine developed by Meta (Facebook), forked from LevelDB and optimized for production use.

• Leveled compaction by default
• Column Families for logical data separation
• Bloom filters to optimize read paths

TiKV (TiDB), MyRocks, and other systems use RocksDB as their internal storage engine. CockroachDB also used RocksDB in the past but has since moved to Pebble, a Go storage engine modeled on RocksDB.

SQLite

SQLite uses two types of B-trees internally. Table B-trees, which store rows, keep all data in leaf nodes, much like a B+ tree. Index B-trees, used for indexes, hold keys in both internal and leaf nodes, closer to a traditional B-tree. WITHOUT ROWID tables store rows in index B-trees and use a clustered index for the primary key.

Advanced Topics

Write-Optimized B-Trees (Bε-Tree)

The Bε-Tree (B-epsilon Tree) sits between B+ trees and LSM-Trees. Each internal node has a buffer that collects writes and passes them down in batches, which makes writes faster than in a B+ tree while keeping read performance. It was used by TokuDB (formerly available in Percona Server for MySQL, since removed).

Learned Index

Learned Indexes, proposed by Tim Kraska et al. in 2018, replace the routing done by B+ tree internal nodes with machine learning models (linear regression, neural networks). When the data distribution is predictable, they may be faster and use less memory than B+ trees. Practical adoption still faces many challenges, and the technique remains largely in the research stage.

ALEX (Adaptive Learned Index)

ALEX makes learned indexes more practical by supporting dynamic inserts and deletes and by updating its models as the data distribution changes.

Summary

Both B+ trees and LSM-Trees are designed around the characteristics of disk I/O:

• B+ trees reduce random reads through high fan-out and speed up range scans with linked leaves. They suit read-heavy OLTP workloads
• LSM-Trees convert all writes to sequential I/O to raise write throughput. They suit ingesting logs and time-series data
• The better structure depends on whether reads or writes dominate and how often queries scan ranges

I hope that the next time you look at an EXPLAIN query plan, you can picture how the B+ tree determines the search path behind it.