Your query took 2ms for two years. Last month it started taking 4 seconds. The data grew. The index stopped being used. The algorithm did not scale — the query planner changed its mind about it.
Most engineers treat a database index as a switch. Turn it on, queries get fast. Turn it off, queries get slow. That model breaks the moment a query planner decides an index scan is worse than a sequential scan. Understanding when that flip happens requires understanding what a B-tree actually is and what it actually costs.
The concept
A B-tree is a binary search tree redesigned for disk-based storage. It keeps keys sorted. It stays balanced. It answers lookups in O(log N) comparisons. That much is shared with every other balanced tree.
What is different is the node size. A binary search tree stores one key per node. A B-tree stores hundreds of keys per node, sized to match a disk page — typically 8 KB in PostgreSQL. The branching factor jumps from 2 to around 400.
The insight behind that choice: a disk read has a fixed cost regardless of how much data you read within a page boundary. Reading one byte and reading 8 KB take the same time. So the B-tree packs as many keys into each read as the page will hold.
With 400 entries per page and a balanced tree, a table with 400³ rows — 64 million — requires a B-tree of only 3 levels. Three disk reads to find any row in a 64-million-row table. That is why B-trees dominate database indexing.
How it works
Each B-tree node is one page. The page holds a header, an array of item pointers, and the sorted key entries themselves. Internal nodes hold keys and child-page pointers. Leaf nodes hold keys and heap pointers.
A heap pointer is a (block_number, tuple_offset) pair. It tells PostgreSQL where the actual row lives in the table's heap storage. The index stores keys. The heap stores full rows.
An index scan does two things in sequence. First, it searches the B-tree for the key — O(log N) disk reads, one per level. Second, it fetches the heap page the pointer names — one more disk read.
def btree_search(node, key):
result = node.search(key) # binary search within the node
if result:
_, idx = result
return node.children[idx] # leaf: heap pointer
if node.is_leaf:
return None
for i, k in enumerate(node.keys):
if key < k:
return btree_search(node.children[i], key)
return btree_search(node.children[-1], key)
At every level, the number of pages read is one. Tree height is log_order(N). With order 400, height is log₄₀₀(N). For N = 64 million, height is 3.
The B-tree is not a smarter binary search tree. It is a binary search tree rebuilt around a storage medium where the unit of I/O is 8 KB.
The tradeoff
This is AT4 — Precomputation vs On-Demand. The index is precomputed at write time. Every INSERT and every UPDATE that touches an indexed column must update the index. That cost is paid now, on the write path.
The benefit arrives on the read path. A query that would scan the whole table instead walks three levels of tree. A million-row table becomes a three-page read. The write pays. The read wins.
But the win is conditional. The index helps only when the query is selective — when it returns a small fraction of the table. For a query that returns 30% of the rows, the index makes the database fetch 30% of the heap pages through random I/O. A sequential scan reads pages in order. Sequential I/O is 10–100× faster than random I/O on spinning disks. On a low-selectivity query, the sequential scan wins.
PostgreSQL's query planner estimates this ratio from its statistics and picks the plan it thinks is cheaper. The planner is what flips your query from 2ms to 4 seconds. The index did not stop working. The planner stopped choosing it because the data distribution changed.
There is a second tradeoff underneath. AT3 — Simplicity vs Flexibility. A binary search tree is under 100 lines of code. A production B-tree spans thousands. Node splits on insert, node merges on delete, page-level locking, WAL logging, concurrent access — all of that complexity exists to give one property: predictable performance on disk-based storage.
Where it fails
FM5 — Latency Amplification. This is the failure mode that turns a working index into a slow query.
An index lookup that returns one row costs four disk reads: three for the B-tree, one for the heap. An index lookup that returns 100,000 rows costs three B-tree reads and up to 100,000 random heap fetches. Each random fetch is a seek. Seeks do not compose linearly with data size — they compose with latency multipliers.
The query that was fast at 100,000 rows in the table is slow at 100 million rows in the table not because the index grew, but because the number of matching rows grew. The selectivity ratio degraded. The planner switched to a sequential scan, or worse, it did not switch and kept doing random I/O.
There is a second failure mode on the write path. FM3 — Unbounded Resource Consumption through write amplification. Every index on a table multiplies the write cost. A table with five indexes pays five B-tree updates per row inserted. Add an index without accounting for the write path and your INSERT throughput drops.
And there is FM8 — Schema/Contract Violation. A B-tree imposes an ordering on keys. Change the column type from integer to string and the ordering changes. The index must be rebuilt. On a large table this migration takes hours and locks the table. The index's dependence on ordering is a contract between the column type and the tree structure, and changing one side breaks the other.
Real systems
PostgreSQL uses B-trees for its default index type. Each node is 8 KB, packing ~400 entries. The heap and the index are separate storage — the index points to heap tuples through (block, offset) pairs.
MySQL InnoDB uses B+ trees. Data lives only in leaf nodes, and the leaves are linked in a doubly-linked list. That makes range scans cheap — walk the leaves in order rather than re-traversing the tree. The primary key B+ tree is the clustered index; secondary indexes point to the primary key, not directly to the row. A secondary lookup requires two B-tree traversals.
ext4 uses HTree indexes for directories with more than a few entries. Directory entries are hashed and stored in a B-tree-like structure, giving O(log N) lookup per path component.
Different storage media. Same shape.
What this means for your system
Every index decision is a version of AT4. You are choosing to spend write cost now to save read cost later. Three questions determine whether the tradeoff is correct.
What is the selectivity of the queries this index serves? An index on a column where every query returns a single row is worth its write cost. An index on a column where every query returns 40% of the table is not — the planner will refuse to use it and you will pay the write cost anyway.
How many indexes does the table already carry? Each additional index multiplies write cost. A table on the write-heavy path with eight indexes is running eight B-tree updates on every insert. If throughput matters, count the indexes.
What is the growth curve of the data? A query that is fast today because it returns 1% of a small table is not fast tomorrow when it returns 1% of a table 1000× larger — because 1% of 1000× larger is still a large number of random heap fetches. Selectivity is a ratio; the absolute row count still matters for latency.
The signal that tells you this applies
Your query latency jumped between two data volumes without a code change. Your EXPLAIN output changed from Index Scan to Seq Scan. Your INSERT throughput dropped after you added the index that fixed the slow read. Any one of these means the AT4 tradeoff has shifted underneath you.
The B-tree is not the problem. The B-tree is doing exactly what it was designed to do — trade write cost for read cost, and trade log(N) comparisons for log₄₀₀(N) disk reads. The problem is that the planner's estimate of which side of the tradeoff wins depends on statistics you did not maintain, on selectivity you did not measure, and on data growth you did not model.
The question worth asking next: when the planner refuses to use your index, is it wrong, or is your query wrong? Most engineers answer the first. Almost no one checks the second.
The full framework treatment — compression blocks, three-level exercises, and the complete AT/FM mapping — is in Book 2: Algorithm Engineering, Chapter 3 (Tree Patterns Everywhere). Free chapter available at computingseries.com/books/book2.