Basic Indexing

You've built a database that can insert, update, delete, and query. But every lookup scans the entire table — O(n). For large tables, this is slow, and it's slow in the way that hurts most in production: everything works fine in development with 100 rows, then the table hits 10 million and every request does 10 million comparisons.

The solution is indexing: a second data structure, maintained alongside the table, that maps column values to row locations so lookups can skip the scan.

Why Indexes Are a Trade, Not a Free Win

An index is redundant data. Everything in it can be derived from the table — which means every write to the table must also update every index, or the index silently lies. This is the fundamental index bargain:

• Reads get faster: O(n) scan → O(1) hash lookup or O(log n) tree descent.
• Writes get slower: one insert becomes 1 + (number of indexes) updates.
• Consistency becomes your problem: the index and the table must agree after every operation, including the weird ones (deletes that shift rows, loads that replace the table). Most index bugs are consistency bugs.

That's why "just index everything" is wrong: a table with ten indexes does eleven writes per insert. Choosing which columns deserve indexes — based on which queries actually run — is a core part of database tuning.

Choosing the Structure: Hash vs. Sorted vs. B-Tree

An index maps column values to row positions. What structure holds the map?

• A hash table gives O(1) exact-match lookup (id == 5) but is useless for ranges (age > 25) — hashing destroys ordering by design.
• A sorted array gives O(log n) binary-search lookup and ranges (find the first match, walk forward), but inserting into the middle is O(n).
• A balanced tree gives O(log n) everything.

So why does every serious database use B-Trees rather than the binary trees you learned first? Disk, again. A binary tree node holds one key and two children, so finding one row in a billion takes ~30 node visits — and on disk, each visit is a page read. A B-Tree node is sized to exactly one page (4 KB) and holds hundreds of keys, so the tree's fanout is huge: with 200 keys per node, a billion rows is log₂₀₀(10⁹) ≈ 4 levels. Four page reads instead of thirty — and the top levels are hot enough to always be in cache, so usually one or two. The B-Tree is what "cache-line-friendly array" (lesson 1) looks like when generalized into a tree: pack as much decision-making as possible into each unit of I/O.

We'll build the honest starter version: an index over the unique ID column, stored as a growing array of {id, row_index} pairs. Its lookup is still O(n) inside the index — the structure is a stand-in — but it forces you to solve the real problem, which is maintenance: keeping table and index in lockstep through inserts and deletes.

The Maintenance Problem (Read This Before Coding)

Insert is easy: append {id, row_position} to the index. Delete is where it gets interesting, because our table uses remove-and-shift: deleting the row at position p moves every row after p down by one. The index entry for the deleted ID must go — but the index entries for all those shifted rows now point one position too high. After every delete you must also walk the index and decrement every row_index greater than p.

Miss that and you get the classic index-corruption bug: lookups that return the wrong row rather than failing. (This, incidentally, is another reason real databases prefer tombstones — positions never change, so indexes never need mass fix-ups — and why B-Tree indexes point at stable row identifiers rather than physical positions.)