Inside the database: B-trees and LSM trees

Part of the free System Design course on LogicWiz, in the chapter: Storage engines, search and geo. The interactive whiteboard exercises and simulations run in the app.

Week 10: Ten thousand pings a second

"The orders database answers lookups beautifully. Then someone pointed rider location pings at it, and the disks hit 100%."

Meera, staring at the disk graph

How a B-tree finds one order

A customer opens order 81,723,004. How does the database find it among hundreds of millions of rows without reading them all?

A database keeps data on disk in fixed-size blocks called pages: 8 KB in PostgreSQL, 16 KB in MySQL's InnoDB. A B-tree is a sorted tree of pages. The root page holds a few hundred keys. Each key points to a child page that covers a range of keys, and those point to further pages. The bottom pages (leaves) hold the rows, or pointers to them.

Real arithmetic. An 8 KB page with small keys can point to a few hundred children. Call it 500. This number is the fan-out: how many children each page points to.

  • 1 level: 500 keys
  • 2 levels: 500 × 500 = 250,000
  • 3 levels: 125 million
  • 4 levels: about 62 billion

SwiftKart creates about 500,000 orders a day, roughly 180 million a year. A four-level tree covers years of orders, so finding any one order means reading 4 pages. The top two levels are tiny (about 500 pages, roughly 4 MB) and stay in memory. So a lookup usually costs one or two real disk reads. That is why one SQL database can serve thousands of simple lookups a second.

Writes are where it gets expensive. A B-tree updates in place: find the leaf page, change it, write the page back. Changing a 100-byte order status rewrites an 8 KB page. Before that, the database writes a record to the write-ahead log (an append-only file of changes), so it can recover after a crash. The pages being changed sit all over the disk, so these are small scattered writes. For SwiftKart's 4 million status updates a day (about 46 a second) that is nothing. For 10,000 location pings a second, it is the disk graph Meera was staring at.

How an LSM tree takes a write

A log-structured merge tree (LSM tree) never changes a page in place. Each write does this:

  1. Append it to the write-ahead log on disk, so a crash loses nothing. Appending (adding to the end of a file) is the cheapest thing a disk does.
  2. Put it in the memtable, a sorted structure in memory.
  3. When the memtable fills up (say 64 MB), write it to disk in one go. The result is a sorted file that is never modified, called an SSTable (sorted string table).
  4. In the background, compaction merges several SSTables into one bigger one. It keeps only the newest value for each key and drops deleted ones.
flowchart LR
  W["Write"] --> L["Log: append"]
  W --> M["Memtable in memory"]
  M -->|"flush when full"| S["SSTables on disk"]
  S -->|"compaction"| B["Bigger SSTable"]

Every disk write is an append or one big file written in order (a sequential write). Both spinning disks and SSDs handle these far better than scattered small writes. That is why LSM trees absorb heavy write traffic well.

Reads pay for it. To find a key, check the memtable, then the newest SSTable, then older ones, until you find it. That could mean many files. The fix is a bloom filter per SSTable. It is a small array of bits that answers "definitely not in this file" or "maybe in this file". With about 10 bits per key it is wrong only about 1% of the time. So a read skips almost every file that does not hold the key.

Write and read amplification, in plain words

Two phrases you will hear in interviews:

  • Write amplification: how many bytes the disk really writes for each byte you asked to write. B-tree: a 100-byte change rewrites an 8 KB page, roughly 80 times the size. But these writes happen only as often as your updates. LSM: each value is written to the log and flushed once. Then it is rewritten every time compaction merges it into a bigger file. That is often several to tens of times over its life, but always in large sequential writes.
  • Read amplification: how many places a read must look. B-tree: one path of 3 or 4 pages, the top ones in memory. LSM: the memtable plus possibly several SSTables. Bloom filters keep point lookups (one key) cheap. But a range scan ("all pings for rider 4521 in the last hour") must merge results from several files.

The trade-off in one line: B-trees make reads predictable and pay on writes; LSM trees make writes cheap and pay on reads and background compaction.

💡 Tip: Compaction is real work that competes with your traffic for disk. An LSM store that is fast in a 5-minute benchmark can slow down after a day of heavy writes, once compaction falls behind. Test with load that runs for hours.

No engine is faster in general

In a mock interview, a candidate told Kabir: "Cassandra is faster than PostgreSQL, so I'll use it everywhere." You will hear "NoSQL is faster" said as if it were a law. It is not. No engine is faster in general; each is built for a shape of work. Here are the well-known facts. PostgreSQL's default indexes and MySQL's InnoDB tables are B-trees. Cassandra, RocksDB and LevelDB use LSM trees, and RocksDB is also used as the storage engine inside other databases.

Give an LSM store a workload with many reads, in-place updates and multi-row transactions. It can be slower than PostgreSQL. Give PostgreSQL 10,000 small inserts a second, all day, every day, and you are fighting its write path. So do not ask "which is faster?" Ask two questions. Is this data written much more than it is read? Does it need transactions?

Choosing a store for pings and for orders

Do the numbers for each.

Rider location pings. About 10,000 writes a second, each roughly 100 bytes: 1 MB a second. That is 10,000 × 86,400 ≈ 864 million pings a day, about 86 GB. Reads are rare by comparison: "where is rider 4521 now?" and "the last hour of rider 4521's route". Old pings can expire after a few days. This is write-heavy, append-only, short-lived data with no transactions. An LSM store such as Cassandra fits it. The customer's map often reads each rider's latest position, so that can also live in an in-memory cache.

Orders. About 20 million status reads and 4 million updates a day: read-heavy, about 5 to 1. Placing an order must reserve stock and record payment together, in one transaction. Support also asks for range queries like "this customer's orders this month". That suits a B-tree: orders stay in PostgreSQL, as decided in Week 5.

In an interview, say it in two sentences: "Pings are write-heavy, append-only and expire, so I'd store them in an LSM-based store like Cassandra. Orders are read-heavy and transactional, so they stay in a B-tree SQL database."

📌 Summary: A B-tree finds a row in 3 or 4 page reads but rewrites a page per write. An LSM tree turns writes into appends and pays on reads. Pings suit LSM; orders suit B-trees.

What Meera learns next

Neither tree can answer "which products mention milk?" or "which riders are near this store?". Next: the two special indexes that can, inverted indexes and geohashes.

Check your understanding

  1. SwiftKart's orders table has about 500 million rows, yet a lookup by order id takes one or two disk reads. Why?
  2. Rider pings arrive at about 10,000 writes a second, are rarely read, and expire after a few days. Which storage choice fits best?
  3. In an LSM store, a read asks for a rider id that is in none of the 12 SSTables on disk. What stops it from reading all 12 files?
  4. A colleague says "Cassandra is faster than PostgreSQL, let's move orders there." What is the best reply?