Storage Engines Explained: B-Tree vs LSM Tree

MySQL reads fast. Cassandra writes fast. It all comes down to where each one puts your row the moment you write it. MySQL keeps it in a B-tree, Cassandra in an LSM tree, and this article follows one order through both.

The video tells the same story in six minutes. This is the written version, with the SQL.

One order, one row, one page

Say Anna orders a pizza. That tap becomes one row in the orders table:

CREATE TABLE orders (
  order_id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  customer VARCHAR(64)     NOT NULL,
  item     VARCHAR(64)     NOT NULL,
  status   VARCHAR(16)     NOT NULL,
  PRIMARY KEY (order_id)
) ENGINE=InnoDB;

INSERT INTO orders (customer, item, status) VALUES ('Anna', 'pizza', 'placed');

MySQL doesn't store that table as a list of rows. It stores it in pages, blocks of 16 KB, and one page holds a few hundred small rows like this one. You can see the size on your own server:

SHOW VARIABLES LIKE 'innodb_page_size';
-- innodb_page_size | 16384

A read pulls in the whole page

Anna's order lands on one page. When she checks on it, the database doesn't fetch one row. It pulls the whole page from disk into memory and picks her row out.

A write sends back the whole page

Now the rider marks it delivered:

UPDATE orders SET status = 'delivered' WHERE order_id = 4473;

The database changes her row inside the page in memory, and marks that page dirty. One field changed, but the whole page gets written back. It doesn't happen right away: page cleaner threads write the dirty pages to disk in the background.

So here's the thing. A row costs whatever its page costs. And which page a new row goes to is the whole difference between MySQL and Cassandra.

The B-tree: every row has a home

In MySQL, every row has a home. The table is kept sorted by its primary key, so Anna's order sits right next to the orders before and after it. The MySQL manual puts it this way: "Each InnoDB table has a special index called the clustered index that stores row data." That clustered index is a B-tree: a root page that points down to the pages holding the rows, each page covering a range of ids.

Counting ids against random ids

When the ids count up, like the AUTO_INCREMENT above, every new order has the biggest id so far. Its home is the newest page, and that page is already in memory. The database adds the row and moves on.

Now give the same table random ids:

CREATE TABLE orders_random (
  order_id BINARY(16)  NOT NULL,   -- a random UUID (version 4), made by the application
  customer VARCHAR(64) NOT NULL,
  item     VARCHAR(64) NOT NULL,
  status   VARCHAR(16) NOT NULL,
  PRIMARY KEY (order_id)
) ENGINE=InnoDB;

A new order can now land on any page. That page is probably not in memory, so the database reads it from disk first. And if that page is full, it gets split into two half empty pages. The MySQL manual gives the result: when rows are inserted in order, the pages end up about 15/16 full; when they are inserted in random order, the pages are anywhere from 1/2 to 15/16 full. More pages, half empty, for the same rows.

One long write, or many small ones

Then the dirty pages have to go back to disk. With counting ids, the dirty pages sit together at the end of the table, so it's one long write. With random ids, they're scattered all over the disk, so it's many small writes. A disk is far faster at one long write than at many small ones.

So in MySQL, a write pays to find its home.

The LSM tree: no home page

Cassandra just refuses to pay that price. Here a row has no home page. A new row goes into a sorted list in memory, and that list is called the memtable.

Rider locations are a good example, because they arrive by the thousand every second:

CREATE TABLE rider_locations (
  rider_id uuid,
  seen_at  timestamp,
  lat      double,
  lon      double,
  PRIMARY KEY (rider_id, seen_at)
) WITH CLUSTERING ORDER BY (seen_at DESC);

INSERT INTO rider_locations (rider_id, seen_at, lat, lon)
VALUES (5b6962dd-3f90-4c93-8f61-eabfa4a803e2, toTimestamp(now()), 52.37, 4.89);

That insert does not look for a page on disk. Cassandra appends it to its commit log and puts it in the memtable, and the write is done.

A file that never changes

When the memtable fills up, the whole list goes to disk as one new file, in one long write. And that file is never touched again. The Cassandra documentation says it plainly: "SSTables are immutable, and never written to again after the memtable is flushed."

So if Anna's order changes, nobody edits the old row. A newer copy goes into the memtable, and the old copy stays in its file.

Reads go newest to oldest

To read her order, the database checks the memtable first, then the files, newest to oldest. The first copy it finds is the newest, so that's the answer. That can take a few looks, and MySQL only needed one.

Real engines make the looks cheaper. Each file carries a Bloom filter that says quickly when a key cannot be in it, so most files are skipped without a disk read. Cassandra goes one step further and merges the pieces of a row from every file that holds them, by timestamp. Newest first is the simple form, and it is how RocksDB answers a single key.

Compaction

The files pile up, so a background job merges them. It keeps only the newest copy of each row and writes one new file. That's called compaction, and on Cassandra you can watch it run with nodetool compactionstats.

This whole shape is the LSM tree, a log-structured merge tree. Cassandra uses it, and so does RocksDB, the engine inside many other databases. The cost of writing didn't disappear. It just moved to later.

Which one to pick

Back to the delivery app. The orders table gets read all day, by customers, the kitchen and support, and each order changes only a few times. That belongs in MySQL.

Rider locations come in by the thousand every second, and nobody reads one ping on its own. Those belong in Cassandra.

The law

A B-tree pays when you write, so reads are cheap. An LSM tree pays later, so writes are cheap. Pick by what your data does more.

Go deeper

• The physical structure of an InnoDB index (MySQL 8.4 Reference Manual): the 16 KB page, and how full pages get with ordered and random inserts.
• Buffer pool flushing (MySQL 8.4 Reference Manual): the page cleaner threads that write dirty pages in the background.
• The storage engine (Apache Cassandra documentation): the commit log, the memtable, SSTables and compaction.
• Designing Data-Intensive Applications, 2nd edition, by Martin Kleppmann and Chris Riccomini (2026), chapter 4, Storage and Retrieval, which compares B-trees and LSM trees in depth.

Next time

This is the first part of Database Internals, a series on how a database works inside. Next time, the power goes out before the page reaches the disk, and we find out how your row survives.

Anna, her order, the ids and the page numbers are an invented example. Does your app read more than it writes, or write more than it reads?