How a B+tree finds a row

Three kinds of page

A PostgreSQL B-tree index is a file of 8 kB pages, like a table. The pages play three roles:

Page	What it holds	How many
Metapage	Where the root is, and how tall the tree is	Exactly one, always the first page
Internal pages	Separator keys, each with a pointer one level down	A few, including the root at the top
Leaf pages	Every key, in sorted order, each with the CTID of its row	Almost all of them

The email index from the previous page has 4,961 pages: 1 metapage, 33 internal pages and 4,927 leaves. Over 99% of an index is leaves, which is typical. The tree above them is a small routing layer that stays hot in memory.

Every leaf is at the same depth. That is what makes the tree balanced: no key is ever further away than any other.

Following a lookup down the tree

To find user777777@example.com, PostgreSQL starts at the root page. There it compares the key with the separators and follows the one pointer whose range contains it. It repeats that on each level until it reaches a leaf. The leaf holds the key and its CTID, and one more read fetches the row.

That is the 4 pages you saw in the EXPLAIN output: root, internal page, leaf, table page.

Range scans walk sideways

Each level of the tree is also a linked list: every page knows its left and right neighbors. So once a search reaches the first matching leaf, a range query does not go back up the tree. It walks along the leaves in key order and stops when keys pass the end of the range.

This is why a B-tree serves BETWEEN, <, > and ORDER BY. It is the only PostgreSQL index type that returns rows in sorted order. With ORDER BY created_at DESC LIMIT 50, PostgreSQL can read the first 50 entries from the end of the index and stop, without sorting the whole table.

Inserts and page splits

A new key goes into the leaf where it belongs in sorted order. If that leaf is full, it splits: a portion of its keys, roughly half, moves to a new page, and a new separator goes up into the parent. If the parent is full too, it splits in turn, and splits can cascade all the way up.

When the root splits, PostgreSQL creates a new root above it and the tree gains one level. That is the only way a B-tree grows taller, so every leaf always moves down together.

Loading interactive…

Step through Load 24 keys in order, then Same keys, random order. Watch the message under the tree at each split, and compare the “leaves % full” figure at the end.

Order only matters while the index is being built up by inserts. When we built an index on the shuffled table after loading it, it came out at 2,733 leaf pages and 90% full, identical to the in-order one. CREATE INDEX builds the whole index from one scan of the table and fills each leaf to the fillfactor as it goes.

Repeated keys are stored once

Many indexes contain the same key many times, such as a status or a foreign key column. PostgreSQL B-trees deduplicate them by default: a group of identical keys becomes one entry that stores the key once, followed by a sorted list of row pointers. Indexes on repetitive columns shrink a lot as a result, but every row still needs its pointer, so the index never becomes free.

Check yourself

1. What do internal pages and leaf pages each store, and which kind makes up almost all of the index?

   Show answer

   Internal pages store separator keys and pointers to the next level down; they only route searches. Leaf pages store every key in sorted order with the CTID of its row. Leaves are typically over 99% of the pages.

   I could explain this without looking

2. How does a B-tree answer WHERE created_at BETWEEN a AND b without visiting the tree once per row?

   Show answer

   It descends once to the first leaf containing a, then walks right along the linked leaf pages, reading keys in order until they pass b.

   I could explain this without looking

3. How does a B-tree become taller, and why does that keep every leaf at the same depth?

   Show answer

   Only by splitting the root: a new root is created above the old one. Every leaf moves down one level at the same moment, so the tree stays balanced.

   I could explain this without looking

4. Why does inserting keys in increasing order produce a smaller index than inserting the same keys at random?

   Show answer

   Appending to the right edge keeps the old leaf filled to the fillfactor (90% by default) before starting a new page. Random inserts split full leaves in the middle, leaving pages around two thirds full, so the same keys need more pages.

   I could explain this without looking