9.3 What does an index look like inside?

In a book: Most indexes are alphabetical lists. But a library might also use a coat-check board (go straight to hook 47), or a pile of new cards sorted into the main drawer at the end of the day. Different structures, different strengths.

In the system: Three structures cover almost everything you'll meet.

9.3.1 B-tree

In a book: A multi-level index: the first page says "A–F on page 2, G–M on page 3...", page 2 says "Ca–Ce on page 40", and page 40 lists the words. Each step narrows the range.

In the system: A B-tree (in practice usually a B+ tree) is a tree of pages. Each page holds many sorted keys and pointers to the next level down; the bottom leaf pages hold the keys and where their rows are, and the leaves are linked in order.

Figure: each level narrows the range. With hundreds of keys per page, three or four levels are enough for billions of rows.

• Equality (= 7042): follow one path from root to leaf.
• Ranges (BETWEEN 7000 AND 7100), sorting (ORDER BY) and prefixes (LIKE 'Rao%'): find the start, then walk along the linked leaves in order.
• Stays balanced as rows are added, so every lookup takes the same few steps.

It's the default index type in PostgreSQL, MySQL (InnoDB), SQLite, SQL Server and Oracle.

9.3.2 Hash index

In a book: A coat-check board: hand over ticket 47, go straight to hook 47. Instant, but you can't ask "all hooks between 40 and 50".

In the system: A hash index runs each value through a hash function to find its bucket directly. Equality lookups are very fast, but it can't do ranges, sorting or prefixes, because hashing scatters neighbouring values. Some databases offer it (PostgreSQL has hash indexes); key-value stores like Redis work this way internally (Chapter 8). In most relational databases, a B-tree does equality almost as well and handles ranges, so it stays the default.

9.3.3 LSM tree in brief

In a book: New index cards go on a small pile on the desk, kept in order. When the pile gets big, it's filed as a new sorted drawer. Every so often, drawers are merged into one.

In the system: A log-structured merge tree (LSM tree) is built for heavy writes:

Figure: writes are cheap because nothing is updated in place; reads may need to check several files.

1. Writes go to a sorted structure in memory (the memtable), plus an append-only log on disk so nothing is lost in a crash.
2. When it's full, it's written out as an immutable sorted file.
3. In the background, compaction merges files and drops old versions.

Writes are fast because they never update pages in place. Reads may need to check several files; Bloom filters (Chapter 20) let them skip files that can't contain the key. LSM trees power Cassandra, RocksDB, LevelDB and the storage of many wide-column stores (Chapter 8).

Memory code: "Tree for ranges, hash for exact, LSM for floods of writes."

---