How Database Indexes Work: B-Trees, Intuitively

Every database tutorial eventually lands on the same advice: “add an index.” The advice works — a query that scanned a million rows in seconds returns in milliseconds — but the explanation usually stops there. An index is not magic, and it's not free. Under the hood of PostgreSQL, MySQL, and SQLite, indexes are a single data structure, the B-tree, and understanding it will tell you exactly when an index helps, when it hurts, and why some queries still ignore yours.

The problem: sorted data that must stay sorted

Start without an index. A table is an unordered heap of rows; a WHERE email = 'x' query reads every row and checks. That's a full scan, and its cost grows linearly with the table. For a million rows, every lookup touches a million rows.

The obvious fix is sorting: if rows were ordered by email, you could binary-search your way to the answer in about 20 comparisons. But real tables aren't read-only. Insert a new row in the middle of a sorted file and everything after it shifts; delete one and everything shifts back. On disk, where storage moves in fixed-size blocks, that shifting is ruinously expensive.

What we need is a structure that keeps data ordered for fast search, yet lets inserts and deletes happen locally, without rewriting the world. In 1969 at Boeing Research Labs, Rudolf Bayer and Edward M. McCreight designed exactly that; their paper, “Organization and Maintenance of Large Ordered Indexes,” was published in Acta Informatica in 1972. The B-tree has been the backbone of database indexing ever since.

The core idea: a wide, shallow, self-balancing tree

A B-tree organizes keys into pages (also called nodes or blocks) — chunks of data sized to match what the disk reads in one go. Each page holds a sorted list of keys and pointers to child pages. To find a key, you start at the root page, compare your target against its keys, follow the pointer into the right child page, and repeat. Every level you descend eliminates a huge fraction of the remaining search space.

The critical trick is the fan-out: each page points to many children, not two like a binary tree. That makes B-trees extraordinarily wide and shallow. Suppose entries are about 32 bytes each and pages are 16 KiB — PostgreSQL uses 8 KiB pages by default; InnoDB uses 16 KiB. A 16 KiB page holds roughly 500 entries, so each page can point to ~500 children. Tree height then grows as the logarithm of the row count with base 500:

1 level: ~500 keys
2 levels: ~500 × 500 = 250,000 keys
3 levels: ~500³ ≈ 125,000,000 keys

So a lookup in a 125-million-row index costs about three page reads. Double the table to 250 million rows and the height still rounds to three — the logarithm's base is so large that lookup cost is effectively constant. That is the entire reason indexes exist: an O(log N) search with a base-500 logarithm.

The tree also stays balanced by construction: every leaf page is exactly the same distance from the root, so every lookup costs the same number of steps. When a page fills up, it splits into two half-full pages and the middle key is promoted to the parent — a local operation. If splits cascade all the way up and the root itself splits, the tree gains one new level. Inserts and deletes touch only the pages on one root-to-leaf path, which is why maintaining order costs so little.

B+ trees: the variant everyone actually uses

The classic B-tree stores data pointers in every node, including internal ones. The variant used by real database engines, the B+ tree, pushes all record pointers down to the leaf level; internal nodes hold only keys and child pointers. This means each internal node packs in more keys, which raises the fan-out and keeps the tree even shallower.

The other B+ innovation is leaf chaining: leaf pages are linked together in key order, so range scans (WHERE created_at BETWEEN x AND y) and ordered output (ORDER BY) just walk the chain instead of doing a fresh tree descent per row.

Real engines are close cousins of this design. PostgreSQL's implementation is officially called “B-Tree” (nbtree) — a high-concurrency variant after Lehman and Yao — and its docs note that each level of the tree doubles as a doubly-linked list of pages, which is structurally B+-like. In fact, CREATE INDEX defaults to the B-tree method; it's the index type you get unless you ask for something else. InnoDB documents all of its indexes as B-tree structures (storing index records in leaf pages). SQLite's file format spec likewise describes its pages as B-tree pages. The exact label differs, but the shape — wide, shallow, leaf-chained — is the same everywhere.

What the engine actually stores

The index structure is only half the story; the other half is what each entry points to, and this differs by engine.

In InnoDB, the primary key defines the clustered index: the table's rows themselves live in the B-tree's leaves, ordered by primary key. (No primary key? InnoDB falls back to the first suitable unique NOT NULL index, then to a hidden internal one.) Every secondary index stores the primary key alongside its own columns — so a lookup through a secondary index is really a double lookup: search the secondary index, then use the PK value to find the row in the clustered index. This has a practical consequence straight from MySQL's docs: long primary keys bloat every secondary index, “so it is advantageous to have a short primary key.”

PostgreSQL separates the two: the index holds keys plus pointers to heap rows, and the heap holds the actual row data. This enables a neat optimization, the index-only scan: if a query needs only columns present in the index, PostgreSQL can answer without touching the heap at all. But there's a catch — the engine must be sure the heap rows are visible to your transaction, and it tracks that with per-page “all-visible” bits in the table's visibility map. If those bits aren't set (common right after heavy writes), the scan visits the heap anyway and gains nothing.

The price of speed: what indexes cost

Indexes make reads fast by making writes do more work. Every insert, update, or delete must maintain each index on the table. The costs show up in several concrete ways:

Page splits. Random-order inserts split pages constantly, and a freshly split page is only about half full — InnoDB notes that random inserts leave pages anywhere from half to 15/16 full, versus ~15/16 for sequential inserts. If a page's fill factor drops below 50%, InnoDB tries to merge it with a neighbor to reclaim the page. Splits can cascade upward; when the root splits, the whole tree grows one level.
Write amplification. In PostgreSQL, updating a single indexed column creates a new index entry in every index on the table — even indexes on columns you didn't touch. (Modern versions mitigate this with bottom-up index deletion, but the fundamental cost remains.)
Storage. Each index is a full copy of its key columns plus pointers. Index three columns on a wide table and you've stored a substantial fraction of the table twice.

The rule of thumb follows directly: index the columns your queries actually filter, join, and sort on — and stop there. An index on a rarely-queried column is pure overhead, paid on every write, and it can even slow reads by tempting the planner into a worse plan. Also remember that very low-cardinality columns (a boolean flag) rarely deserve an index on their own: the planner will usually prefer a full scan.

Still evolving

Fifty-plus years on, the B-tree is still being refined. PostgreSQL 18 added skip scan support, letting the planner use multi-column B-tree indexes in cases it previously couldn't — proof that even the most settled data structure in computing keeps improving.

The mental model to carry away is simple: a database index is a wide, shallow, self-balancing tree of pages, and every design decision in it — the page size, the fan-out, the leaf chaining, the clustered storage — exists to turn a linear scan into three disk reads while keeping inserts local. Once you see that, EXPLAIN output stops being mysterious: an index scan is a walk down that tree, a sequential scan is the engine admitting the tree can't help, and the right index is simply the one whose key order matches your query's question.