This module implements
MerkleBIT with an attached storage module. The implemented
RocksTree structures allow use with persistence in memory and storage respectively. Write
operations are batched together and committed at the end of each insert op. The
abstracts all actions related to maintaining and updating the storage tree. The public APIs are
- and the associated function
After each call to either
insert_one, a new root hash will be created which can be
later used to access the inserted items.
Branch node contains first a
which indicates which bit of a given hash should be used to traverse the tree. This is an optimisation
that makes this a sparse merkle tree. It then contains pointers
to either the
one side of the tree or the
zero side of the tree. Additionally, a branch contains
a copy of the
key used during creation to determine if a branch should be inserted before it, and
count of the nodes under that branch.
Leaf node contains an associated
key for comparison, and a pointer to a
Data node for retrieving
information regarding access to the data. This is separate from the
Data node for the purpose of only
accessing data information if data should be retrieved.
Data node contains the actual information to be retrieved.
Data nodes can be arbitrary in size
and the only restriction is that the data must be serializable and deserializable.
To illustrate these concepts, please refer to the diagram below:
---------------------- branch ---> | split_index: usize | | | zero: [u8] | ---------------- / \ | one: [u8] | | key: [u8] | / \ | count: u64 | | data: [u8] | <---- leaf leaf | key: [u8] | ---------------- | ---------------------- | V data | V ------------------ | value: Vec<u8> | ------------------
MerkleBIT can be extended to support a wide variety of backend storage solutions given that
you make implementations for the
Defines constants for the tree.
An implementation of the
Contains the actual operations of inserting, getting, and removing items from a tree.
Contains the traits necessary for tree operations
Contains a collection of structs for representing locations within the tree.
Contains a collection of structs for implementing tree databases.
Contains a collection of structs for implementing hashing functions in the tree.
Contains a collection of useful structs and functions for tree operations.