B-tree index: an interactive visualization of inserts, splits and page fill

A B-tree is the index behind almost every relational database: PostgreSQL, MySQL’s InnoDB, SQL Server, Oracle and SQLite all use one by default. It is a balanced tree of fixed-size pages, each holding hundreds of sorted keys, so even billions of rows are only a few levels deep and any lookup reads one page per level. Its leaves are kept in key order, which makes range scans and ORDER BY cheap.

The playground grows a small tree one key at a time. Change the order keys arrive in and how many fit in a node, and watch nodes fill, split and push the tree a level taller.

Lookups, inserts and splits

Internal nodes hold separator keys that say which child to follow; a lookup starts at the root and takes one branch per level down to a leaf. An insert does the same walk and adds the key to the leaf. When the leaf has no room, it splits: half its keys move to a new page and a separator for the new page goes up to the parent, which may split in turn. When the root splits, a new root is created above it. The tree grows from the top, so every leaf stays the same distance from the root without a separate rebalancing step.

Real pages are wide. An 8 KB page holds a few hundred keys, so with 400 per page, 70% full, an index over a million rows is 3 levels tall, over 100 million 4, and over 10 billion 5. The top levels are read so often that they stay in memory, and a lookup usually costs one or two disk reads.

Ascending keys vs random keys

With random keys, inserts land all over the tree and each split leaves two half-full pages behind: in the playground, 30 random keys with 4 per node leave the leaves 83% full, and the last 10 inserts wrote 7 different leaf pages. Ascending keys always land in the rightmost leaf. PostgreSQL and InnoDB notice this and split that leaf unevenly, leaving the old page nearly full and starting the new one almost empty, so the pages behind the edge stay full: 94% here, where the split moves just the new key, with the last 10 inserts writing only 4 leaves.

That difference matters for primary keys. A random UUID (version 4) scatters inserts across every leaf of the index, so once the index is bigger than memory, each insert can mean a page read and a page write, and the index ends up larger than it needs to be. Time-ordered ids, such as an auto-increment column, UUID version 7 or a Snowflake id, keep inserts at the right edge, where the pages are already in memory.

B-trees and LSM trees

A B-tree updates pages in place, so reads are fast and predictable but every write rewrites a whole page somewhere in the tree. An LSM tree buffers writes in memory and writes sorted files sequentially, which suits write-heavy workloads, at the cost of reads that may check several files and of background compaction. Most indexes called B-trees are strictly B+ trees: values live only in the leaves, and the leaves are linked so a range scan walks along them.

B-tree indexes in SQL

-- a B-tree is the default index type
CREATE INDEX orders_by_customer ON orders (customer_id, created_at);

-- one lookup walks root to leaf, then reads along the leaves in order
EXPLAIN SELECT * FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
--  Limit
--    ->  Index Scan Backward using orders_by_customer on orders
--          Index Cond: (customer_id = 42)

-- time-ordered ids keep inserts on the rightmost leaf (uuidv7() is built in from PostgreSQL 18)
CREATE TABLE events (
  id uuid PRIMARY KEY DEFAULT uuidv7(),
  payload jsonb
);

In a system design interview

Indexes come up whenever you name a query: “Orders are looked up by customer, newest first, so there is a B-tree index on customer_id and created_at; a lookup is 3 or 4 page reads and the next page of results is a scan along the leaves. Primary keys are time-ordered, so inserts append to the right edge of the index instead of touching random pages.” Expect the follow-ups: the cost of each extra index on writes, which column order a composite index needs, and when a write-heavy table is better served by an LSM-based store.

Read the guide to database indexing or storage engines, or watch a strong candidate design a key-value store.

Questions people ask