B-tree indexes

A B-tree keeps index entries sorted inside fixed-size pages. Internal pages point down to the next level; leaf pages hold the keys with pointers to rows, and each level is linked to its neighbours, so a range scan finds its first key and then walks along the leaves. When a leaf is full it splits and adds a pointer to its parent, which may split in turn, so the tree stays balanced; in PostgreSQL over 99% of pages are leaves. One structure answers =, <, >, BETWEEN, IN, IS NULL and patterns anchored at the start such as LIKE 'foo%', and returns rows already sorted for ORDER BY.

A composite index on (a, b) sorts by a, then by b, so conditions on the leading columns narrow the search. PostgreSQL 18 added skip scan, which uses such an index for a condition on b alone when a has few distinct values. PostgreSQL 13 began storing duplicate keys once with a list of row pointers, which shrinks indexes on columns with many repeated values.

Where rows live depends on the engine. MySQL’s InnoDB stores each table inside its primary-key B-tree and makes secondary indexes carry the primary key; SQLite’s rowid tables also keep all data in the tree’s leaves. PostgreSQL keeps rows in a separate heap, and all of its indexes, the primary key included, point into it.