Database Indexing: B-Trees and LSM-Trees

Why we need indexes at all

Without an index, finding WHERE email = 'asha@example.com' means reading every row. This is a full scan, and the work grows with the number of rows n: O(n). With a sorted structure you can use binary search. Binary search checks the middle, then keeps only the half that can hold the answer, and repeats. The work grows very slowly: O(log n).

That is why indexes make such a big difference as tables grow.

B-trees (and B+trees)

A B-tree is a sorted tree that is wide and shallow. It is stored in fixed-size blocks called pages on disk (8 KB in PostgreSQL and 16 KB in MySQL InnoDB by default). Each page is one node of the tree.

                     [  50  |  100  ]                  ← root page                    /        |        \         [10 | 25 | 40]   [60 | 75 | 90]   [120 | 150]   ← internal pages          /  |  |  \        ...     [1..9][10..24][25..39][40..49]  ...                 ← leaf pages (point to rows)

• Each page holds hundreds of keys, so every node has many children. This is called high fan-out.
• Because of that, even a billion rows need only about 3–4 levels. That means 3–4 page reads to find anything. The top levels are usually kept in memory, so often it is just 1–2 disk reads.
• In a B+tree (the version most databases really use), the bottom pages (leaves) are linked in order. So range queries (WHERE created_at BETWEEN ...) are fast. You find the start, then walk along the leaves.

Writes in a B-tree:

1. Find the right leaf page.
2. Insert or update the key in place.
3. If the page is full, split it into two and update the parent.

Every write may touch several pages, in random places on disk. For crash safety, the change is written to the WAL (write-ahead log, a file of changes) first. See Lesson 21.

B-trees are good for:

• fast point lookups (find one key) and range scans (find all keys between two values),
• predictable read speed,
• the default in PostgreSQL, MySQL InnoDB, SQL Server, Oracle and SQLite.

LSM-trees (Log-Structured Merge-trees)

An LSM-tree (Log-Structured Merge-tree) never updates data in place. It only adds new data and merges it later. These are the steps:

Why writes are fast: a write is just an append to a log plus an insert in memory. Data goes to disk in big sequential chunks (one after another). This is good for both SSDs and spinning disks.

Reads are more work:

1. Check the memtable.
2. Check the newest SSTable, then older ones, until you find the key. An SSTable (sorted string table) is one sorted file on disk.

To keep this fast:

• Bloom filters. A Bloom filter is a small, compact structure that tells you "this key is definitely not in this file" or "it might be". It never gives a wrong "not here" answer. Each SSTable has one. So most files are skipped without reading them from disk.
• Sparse indexes inside each SSTable (an index with only some of the keys) let the engine jump close to the right spot.
• Compaction (merging files in the background) keeps the number of files small.

Deletes are written as tombstones. A tombstone is a marker that says "key X was deleted". The data only really disappears when compaction runs.

Compaction strategies:

• Size-tiered: merge files of similar size. Good for write-heavy loads. But it uses more temporary disk space.
• Levelled: organise files into levels. Inside one level, the files do not share any keys. Reads are better and less space is used. But data is rewritten more often.

LSM-trees are used by: RocksDB and LevelDB (embedded engines), Cassandra, ScyllaDB, HBase, Google Bigtable, and the storage layers of many modern databases (CockroachDB and TiDB use LSM-based engines).

Hash indexes

The simplest index is a hash map. It maps each key to a position on disk. It is very fast for exact lookups (WHERE id = 42). But it is useless for ranges (WHERE id > 42) and for sorting. Some key-value stores use this design (for example, the Bitcask model). PostgreSQL also offers hash indexes, but B-trees are almost always the better choice.

The three "amplifications"

Engineers compare storage engines using three costs. "Amplification" means doing more work than the minimum:

Roughly: B-trees are best for reads. LSM-trees are best for writes. Real performance depends a lot on the workload and the settings, so test with your own data.

Types of indexes you will use

Clustered vs secondary (non-clustered).

• A clustered index stores the table rows themselves in index order. In MySQL InnoDB, the primary key is the clustered index. Lookups by primary key are very fast. A table can have only one clustered index.
• A secondary index is any other index. It stores the indexed column(s) plus a pointer to the row. In InnoDB the pointer is the primary key. In PostgreSQL it is the row location. Using it takes one lookup in the index plus one fetch of the row.

Composite (multi-column). One index over several columns, for example (country, city, created_at). It follows the left-prefix rule from Lesson 5: it can help a query on country, or on country and city, but not on city alone.

Covering index. It contains all the columns a query needs. So the database never has to fetch the table row. The INCLUDE columns are stored in the index but are not part of the sort key:

CREATE INDEX idx_orders_user_cover ON orders (user_id, created_at) INCLUDE (total, status);-- SELECT created_at, total, status FROM orders WHERE user_id = 42 → index-only scan

Unique index. It does not allow two rows with the same value. It is the safety net from Lesson 21.

Partial index. It only indexes the rows that match a condition. This saves space:

CREATE INDEX idx_pending_orders ON orders (created_at) WHERE status = 'pending';

Specialised indexes (PostgreSQL examples):

• GIN (an inverted index, like the one in Lesson 19) for arrays, JSONB and full-text search,
• GiST / SP-GiST (flexible tree indexes) for shapes and map data,
• BRIN (a very small index that stores the min and max value of each block of rows) for huge tables whose rows are already in order, like time-series logs,
• geospatial indexes (PostGIS, geohashes) for "restaurants near me". PostGIS is a PostgreSQL extension for map data. A geohash is a short text code for a map area.

Choosing indexes in practice

1. Start from real queries. Look at the slow-query log (a list of slow queries) and at the most frequent queries.
2. Index columns used in WHERE, JOIN and ORDER BY. In a composite index, put the columns that you compare with equality first, and a range column last.
3. Check with EXPLAIN ANALYZE (Lesson 5). It shows the plan the database really used and how long each step took.
4. Do not add too many indexes. Each index slows every insert and update and uses memory. A write-heavy table with 15 indexes will struggle.
5. Remove unused indexes. Most databases can tell you which indexes are never used.
6. Watch for low-selectivity columns. Selectivity means how well a value narrows down the rows. An index on is_active (true/false) has low selectivity. It rarely helps on its own.
7. Remember that indexes work best in memory. If your most-used indexes do not fit in RAM, performance drops sharply.