How B+ Tree Indexes Work
Why databases index with B+ trees: wide nodes keep the tree 3 levels deep for 134 million keys, and linked leaves make range scans cheap. A small Python B+ tree and SQLite query plans show it.
A B+ tree index is a balanced tree whose nodes are each one disk page holding hundreds of keys, with all entries stored in sorted leaves that are linked together. Interviewers expect the reason databases use it: the wide fan-out keeps the tree only 3 or 4 levels deep, and the leaf chain makes range queries cheap.
Most database indexes are B+ trees. Each node is as large as a disk page and holds hundreds of keys, so the tree is very shallow: with 512 entries per node, three levels cover about 134 million keys. All values sit in linked leaf nodes, so a lookup costs a few page reads and a range query walks along the leaves.
- With 8 KB pages and 16-byte entries, a B+ tree node holds 512 entries, so three levels address about 134 million keys and four levels about 69 billion.
- A B+ tree lookup in a million-row table needs about 3 page reads, while a balanced binary tree with a million keys is about 20 levels deep.
- In a B+ tree, internal nodes hold only routing keys and all entries sit in leaves chained in sorted order, which makes range queries a walk along the leaves.
- In SQLite query plans on a 200,000-row table, LIKE '%777%' and WHERE age + 1 = 31 both caused a full table scan despite indexes on those columns.
- A composite B+ tree index on (a, b) helps queries on a, or on a and b, but not on b alone, because the tree is sorted by a first.
- Random UUID keys insert into random B+ tree leaves, causing more page splits and cache misses than monotonically increasing ids.
01Why not a binary tree
A balanced binary tree with a million keys is about 20 levels deep. If each level lives on a different disk page, a lookup costs about 20 page reads, and reading a page from disk is thousands of times slower than a comparison in memory. So a database wants the fewest page reads, not the fewest comparisons.
The fix is to make each node as large as one disk page and pack in many keys. A node with hundreds of children needs very few levels. That is the idea behind the B-tree family.
02The numbers: how shallow is it?
Suppose a page is 8 KB and each entry is an 8-byte key plus an 8-byte pointer. Then one page holds 8192 / 16 = 512 entries. Each level multiplies the reach by about 512, so:
import math
fan = 8192 // (8 + 8) # 512
print(fan ** 3, fan ** 4) # 134217728 68719476736
print(math.ceil(math.log(1_000_000, fan))) # 3
print(math.ceil(math.log(1_000_000_000, fan))) # 4Three levels address about 134 million keys and four levels about 69 billion. So a table of a million rows needs 3 page reads to find a key, and a billion-row table needs 4. The top levels are small and almost always cached in memory, so in practice a lookup often touches disk once or twice. These are idealised numbers: real pages are not perfectly full, and key sizes vary.
03B-tree versus B+ tree
In a plain B-tree, keys and their data can live in internal nodes too. Most databases (MySQL InnoDB, PostgreSQL, SQLite for its indexes) use the B+ tree variant. Internal nodes hold only separator keys used for routing, which lets each internal page hold more keys and keeps the tree shallower. All the actual entries are in the leaf level, and the leaves are chained together in sorted order like a linked list.
That chain is what makes range queries cheap, as the next section shows.
04A small B+ tree you can run
import bisect
M = 4 # max keys per node
class Leaf:
def __init__(s, keys): s.keys, s.next = keys, None
class Inner:
def __init__(s, keys, kids): s.keys, s.kids = keys, kids
def first_key(n):
while isinstance(n, Inner): n = n.kids[0]
return n.keys[0]
def build(keys): # bulk-load from sorted keys
level = [Leaf(keys[i:i+M]) for i in range(0, len(keys), M)]
for a, b in zip(level, level[1:]): a.next = b
while len(level) > 1:
level = [Inner([first_key(k) for k in level[i+1:i+M+1]], level[i:i+M+1])
for i in range(0, len(level), M + 1)]
return level[0]
def find_leaf(root, k):
n, reads = root, 1
while isinstance(n, Inner):
n = n.kids[bisect.bisect_right(n.keys, k)]; reads += 1
return n, readsWith keys 10, 20, ... 1000, looking up 370 finds it after 3 node reads (root, one internal node, one leaf). Looking up 375, which is absent, also takes 3 reads, and the leaf shows it is absent. The cost does not depend on whether the key exists, only on the height. This version only bulk-loads sorted data. Real databases also split full nodes on insert and merge sparse ones on delete to stay balanced.
05Range queries follow the leaf chain
def range_scan(root, lo, hi):
leaf, reads = find_leaf(root, lo)
out = []
while leaf:
for k in leaf.keys:
if k > hi: return out, reads
if k >= lo: out.append(k)
leaf = leaf.next
if leaf: reads += 1
return out, reads
root = build(list(range(10, 1001, 10))) # keys 10, 20, ... 1000
print(find_leaf(root, 370)[1], find_leaf(root, 375)[1]) # 3 3
print(range_scan(root, 370, 450))The output is the nine keys 370 through 450 with 5 node reads: 3 to descend to the leaf holding 370, then 2 hops along the chain. A hash index cannot do this. It finds exact matches fast but keeps no order, so BETWEEN, ORDER BY and prefix searches need something ordered. This is why B+ trees are the default index type.
06What the query planner does with an index
I built a table of 200,000 rows with a primary key, an index on email and an index on age, then asked SQLite to explain each query. The plans were:
WHERE id = 150000 SEARCH t USING INTEGER PRIMARY KEY
WHERE id BETWEEN 1000 AND 1100 SEARCH t USING INTEGER PRIMARY KEY (range)
WHERE email = 'u777@x.com' SEARCH t USING INDEX idx_email
WHERE age = 30 SEARCH t USING INDEX idx_age
WHERE email LIKE '%777%' SCAN t
WHERE age + 1 = 31 SCAN tThe first four walk the tree. The last two scan the whole table. A leading wildcard in LIKE defeats the index because the tree is sorted by the start of the string. And wrapping the column in an expression, age + 1, hides it from the index. Rewrite it as age = 30. Whether an index helps is decided by how the query is written.
07Costs and design choices
Every insert, update or delete touches the table and every index on it, and may split or merge pages. Each index also takes disk space. So index the columns you filter, join and sort on, and not everything.
A few choices matter at scale. Keys that grow monotonically, like auto-increment ids, append to the right edge and fill pages neatly. Random keys such as UUIDs insert all over the tree, causing more page splits and cache misses. A composite index on (a, b) helps queries on a or on a and b, but not on b alone, because the tree is sorted by a first. Short keys give higher fan-out and a shallower tree.
08Common interview questions
Q: Why do databases use B+ trees rather than binary trees?
A: Wide nodes sized to a disk page keep the tree very shallow, so a lookup needs few page reads.
Q: B-tree versus B+ tree?
A: A B+ tree stores all data in the leaves and links the leaves. Internal nodes hold only routing keys, so they fit more keys.
Q: How does a B+ tree answer a range query?
A: Descend to the first matching leaf, then follow the leaf links until the range ends.
Q: When will an index not be used?
A: With a leading wildcard in LIKE, a function or expression applied to the column, or when the query returns most of the table anyway.
Q: Do indexes have a cost?
A: Yes. They slow writes and use space, so add only those your queries need.
Q: Why are random UUID keys slower to insert than sequential ids?
A: They land in random leaves, causing more page splits and poorer cache use.