Why an index
Find the book with id 28. The table’s rows sit in its pages in the order they arrived, not sorted. With no index, the DBMS must read every page and test all 8 rows: a sequential scan.
CREATE INDEX builds a B-tree beside the table. It is made of pages too, but keeps the keys sorted. Leaf pages at the bottom hold every key. The root page above holds separator keys that steer each search.
Each leaf entry pairs a key with a TID, the row’s address in the table: (page, slot). Key 28 says page 1, slot 3. The leaves are in key order and linked side by side, so they read like one sorted list.
Finding keys
To find 28, start at the root. Its keys 20 and 40 split all keys into three ranges: under 20, 20 to 39, and 40 or more. 28 falls in the middle range, so follow the middle pointer.
That pointer leads to leaf B. Its keys are sorted, so a binary search finds 28 quickly, with TID (1,3). Only 2 index pages were read, not the whole table.
The TID says where the row lives: table page 1, slot 3. The DBMS reads that one page and returns Piranesi. PostgreSQL’s EXPLAIN calls this an Index Scan, not a Seq Scan.
For WHERE id BETWEEN 17 AND 33, descend once to the first key, 17, in leaf A. Then walk right along the leaf links: 17, 20, 28 and 33. 40 is past the end, so stop. The keys arrive sorted.
Growing the tree
INSERT puts the new row in table slot (1,5), then adds key 30 to the index. The search for 30 ends in leaf B, between 28 and 33. In this small tree a page holds 3 keys, and B is full.
So B splits. A new leaf, D, takes the upper half: 30 and 33. B keeps 20 and 28. D’s first key, 30, is copied up into the root with a pointer to D. The root now reads 20, 30, 40.
Every leaf sits the same distance below the root, so every search reads the same number of pages. When a full root splits, a new root grows above it: a B-tree only grows taller at the top.
Real index pages are 8 kB and hold hundreds of keys, not 3. If each page holds 300, three levels reach 300 × 300 × 300 = 27 million rows. Finding any one reads 3 index pages and 1 table page.
What happens
;; step 1/11 · scan SELECT name FROM books WHERE id = 28; no index: read every table page, test every row page 0: 20 46 5 33 page 1: 12 40 28 17 8 rows tested, 1 matches ((1,3) Piranesi) it cannot stop early: another row could have id 28 too a million rows means a million tests EXPLAIN calls this a Seq Scan
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.