A key chooses one drawer.
Why can an index skip most records?
Why can an index skip most records?
Fit the rack, leaf drawers and records.
A balanced search tree uses separators to choose a small leaf page. In this cabinet, any key needs one root and one leaf page; the full scan examines records until it finds a match or reaches the end. Missing keys return no record. The counts describe this fixed tree, not a universal database speedup.
A fixed balanced two-level B+ tree over keys 1–16, with root separators 5, 9 and 13 and four leaves of four keys. Leaf records contain payload key × 10 + 3. Separator and leaf searches are explicitly linear within each page. Page reads and key comparisons are separate counts. This teaching cabinet is not a running PostgreSQL database; heap fetches, MVCC, cache state and mutations are omitted.
Find key 14 through two index pages using fewer comparisons than a full scan.
Compare indexed lookup with a full scan.