13 releases (8 breaking)
|0.10.1||Jan 9, 2022|
|0.9.0||Jul 15, 2021|
|0.2.2||Mar 25, 2021|
#1063 in Data structures
31 downloads per month
Banyan trees are the trees with the widest canopy. They also sprout new roots, which after some time can become indistinguishable from the original root. Seems appropriate.
- fat leafs, containing as much data as possible and being roughly the same size
- low depth, fat branches
- quick traversal, filtering and random access
cheap append(possible, but would require more complex interaction with block store)
- no insert/splice
- possibility for removal
The tree should have a structure that is fully determined by the content, unlike e.g. a balanced tree which has a memory of its history.
It should support append and bulk append.
A node is split into two parts. An index part that lives in the parent for quick access, and a value part that is linked from the parent.
Leafs are the biggest things. The builder incrementally encodes and compresses data. The state of a builder should at any time be able to be persisted. The storage format should be also incremental (adding stuff at the end does not require changes at the start)
Whereas leafs are always appended to, branches are most of the time updated at their last index. Branches are stored as valid IPLD so they can be traversed by ipfs. The non-link data is zstd compressed cbor.