B-trees are older, more widely deployed, and take the opposite approach to the same problem. They are the default index in PostgreSQL, MySQL, SQLite, Oracle, SQL Server — most of the databases running most of the world’s transactions.
Where an LSM-tree writes new files and merges them later, a B-tree updates pages in place.
The structure
The database file is divided into fixed-size pages, traditionally 4KB. One page is the root. Every page holds keys in sorted order, and each key sits between two references to child pages.
[ 100 | 500 ]
/ | \
<100 100-499 >=500To find key 250: start at the root, see that 250 falls between 100 and 500, follow that child, repeat until you reach a leaf page holding the actual value.
The number of children a page can hold is its branching factor, typically in the hundreds because a 4KB page holds a lot of keys and pointers. That is what makes the tree so shallow: with a branching factor of 500, four levels address 500⁴ ≈ 62 billion keys.
The idea
A B-tree lookup is O(log n) with a very large base, which in practice means three or four page reads for almost any dataset. The upper levels stay cached in memory, so a typical point read costs about one disk access — and it costs that whether the table holds a thousand rows or a billion.
Writes, and the split
Updating a value: find the leaf page, change the bytes, write the page back.
Inserting into a page with no room left is where it gets interesting. The page splits: its contents are divided into two half-full pages, and a reference to the new page is inserted into the parent. If the parent is also full, it splits too, and the cascade can reach the root — which is how the tree grows a level, and why it stays balanced.
The three amplifications
Comparing storage engines comes down to three numbers, and every engine trades one against the others.
Write amplification — bytes physically written per byte of data you asked to store. A B-tree writes the page plus the WAL entry, and occasionally splits, so roughly 2-3×. An LSM-tree rewrites each record once per compaction level it passes through, so it grows with the number of levels.
Read amplification — disk reads per lookup. A B-tree reads one page per level, with the upper levels cached, so near 1. An LSM-tree may probe several levels, though Bloom filters skip most of them.
Space amplification — bytes stored per byte of live data. B-trees leave pages part-empty so inserts have somewhere to go, and fragment over time. LSM holds superseded versions until compaction reclaims them.
You cannot minimise all three. Pick two, and pay for the third.
Find the crossover
Workload
How the operations actually split. Most OLTP sits well to the read side.
More levels holds more data, and rewrites each record once more on its way down.
How much bigger each level is than the one above. Larger means rarer, heavier merges.
B-tree suits this workload
Reads dominate. One authoritative page per key beats probing several levels, and the write path never has to catch up on merges.
Turn Bloom filters off and watch LSM read amplification climb with every level — that one checkbox is why LSM engines are usable for point lookups at all. Push writes to 100% and the ordering flips, which is the entire argument in one drag.
Push writes toward 100% and LSM wins; push toward reads and the B-tree does. Uncheck Bloom filters and watch the LSM read cost climb with every level. Increase the size ratio and space amplification rises while write amplification falls — that is the compaction-strategy knob real engines expose, and it is a genuine trade rather than a setting with a right answer.
What the model does not capture
The simulator compares mechanical costs. Several real considerations sit outside it:
Transactions. A B-tree has exactly one authoritative location per key, which makes range locks and serialisable isolation comparatively natural. LSM engines can and do implement transactions, but a key existing in several places at once makes it harder work.
Latency predictability. B-tree latency is steady and boring. LSM latency is usually better and occasionally much worse, when a large compaction is competing for I/O. If your SLO is on p99.9, “usually faster” may lose to “never surprising” — which is the argument from Module 1, arriving here.
Operational surface. LSM engines expose compaction strategies, level sizes, and write-stall thresholds. That is real tuning capability and real ongoing work. B-trees have far fewer knobs, which is a feature when nobody has time to tune anything.
Check yourself
A system ingests 50,000 sensor readings per second and serves dashboards querying time ranges for one sensor. Which engine, and why?
What to take away
B-trees and LSM-trees solve the same problem from opposite directions: authoritative pages updated in place, versus immutable files merged in the background. Both keep a log for durability. Choose on the ratio of your workload and on how much latency variance you can tolerate — then measure, because the crossover moves with your data.