Introduction

Pages & Storage Layout left us with a heap: rows sit in whatever page had room, and each one has an address like (7,3). That is fine for storing rows and useless for finding them. To answer WHERE id = 42 on a heap you read every page.

Every mainstream relational engine fixes this with the same structure, the B-tree, and has for about fifty years. PostgreSQL's default index, SQLite's tables and indexes, and InnoDB's clustered tables are all B-trees built from the slotted pages of the last article. This one covers why the tree is shaped the way it is, how it grows through page splits, and what that looks like inside a real PostgreSQL index.

A binary tree on disk is too tall

Part 2 of Data Structures with Golang built a BinarySearchTree and an AVLTree, and its last section listed B-trees among the variations that build on the same ideas. This is where that one comes in. The search rule is the BST rule, smaller keys to the left and bigger ones to the right, and like the AVL tree it stays balanced no matter the insert order. What changes is the shape, because the tree now has to live on disk.

An AVL tree with a million keys is about 20 levels deep, since log2(1,000,000) is roughly 20. In memory that's 20 pointer hops and nobody notices.

On disk each of those hops can be a page read. Twenty random reads per lookup is slow on an SSD and terrible on a spinning disk, and most of each 8 KB read would be wasted: a binary node holds one key and two pointers, maybe 24 bytes of the page.

The fix is to make each node fill a page. If a page holds a few hundred keys and a few hundred child pointers, every level divides the search space by a few hundred instead of by two:

A PostgreSQL index on an int column fits around 400 entries per page, so a billion-row table is four levels deep. The top two levels are a handful of pages that get read on every lookup and stay in the buffer pool permanently. In practice a point lookup costs one or two page reads that actually miss the cache, no matter how big the table is.

That's the whole idea of the B-tree. It is a balanced search tree whose nodes are pages, wide enough that the tree stays short.

B-tree or B+tree

The original B-tree from Bayer and McCreight (1970) stores keys and values in every node. Almost every database actually uses the variant called a B+tree:

• Leaf pages hold every key, each with its value. In a PostgreSQL index the value is the heap ctid; in SQLite's table trees it is the row itself.
• Internal pages only hold separator keys and child page numbers. A separator just says which child to follow, and it doesn't have to be a key that still exists.
• Leaves are linked to their siblings, so a range scan finds the first key and then walks sideways along the leaf level without going back up.

Keeping values out of internal pages is what makes the fanout high. An internal page full of 4-byte keys and 4-byte page numbers holds far more entries than one that also carries rows. The sibling links are what make BETWEEN, ORDER BY and > cheap: once you find the start, the rest is reading leaves in order. That is also what the hash table from Part 3 can't give you: it finds one key in O(1), but WHERE id BETWEEN 100 AND 200 means checking every bucket.

Most papers and source code just say "B-tree" and mean B+tree, and so does the rest of this article.

A B+tree in Go

Here is a small B+tree. Nodes are identified by a PageID and looked up in a map, which stands in for the buffer pool from the last article, and MaxKeys is set to 4 so splits happen often enough to watch. A real engine would serialize each node into a slotted page. The tree also implements the same Container interface used throughout the Data Structures series, so it sits next to BinarySearchTree and AVLTree.

package btree

import (
	"fmt"
	"math"
	"slices"
)

// MaxKeys is tiny so splits are easy to watch. A real 8 KB page holds hundreds.
const MaxKeys = 4

type PageID uint32

type node struct {
	leaf     bool
	keys     []int64
	children []PageID // internal: len(keys)+1 child pages
	values   []string // leaf: one value per key
	next     PageID   // leaf: right sibling, 0 = none
}

type Tree struct {
	pages  map[PageID]*node // stands in for the buffer pool
	root   PageID
	nextID PageID
	size   int
}

func New() *Tree {
	t := &Tree{pages: map[PageID]*node{}, nextID: 1}
	t.root = t.alloc(&node{leaf: true})
	return t
}

func (t *Tree) alloc(n *node) PageID {
	id := t.nextID
	t.nextID++
	t.pages[id] = n
	return id
}

// childIndex picks the child to follow. keys[i] separates children[i]
// (everything < keys[i]) from children[i+1] (everything >= keys[i]).
func childIndex(keys []int64, key int64) int {
	i, found := slices.BinarySearch(keys, key)
	if found {
		return i + 1
	}
	return i
}

func (t *Tree) findLeaf(key int64) *node {
	n := t.pages[t.root]
	for !n.leaf {
		n = t.pages[n.children[childIndex(n.keys, key)]]
	}
	return n
}

func (t *Tree) Get(key int64) (string, bool) {
	n := t.findLeaf(key)
	i, found := slices.BinarySearch(n.keys, key)
	if !found {
		return "", false
	}
	return n.values[i], true
}

// Scan calls fn for every key in [from, to], following leaf siblings.
func (t *Tree) Scan(from, to int64, fn func(int64, string)) {
	for n := t.findLeaf(from); n != nil; n = t.pages[n.next] {
		for i, k := range n.keys {
			if k > to {
				return
			}
			if k >= from {
				fn(k, n.values[i])
			}
		}
	}
}

func (t *Tree) Empty() bool { return t.size == 0 }

func (t *Tree) Size() int { return t.size }

func (t *Tree) Clear() { *t = *New() }

// Values walks the leaf level left to right, so keys come out sorted.
func (t *Tree) Values() []interface{} {
	values := make([]interface{}, 0, t.size)
	t.Scan(math.MinInt64, math.MaxInt64, func(k int64, _ string) {
		values = append(values, k)
	})
	return values
}

func (t *Tree) String() string {
	return fmt.Sprintf("%v", t.Values())
}

A lookup is a binary search inside each page, from the root down to a leaf. Every level is one page visit, so the cost of Get is the height of the tree. Scan does one descent to find where from would be and then never goes back up: it reads the rest of that leaf and follows next until it passes to.

Values is where the difference from Part 2 shows. There, bstInOrder recursed into the left subtree, visited the node and recursed into the right one to produce sorted output. A B+tree keeps every key in the leaves, already sorted and linked, so the in-order traversal is a loop along the bottom level. With the same keys as the BST example from Part 2:

t := btree.New()
for _, k := range []int64{8, 3, 10, 1, 6, 14, 4, 7, 13} {
	t.Put(k, "")
}
fmt.Println(t.Size(), t.Height()) // 9 2
fmt.Println(t)                    // [1 3 4 6 7 8 10 13 14]

The BST needed four levels for those nine keys. With four keys per page, the B+tree needs two.

Inserting and splitting

Inserting always happens at a leaf. The interesting case is when the leaf is already full:

// Put inserts or replaces key. When the root splits, the tree grows by one level.
func (t *Tree) Put(key int64, value string) {
	if sep, right, split := t.insert(t.root, key, value); split {
		t.root = t.alloc(&node{keys: []int64{sep}, children: []PageID{t.root, right}})
	}
}

// insert returns the separator and new right page when id had to split.
func (t *Tree) insert(id PageID, key int64, value string) (int64, PageID, bool) {
	n := t.pages[id]
	if n.leaf {
		i, found := slices.BinarySearch(n.keys, key)
		if found {
			n.values[i] = value
			return 0, 0, false
		}
		n.keys = slices.Insert(n.keys, i, key)
		n.values = slices.Insert(n.values, i, value)
		t.size++
	} else {
		i := childIndex(n.keys, key)
		sep, right, split := t.insert(n.children[i], key, value)
		if !split {
			return 0, 0, false
		}
		n.keys = slices.Insert(n.keys, i, sep)
		n.children = slices.Insert(n.children, i+1, right)
	}
	if len(n.keys) <= MaxKeys {
		return 0, 0, false
	}
	return t.split(n)
}

func (t *Tree) split(n *node) (int64, PageID, bool) {
	mid := len(n.keys) / 2
	sep := n.keys[mid]
	r := &node{leaf: n.leaf}
	if n.leaf {
		// Leaf: the separator is copied up and stays in the right page.
		r.keys = slices.Clone(n.keys[mid:])
		r.values = slices.Clone(n.values[mid:])
		n.keys, n.values = n.keys[:mid], n.values[:mid]
		r.next = n.next
	} else {
		// Internal: the separator moves up and leaves both halves.
		r.keys = slices.Clone(n.keys[mid+1:])
		r.children = slices.Clone(n.children[mid+1:])
		n.keys, n.children = n.keys[:mid], n.children[:mid+1]
	}
	rid := t.alloc(r)
	if n.leaf {
		n.next = rid
	}
	return sep, rid, true
}

When a leaf overflows, half its keys move to a new page, and the first key of the new page goes up to the parent as a separator. If that makes the parent overflow, it splits too, and so on up. When the root itself splits, Put creates a new root above both halves. That is the only way a B-tree gets taller.

Compare that with insertAVL from Part 2. The AVL tree adds a node at the bottom, recomputes heights on the way back up, and rotates when one side becomes two levels taller than the other. A B-tree never rotates. It grows at the root instead of at the leaves, so every leaf is always at the same depth and there is no balance factor to track. The recursion looks familiar, though: insert hands its split back to the caller the same way insertAVL hands back a new subtree root.

Inserting 5 into a full leaf looks like this:

Leaf and internal splits are slightly different. A leaf split copies the separator up and keeps 3 in the right leaf, because the leaf level has to hold every key. An internal split moves its middle separator up and drops it from both halves, since it only exists to route searches.

Using it:

t := btree.New()
for i := int64(1); i <= 20; i++ {
	t.Put(i, fmt.Sprintf("user-%d", i))
}
fmt.Println(t.Height()) // 3

t.Scan(7, 10, func(k int64, v string) { fmt.Print(v, " ") })
// user-7 user-8 user-9 user-10

Now look at how full the leaves end up. Insert 100,000 keys in ascending order into one tree and the same keys in random order into another, and count how many of the MaxKeys slots in each leaf are used:

sequential: 50% full, random: 73% full

Sorted input was the bad case in Part 2 too, where it turned a plain BST into a linked list. A B-tree's height can't degenerate like that, so here sorted input costs space instead. Every split happens at the rightmost leaf, leaves the left half with 2 keys, and nothing is ever inserted into that left page again. Random inserts land all over the tree and fill pages back up between splits, which is why they average around 70%. Real engines handle the ascending case specially, as we'll see next.

Inside a PostgreSQL B-tree

PostgreSQL's B-tree is called nbtree, and its code lives in src/backend/access/nbtree/. The README in that directory is the design document, and it's worth reading in full once you've finished this article. Let's build an index and open it:

CREATE EXTENSION pageinspect;
CREATE TABLE seq (id int PRIMARY KEY);
INSERT INTO seq SELECT generate_series(1, 1000000);

SELECT root, level FROM bt_metap('seq_pkey');

 root | level
------+-------
  412 |     2

Block 0 of every nbtree index is a metapage that records where the root is. The root is at block 412, two levels above the leaves (level 0), so the tree has three levels. The root can move when it splits, and the metapage is how every search finds it. A million rows, three levels.

Now a leaf. bt_page_stats reads the page header and the special space, the 16-byte BTPageOpaqueData at the end of the page that the last article said B-tree pages use for sibling links:

SELECT type, live_items, free_size, btpo_prev, btpo_next, btpo_level
FROM bt_page_stats('seq_pkey', 1);

 type | live_items | free_size | btpo_prev | btpo_next | btpo_level
------+------------+-----------+-----------+-----------+------------
 l    |        367 |       808 |         0 |         2 |          0

Block 1 is the leftmost leaf (btpo_prev is 0), its right sibling is block 2, and it holds 367 items. Each item is an IndexTupleData: a 6-byte heap TID, 2 bytes of flags and length, and the 4-byte key, padded to 16 bytes, plus a 4-byte line pointer. That's 20 bytes per entry, so (8192 - 24 - 16) / 20 gives a maximum of about 407 per page. The page is only 90% full, and that's on purpose.

SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('seq_pkey', 1) LIMIT 3;

 itemoffset | ctid  | itemlen |          data
------------+-------+---------+-------------------------
          1 | (1,1) |      16 | 6f 01 00 00 00 00 00 00
          2 | (0,1) |      16 | 01 00 00 00 00 00 00 00
          3 | (0,2) |      16 | 02 00 00 00 00 00 00 00

Items 2 onward are the index entries: key 1 points at heap tuple (0,1), key 2 at (0,2), in little-endian bytes. Item 1 is not an entry. It's the page's high key, 0x16f = 367, an upper bound on every key the page can contain. Every leaf except the rightmost has one, and it's what makes concurrent splits safe, as we'll see below.

The root shows the other half of the format:

SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('seq_pkey', 412) LIMIT 3;

 itemoffset |  ctid   | itemlen |          data
------------+---------+---------+-------------------------
          1 | (3,0)   |       8 |
          2 | (411,1) |      16 | 77 97 01 00 00 00 00 00
          3 | (698,1) |      16 | ed 2e 03 00 00 00 00 00

On internal pages the ctid field holds a child block number instead of a heap address. The first item has no key at all: it means "minus infinity", and points at block 3 for everything below the next separator. The second says keys from 0x19777 (104,311) go to block 411. That's the same layout as childIndex in the Go version, with one more child than separators.

A point lookup touches one page per level plus the heap:

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
  SELECT * FROM seq WHERE id = 500000;

 Index Only Scan using seq_pkey on seq (actual rows=1.00 loops=1)
   Index Cond: (id = 500000)
   Heap Fetches: 1
   Index Searches: 1
   Buffers: shared hit=4

Four buffers: root, internal page, leaf, and one heap page. The heap fetch happens because the table hasn't been vacuumed yet, so the visibility map can't vouch for the row; after a VACUUM, this becomes three.

The rightmost page splits differently

The 90% fill comes from _bt_findsplitloc in nbtsplitloc.c. When the page being split is the rightmost one on its level, nbtree assumes the inserts are ascending and splits so the left page keeps fillfactor percent of the data: 90 for leaves by default, 70 for internal pages. Everything else splits roughly in the middle. CREATE INDEX packs leaves to the same 90% when it builds from sorted input.

That's the fix for the 50% our Go tree gets on sequential keys. Serial IDs, timestamps and other ascending keys fill pages almost completely and never touch them again. SQLite has the same trick for tables: balance_quick in btree.c handles an append to the rightmost leaf by putting the new row alone on a fresh page and leaving the full page as it is.

Splitting without stopping readers

Our Go tree assumes nothing else runs during a split. In PostgreSQL, hundreds of backends may be reading and inserting into the same index, and you don't want one split to lock everyone out of the path from root to leaf.

nbtree uses the design from Lehman and Yao's 1981 paper, which is why every page has a right sibling link and a high key. A search reads the parent, releases it, and then reads the child. Between those two steps the child might split and send the key it's looking for to a new right sibling. So when the search lands on the child, it compares its key with the high key. If the key is bigger, the page has split under it and the search follows the right link, as many times as needed. Readers never hold more than one page lock at a time while descending.

Splits happen in two steps. First the page is split and the new right sibling is linked in, written as one WAL record. Then the separator for the new page is inserted into the parent as a separate step. If the server crashes between the two, the left page carries a BTP_INCOMPLETE_SPLIT flag, and the next insert that comes across it finishes the job. In the meantime nothing is lost, because any search that reaches the left page can still find the right one through the sibling link.

Duplicates and posting lists

A primary key has one entry per value. An index on status with five distinct values has 200,000 entries per value, and storing the same key 200,000 times is mostly waste. Since PostgreSQL 13, nbtree deduplicates them into posting lists: one key followed by a sorted array of heap TIDs.

CREATE TABLE orders (id int, status int);
INSERT INTO orders SELECT i, i % 5 FROM generate_series(1, 1000000) i;
CREATE INDEX orders_status ON orders (status);
CREATE INDEX orders_status_nodedup ON orders (status) WITH (deduplicate_items = off);

 orders_status | orders_status_nodedup
---------------+-----------------------
 6800 kB       | 21 MB

Three times smaller, with the same number of rows indexed. bt_page_items shows the posting lists as 808-byte items with a tids array. Deduplication runs lazily, only when a leaf is about to split, so it costs nothing on pages that still have room. Unique indexes benefit too, because MVCC leaves several versions of the same key around until vacuum, which is the subject of a later article.

PostgreSQL 12 also added suffix truncation: when a leaf splits, the new separator keeps only as many leading columns as it needs to tell the two pages apart. On a (customer_id, created_at) index, the separators in internal pages often contain just the customer_id, which makes internal pages hold more entries and the tree shorter.

Pages don't merge

Splits have no opposite in nbtree. VACUUM removes dead entries from leaves, and it deletes a page only once it is completely empty. Two neighboring leaves at 10% each stay as two pages.

That's the usual source of index bloat. A table where most rows are deleted over time, or one with a hot range of keys that keeps getting updated, ends up with an index much bigger than its live data. PostgreSQL 14's bottom-up deletion helps the update case by clearing old row versions out of a leaf before splitting it, but it can't merge pages that are already half empty. The fix is a rewrite, and REINDEX INDEX CONCURRENTLY does it without blocking writes.

What random keys cost

Insert the same million integers in random order instead of ascending:

CREATE TABLE rnd (id int PRIMARY KEY);
INSERT INTO rnd SELECT i FROM generate_series(1, 1000000) i ORDER BY random();

 index    | leaf_pages | avg_leaf_density | size
----------+------------+------------------+-------
 seq_pkey |       2733 |            90.01 | 21 MB
 rnd_pkey |       3761 |            65.48 | 30 MB

Same keys, 40% more pages. Random inserts split pages in the middle all over the tree, and pages hover around two-thirds full, which is what our Go tree showed too. pgstatindex from the pgstattuple extension is where these numbers come from, and running REINDEX on rnd_pkey brings it back to 21 MB because the rebuild sorts the keys.

Size isn't the only cost. With ascending keys, all inserts go to the same rightmost leaf, which stays in the buffer pool. With random keys, every insert goes to a different leaf, so the whole index has to fit in memory or inserts start reading pages from disk. The first change to each page after a checkpoint also writes a full copy of that page to the WAL, so touching many pages produces much more WAL than touching a few.

This is the practical case against UUIDv4 primary keys. The same test with a million UUIDs:

CREATE TABLE u4 (id uuid PRIMARY KEY DEFAULT gen_random_uuid());
CREATE TABLE u7 (id uuid PRIMARY KEY DEFAULT uuidv7());
INSERT INTO u4 SELECT FROM generate_series(1, 1000000);
INSERT INTO u7 SELECT FROM generate_series(1, 1000000);

 index   | leaf_pages | avg_leaf_density | size
---------+------------+------------------+-------
 u4_pkey |       4778 |            72.23 | 38 MB
 u7_pkey |       3832 |            89.98 | 30 MB

UUIDv7 puts a millisecond timestamp in its leading bits, so new values arrive in nearly ascending order and nbtree's rightmost split applies. PostgreSQL 18 ships uuidv7() built in. If you want UUIDs as keys, that's the one to use. In a clustered engine like InnoDB or SQLite the difference is even bigger, because there the random key decides where the whole row goes.

SQLite: two kinds of tree

SQLite's file is a collection of B-trees, and the rootpage column of sqlite_schema tells you where each one starts:

CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT);
CREATE INDEX users_email ON users (email);
-- insert 100,000 rows
SELECT name, rootpage FROM sqlite_schema;

users|3
users_email|4

Not all of them are the same kind of tree. A table is a table B-tree: a B+tree keyed by rowid, with rows stored only in leaves and interior pages holding just the integer separators. An index is an index B-tree, which is a classic B-tree: interior cells hold real keys, and each key appears exactly once somewhere in the tree. You can see the difference with dbstat:

SELECT name, pagetype, count(*) AS pages, sum(ncell) AS cells
FROM dbstat GROUP BY name, pagetype;

users|internal|3|728
users|leaf|729|100000
users_email|internal|8|787
users_email|leaf|788|99213

The table keeps all 100,000 rows in its leaves, and the 728 interior cells are extra separator copies. The index has 99,213 entries in leaves and 787 in interior pages, adding up to exactly 100,000. A lookup in the index can stop at an interior page if it finds the key there.

A few other things work differently from nbtree:

• The root never moves. rootpage is stored in the schema, so when the root fills up, balance_deeper copies its contents into a new child page and the root becomes an interior page above it. PostgreSQL moves the root and updates the metapage instead.
• Splits spread over siblings. balance_nonroot redistributes cells among up to three neighboring pages instead of always splitting one page into two, which keeps pages fuller after random inserts.
• No sibling links. SQLite pages don't point at their neighbors. A cursor keeps the stack of pages it descended through and goes back up to the parent to find the next leaf. SQLite allows only one writer at a time, so it doesn't need Lehman and Yao's right links for concurrency.

What a B-tree charges for writes

B-trees are hard to beat for reads. A point lookup takes a fixed handful of page reads, a range scan reads leaves in key order, and the data is always fully sorted, so ORDER BY on an indexed column needs no sort step.

Writes are where they cost. Changing one 16-byte index entry dirties an 8 KB page, and that page will eventually be written back in full. With random keys, those dirty pages are spread over the whole index, so writes turn into random I/O. Each index on a table repeats the cost: a row insert into a table with five B-tree indexes modifies at least six pages in different places. Splits add more, and the half-empty pages they leave make the index bigger than its data.

For most OLTP workloads that trade is fine, since reads outnumber writes and the hot part of the index stays in memory. For workloads that are mostly writes, like event logs, metrics or message queues, a different design pays off: buffer writes in memory, write them out as sorted files in one sequential pass, and merge those files in the background. That is the LSM tree.

Conclusion

A B-tree is a search tree with page-sized nodes. The high fanout keeps it three or four levels deep at any realistic size, splits keep every leaf at the same depth, and sibling links turn range scans into sequential reads. Most of what PostgreSQL adds on top, from the rightmost split rule and Lehman and Yao's high keys to deduplication, deals with ascending keys, many concurrent backends, and duplicate values.

Next is LSM Trees: how LevelDB and RocksDB trade some read performance for writes that are always sequential, and what compaction does to keep the reads in check.