Indexes

An index is a second copy of one or more columns kept in a sorted, high-fanout balanced tree (almost always a B+tree) that sits beside the table; because the keys are sorted, the database finds a row by making a handful of comparisons that halve the search space each step — roughly log(n) node visits — instead of reading every row. That single structural fact is the whole story: reads get cheap because the data is ordered, and writes get more expensive because that order must be maintained on every insert, update, and delete.

Why a sorted structure wins: the numbers

Take a books table with 1,000,000 rows and a query WHERE id = 42. Without an index the engine does a full table scan: it reads rows one by one until it finds 42 (or reaches the end to prove there is no more). That is O(n) — on average 500,000 row reads, worst case 1,000,000.

A B+tree index on id stores those keys sorted and packed into fat nodes. A realistic node (one disk page, ~8 KB) holds on the order of 100+ keys, so the tree fans out by ~100 at every level. That means:

• 1 level indexes ~100 keys
• 2 levels index ~100 × 100 = 10,000 keys
• 3 levels index ~100 × 100 × 100 = 1,000,000 keys

So a million-row table needs a tree only 3 levels deep. A lookup touches 3 nodes — root, internal, leaf — then one pointer to the row. That is O(log n), and because the fanout is ~100 (not 2), the base of the log is huge and the height barely grows: a billion rows is still only ~5 levels. The comparison, per point lookup:

Tracing one lookup

Suppose the B+tree on id looks like the diagram below and we run SELECT * FROM books WHERE id = 42. The traversal:

1. Root holds separator keys [30 | 60]. Compare 42: since 30 ≤ 42 < 60, follow the middle pointer.
2. Leaf node [30, 42, 55]: binary-search within the node, land on 42.
3. The leaf entry for 42 carries a row pointer (a primary-key value or a physical page/row id). Follow it once to read the full row.

Three comparisons plus one fetch instead of scanning ~500,000 rows. And because leaves are chained left-to-right, a range query like WHERE id BETWEEN 42 AND 90 finds 42 the same way, then walks the leaf chain — no re-descending the tree per row. That leaf ordering is exactly why a B+tree also accelerates ORDER BY, >/<, and prefix matches, not just equality.

Composite indexes and the leftmost-prefix rule

An index on multiple columns, e.g. INDEX (last_name, first_name), sorts by last_name first, then first_name within each last name — like a phone book. This means the index only helps a query if it uses a leftmost prefix of the key columns:

• WHERE last_name = 'Kumar' → uses the index (contiguous slice).
• WHERE last_name = 'Kumar' AND first_name = 'Mathan' → uses the index fully.
• WHERE first_name = 'Mathan' alone → cannot use it — first names are scattered across every last name, exactly as you can't find everyone named "Mathan" in a phone book without scanning it all. You would need a separate index leading with first_name.

A related lever is the covering index: if the index already contains every column the query returns, the engine answers from the index alone (an index-only scan) and skips the second hop to the table row entirely. INDEX (last_name, first_name) covers SELECT first_name WHERE last_name = 'Kumar' — no row fetch needed. A complementary lever is the partial index (Postgres) / filtered index (SQL Server): index only the rows matching a predicate — e.g. CREATE INDEX ... WHERE status = 'ACTIVE' — so a small hot subset of a huge table gets a tiny, cheap-to-maintain index instead of one spanning every dead row.

Pitfalls

• Write amplification and node splits. Every insert/update/delete must also update each affected index, and when a leaf page fills, the B+tree splits it — extra I/O and, under load, page-lock contention. Ten indexes on a hot table means each write does eleven writes.
• Functions, type mismatches, and leading wildcards kill the index. WHERE YEAR(created_at) = 2026 or WHERE user_id = '42' (string vs int column) forces a full scan because the stored sorted values no longer match what you're comparing. A leading-wildcard LIKE '%foo' is the same trap: the B+tree is sorted by prefix, so an unanchored pattern has no prefix to seek on and must scan (a trailing wildcard LIKE 'foo%' is fine — it is a range). Rewrite as a range (created_at >= '2026-01-01'), fix the type, or add an expression index.
• Low selectivity is wasted. An index on a gender or is_active boolean rarely helps: if a value matches 50% of rows, following millions of random row pointers is slower than a sequential scan, so the planner ignores the index anyway. Index high-cardinality columns.
• Redundant / unused indexes. INDEX (a, b) already covers queries on a, so a separate INDEX (a) is dead weight that only slows writes. Audit with pg_stat_user_indexes / MySQL's sys.schema_unused_indexes and drop the ones with zero scans.
• The optimizer, not you, decides. Having an index doesn't guarantee its use — stale statistics or a bad row estimate can make the planner pick a scan. Always confirm with EXPLAIN.

When to use it — and when not

Reach for a B+tree index when a column is queried selectively and often, especially for equality and range/ordering/prefix work (WHERE, JOIN keys, ORDER BY, BETWEEN). It is the default for a reason: it serves point lookups, ranges, sorting, and prefix scans from one structure. The cost you accept is extra storage and slower writes.

Signals you should NOT add one: the table is tiny (a scan is already cheap and the tree is pure overhead); the query returns a large fraction of rows (a scan beats millions of random pointer hops); or the workload is write-dominated and rarely read (you'd be taxing the common operation to speed up the rare one).

Trade-offs versus named alternatives:

• Hash index — gives O(1) equality lookups and can beat a B+tree on pure exact-match, but it stores no order, so it can't do ranges, ORDER BY, or leftmost-prefix. Choose a hash index when you only ever do col = ? (e.g. an in-memory cache key, Postgres USING hash); prefer a B+tree when any range, sort, or prefix query is possible — which is nearly always.
• LSM-tree (log-structured merge tree, as in Cassandra / RocksDB / ScyllaDB) — buffers writes in memory and flushes sorted runs sequentially, giving far higher write throughput and less write amplification than a B+tree's in-place page updates; the cost is read amplification (a read may check several runs + Bloom filters) and background compaction. Choose an LSM-tree for write-heavy ingest / time-series / event logs; prefer a B+tree for read-heavy OLTP where low, predictable read latency matters (Postgres, MySQL InnoDB).
• No index (full scan) — zero write penalty and zero storage. Choose it for small or write-only tables and for analytical queries touching most rows; prefer an index the moment a selective lookup becomes hot.

Takeaways

• Reads are fast because the index is sorted; a high-fanout B+tree turns an O(n) scan into ~3–5 node visits (O(log n)), and the sorted leaves also serve ranges and ORDER BY.
• The price is paid on writes: every insert/update/delete maintains the tree (and may split pages), so add indexes deliberately and drop unused ones.
• Composite indexes only help on a leftmost prefix of their columns; a covering index can skip the row fetch entirely.
• Match the structure to the access pattern: B+tree for range + ordering (the default), hash for pure equality, LSM-tree for write-heavy ingest — and always verify real behavior with EXPLAIN.

Re-authored and deepened for this guide. Sources: Ramakrishnan & Gehrke, Database Management Systems (B+tree structure and cost model); Kleppmann, Designing Data-Intensive Applications, ch. 3 (B-trees vs LSM-trees, write vs read amplification); the PostgreSQL and MySQL InnoDB documentation on index types, composite/leftmost-prefix rules, and covering (index-only) scans; and Wikipedia: Database index.