A B Tree With Buffers
A fractal tree index is a B tree variant where each internal node carries a message buffer alongside its child pointers. A write is not pushed straight to a leaf. Instead it is appended as a message into the buffer of the root node.
Cascading Flushes
When a node buffer fills, its messages are flushed down to the buffers of the relevant children in one batched, sequential write. Eventually messages reach the leaves and apply there.
- A single write touches only one buffer near the top, so it is cheap.
- Many writes share the cost of moving a node worth of messages downward.
- This turns scattered updates into large sequential transfers.
Reads
A lookup walks from the root to a leaf as in a B tree, but it must also apply any pending messages it passes in node buffers. Because the tree stays B tree shaped, a read still touches a logarithmic number of nodes.
Why It Matters
Fractal trees achieve write throughput closer to an LSM tree while keeping the predictable, low read amplification of a B tree, and they support rich indexes and range scans naturally.
Key idea
A fractal tree buffers writes in internal nodes and cascades them downward in batches, blending LSM like write speed with B tree like read cost.