The Data Structure Behind Every Database Index: B-Trees

Every database index you've used is probably a B+ tree — a wide, shallow tree where each node fills one disk page. With a fanout of ~400 keys per 8 KB page, a Postgres btree index stays just 3 levels tall for tens of millions of rows. That's 3 page reads to find any key, compared to 23 with a binary search tree.

Internal nodes hold only separator keys for routing; all actual data pointers live in the leaf pages, which are linked together as a doubly-linked list. This linked-leaf structure is what makes range scans and ORDER BY cheap — once you find the first match, you follow forward pointers sequentially without re-traversing the tree.

The post covers page splits, key promotion, fill factor, and why random UUIDv4 primary keys cause index fragmentation while UUIDv7 and ULID keep inserts appending to the right edge. Pick your key shape deliberately — the B+ tree rewards sequential patterns.