DSA & System Design
Databases internals · Lesson 9 of 12 · 25 min

Indexes: B-trees, LSM-trees and Query Plans

What an index costs, how a B-tree and an LSM-tree each find and store data, how composite and covering indexes work, and how to read a plan.

✓ Explain what an index costs on writes, disk and memory✓ Compare B-tree and LSM-tree read and write paths✓ Order a composite index and read an EXPLAIN plan
Say it in 30 seconds
  • 4 levelsB-tree depth for a billion rows, fanout 300
  • n → log nRows scanned versus index steps
  • 1 write → NIndex updates per insert with N indexes
Show what to say

“An index trades slower writes and more space for fast lookups. A B-tree is wide and shallow, so a lookup reads a few pages, and it updates pages in place. An LSM-tree appends to a log and a memtable and merges sorted files in compaction, so writes are cheap and reads need Bloom filters. I order composite indexes equality first and check the plan with EXPLAIN.”

Trade-offs

  • B-tree vs LSM-tree: B-trees give predictable reads and range scans; LSM-trees give cheap sequential writes at the cost of read amplification and compaction.
  • More indexes vs fewer: each index speeds some reads but adds a write, disk and a planner choice.
  • Covering vs narrow index: a covering index avoids the table fetch but is larger and costs more on every write.

Bring it up before they ask

Say you would check EXPLAIN before adding an index, because low-selectivity columns and functions on columns often ignore it.

0 of 0 sections ticked
30-second answer

An index is a sorted copy of some columns that turns a full scan into a few page reads, paid for with slower writes and more space. update pages in place; LSM-trees turn writes into sequential appends and pay on reads and in compaction.

What an index is and what it costs

Without an index, finding one row means scanning the table.

Read more · 77 words

An index is a sorted structure from key to row location, so a lookup takes about log(n) steps instead of n.

Every write must also update each index, and indexes take disk and memory. Index the columns you filter, join and sort on, and no more. More in the HLD path.

B-trees

A (in practice a B+tree) stores keys in pages of 8 to 16 KiB.

Read more · 78 words

Each internal page holds hundreds of keys and child pointers, so the tree is wide and shallow: with about 300 keys per page, three levels reach 27 million rows and four reach 8 billion.

A lookup reads one page per level, and the top levels sit in memory. Leaf pages are linked in order, so a range scan walks along them. A full page splits in two. Writes change pages in place, so they are random I/O.

Press Play to watch it run · 4 steps

The query walks from the root page through an internal page to a leaf page, then follows the leaf's pointer to the row. With hundreds of keys per page, three levels cover tens of millions of rows.

A B-tree lookup: one page per levelThe query walks from the root page through an internal page to a leaf page, then follows the leaf's pointer to the row. With hundreds of keys per page, three levels cover tens of millions of rows.WHERE id = 42Always in memory.Root pagekeys 1..1MInternal pagekeys 1..5000Leaf pagekeys 1..16Table rowid 42

Tap any box to see what it is and what it talks to.

  • Client
  • Database
  • Object storage
Open in playground
Text description
  1. Start at the root page, which is almost always cached in memory.
  2. Keys 1 to 5000 live under the first child: follow that pointer.
  3. The internal page narrows it to one leaf page.
  4. The leaf holds key 42 and where its row is. Three page reads, then one row fetch.

LSM-trees

An LSM-tree never updates in place.

Read more · 126 words

A write is appended to a log and inserted into a sorted in-memory table (the memtable), which is flushed as an immutable sorted file when full. A read checks memory, then files newest to oldest; skip files that cannot hold the key.

Background compaction merges files and keeps the newest version of each key. A delete is a that hides older values until compaction removes both.

RocksDB, LevelDB, Cassandra and HBase work this way.

Press Play to watch it run · 4 steps

A write is appended to the log and inserted into the in-memory table, and flushed as a sorted file when full. A read checks memory, then the files from newest to oldest. Compaction merges files in the background.

LSM-tree: write path and read pathA write is appended to the log and inserted into the in-memory table, and flushed as a sorted file when full. A read checks memory, then the files from newest to oldest. Compaction merges files in the background.ClientWrite-ahead logsequentialMemtablesorted, in RAMSorted filesimmutableCompactionbackground

Tap any box to see what it is and what it talks to.

  • Client
  • Object storage
  • Cache
  • Worker
Open in playground
Text description
  1. Append the write to the log first, so a crash cannot lose it.
  2. Insert it into the sorted in-memory table. The write is done.
  3. When the memtable is full it is flushed as one sequential, immutable sorted file.
  4. Later, compaction merges files, keeps the newest version of each key and drops deleted ones.
// A tiny LSM-tree. Writes go to an in-memory table; when it fills, it is flushed as an immutable
// sorted run. Reads check memory, then runs from newest to oldest. Compaction merges the runs.
const TOMBSTONE = Symbol('deleted'); // a delete is a write too: it hides older versions

const find = (run, key) => {
  let lo = 0;
  let hi = run.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (run[mid][0] === key) return run[mid];
    if (run[mid][0] < key) lo = mid + 1;
    else hi = mid - 1;
  }
  return null;
};
const byKey = ([a], [b]) => (a < b ? -1 : a > b ? 1 : 0);
const visible = (v) => (v === TOMBSTONE ? undefined : v);

export class Lsm {
  constructor(memtableLimit = 4) {
    this.limit = memtableLimit;
    this.mem = new Map();
    this.runs = []; // newest first, each a sorted array of [key, value]
    this.runsRead = 0; // how many runs reads had to look in: read amplification
  }

  put(key, value) {
    this.mem.set(key, value);
    if (this.mem.size >= this.limit) this.flush();
  }

  delete(key) {
    this.put(key, TOMBSTONE);
  }

  flush() {
    this.runs.unshift([...this.mem].sort(byKey)); // one sequential write
    this.mem = new Map();
  }

  get(key) {
    if (this.mem.has(key)) return visible(this.mem.get(key));
    for (const run of this.runs) {
      this.runsRead += 1;
      const hit = find(run, key);
      if (hit) return visible(hit[1]); // the newest version wins
    }
    return undefined;
  }

  compact() {
    const merged = new Map();
    for (const run of [...this.runs].reverse()) for (const [k, v] of run) merged.set(k, v); // newer overwrites older
    this.runs = [[...merged].filter(([, v]) => v !== TOMBSTONE).sort(byKey)]; // dead keys finally disappear
  }
}

B-tree or LSM: read and write cost

Both pay somewhere. A rewrites a whole page for a small change.

Read more · 50 words

An LSM-tree makes writes sequential, but a read may touch several files and compaction rewrites data later.

B-treeLSM-tree
Point readA few pages, predictableSeveral files, helped by Bloom filters
WriteRandom in-place page writesSequential appends, compaction later
Best forRead-heavy, range scans, OLTPWrite-heavy, ingest, time series
Interactive

Index cost lab: B-tree against LSM-tree

A teaching model with round numbers, not a benchmark. Move the sliders to see which costs grow and which stay flat.

Show
B-tree height
4 pages
fanout about 300
LSM disk levels
4
64 MiB memtable, ratio 10
Pages or runs read for one point lookup
012344B-tree4LSM, no filters1LSM, Bloom
Show data table
Pages or runs read for one point lookup
B-tree4
LSM, no filters4
LSM, Bloom1

One lookup in 1B rows: the B-tree reads 4 pages (the top levels are normally cached). The LSM-tree checks 4 runs, one per level, or about 1 when Bloom filters skip the levels that cannot hold the key.

Composite and covering indexes

A composite index on (a, b, c) is sorted by a, then b within a, then c within b.

Read more · 79 words

It narrows a search using equality on a leading run of columns plus one range column after. That is the leftmost-prefix rule: a filter on b alone cannot use it.

Put equality columns first, the range column last. A holds every column the query needs, so the answer comes from the index alone (an index-only scan).

// An index on (a, b, c) is sorted by a, then by b inside each a, then by c inside each b.
// It can narrow a search using equality on a leading run of its columns, plus one range column right after.
export function usableColumns(indexColumns, { equals = [], range = [] }) {
  let used = 0;
  for (const column of indexColumns) {
    if (equals.includes(column)) {
      used += 1;
      continue;
    }
    if (range.includes(column)) used += 1; // a range ends the useful prefix
    break;
  }
  return used;
}

// A covering index holds every column the query needs, so the table itself is never touched.
export const isCovering = (indexColumns, needed) => needed.every((column) => indexColumns.includes(column));

Reading a query plan

Ask the database how it will run a query, and then how it did.

Read more · 40 words

Read the scan type: a sequential scan reads the whole table, an index scan follows the index and fetches rows, an index-only scan fetches none. A big gap between estimated and actual rows means stale statistics. Wording differs by database.

EXPLAIN ANALYZE
SELECT status, created_at FROM orders
WHERE user_id = 42 AND status = 'paid';
Index Only Scan using orders_user_status_idx on orders
  (cost=0.43..8.45 rows=3) (actual time=0.03..0.04 rows=3 loops=1)

When an index does not help

Read more · 113 words
  • Low selectivity. If a query matches a large share of the rows (a boolean column, for example), reading the table in order is cheaper than jumping around, so the planner scans.
  • A function on the column. WHERE lower(email) = ... cannot use a plain index on email; index the expression.
  • A leading wildcard. LIKE '%abc' cannot use the sorted order.
  • A type mismatch, or an OR across different columns.
  • Tiny tables. Scanning a few pages is faster than any index.

Other index types

Read more · 135 words
  • Hash index. Equality only, no ranges.
  • (GIN). Words or JSON keys to rows, for full-text search.
  • Spatial (GiST, R-tree). Nearby points and boxes.
  • Clustered versus secondary. In InnoDB the table is stored in primary-key order, and a stores the , so a secondary lookup is two tree walks.
  • Partial index. Index only the rows you query, such as WHERE status = 'open'.

Follow-up questions

What does an index cost?

Every insert, update and delete also updates each index, and indexes use disk and memory. It speeds reads that match its sort order and slows writes.

B-tree or LSM-tree for a write-heavy workload?

An LSM-tree: writes are sequential appends. The price is read amplification, softened by , and background compaction. Read-heavy OLTP with range scans suits a .

How do you order a composite index?

Equality columns first, then the range column, because the index narrows on a leading run of equalities and one range.

Why might the planner ignore your index?

The query matches too many rows, statistics are stale, the table is tiny, or a function or leading wildcard is applied to the column.

Check yourself

Question 1 of 7

Score 2 out of 3 or better to mark this page complete.

1. A B-tree page holds about 300 keys. Roughly how many levels does it need for one billion rows?

Next: Indexes make single queries fast. Next: what a transaction promises when many run at once.