Lesson 13 · Inside a database

B-trees

Without an index, finding one row means reading every page of the table. A B-tree index keeps the keys sorted in a tree of pages, so the database reads one page per level instead. Follow CREATE INDEX on a small books table, a search for id 28, a range scan along the linked leaves, and an insert that fills a page, splits it and copies a separator key up to the root.

14 min11 steps5 questionsAdvanced

Fig 13 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01The figure's root page holds the keys 20 and 40. Which pointer does a search for 35 follow?

20 ≤ 35 < 40, so the search follows the middle pointer to leaf B. Each page read sends the search down exactly one pointer.

02What does a leaf entry in a PostgreSQL B-tree index store?

Each leaf entry pairs a key with a TID, the row's physical address, which PostgreSQL shows as the hidden column ctid. The index then reads just that one table page.

03Why can WHERE id BETWEEN 17 AND 33 use the B-tree after one descent?

The search descends once to 17, then walks right along the leaf links: 17, 20, 28, 33. At 40 it is past 33, so it stops, and the keys come out in order.

04Inserting key 30 into a full leaf [20 28 33] (3 keys per page in the toy tree). What happens?

The full page splits in two: the old leaf keeps the lower half and a new leaf takes the upper half. The new leaf's first key, 30, is copied into the parent as a separator with a pointer to it.

05A B-tree has 300 entries per page and 3 levels. About how many keys can it reach, and how many index pages does a lookup read?

300 × 300 × 300 = 27,000,000. Every leaf is the same depth, so any lookup reads one page per level: 3 index pages, then 1 table page.

Key terms

Glossary

Index: A separate structure beside a table that lets the DBMS find rows by a column's value without reading every page.
Sequential scan: Reading every page of a table and testing every row. PostgreSQL's EXPLAIN calls it a Seq Scan.
B-tree: A balanced tree of pages that keeps keys sorted; PostgreSQL's default index type. Database B-trees are usually B+-trees: all keys live in the leaves.
Leaf page: A bottom page of a B-tree: every key with the TID of its row, linked to the leaf pages beside it.
Root and internal pages: The pages above the leaves. They hold separator keys and pointers that steer a search down one level at a time.
TID: Tuple identifier: a row's address in the table as (page, slot). PostgreSQL shows it as the hidden column ctid.
Page split: What happens when a key must go into a full page: the page divides in two and a separator key is added to the parent.
Fanout: How many child pointers one page holds. With hundreds per page, a few levels reach millions of keys.

Fine print

Notes and sources

The toy pages hold at most 3 keys so the tree fits the picture. A real 8 kB PostgreSQL page holds hundreds of small keys, so real trees are wide and shallow.
Strictly, this is a B+-tree: every key lives in a leaf, and the pages above only hold separator copies. PostgreSQL’s B-tree index (and most database “B-trees”) work this way.
PostgreSQL links the pages of every level in both directions, not just the leaves, and stores a “high key” on each page. These come from the Lehman and Yao design and let searches run while other sessions split pages.
PostgreSQL chooses the split point to balance free space between the two pages. When keys arrive in increasing order it packs the left page fuller, to the fillfactor (90% by default for B-tree leaves).
On a table this small PostgreSQL would usually still choose a Seq Scan, because reading one or two pages is cheaper. The index wins as the table grows.
An index entry can point to a row version that another transaction cannot see yet, or that was deleted. PostgreSQL checks the row in the table before returning it.
SQLite stores every table and every index as a B-tree. The Python example prints its plan before and after CREATE INDEX: SCAN books, then SEARCH books USING INDEX books_id (id=?), then Piranesi.

Quiz Unlocks after the last step.