Indexes

Indexes

An index is a secondary, sorted data structure — almost always a B+tree — that lets the engine find a row by binary-descending a shallow, high-fanout tree in O(log n) page reads instead of scanning every row in O(n); the trade is that every write must now update the table and each index, so you buy fast reads with slower writes and extra disk.

The naive picture — "an index is a pointer to the data" — is true but useless: it explains nothing about why a lookup gets faster. The real answer is the tree's fanout. A disk page is ~8 KB; pack a few hundred keys into each internal node and the tree's height stays tiny even for billions of rows, so a point lookup touches only a handful of pages.

Why the tree is so shallow: fanout beats a balanced binary tree

A binary search tree branches 2 ways per node, so 1 billion keys need a height of log₂(10⁹) ≈ 30 — 30 pointer-chases, each a potential random disk seek. A B+tree branches by how many keys fit on a page. With ~400 keys per 8 KB node the fanout is ~400, so height is log₄₀₀(10⁹) ≈ 3.4, i.e. 4 levels. Same billion rows, ~4 page reads instead of 30. That gap — chosen specifically because disk seeks dominate — is the whole reason databases use B+trees rather than the binary trees you learned in DSA.

Two structural facts make the B+plus tree (the variant nearly every RDBMS ships) ideal for SQL:

• Only leaf nodes hold the actual keys + row pointers. Internal nodes are pure routing (separator keys only), so they pack more entries and the tree stays shorter.
• Leaves are linked left-to-right in sorted order. Once you descend to the start of a range, a BETWEEN / ORDER BY / > query just walks the leaf chain sequentially — no re-descending the tree per row. This is why one index serves equality, range, and sort.

Worked example: tracing one lookup

Take a users table with 1,000,000 rows and an index on id. Pages hold ~400 entries, so the B+tree is 3 levels deep (400³ = 64M > 1M). Run:

SELECT name FROM users WHERE id = 57;

Without the index the engine does a sequential scan: read every page of the table, test id = 57 on each row, ~2,500 page reads (1M rows / 400 per page) until it finds the match — worst case the whole table. With the index it does an index scan:

That is ~4 page reads versus ~2,500 — a ~600× reduction in I/O, and it barely grows as the table grows (a 1-billion-row table is still only 4–5 reads). Step 4 — the jump from the index back to the table to fetch non-indexed columns — is the heap fetch, and it matters for the next idea.

"Clustered vs non-clustered" is a storage choice, not a universal taxonomy

The original page called clustered and non-clustered "the two main types" of index. That is a SQL Server / MySQL-InnoDB framing and is misleading elsewhere. The real distinction is where the row's data lives relative to the index:

• Clustered (index-organized): the table's rows are stored in the leaf nodes of the index, physically sorted by the key. There can be only one (you can only sort the rows one way). The leaf is the row, so there is no separate heap fetch. InnoDB makes the primary key clustered automatically; SQL Server lets you choose.
• Non-clustered (secondary): a separate tree whose leaves hold the key plus a pointer back to the row (a heap row-id, or in InnoDB the clustered key). Reaching non-indexed columns needs the extra heap fetch from step 4 above. A table can have many of these.

PostgreSQL has no clustered index at all. Every table is a heap (unordered), and every index — including the primary key — is a secondary B-tree pointing into that heap via a ctid. Its CLUSTER command is a one-time physical re-sort, not a maintained clustered index. So treat clustered/non-clustered as "how this specific engine stores rows," not as the definition of an index. Other index structures coexist: hash (equality only, no ranges), GiST/GIN (geometric, full-text, JSON), LSM-trees (RocksDB, Cassandra — write-optimized, the opposite trade from B+trees).

The write side: index maintenance and write amplification

Reads are only half the bargain. Every INSERT, UPDATE of an indexed column, or DELETE must keep the trees consistent. Insert one row into a table with 4 indexes and the engine performs 5 writes: the row itself plus one entry in each index tree. This is write amplification. Worse, those index writes land at scattered key positions, so they are random I/O, and when a leaf page fills it must split — allocate a new page, move half the keys, fix parent pointers. A table over-indexed "just in case" can have its write throughput cut by 3–5× for indexes the read path never uses.

Pitfalls

• Function/expression on the indexed column kills the index. WHERE LOWER(email) = 'a@b.com' or WHERE created_at::date = '2026-06-29' can't use a plain index on email/created_at — the engine would have to transform every row first, so it falls back to a full scan. Fix: index the expression (CREATE INDEX ON users (LOWER(email))) or rewrite to a sargable range (created_at >= '2026-06-29' AND created_at < '2026-06-30').
• Low cardinality → the planner ignores the index. An index on a boolean or status with 3 values is often slower than a scan: matching half the rows via random heap fetches beats one sequential pass. The optimizer correctly skips it — adding the index just slows writes for nothing.
• Leading-column rule on composite indexes. An index on (last_name, first_name) accelerates WHERE last_name = 'Lee' and WHERE last_name='Lee' AND first_name='Sam', but not WHERE first_name='Sam' alone — you can't start a tree descent from the middle of the sort key.
• Implicit type mismatch. An indexed varchar column compared to an integer literal (WHERE phone = 5551234) forces a cast on every row and bypasses the index. Quote it.
• Over-indexing. Each index costs disk and the write amplification above. Index for queries you actually run; drop indexes that pg_stat_user_indexes / sys.dm_db_index_usage_stats show are never scanned.
• Always read the plan. Don't assume an index is used — run EXPLAIN (ANALYZE) and confirm you see Index Scan, not Seq Scan.

Takeaways

• An index is a sorted B+tree; the speedup comes from high fanout shrinking height to O(log n) page reads (~4 for a billion rows), not from "being a pointer."
• It's a read/write trade: fast lookups in exchange for write amplification (one extra write per index per row) and disk. Index deliberately, not defensively.
• Clustered vs non-clustered is an engine storage detail (clustered = rows live in the leaf, one per table; non-clustered = separate tree + heap fetch). PostgreSQL has only the heap + secondary indexes — never present it as the universal taxonomy.
• An index helps only if the query is sargable and respects the leading column; verify with EXPLAIN ANALYZE rather than trusting that CREATE INDEX was enough.

Sources: Ramakrishnan & Gehrke, Database Management Systems (3rd ed., B+tree chapters); Garcia-Molina, Ullman & Widom, Database Systems: The Complete Book; PostgreSQL documentation (Indexes; Index Types; EXPLAIN); MySQL 8.0 Reference Manual (InnoDB clustered/secondary indexes, B-tree); Microsoft SQL Server docs (Clustered and Nonclustered Index Design); Markus Winand, Use The Index, Luke! (sargability and leading-column rule). Re-authored and deepened for this guide — added the B+tree mechanism, fanout math, a traced index-vs-sequential-scan example, write-amplification, and corrected the misleading "clustered/non-clustered are the two universal types" framing.

🎯 STRICT STANDOUT: Why / worked / when-not / failure / drills — Indexes

Why this concept exists (judgment chain)

Indexes buy O(log n) lookups via high-fanout B+trees and pay write amplification. Clustered vs heap is engine storage, not universal taxonomy. Sargability and leading-column rules decide whether CREATE INDEX helps at all.

Worked example with numbers or traced steps

Fanout ~400 keys/8KB page: log_400(1e9) ≈ 4 levels vs log2 ≈ 30.
1M-row users: seq scan ~2500 pages; index id=57 ≈ 4 page reads.
4 secondary indexes → each INSERT does 1 heap + 4 index writes.
WHERE LOWER(email)=… misses plain index → expression index or rewrite.
Composite (last, first) helps last=? but not first=? alone.
PG: all indexes secondary into heap; InnoDB PK is clustered.

When NOT to use / named alternative

Do not index low-cardinality flags “just in case.” Do not wrap indexed columns in functions in WHERE. Drop unused indexes (write tax). Prefer covering/include indexes only for proven hot queries. Hash indexes only for pure equality where supported.

Failure / ops fingerprint

Fingerprint: Seq Scan despite index (non-sargable or bad stats); write latency rises after “add 12 indexes”; bloat from churn. Ops: EXPLAIN (ANALYZE); pg_stat_user_indexes; periodic REINDEX/VACUUM; review leading columns against query shapes.

Hostile-panel drills (defend the decision)

Q1. Why B+tree not binary tree on disk?
Model answer: High fanout packs hundreds of keys per page → height 3–4 for billions; binary tree height ~30 random seeks.

Q2. Clustered index in PostgreSQL?
Model answer: No maintained clustered index; heap + secondary indexes. CLUSTER is one-time reorder.

Q3. Leading-column rule?
Model answer: Composite index (a,b) usable for a and a+b predicates; not for b alone — descent needs leading key.