B-Trees From the Page Up: What a Database Index Actually Is

You add an index, the query gets fast, and the story ends there for most developers. But an index is not a sorting spell the database casts on your column — it is a concrete on-disk data structure with pages, pointers, and failure modes of its own. Understanding what a B-tree actually looks like on disk explains a surprising amount of production behavior: why lookups take the same number of steps whether a table has a thousand rows or a hundred million, why bulk inserts can be dramatically faster than scattered ones, and why indexes bloat over time.

This post dissects the B-tree as your database engine really stores it, using PostgreSQL’s 8 KB page model as the reference, then looks at where the costs live and when the structure stops being the right tool.

An index is a forest of fixed-size pages

PostgreSQL stores everything — tables and indexes alike — in fixed-size pages of 8 KB. An index on disk is not one big balanced tree in memory; it is a collection of these pages linked by block numbers. Each page holds a sorted list of index entries: in a leaf page, each entry contains the indexed key plus a pointer to a table row; in an interior page, the entries are shorter signposts — a key value and the block number of the child page that covers that range.

The shape falls out of the page size. An index entry for an integer column with a row pointer is on the order of 20 bytes, so an 8 KB leaf page holds a few hundred entries. Interior entries are smaller, which means each interior page can point to hundreds of children. That multiplier is called the fanout, and it is the reason B-trees stay shallow: with a fanout of a few hundred, three or four levels of pages are enough to address tens of millions of rows.

You can convince yourself with a two-line calculation:

package main

import (
	"fmt"
	"math"
)

// levels estimates how many page-levels a B-tree needs for a given
// number of leaf entries, assuming every page is `fanout`-way branching.
func levels(entries int, fanout int) int {
	pages := int(math.Ceil(float64(entries) / float64(fanout)))
	height := 1 // the leaf level counts as one
	for pages > 1 {
		pages = int(math.Ceil(float64(pages) / float64(fanout)))
		height++
	}
	return height
}

func main() {
	fanout := 200
	for _, rows := range []int{10_000, 1_000_000, 100_000_000} {
		fmt.Printf("%d rows, fanout %d -> %d levels\n",
			rows, fanout, levels(rows, fanout))
	}
}

With a fanout of 200, ten thousand rows need 2 levels, a million rows need 3, and a hundred million need 4 — counting the leaf level itself. Since a point lookup reads one page per level on the way down, and the top levels are almost always resident in cache, an indexed lookup costs only a handful of page reads at almost any realistic table size — the logarithm is so flat it barely matters how big the table is. This is why dropping a table from 10 million to 1 million rows rarely makes indexed queries measurably faster.

Looking inside a real page

You do not have to take the page model on faith. PostgreSQL ships the pageinspect extension, which exposes the raw contents of index pages to SQL. The B-tree documentation describes the page layout in detail, but the summary view is the fastest way to get oriented:

CREATE EXTENSION IF NOT EXISTS pageinspect;

-- Summary of page 1 of an index
SELECT blkno, type, live_items, dead_items,
       avg_item_size, free_size, btpo_level
FROM bt_page_stats('orders_customer_id_idx', 1);

-- The actual entries on that page
SELECT itemoffset, itemlen, data
FROM bt_page_items('orders_customer_id_idx', 1)
LIMIT 5;

The type column tells you whether a page is a leaf or an interior node, live_items and dead_items show how full and how bloated it is, and btpo_prev / btpo_next reveal the sibling links that let range scans walk the leaves left to right without climbing back through the interior. That linked leaf level is the defining feature of the B+tree-style variant that most database engines use: interior pages exist only to route you to the right leaf, and all the actual data lives in a doubly-linked chain of leaves, which is what makes both point lookups and range scans efficient with the same structure.

Where the cost actually goes

Reads are the flattering part of the story. Writes reveal the structure’s overheads, and they cluster into three patterns worth knowing:

Page splits. When an insert lands in a leaf page that has no room, the engine splits it in two and promotes a separator key into the parent — which may itself need splitting, rippling upward. Sequential inserts (ascending keys, like timestamps or auto-increment IDs) always append to the rightmost page, and PostgreSQL splits that page asymmetrically — the left page is left about fillfactor full (90% by default) instead of half full, so ascending-key inserts waste almost no leaf space. Random inserts, by contrast, scatter splits across the whole tree, producing half-empty pages and a materially larger index for the same row count. If you have ever wondered why loading a table in key order is so much faster than in random order, page splits are the answer.

Write amplification. Every insert touches not just the table but every index that contains the changed columns — and each index write means a full 8 KB page read-modify-write in the worst case. A table with six indexes does roughly seven disk-level writes per insert. This is why “add an index” is never free on write-heavy tables, and why dropping unused indexes is one of the highest-leverage cleanups available.

Bloat from updates and deletes. When an indexed column is updated, PostgreSQL’s default behavior inserts a new index entry for the new key value while marking the old one dead; the space is only reclaimed by vacuum and page reuse. Dead items linger in bt_page_stats output as the gap between live_items and dead_items, and enough of them inflate the tree, wasting cache space on pages that hold mostly garbage. (One pleasant exception: updates that change no indexed column and can place the new row version on the same table page take the heap-only-tuple path and skip index updates entirely — a good reason to keep hot, frequently-updated columns out of your indexes.)

When a B-tree is the wrong tool

The B-tree optimizes reads at the cost of in-place writes: every insert must find one specific page and mutate it. That is the worst possible pattern for write-heavy append-only workloads, which is why LSM-tree storage engines (as found in RocksDB-derived systems and several analytical databases) invert the trade: they append writes to an in-memory structure and compact sorted runs in the background, accepting slower reads and background work in exchange for fast ingestion. Neither design dominates — the right question is your read/write ratio and whether your access pattern is point lookups, range scans, or aggregations.

Within the B-tree world, a few practical corollaries are worth internalizing:

  • Index column order in composite indexes matters because the tree sorts by the leading column first — the structure cannot “skip” an unconstrained leading column.
  • Very wide index entries shrink the fanout, deepening the tree and lowering cache hit rates. Index only the bytes you will seek by.
  • Keeping frequently-accessed interior pages in cache matters more than total index size, because every descent from the root touches the same top pages.
  • After a large backfill in random key order, expect substantially wasted leaf space from splits until a REINDEX compacts it.

Wrapping up

A B-tree index is just sorted 8 KB pages arranged in a shallow fanout tree, with the leaves chained together for range scans. Its consistency under concurrent access and its near-flat lookup cost are why it has survived fifty years as the default index structure. Its costs — page splits, write amplification, and bloat under churn — are equally predictable from the same page model. When the next “should I add an index?” decision comes up, think past the query planner to the pages: how many bytes per entry, how scattered the inserts will be, and whether the columns you are indexing will actually churn.

Leave a Reply

Your email address will not be published. Required fields are marked *