The problem
Incremental B+Tree maintenance is expensive: splits and merges, and in the worst case a single insert forces rebalancing the whole tree 1:16:12.
The idea
Absorb updates in a buffer and apply them in batches only when forced. 1:16:12
- Names: write-optimized B+Tree, fractal tree (Wikipedia's term), Bε tree; invented by a researcher out of Stony Brook
1:16:37. - Same log-structured pattern as the LSM tree covered earlier, and as MySQL's compression scheme, which put a mod log in front of every page so inserts didn't require decompressing everything. Log-structuring recurs everywhere in a DBMS
1:16:37.
Mechanics
Every node carries a mod log 1:16:37:
- Insert → write the entry into the mod log if there is space. No traversal to the leaf. Fast, like appending to an LSM log
1:16:371:17:37. - Delete → also just a mod-log entry; the key stays physically present at the leaf but is logically deleted
1:17:371:18:20. - Lookup → check the mod log at each node from the root down; if the key's fate is recorded there, stop immediately, otherwise continue the normal descent
1:17:581:18:20. - Mod log full → push its entries down one level, routing each entry left or right by its key; they get absorbed by the child's mod log, recursively cascading if that one is full too. This cascading is why it's called a fractal tree
1:18:34. - At the leaf → the buffered inserts/deletes are finally applied, and normal B+Tree rebalancing kicks in if the leaf underflows
1:19:571:20:27.
Systems that used it
| System | Status |
|---|---|
| TokuTech / TokuDB | built entirely on fractal trees; acquired by Percona, became "extra DB" for MySQL, eventually died 1:19:12 |
| "SSDB"-style project out of China | also dead 1:19:12 |
| SplinterDB (VMware) | the most famous current user; used by an AI-adjacent speaker's system, not heavily advertised 1:19:12 |
| A new system out of China ("chomo") | claims Bε trees 1:19:12 |