B-Trees vs LSM Trees: How Databases Keep Data Sorted on Disk

The B+ tree. The data is split into fixed-size pages (often 4 to 16 KB). Each internal page holds many keys and pointers, so the tree is very wide and very shallow. With about 500 keys per page, three levels reach 500 x 500 x 500 = 125 million entries, and four levels reach 62.5 billion. A lookup is therefore three or four page reads, and the top levels stay in memory.

What a B+ tree does on a write. It finds the right leaf page and changes it in place. When the page is full, it splits into two and pushes a key up to the parent. Leaves are linked in order, so a range scan walks the leaf chain. Because pages are overwritten, a crash in the middle could leave a half-written page, so engines log the change first in a write-ahead log.

The LSM tree. A write is appended to a log (for crash safety) and inserted into a sorted in-memory table, the memtable. When the memtable is full, it is written out as one immutable sorted file, an SSTable. Nothing on disk is ever edited, so writes are sequential and fast. Many files pile up, so a background compaction merges them into fewer, bigger ones.

Reading an LSM tree. Check the memtable, then the files from newest to oldest, and stop at the first hit. To avoid opening files that cannot hold the key, each file carries a Bloom filter (a compact set that can say 'definitely not here') and a sparse index. A delete cannot erase an old copy in an older file, so it writes a tombstone marker that hides the key until compaction drops both.

memtable, sstables = {}, []        # sstables: newest last, each a sorted list of (key, value)

def put(key, value, limit=2):
    memtable[key] = value          # value None is a tombstone (a delete)
    if len(memtable) >= limit:
        sstables.append(sorted(memtable.items()))
        memtable.clear()

def get(key):
    if key in memtable:
        return memtable[key]
    for table in reversed(sstables):          # newest file first
        for k, v in table:
            if k == key:
                return v
    return None

def compact():
    merged = {}
    for table in sstables:                    # oldest first, so newer values win
        merged.update(dict(table))
    sstables[:] = [sorted((k, v) for k, v in merged.items() if v is not None)]

for k, v in [('a', 1), ('b', 2), ('c', 3), ('a', 10), ('b', None), ('d', 4), ('e', 5)]:
    put(k, v)
print(len(sstables), 'files, memtable holds', memtable)  # 3 files, memtable holds {'e': 5}
print(get('a'), get('b'), get('c'))                      # 10 None 3  (b was deleted)
compact()
print(sstables)                                          # [[('a', 10), ('c', 3), ('d', 4)]]

The three amplifications. Every design trades three costs. Write amplification is how many bytes reach disk per byte you wrote: compaction rewrites data many times, and a B+ tree rewrites a whole page for a small change. Read amplification is how many places a read must look. Space amplification is how much extra room old versions and half-empty pages take. LSM trees favor writes; B+ trees favor predictable reads.

The skip list. A skip list is a sorted linked list with express lanes. Each new node is given a random height by flipping a coin until tails, so about half the nodes reach level 2, a quarter reach level 3, and so on. A search starts in the top lane, runs forward until the next key is too big, drops down a lane, and repeats. That gives expected O(log n) search and insert with no rebalancing, and it is easy to make safe for concurrent writers, which is why it is a popular memtable.

Choosing. Read-heavy workloads with many point lookups and updates in place fit a B+ tree (most relational databases). Write-heavy ingestion, logs and time series fit an LSM tree (many key-value and wide-column stores). Many systems expose both and let you choose per table. Whichever you pick, you will meet the same ideas in the levels: sorted structure, a log for safety, and background maintenance.