B-Tree Indexes Explained

Analogy categoryAnalogies

What a B-Tree Index Actually Is

PostgreSQL's default index type is the B-tree (balanced tree), implemented as a self-balancing structure of fixed-size 8KB pages arranged so that every leaf page sits at the same depth from the root. Internal pages hold routing keys that guide a search downward, while leaf pages hold the actual indexed values paired with tuple identifiers (TIDs) pointing back to the heap. Because the tree stays balanced, a lookup on a table with a billion rows still takes only a handful of page reads, typically 3-4 levels deep.

🏏

Cricket analogy: Think of a DRS review tree: the third umpire narrows down from 'was there an edge' to 'ball tracking' to 'final verdict' in a fixed number of steps, just as a B-tree narrows a search from root to leaf in a fixed number of hops regardless of how many deliveries were bowled that season.

Page Splits and Sorted Leaf Chains

Leaf pages are doubly linked so PostgreSQL can walk the index in sorted order without revisiting internal nodes, which is exactly what makes B-trees efficient for ORDER BY and range predicates like BETWEEN or >=. When a leaf page fills up, PostgreSQL performs a page split: it allocates a new page, moves roughly half the entries into it, and inserts a new routing key into the parent. Repeated splits under heavy insert load, especially with random (non-sequential) key values such as UUIDs, can fragment the tree and increase index size relative to the same data inserted in sorted order.

🏏

Cricket analogy: It is like a scorebook running out of lines mid-innings, forcing the scorer to open a fresh page and cross-reference it to the previous one, exactly as a full leaf page splits and links to a new page mid-sequence.

sql

-- Create a standard B-tree index (the default, so USING btree is optional)
CREATE INDEX idx_orders_customer_id ON orders (customer_id);

-- B-tree indexes support equality and range predicates efficiently
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders
WHERE customer_id = 4821
  AND order_date >= '2026-01-01';

-- Multicolumn B-tree: column order matters for which queries can use it
CREATE INDEX idx_orders_customer_date ON orders (customer_id, order_date);

A B-tree index can satisfy an ORDER BY on its leading column(s) without a separate sort step, because leaf pages are already stored in sorted order and linked for forward and backward traversal. This is why 'CREATE INDEX ... (col)' followed by 'ORDER BY col' or 'ORDER BY col DESC' often shows an Index Scan with no explicit Sort node in EXPLAIN output.

What B-Trees Are Not Good At

B-tree indexes excel at equality, range, and sorted-order access on scalar, comparable data types, but they cannot accelerate substring searches like LIKE '%term%', full-text search, or containment queries on arrays and JSONB unless the operator maps to a supported strategy (equality, less-than, greater-than). For those workloads PostgreSQL provides GIN and GiST index types, and for pattern-prefix searches like LIKE 'term%' a B-tree index built with the text_pattern_ops operator class can help under the C locale. Choosing the wrong index type is a common source of unexplained sequential scans in query plans.

🏏

Cricket analogy: It is like using a strict batting-order lineup card to find 'any player who ever hit a six off Bumrah', a query the lineup card was never designed to answer, unlike simply finding who bats at number four.

Do not assume every WHERE clause on an indexed column will use the index. Functions applied to the column, such as WHERE lower(email) = 'a@b.com', prevent a plain B-tree index on email from being used; you need either an expression index on lower(email) or to store the value pre-normalized.

B-tree indexes are PostgreSQL's default and store data in balanced, sorted leaf pages linked for forward/backward traversal.
Lookups take a near-constant number of page reads (typically 3-4) regardless of table size, because tree depth grows logarithmically.
Leaf pages split when full, which can fragment the index under random-order inserts such as UUID primary keys.
B-trees natively support equality, range (<, <=, >, >=, BETWEEN), and ORDER BY on the indexed columns.
They cannot accelerate substring search, full-text search, or JSONB/array containment without specialized operator classes or index types.
Applying a function to an indexed column in a WHERE clause defeats a plain B-tree index unless a matching expression index exists.
EXPLAIN (ANALYZE, BUFFERS) is the primary tool to verify whether a B-tree index is actually being used as intended.