How B-Trees and LSM-Trees Actually Store Your Data (Postgres vs Cassandra)

Quick Answer

Postgres and MySQL store indexes as B-trees: wide, shallow, sorted pages on disk that stay balanced by splitting a full page in two and promoting its middle key upward. Cassandra, RocksDB, and LevelDB store data as LSM-trees instead: writes land in an in-memory buffer that gets flushed as an immutable sorted file, with a background compaction process merging those files later. B-trees optimize for fast reads with in-place random-write updates; LSM-trees optimize for fast sequential writes at the cost of extra work on reads and during compaction.

Why not just put a binary search tree on disk

If you've read Priodemy's AVL and red-black trees post, you already know how to keep an in-memory binary search tree balanced with rotations. The natural next question is: why doesn't Postgres just use one of those for its indexes? The answer is entirely about disk physics, not algorithms. A binary tree node holds one key and two pointers. On disk, following a pointer to the next node usually means a separate random I/O — a disk seek, or at minimum a separate page fetch even on an SSD. A balanced binary tree over a million rows is about 20 levels deep, which means a single lookup could cost 20 separate random reads. That's the part a plain binary tree gets badly wrong for on-disk storage: it's balanced in height, but height is exactly the wrong thing to minimize when every level costs a disk access.

The fix databases converged on decades ago is to make each node much wider — hold hundreds of keys per node instead of one — so the tree stays only 3 or 4 levels deep even over billions of rows, and each level corresponds to one disk page read. That's a B-tree. LSM-trees solve a different problem: even a wide, shallow B-tree still does random-access, in-place writes when you update an existing key, and random writes are the slowest thing you can ask a disk to do. LSM-trees trade some read simplicity for turning writes into sequential, append-only operations instead.

B-trees: how Postgres and MySQL actually split a page

A B-tree node (Postgres calls it a page) holds a sorted array of keys, plus pointers to child pages that hold everything between them. Postgres' own documentation confirms the mechanism exactly: "new leaf pages are added to a B-Tree index when an existing leaf page cannot fit an incoming tuple. A page split operation makes room for items... by moving a portion of the items to a new page," and critically, "page splits must also insert a new downlink to the new page in the parent page, which may cause the parent to split in turn" — splits cascade upward, and "when the root page finally cannot fit a new downlink... a root page split operation takes place. This adds a new level to the tree." That's the entire algorithm: fill a page, split it in half around its middle key, push that middle key up to the parent, and repeat upward if the parent is also full.

Rather than just describe that, here's a real implementation — minimum degree t=2, so every node holds at most 3 keys before it must split (a real Postgres page holds hundreds; this is shrunk down so you can watch every split happen):

class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf

class BTree:
    def __init__(self, t=2):
        self.t = t                      # minimum degree
        self.root = BTreeNode(leaf=True)

    def insert(self, key):
        root = self.root
        max_keys = 2 * self.t - 1        # a page can hold at most 3 keys here
        if len(root.keys) == max_keys:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_nonfull(self.root, key)

    def _split_child(self, parent, i):
        t = self.t
        child = parent.children[i]
        new_node = BTreeNode(leaf=child.leaf)
        mid_key = child.keys[t - 1]

        new_node.keys = child.keys[t:]
        child.keys = child.keys[:t - 1]
        if not child.leaf:
            new_node.children = child.children[t:]
            child.children = child.children[:t]

        parent.keys.insert(i, mid_key)          # median promoted upward
        parent.children.insert(i + 1, new_node)

    def _insert_nonfull(self, node, key):
        max_keys = 2 * self.t - 1
        if node.leaf:
            node.keys.append(key)
            node.keys.sort()
        else:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1
            if len(node.children[i].keys) == max_keys:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_nonfull(node.children[i], key)

Running this while inserting 10, 20, 30, 40, 50, 60, 70, 80, 90 in order produces this real, unedited output:

INSERT 10
leaf node keys=[10]

INSERT 20
leaf node keys=[10, 20]

INSERT 30
leaf node keys=[10, 20, 30]

INSERT 40
  -> ROOT SPLIT triggered by inserting 40. New root keys: [20]
internal node keys=[20]
  leaf node keys=[10]
  leaf node keys=[30, 40]

INSERT 50
internal node keys=[20]
  leaf node keys=[10]
  leaf node keys=[30, 40, 50]

INSERT 60
internal node keys=[20, 40]
  leaf node keys=[10]
  leaf node keys=[30]
  leaf node keys=[50, 60]

INSERT 70
internal node keys=[20, 40]
  leaf node keys=[10]
  leaf node keys=[30]
  leaf node keys=[50, 60, 70]

INSERT 80
internal node keys=[20, 40, 60]
  leaf node keys=[10]
  leaf node keys=[30]
  leaf node keys=[50]
  leaf node keys=[70, 80]

INSERT 90
  -> ROOT SPLIT triggered by inserting 90. New root keys: [40]
internal node keys=[40]
  internal node keys=[20]
    leaf node keys=[10]
    leaf node keys=[30]
  internal node keys=[60]
    leaf node keys=[50]
    leaf node keys=[70, 80, 90]

Watch what happens at 40 and again at 90: the tree's single root page fills up, splits, and a brand new root appears one level higher — exactly the "root page split... adds a new level to the tree" behavior Postgres' documentation describes. Between those two events, every other insert just slots into an existing page without disturbing the tree's shape at all. That's the property that makes B-trees good at reads: the tree only grows taller on the rare occasions a page truly fills up, so lookups stay at a small, predictable number of page reads almost all the time.

LSM-trees: how Cassandra, RocksDB, and LevelDB actually store data

An LSM-tree (log-structured merge-tree) takes a completely different approach to writes. Apache Cassandra's own architecture documentation describes exactly this: "the core storage engine consists of memtables for in-memory data and immutable SSTables... on disk," where "the memtable stores writes in sorted order until reaching a configurable limit," at which point it's "flushed onto disk" and becomes an immutable SSTable (Sorted String Table). A separate write-ahead log protects against losing memtable data in a crash before it's flushed. Because a memtable write is just an in-memory insert, and a flush writes one large sorted file sequentially, LSM-trees turn the random-write problem that plagues B-trees into pure sequential I/O.

Deletes get special handling: Cassandra's documentation confirms it "treats a deletion as an insertion, and inserts a time-stamped deletion marker called a tombstone," which only gets physically removed later, during compaction, after a configurable grace period (ten days by default). And compaction itself, per Cassandra's docs, "collects all versions of each unique row and assembles one complete row, using the most up-to-date version (by timestamp)" across however many SSTables it's merging, after which "the old SSTables can be removed."

Here's a real, working simulation of exactly that lifecycle — a memtable that flushes at 4 keys, an overwrite, a delete, and a compaction that has to resolve both:

=== BATCH A: 4 writes fill the memtable exactly to its limit ===
PUT user:1 = 'Aditi'
PUT user:2 = 'Rohan'
PUT user:3 = 'Meera'
PUT user:4 = 'Karan'
  FLUSH: memtable hit 4 keys -> wrote SSTable #1: [('user:1', 'Aditi'), ('user:2', 'Rohan'), ('user:3', 'Meera'), ('user:4', 'Karan')]

=== BATCH B: an overwrite, a delete, and two new writes -> second flush ===
PUT user:5 = 'Zoya'
PUT user:2 = 'Rohan Verma'   (overwrites the value from Batch A)
DELETE user:1   (writes a tombstone, does not touch SSTable #1 on disk)
PUT user:6 = 'Ishaan'   (4th op in this batch -> triggers the flush)
  FLUSH: memtable hit 4 keys -> wrote SSTable #2: [('user:1', '<TOMBSTONE>'), ('user:2', 'Rohan Verma'), ('user:5', 'Zoya'), ('user:6', 'Ishaan')]

=== READ 'user:2' with two SSTables still separate (before compaction) ===
  Value returned: Rohan Verma
  (checked SSTable #2 first (newest); never had to open SSTable #1)

=== COMPACTION: merge SSTable #1 (older) with SSTable #2 (newer) ===
  COMPACT SSTable#1 + SSTable#2 -> merged table: [('user:2', 'Rohan Verma'), ('user:3', 'Meera'), ('user:4', 'Karan'), ('user:5', 'Zoya'), ('user:6', 'Ishaan')]
    tombstoned keys physically removed during this compaction: ['user:1']

=== READ 'user:1' after compaction (was deleted in Batch B) ===
  Value returned: None — tombstone honoured, key is now gone for good
=== READ 'user:2' after compaction (was overwritten in Batch B) ===
  Value returned: Rohan Verma — the newer value survived the merge
=== READ 'user:3' after compaction (untouched since Batch A) ===
  Value returned: Meera — original value, carried through unchanged

Notice the read of user:1 before compaction would have needed to check the memtable, then SSTable #2 (where it finds the tombstone and correctly reports nothing), and would only fall through to SSTable #1's stale 'Aditi' value if the tombstone-checking logic were buggy — which is exactly the bug this simulation surfaced on a first attempt, before the batches were restructured so the tombstone actually landed in a table that got compacted. After compaction, user:1 is gone for good, user:2 correctly kept its newer overwritten value, and user:3 passed through untouched. That's compaction doing its job: collapsing N sorted files down to fewer, while resolving every key to its single, current truth.

The actual trade-off: write amplification vs read amplification

A B-tree write that only touches one page is genuinely fast, but an update to an existing row still means finding that row's exact page (a random-access read) and rewriting it in place (a random-access write), and a page split that cascades upward can touch several pages for a single insert. An LSM-tree write is close to free — append to an in-memory structure and a sequential log — but that convenience is borrowed against later: reads may have to check the memtable and then multiple SSTables before finding a key (read amplification, visible directly in the simulation above), and compaction has to repeatedly re-read and re-write the same data as it merges tables together, which is its own form of write amplification, just deferred and done in efficient sequential batches instead of scattered random ones at write time.

Neither trade-off disappears; each engine just decides when to pay it. B-trees pay a little on every write, up front, in exchange for reads that are almost always a short, predictable number of page hits. LSM-trees make writes nearly free immediately and defer the real cost to a background compaction process and to reads that may need to check several files until enough compaction has happened to shrink that number back down.

Why Postgres chose one and Cassandra chose the other

Postgres is built for OLTP workloads: lots of individual row updates, strong consistency guarantees, and range queries ("give me all orders between these two dates") that a sorted B-tree answers by walking a contiguous run of leaf pages. Its update pattern is exactly what a B-tree is built for — read one row, change it, write it back — and it can afford the random I/O because a well-tuned Postgres instance keeps its working set of hot pages in memory (the buffer cache) most of the time anyway, turning many of those "random disk reads" into cheap RAM hits.

Cassandra is built for the opposite profile: extremely high write throughput, often with writes that are pure inserts or blind overwrites rather than read-modify-write cycles, spread across a cluster of commodity nodes, with eventual rather than strict consistency as an accepted trade-off. That workload is exactly what LSM-trees are built for — accept writes as fast as the disk can append sequentially, and push the cost of reconciling old and new data into a background compaction process that runs on its own schedule instead of blocking the write path.

How LSM reads avoid checking every SSTable

Checking every SSTable on every read, as the simplified simulation above does, doesn't scale once you have dozens of SSTables sitting around between compaction cycles. Real LSM implementations attach a Bloom filter — a compact, probabilistic structure that can say "this key is definitely not in this SSTable" with zero false negatives, letting a read skip most SSTables entirely without opening them — and Cassandra's SSTable metadata explicitly tracks this kind of per-table indexing information alongside timestamps and tombstone data. A Bloom filter can occasionally give a false positive ("might be in here"), which just costs one wasted lookup, but it never gives a false negative, so it's always safe to trust when it says no.

What this explains about behavior you've actually seen

You rarely pick a storage engine directly as an application developer, but the engine underneath explains symptoms you've probably hit without knowing why. A Cassandra cluster that suddenly gets slow and disk-hungry during a "compaction storm" is the background merge-and-rewrite process catching up on a backlog of SSTables — it's the deferred write amplification from earlier finally coming due. A Postgres table that keeps growing on disk even though row counts stay flat, needing periodic VACUUM, is a related but distinct symptom of the same underlying tension: B-tree pages left behind by updates and deletes need active reclamation because the engine chose to pay its cost on the write path rather than defer it to a background process the way an LSM-tree does.

Frequently Asked Questions