Database Indexing: How B-Trees Work (Postgres/MySQL)

Q: What is a B-tree index and why do databases use it?

A B-tree is a sorted, balanced tree with very high fan-out: each node is one disk page (8KB in Postgres, 16KB in InnoDB) holding hundreds of keys in sorted order, and each key in an internal node points to a child covering a narrower key range. Three properties make it the default index in essentially every relational database for four decades. First, sorted order means one structure answers both equality lookups and range queries — WHERE id = ?, WHERE created_at BETWEEN, and ORDER BY all descend the same tree. Second, balance guarantees every leaf sits at the same depth, so worst-case lookup cost equals average-case — no degenerate slow paths. Third, and decisively, the fan-out: branching hundreds of ways per level keeps the tree extraordinarily shallow — three levels cover ten million rows, four cover a billion — and because the root and second level are hot, they live permanently in RAM, so a lookup typically costs one or two physical reads regardless of table size. That logarithmic-with-huge-base behaviour, aligned exactly with page-based storage, is why the answer to "which index type" is B-tree unless you have a specific reason (text search, vectors, geospatial) to reach for a specialist structure.

Q: What is the leftmost-prefix rule for composite indexes?

A composite index on (a, b, c) is a single B-tree sorted by a first, then b within equal a, then c within equal (a, b) — like a phone book sorted by last name, then first name. The consequence: the index serves any query that constrains a leftmost prefix of those columns — a alone, a and b, or all three — but is useless for queries constraining only b, only c, or (b, c), because rows with a given b value are scattered throughout the tree just as people with the first name "Maria" are scattered through a phone book. This is the most common indexing misunderstanding in practice: a team indexes (tenant_id, created_at), later ships a cross-tenant report filtering only created_at, and is baffled that the query scans. Design rules that follow: order columns by how queries actually filter, not alphabetically; put equality-tested columns before range-tested ones (equality on tenant_id then range on created_at lets the tree narrow to one tenant then scan a contiguous date stripe); and when two query shapes need incompatible orders, that is two indexes, not one compromise index. In multi-tenant systems the rule has an architectural corollary: tenant_id leads nearly every index, which is precisely what makes per-tenant queries fast and cross-tenant leaks visible in review.

Q: Why is my database not using my index?

Three causes account for nearly every case, and EXPLAIN distinguishes them in seconds. First, low selectivity: if the filter matches a large fraction of the table — WHERE status = 'active' hitting 90 percent of rows — the planner correctly chooses a sequential scan, because reading pages in order is cheaper than millions of random index probes plus heap fetches; the index is not broken, the query genuinely does not benefit from one. Second, a function or cast wrapping the indexed column: WHERE LOWER(email) = ? cannot use an index on email, because the tree stores email values, not LOWER(email) values — the fix is an expression index on LOWER(email), or normalizing case at write time; the same trap hides in date functions (DATE(created_at) = ?) and implicit type casts (comparing a text column to a number). Third, the leftmost-prefix rule: a composite index whose leading column is not constrained by the query cannot be descended. A fourth, subtler case: the index IS used but the query is still slow because every match requires a heap fetch — visible in EXPLAIN as index scan plus high buffer reads — and the cure is a covering index. The meta-rule: never debug from folklore; EXPLAIN ANALYZE shows the plan the database actually chose, its cost reasoning, and the real row counts.

Q: What is a covering index and an index-only scan?

A covering index contains every column a query needs, allowing the database to answer entirely from the index without touching the table — an index-only scan. Normally an index lookup is two steps: descend the B-tree to find matching entries, then fetch each full row from the table heap (in Postgres) or via the clustered tree (InnoDB) to get the other columns. Those heap fetches are random I/O and dominate the cost of wide result sets. If a hot query is "latest 20 orders for a tenant, returning id, status, and total," a covering index on (tenant_id, created_at) INCLUDE (id, status, total) — Postgres syntax; in MySQL you simply widen the composite — lets the database descend to the tenant's date range and read everything from contiguous leaf pages, routinely turning a 50ms query into 2ms. The trade-offs are honest: the index gets physically larger (it stores those extra columns), every write to the covered columns must update it, and Postgres index-only scans additionally depend on the visibility map being current (a heavily-updated table may still incur heap checks until vacuum catches up). The discipline: cover only the genuinely hot list-style queries — a few deliberately fat indexes on the paths users hammer, not INCLUDE-everything sprawl.

Q: How many indexes are too many on one table?

There is no magic number, but there is a hard trade to price: every index is a complete second copy of the indexed columns that every INSERT must add to and many UPDATEs must maintain, so a table with eight indexes performs nine physical writes per inserted row, holds nine structures hot in the buffer cache, and pays the tax on every single write forever. Read-heavy tables with stable rows (a product catalog) can happily carry many indexes; write-heavy tables (events, logs, queue-like tables) should carry the minimum that their read paths genuinely require. The empirical approach beats the philosophical one: both major databases expose per-index usage statistics (pg_stat_user_indexes in Postgres, sys.schema_unused_indexes in MySQL), and a quarterly review that drops never-scanned indexes is pure win — an unused index costs write amplification, cache space, and vacuum/maintenance time while returning nothing. Watch for redundancy too: an index on (a) is subsumed by one on (a, b) for most purposes and can usually be dropped. And remember the InnoDB-specific multiplier: every secondary index stores the primary key in its leaves, so a fat primary key (a random string UUID, say) silently fattens every index on the table — compact or ordered keys keep the whole estate lean.

Q: What is the difference between clustered and non-clustered indexes?

The distinction is where the actual row data lives. In a clustered index, the table IS the index: rows are physically stored in the leaf pages of the primary-key B-tree, in primary-key order. MySQL/InnoDB works exactly this way — every table is a clustered index on its primary key — so a primary-key lookup lands directly on the row with no second hop, and range scans over the primary key read physically contiguous data. The costs: secondary indexes cannot point to a physical location (rows move as the tree rebalances), so their leaves store the primary-key value instead, making every secondary-index lookup a two-tree operation (descend the secondary, then descend the primary with the found key) and making fat primary keys expensive estate-wide. Postgres takes the other design: tables are heaps — rows live in unordered heap pages — and every index, including the primary key's, is a separate structure whose leaves point into the heap. Lookups always cost index-descent plus heap fetch, no index is privileged, and there is no clustered ordering to exploit (CLUSTER exists but is a one-time physical sort, not maintained). Practical consequences: on InnoDB, choose compact, monotonic primary keys and exploit PK-order range scans; on Postgres, lean on covering indexes to skip heap fetches, and mind the visibility map for index-only scans.

Q: Do indexes slow down writes, and by how much?

Yes, mechanically and measurably. Every INSERT must add an entry to every index on the table: descend each B-tree, place the key in the correct leaf, and occasionally split a full page — so a table with one primary key and seven secondary indexes turns one logical insert into roughly nine physical write operations plus their WAL/redo logging. UPDATEs pay per index whose columns changed (Postgres adds a wrinkle: unless the update qualifies for HOT — heap-only tuples, possible only when no indexed column changed and the page has room — it writes a new row version and updates every index). DELETEs mark entries dead and defer cleanup to vacuum/purge, which the indexes also enlarge. The magnitude in practice: each additional index typically costs a few percent to tens of percent of write throughput depending on key randomness (random UUIDs cause page splits and cache misses; monotonic keys append neatly), row width, and cache pressure — and on bulk loads the effect is dramatic, which is why the standard pattern is dropping secondary indexes before a mass import and rebuilding after. The operational rules: budget write amplification when adding "just one more" index to a hot table, prefer ordered keys where insert volume is high, and audit usage stats so the tax is only paid on indexes that earn it.

Q: When should I use something other than a B-tree index?

When the query shape is not "ordered scalar comparison," the B-tree stops being the right tree, and the families diverge by workload. Text search — "find documents containing these words" — belongs to inverted indexes (GIN in Postgres, or a dedicated engine like Elasticsearch): a B-tree can only match string prefixes, which is why LIKE with a leading wildcard cannot use one, while trigram GIN indexes handle substring matching. Semantic similarity over embeddings belongs to vector indexes — HNSW and IVF, via pgvector or a dedicated store — because "nearest neighbours in 768-dimensional space" has no sorted order a B-tree could exploit. Geospatial containment and proximity use GiST/R-tree structures that index bounding regions. Postgres GIN also serves JSONB containment and array-membership queries — common in event and config tables. Hash indexes answer only pure equality, saving a little depth over B-trees in narrow cases; BRIN indexes suit huge append-only tables where values correlate with physical position (timestamps in a log), costing kilobytes where a B-tree would cost gigabytes, at the price of coarse filtering. The unifying principle across all of them: an index is a data structure whose shape matches a query shape — B-trees for order, inverted for tokens, HNSW for proximity — and the failure mode is always the same, demanding answers from a structure whose geometry cannot provide them.