A prolly tree is similar to a B+ tree, but its node boundaries are determined by the data rather than by insertion order. Each node is addressed by the hash of its contents, and updates create a new root while sharing unchanged nodes with older versions.
This makes it useful when an application needs more than basic key/value storage: cheap snapshots, efficient diffs, three-way merges, deduplication, and incremental sync between replicas.
Some use cases I’m exploring include local-first applications, versioned database indexes, Git-like filesystem snapshots, agent memory and event logs, and reproducible RAG indexes where the exact data snapshot used for an answer can be recorded.
It’s a storage primitive rather than a complete database. The goal is to provide the ordered-map layer and let applications choose their own storage backend, data model, and conflict policy.
The project is still evolving, and I’d appreciate feedback—especially about real-world use cases, the API, and what is missing.
Great primitive, I’m a big fan of prolly trees! You mentioned git like filesystem snapshots? How would you retrofit that on an existing filesystem? Or you’re talking about writing a new one?
This is pretty neat. How long did it take for you to implement the core basics?
Upon insertion do you incrementally build the tree, or do you rebuild it from scratch?
How did you ensure the distribution of nodes was about the same with the chunker?
Is there any reason why you only target sse2 for simd acceleration? You're leaving a lot of performance on the table.
I’ve been working on Prolly, a Rust implementation of a content-addressed ordered map built on prolly tree(intro from dolthub https://www.dolthub.com/docs/architecture/storage-engine/pro...)
A prolly tree is similar to a B+ tree, but its node boundaries are determined by the data rather than by insertion order. Each node is addressed by the hash of its contents, and updates create a new root while sharing unchanged nodes with older versions.
This makes it useful when an application needs more than basic key/value storage: cheap snapshots, efficient diffs, three-way merges, deduplication, and incremental sync between replicas.
Some use cases I’m exploring include local-first applications, versioned database indexes, Git-like filesystem snapshots, agent memory and event logs, and reproducible RAG indexes where the exact data snapshot used for an answer can be recorded.
It’s a storage primitive rather than a complete database. The goal is to provide the ordered-map layer and let applications choose their own storage backend, data model, and conflict policy.
The project is still evolving, and I’d appreciate feedback—especially about real-world use cases, the API, and what is missing.
Great primitive, I’m a big fan of prolly trees! You mentioned git like filesystem snapshots? How would you retrofit that on an existing filesystem? Or you’re talking about writing a new one?