Database Indexing: The B-Tree You Rely On

An index is often introduced as a book’s table of contents: extra structure that lets a database find a row without reading the whole table. The analogy is useful, but it hides the engineering. A PostgreSQL B-tree is not a dictionary floating beside the data. It is a concurrent, page-oriented data structure that must remain balanced while transactions insert, update, delete, roll back, and read old row versions.

That distinction matters. An index can turn a selective lookup from milliseconds of scanning into a few page reads, but every index also consumes cache, produces write amplification, and gives the planner another access path to evaluate. The right question is not “Should this column be indexed?” It is “Which access pattern deserves an ordered copy of these keys, and will its read savings repay the write and maintenance cost?”

PostgreSQL’s default CREATE INDEX method is B-tree because ordered keys answer an unusually broad set of questions: equality, ranges, prefix ordering, minimum and maximum, and ordered pagination. Understanding the pages below those operations makes index design much less mysterious.

Pages, fanout, and why trees stay shallow #

PostgreSQL reads and writes fixed-size blocks, normally 8 KiB. A B-tree stores many sorted key-pointer pairs in each page rather than one key per node. Internal pages direct a search toward child pages; leaf pages contain index tuples that refer to heap tuple locations. Sibling links connect leaves so a range scan can continue horizontally after finding its starting point.

If a page has usable payload $P$ bytes and an average separator plus child pointer costs $K$ bytes, a rough fanout is:

For $N$ indexed entries, the idealized height is:

The labels $F$, $P$, $K$, $N$, and $H$ are deliberately simple: fanout, page payload, key cost, entry count, and height. If an internal page can direct searches to 300 children, even hundreds of millions of entries need only a few levels. The upper pages are also small and frequently cached, so a lookup often performs one or two uncached reads rather than one I/O per conceptual comparison.

Search within a page is itself a binary search over separators. A simplified traversal can be expressed without PostgreSQL’s concurrency and buffer-management machinery:

type InternalPage = {
  kind: 'internal';
  separators: number[];
  children: Page[];
};

type LeafPage = {
  kind: 'leaf';
  entries: Array<{ key: number; rowId: string }>;
  next?: LeafPage;
};

type Page = InternalPage | LeafPage;

function lowerBound(values: number[], target: number): number {
  let low = 0;
  let high = values.length;
  while (low < high) {
    const middle = Math.floor((low + high) / 2);
    if (values[middle]! < target) low = middle + 1;
    else high = middle;
  }
  return low;
}

function findLeaf(root: Page, key: number): LeafPage {
  let page = root;
  while (page.kind === 'internal') {
    const childIndex = lowerBound(page.separators, key);
    page = page.children[childIndex]!;
  }
  return page;
}

When a leaf no longer has room, an insertion allocates a sibling, redistributes entries, and promotes a separator to the parent. A full parent can split recursively; a split root creates a new root and increases height by one.

function splitLeaf(full: LeafPage): { left: LeafPage; separator: number; right: LeafPage } {
  const middle = Math.ceil(full.entries.length / 2);
  const left: LeafPage = { kind: 'leaf', entries: full.entries.slice(0, middle) };
  const right: LeafPage = {
    kind: 'leaf',
    entries: full.entries.slice(middle),
    next: full.next,
  };
  left.next = right;
  return { left, separator: right.entries[0]!.key, right };
}

Real implementations use latches, write-ahead logging, high keys, deduplication, and careful split protocols. The simplified algorithm exposes the invariant that matters: every page is ordered, every child covers a key interval, and all leaves remain at the same depth.

Lookup, range, and order are one capability #

Because leaf entries are sorted, one structure supports several operators. PostgreSQL B-trees handle =, <, <=, >=, >, and ordered operations such as BETWEEN or ORDER BY. Equality descends to one leaf. A range descends once to its lower bound, then walks adjacent leaves until the upper bound. An ordered query can read entries in index order and avoid a separate sort.

CREATE TABLE orders (
  id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id bigint NOT NULL,
  status text NOT NULL,
  total_cents integer NOT NULL CHECK (total_cents >= 0),
  created_at timestamptz NOT NULL DEFAULT now()
);

CREATE INDEX orders_created_at_idx ON orders (created_at);

-- Point/range start: descend, then move through neighboring leaves.
SELECT id, customer_id, total_cents, created_at
FROM orders
WHERE created_at >= timestamptz '2025-03-01 00:00:00+00'
  AND created_at <  timestamptz '2025-04-01 00:00:00+00'
ORDER BY created_at;

-- The same ordering makes the newest rows cheap to locate.
SELECT id, created_at
FROM orders
ORDER BY created_at DESC
LIMIT 50;

An index does not guarantee that PostgreSQL will use it. If March contains most of the table, a sequential scan may be cheaper than following thousands of index pointers to heap pages. The index identifies candidate tuple locations; unless an index-only scan is possible, PostgreSQL still visits the heap to fetch columns and check visibility.

Composite and covering indexes follow query shape #

A multicolumn B-tree is sorted lexicographically. An index on (customer_id, created_at) first groups by customer, then orders each customer’s rows by time. This matches a common history query exactly:

CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at DESC);

SELECT id, status, total_cents, created_at
FROM orders
WHERE customer_id = 42017
  AND created_at < timestamptz '2025-03-28 12:00:00+00'
ORDER BY created_at DESC
LIMIT 25;

The leading-column rule follows directly from lexicographic order. The index efficiently narrows customer_id = 42017, then scans a time interval. It can also help WHERE customer_id = 42017 alone. It is generally poor for WHERE created_at >= ... across every customer because timestamps are scattered among customer groups.

Column order should therefore reflect predicates, ordering, and cardinality together. Put equality-constrained columns before range columns in the usual case; once a scan enters a broad range on an earlier column, later columns often filter entries rather than narrow the contiguous interval.

PostgreSQL’s INCLUDE stores payload columns in leaf tuples without making them search keys. That can create a covering index for a stable, frequent query:

CREATE INDEX orders_customer_created_cover_idx
  ON orders (customer_id, created_at DESC)
  INCLUDE (status, total_cents);

EXPLAIN (ANALYZE, BUFFERS)
SELECT created_at, status, total_cents
FROM orders
WHERE customer_id = 42017
ORDER BY created_at DESC
LIMIT 25;

If the heap pages are marked all-visible in the visibility map, PostgreSQL may choose Index Only Scan and return these columns without heap fetches. “Covering” is thus necessary but not sufficient: recently modified pages may still require heap visibility checks.

Partial and expression indexes let the physical structure match an even narrower access pattern:

CREATE INDEX orders_open_customer_idx
  ON orders (customer_id, created_at DESC)
  INCLUDE (total_cents)
  WHERE status IN ('pending', 'processing');

CREATE INDEX users_lower_email_idx ON users (lower(email));

SELECT id FROM users WHERE lower(email) = lower('Ada@example.com');

The query predicate must imply the partial-index predicate, and an expression query must use the indexed expression. These indexes save space and writes when the subset is genuinely the one applications read.

Selectivity and the planner’s cost model #

Selectivity is the fraction of rows expected to survive a predicate. A unique identifier is highly selective; a boolean flag often is not. PostgreSQL’s planner estimates row counts from statistics built by ANALYZE: null fractions, distinct-value estimates, most-common values, and histograms. It combines those estimates with costs for sequential pages, random pages, CPU comparisons, and expected heap visits.

ANALYZE orders;

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT id, total_cents
FROM orders
WHERE customer_id = 42017
  AND created_at >= now() - interval '30 days';

Read the plan from the executed node upward. Compare rows= estimates with actual rows=, and inspect shared buffer hits versus reads. A large estimate error is evidence, not a command to disable sequential scans. Data may be skewed, statistics may be stale, or predicates on correlated columns may be treated as more independent than they are.

-- Give a skewed column a larger statistics sample.
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 1000;

-- Teach the planner that status and customer_id may be correlated.
CREATE STATISTICS orders_customer_status_stats (dependencies, mcv)
  ON customer_id, status
  FROM orders;

ANALYZE orders;

Parameterization adds another wrinkle. PostgreSQL may use a custom plan based on a supplied value for early executions, then choose a reusable generic plan. That generic plan can be bad when one tenant has half the rows and most tenants have dozens. Diagnose the estimate and distribution before forcing planner settings; often better statistics or a different query boundary addresses the cause.

MVCC, write amplification, and maintenance #

PostgreSQL uses multi-version concurrency control. An UPDATE normally creates a new heap tuple version instead of overwriting the old one. Every affected index may need a new entry, while the old entry remains until vacuum can determine that no transaction needs it. This is why a read-optimized collection of indexes can become a write bottleneck.

The cost of one logical write includes heap work, one operation per relevant index, possible page splits, write-ahead log records, dirty buffers, later vacuuming, and replication traffic. Wide keys and INCLUDE payloads reduce fanout and increase this amplification. Random key insertion tends to touch pages across the index; monotonically increasing keys concentrate inserts on the rightmost leaf, improving locality but creating a hot page under intense concurrency.

PostgreSQL can perform a heap-only tuple (HOT) update when no indexed column changes and the new tuple version fits on the same heap page. HOT avoids adding entries to every index. Adding an index to a frequently changed column can quietly remove that optimization.

SELECT
  schemaname,
  relname,
  indexrelname,
  idx_scan,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

SELECT
  relname,
  n_tup_upd,
  n_tup_hot_upd,
  n_dead_tup,
  last_autovacuum,
  last_autoanalyze
FROM pg_stat_user_tables
WHERE relname = 'orders';

Autovacuum removes dead index tuples when safe, updates visibility information, and triggers statistics work. Routine VACUUM (ANALYZE) is not the same as rebuilding an index. Bloat can persist after churn because freed space is reusable inside the relation but not necessarily returned to the operating system. REINDEX CONCURRENTLY can rebuild a damaged or badly bloated index while allowing normal writes, at the cost of extra time, disk, and work.

Fillfactor reserves page space to reduce splits for update-heavy or non-monotonic workloads, but lower fillfactor makes the index larger immediately. Treat it as a measured tuning control, not a ritual setting.

Failure modes and alternatives #

The most common indexing failure is redundancy: separate (customer_id) and (customer_id, created_at) indexes may duplicate the same leading-key capability. Another is indexing low-selectivity columns without a partial predicate. A third is building a giant covering index for one query and then paying to rewrite it on every status change.

Other traps include implicit casts or functions that do not match the indexed expression, leading-wildcard searches such as LIKE '%tree%', and keyset problems disguised as offset pagination. OFFSET 100000 still asks the executor to walk past 100,000 entries. Seek pagination uses the ordered key instead:

SELECT id, created_at
FROM orders
WHERE (created_at, id) < (
  timestamptz '2025-03-28 12:00:00+00',
  900000
)
ORDER BY created_at DESC, id DESC
LIMIT 50;

CREATE INDEX orders_seek_idx ON orders (created_at DESC, id DESC);

B-tree is a default, not a universal winner:

Failure can also be operational. A CREATE INDEX without CONCURRENTLY blocks writes while building; the concurrent form reduces blocking but takes longer, performs more work, and cannot run inside a transaction block. Unique-index creation can fail on existing duplicates. Corruption is uncommon, but hardware faults and collation changes can require reindexing. An index is durable state, so its lifecycle belongs in migrations, monitoring, capacity planning, and recovery exercises.

Takeaways #

A B-tree is fast because each fixed-size page stores many ordered separators. High fanout keeps height low; linked leaves turn the same descent used for equality into efficient range and ordered scans. Composite order, partial predicates, expressions, and included columns are physical decisions derived from actual query shapes.

The planner still chooses based on estimated selectivity and I/O cost, and MVCC means an index hit may require a heap visibility check. Every extra access path also amplifies writes, consumes cache, interacts with HOT updates, and creates vacuum or rebuild work. Measure with EXPLAIN (ANALYZE, BUFFERS) and statistics views, keep indexes that repay their cost, and choose GIN, BRIN, GiST, or a sequential scan when ordered scalar keys are not the real problem.