A modded Prolly-tree implementation in Typescript.
- Efficient diff - yields entry and bucket diffs!
- Powerful cursor api - climb 🌳s like a pro
- Structural validation - codec is aware of tree context
It's in a decent state but have not done performance analysis. API breaks will result in major version change.
I haven't tested with non-local blockstores. Things may not work well with networked blockstores.
This package implements a modded prolly-tree in Typescript. Most relevant code is in src/mutate.ts and src/diff.ts.
mods:
- (number, uint8array) tuples for keys
- right-side backbone
- key-defined boundaries instead of rolling-hash
npm install prollipop
pnpm install && pnpm build
See usage.test.ts!!!
API docs
Example database
As you can see from the list below, a lot of ideas have been stolen from the Dolt project's blog so be sure to check them out!
-
Prolly Tree PoC and technical writeup
- author: ABresting
- implementation: Prolly-tree-Waku-Message
- relevance: Custom implementation of prolly-tree with right side backbone
-
Merklizing the key/value store for fun and profit
- author: Joel Gustafson
- implementation: okra-js
- relevance: content-defined merkle trees: A node is the first child of its parent if u32(node.hash[0..4]) < (2^32 / Q).
-
Range-Based Set Reconciliation
- author: Doug Hoyte
- relevance: Negantrophy section uses [number, hash] tuples as keys