Q10 — How do database indexes actually work — what is a B-tree doing physically?

Why do we need indexes at all?

A database table is, at its core, a collection of rows stored on disk. Without any additional structure, finding a specific row requires scanning every row in the table from start to finish — reading all of it until you either find what you're looking for or exhaust the data. This is called a full table scan, and its cost grows linearly with the number of rows. One million rows means up to one million row comparisons per query.

For a small table this is fine. For a table with 100 million users, a query like SELECT * FROM users WHERE email = 'alice@example.com' touching every row would take seconds. That's unacceptable for a web application.

The solution is a data structure that lets you jump directly to the relevant rows without reading the irrelevant ones. This is what an index is.

Why not just sort the table and use binary search?

Binary search on a sorted array is O(log n) — dramatically faster than a linear scan. If your table rows were stored in sorted order by email, you could find Alice's row in about 27 comparisons out of 100 million rows.

But here's the problem: inserts. If rows are stored physically sorted and you insert a new row with an email that falls alphabetically in the middle, you have to shift half the table to make room. On a table with 100 million rows, that's 50 million rows shuffled for every insert. Totally impractical.

You need a data structure that is:

1. Fast to search — O(log n)
2. Fast to insert — O(log n), not O(n)
3. Self-organizing — stays balanced as data is added and removed

This is the B-tree.

What is a B-tree physically?

A B-tree is a balanced tree where each node contains multiple keys (values) and multiple child pointers. The "B" does not stand for "binary" — it stands for "balanced" (or possibly Bayer, one of its inventors). The key difference from a binary search tree is that each node can hold many keys, not just one.

A node in a B-tree looks like this:

[ 10 | 30 | 50 ]
  ↓     ↓     ↓    ↓
[<10] [10-30] [30-50] [>50]

Every key in the left subtree is less than 10. Every key between the first and second child is between 10 and 30. And so on. This is the same binary search tree invariant, generalized to multiple keys per node.

In a real database B-tree, a single node might hold hundreds of keys. The tree stays shallow — a B-tree indexing 100 million rows might only be 4 levels deep. Finding any row requires traversing at most 4 nodes.

Why multiple keys per node — why not just a regular binary tree?

This is the most important insight about B-trees, and it comes entirely from how disks work.

Reading from disk is not like reading from memory. Memory access is random and fast — any byte in RAM takes ~100 nanoseconds to retrieve. Disk access, even on an SSD, is fundamentally different: you read a block of data (typically 4KB to 16KB) in one operation, and each operation takes ~100 microseconds — about 1000x slower than memory.

The key implication: when you read anything from disk, you read an entire block whether you want one byte or 4000 bytes. That block read costs the same either way.

So the strategy is: pack as many useful keys as possible into one block. If a B-tree node fills an entire disk block and holds 200 keys and 201 child pointers, then one disk read gives you 200 comparison points. A binary tree node holds one key — the same disk read gives you one comparison point.

A binary search tree with 100 million rows would be ~27 levels deep, requiring 27 disk reads to find a row. A B-tree with 200 keys per node needs only 4 levels (~200^4 = 1.6 billion possible entries). 27 disk reads vs 4 disk reads — roughly 7x fewer disk operations, which at 100 microseconds per read is the difference between 2.7ms and 0.4ms per query.

The B-tree was designed specifically around the reality that disk I/O is the bottleneck, not CPU time.

How does inserting into a B-tree work without breaking it?

When you insert a new key, you find the correct leaf node (just like a search) and insert the key there. If the leaf node has room — done. The tree remains valid.

If the leaf node is full (all slots taken), it splits: the node divides into two nodes, and the middle key is pushed up to the parent. This keeps both child nodes within bounds. If the parent is also full, it splits too, and the process cascades upward. In the rare case the root splits, a new root is created and the tree grows one level taller.

Every insertion takes O(log n) time — you traverse down the tree to find the insert position and potentially split nodes on the way back up. The tree stays balanced by construction: splits always happen symmetrically, and leaf nodes are always at the same depth.

Deletions use a mirror process: if a node becomes too empty after deletion, it borrows from a sibling or merges with a sibling and pulls a key down from the parent.

What is the difference between a B-tree and a B+ tree?

Real database indexes are usually B+ trees, a variant with one important difference: in a B+ tree, all actual data (or pointers to data) live only in the leaf nodes. Internal nodes contain only keys for navigation — no data. The leaf nodes are also linked together in a doubly-linked list.

Why? Two reasons:

First, internal nodes with no data can pack more keys per disk block, making the tree shallower and faster to traverse.

Second, the linked leaf nodes enable efficient range scans. A query like WHERE age BETWEEN 25 AND 40 can find the leaf containing age = 25, then follow the linked list forward until it reaches age = 40 — no need to traverse back up the tree for every value in the range.

What does an index actually store vs the table?

The index is a separate data structure from the table. For a query like SELECT * FROM users WHERE email = 'alice@example.com', the email index stores (email_value → row_pointer) pairs in the B+ tree. When you search the index, you find Alice's row pointer (typically a row ID or primary key value), then use that pointer to fetch the actual row from the table.

This is called a secondary index lookup — two disk reads in the worst case: one to find the pointer in the index, one to fetch the row. A primary key index (the clustered index in some databases) stores the actual row data in the leaf nodes, making primary key lookups a single tree traversal with no secondary fetch.

The mental model

Problem: full table scan is O(n) — too slow for large tables

Sorted array: O(log n) search but O(n) insert — impractical

B-tree: O(log n) both — designed around disk I/O
  ├── Multiple keys per node → fills a disk block → fewer disk reads per traversal
  ├── Self-balancing via splits and merges → always O(log n)
  └── B+ tree variant → data only in leaves, leaves linked → efficient range scans

Index = separate B+ tree: (indexed_column_value → row_pointer)
  ├── Find leaf: ~3-4 disk reads (tree is shallow)
  └── Fetch row: 1 disk read (via row pointer)

Total: ~4 disk reads vs millions for a full table scan

The B-tree's design is an answer to one constraint: disk I/O is expensive, and the unit of disk I/O is a block. Pack as much useful structure into each block as possible, and minimize the number of blocks you must read to answer a question.