How Database Indexes Work: B-Trees, Buffers, and the 46% Rule

You add an index, the endpoint stops timing out, you close the ticket. Nobody measures what happened. That's fine right up until you add the twelfth index to a hot table and writes fall off a cliff, or the planner quietly stops using the index you built and nobody notices for a month.

So let's measure. Everything below was run against PostgreSQL 17.6 (8 KB pages, random_page_cost = 1.1) on one table:

CREATE TABLE users (
  id         bigserial PRIMARY KEY,
  age        int  NOT NULL,          -- 100 distinct values, scattered
  last_name  text NOT NULL,          -- ~20,000 distinct values
  first_name text NOT NULL,          -- ~5,000 distinct values
  is_active  boolean NOT NULL,       -- 80% true
  created_at timestamptz NOT NULL,   -- inserted in order: correlation 1.0
  payload    text NOT NULL
);
-- 1,000,000 rows. Heap: 118 MB, 15,152 pages.

Every number here is either EXPLAIN (ANALYZE, BUFFERS) output from that table or a citation you can click.

Pages are the unit, not rows

A database never reads a row. It reads an 8 KB page (16 KB in InnoDB) and picks the row out of it. That fact explains most of index design.

Scanning the whole table with a filter that matches nothing:

Parallel Seq Scan on users  (actual rows=0 loops=2)
  Filter: (payload = 'zzz'::text)
  Buffers: shared hit=15152

The entire heap. Now one row by primary key:

Index Scan using users_pkey on users  (actual rows=1 loops=1)
  Index Cond: (id = 555555)
  Buffers: shared hit=7

Roughly 2,000:1. Note these are all shared hit — buffer accesses served from RAM, not disk seeks. Saying "four disk reads" when your working set is cached is how people optimise the wrong thing. Count buffers.

This is also why a binary search tree is useless here: one value and two pointers per node means every hop is potentially a different page. A structure built for block storage has to pack hundreds of keys into each page it touches.

Hash indexes: fast, narrow, and fatter than you'd think

A hash index maps a key through a hash function straight to a bucket, so exact-match lookups are O(1). Postgres will genuinely pick one:

Index Scan using users_last_name_hash on users
  Index Cond: (last_name = 'LN00042'::text)
  Buffers: shared hit=51

Then it falls apart. Hashing destroys ordering, so with only the hash index present, WHERE last_name BETWEEN 'LN00042' AND 'LN00090' and ORDER BY last_name LIMIT 10 both fell back to a sequential scan — 15,152 and 15,190 buffers. And the size is the real surprise: that one-column hash index measured 32 MB, against 7,328 kB for the two-column B-tree on (last_name, first_name). You pay 4.5x the space for an index that answers one kind of question.

The B-tree, measured

CREATE INDEX builds a B+ tree: internal pages hold only routing keys, every real pointer lives in a leaf. Postgres calls those routing entries pivot tuples — "All tuples on non-leaf pages and high keys on leaf pages are pivot tuples" (nbtree/README).

Leaves are chained both ways. Postgres adds "a right-link pointer to each page, to the page's right sibling" for the Lehman & Yao concurrency algorithm, and "we also store a 'left sibling' link" for backward scans (same README). That chain is what makes BETWEEN cheap: descend once, then walk sideways.

How fat is a page, really?

The usual hand-wave is "about 500 keys". Measured, on 400,000 rows:

int4 and int8 land identically because index tuples are MAXALIGN-padded to the same width — narrowing a key from bigint to int buys nothing in a Postgres B-tree.

At a fanout of 364, three levels index about 48 million rows and four about 17.6 billion. Cross-checking against descent cost: a point lookup took 3 buffers at 100,000 rows (276 index pages, metapage + root + leaf) and 4 buffers at 1,000,000 rows (2,745 pages, one extra internal level). Trees stay short, and the top levels stay pinned in cache.

Searching inside one page

Once a page is resident, the engine binary-searches its sorted key array:

class BTreeNode<T> {
  public keys: T[] = [];
  public pointers: unknown[] = [];
  constructor(public readonly isLeaf: boolean = false) {}
 
  // Internal page: index of the child pointer to follow.
  // Leaf page: insertion position a range scan should start from.
  // Separator semantics: child i covers keys[i-1] <= k < keys[i].
  descend(target: T): number {
    let lo = 0;
    let hi = this.keys.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.keys[mid] <= target) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
}
 
const assert = (cond: boolean, msg: string) => {
  if (!cond) throw new Error(msg);
};
 
const root = new BTreeNode<number>(false);
root.keys = [42, 89];
root.pointers = ["Page_2", "Page_3", "Page_4"];
 
const route = (k: number) => root.pointers[root.descend(k)];
assert(route(41) === "Page_2", "41 routes left of 42");
assert(route(42) === "Page_3", "42 routes into [42, 89)");
assert(route(88) === "Page_3", "88 routes into [42, 89)");
assert(route(89) === "Page_4", "89 routes into [89, inf)");
 
// A leaf returns a position, not hit/miss — that is what lets a range scan
// start at a key that isn't present in the table.
const leaf = new BTreeNode<number>(true);
leaf.keys = [28, 31, 36];
assert(leaf.descend(30) === 1, "scan past 30 starts at the 31 entry");
 
console.log("all descents correct");

That compiles under tsc --strict and every assertion passes. The leaf returning a position rather than null matters: a lookup that answers "not found" can't start WHERE age BETWEEN 28 AND 50 when 28 doesn't exist.

The number that decides everything: selectivity

Most index articles assert a threshold instead of measuring one. age has 100 distinct values scattered through the heap (pg_stats.correlation = 0.012). Sweeping WHERE age < K:

Read the first row again. Matching 1% of the table still costs 10,011 of a possible 15,152 buffers. The index eliminated 99% of the rows and 34% of the I/O, because 10,000 scattered rows land on roughly 10,000 distinct pages.

The crossover sits at 46% — but that's a property of physical layout, not of indexes. created_at was inserted in order, correlation 1.0, and the same sweep looks nothing alike:

Same engine, same index type, crossover moved from 46% to past 70%, purely because matching rows are physically adjacent.

Index-only scans are conditional

An index-only scan answers a query from the index alone. It's dramatic when it works:

Index Only Scan using users_age on users  (actual rows=10000)
  Index Cond: (age = 42)
  Heap Fetches: 0
  Buffers: shared hit=13

Thirteen buffers instead of 15,152. But visibility information isn't stored in indexes, so Postgres must check the visibility map bit for each candidate row's heap page: "If it's not set, the heap entry must be visited to find out whether it's visible, so no performance advantage is gained over a standard index scan" (§11.9).

Same query, immediately after an UPDATE touched scattered rows:

Index Only Scan using users_age on users  (actual rows=10000)
  Heap Fetches: 486
  Buffers: shared hit=499

13 became 499 — 38x worse, no schema change. After VACUUM it drops straight back to 13 and Heap Fetches: 0. On a write-heavy table this is a plan node you hope for, not one you can count on.

The leftmost prefix rule is MySQL's rule

Given an index on (last_name, first_name), everyone knows the leading-column rule. MySQL's manual states it plainly with this exact example: "the name index is not used for lookups in the following queries: SELECT * FROM test WHERE first_name='John';" (MySQL 8.4 §10.3.6).

PostgreSQL doesn't behave that way. From §11.3: "This index could in principle be used for queries that have constraints on b and/or c with no constraint on a — but the entire index would have to be scanned, so in most cases the planner would prefer a sequential table scan over using the index."

On real data it didn't just could, it did:

-- WHERE last_name = 'LN00042'   (leading column)
Index Only Scan using users_name    Buffers: shared hit=1 read=3      -- 4
 
-- WHERE first_name = 'FN0042'    (trailing column only)
Index Only Scan using users_name    Buffers: shared hit=4 read=909    -- 913

The index is 916 pages, so the trailing-column query scanned essentially all of it and filtered: 228x the leading-column lookup, but still 16x cheaper than a 15,152-buffer table scan, which is why the planner took it.

The precise model is the docs' one: equality on leading columns plus one inequality bound how much of the index is scanned, while conditions on columns to the right "are checked in the index, so they save visits to the table proper, but they do not reduce the portion of the index that has to be scanned." You still want a separate index — you just won't see a seq scan in the plan telling you so.

The write side: splits, HOT, and random keys

Every index taxes writes. When a leaf page fills it splits: allocate a page, move entries, update the parent, possibly cascading to the root.

Splits aren't uniformly 50/50. Postgres biases the split point and caches the rightmost leaf: "We optimize for a common case of insertion of increasing index key values by caching the last page to which this backend inserted the last value, if this page was the rightmost leaf page" (nbtree README). Building the same 400,000-row index two ways:

Sequential keys append to the right edge and split cleanly; the incrementally-grown index is the same size as a freshly built one. Random UUIDs scatter inserts and leave 37% dead space. With the wider key on top, the UUID index is 1.93x the bigint one.

Postgres does not rewrite every index on every update

You'll read that any Postgres UPDATE must touch every secondary index, since MVCC writes a new tuple at a new location. That's been conditionally false since PostgreSQL 8.3, released 2008-02-04, which added heap-only tuples: "With HOT dead tuple space can be automatically reclaimed at the time of INSERT or UPDATE if no changes are made to indexed columns" (8.3 release notes).

Measured on a 200,000-row table with three secondary indexes, updating 10,000 rows:

The non-indexed update produced identical WAL to the same test on a table with zero secondary indexes. Touching an indexed column produced 3.3x the WAL and zero HOT updates. The preconditions are exactly the documented ones: no indexed column changes, and "there is sufficient free space on the page containing the old row" (§65.7). Lower fillfactor on update-heavy tables to keep the second one true.

What Uber actually said

The Postgres-versus-InnoDB comparison usually arrives via Uber's 2016 post, and it usually arrives stretched. What it (Evan Klitzke, 26 July 2016) actually claims:

The architectural difference is real and documented on both sides. In Postgres, "All indexes in PostgreSQL are secondary indexes" (§11.9) — every entry points at a physical heap location. InnoDB clusters the table on the primary key, and "each record in a secondary index contains the primary key columns for the row... InnoDB uses this primary key value to search for the row in the clustered index" (MySQL 8.4 §17.6.2.1). I have no MySQL instance here, so that half is cited, not measured.

Three qualifiers the retellings drop:

• Uber scoped it explicitly: "the analysis that we present here is primarily based on our experience with the somewhat old Postgres 9.2 release series." 9.2 shipped in 2012.
• Write amplification was one of five listed limitations, alongside inefficient replication, a 9.2 corruption bug, poor replica MVCC, and brutal major-version upgrades.
• Uber concedes the trade runs both ways: "InnoDB is at a slight disadvantage to Postgres when doing a secondary key lookup, since two indexes must be searched with InnoDB compared to just one for Postgres."

They also didn't simply switch to MySQL — they built Schemaless, a sharding layer on top of it, kept legacy Postgres instances, and used Cassandra elsewhere. It's a workload-specific decision from a decade ago, not a verdict.

Test yourself

A checklist you can run today

1. Read buffers, not milliseconds, in EXPLAIN (ANALYZE, BUFFERS). Milliseconds lie about cache state.
2. Check SELECT attname, correlation FROM pg_stats WHERE tablename = '...' before assuming an index helps a range query.
3. Index Only Scan with non-zero Heap Fetches is a vacuum problem, not an index problem.
4. Never wrap the indexed column in a function. WHERE date_part('year', created_at) = 2020 cost 10,011 buffers against 1,445 for the equivalent range predicate. (YEAR() is MySQL syntax; Postgres errors with function year(timestamp with time zone) does not exist.) Rewrite to a range, or build an index on the expression if it's IMMUTABLE.
5. On update-heavy tables, keep churning columns out of indexes and lower fillfactor so HOT keeps working.
6. Drop indexes with zero idx_scan in pg_stat_user_indexes. Each one taxes every write.

The tree is short, the pages are fat, and the planner is doing arithmetic you can reproduce in ten minutes. Go run it on your own table — your crossover point will not be 46%.