You are in my Digital Garden.

Prolly Tree

Last modified: Sep 11th, 2026

Like a merkle tree and a B-tree had a baby.

Notes

It’s the same as a Merkle Search Tree
- Specifically it’s the same idea and has the same properties, but the implementation is different
The shape of the tree is insert-order independent, this is the big difference with B-trees
- “A set of items has a unique deterministic representation” - MST paper
Each tree node is content-addressed
Root node address is hash of whole tree
Two hashes: a hash (later discarded) to determine chunk boundaries, and then a separate hash to get the chunk/node address
Key concept: recursive chunking
Only leaf nodes at the bottom of the tree hold keys, the other nodes just hold references to keys – like a B+ tree
Internal nodes are also stored in the content-addressed storages
- Along with leaf nodes, obviously
- This allows a tree to be reconstructured from a root hash, by repeatedly looking up addresses in the storage
Dolt uses this to create version-controlled database because it combined a necessary database structure (B-trees) with properties like immutability, fast diffs, deduplication
Like a Merkle tree designed for querying
Like a B-tree was content-addressed