Struct Tree 

pub struct Tree<S> { /* private fields */ }

A merkle search tree data structure, backed by storage implementing AsyncBlockStoreRead and optionally AsyncBlockStoreWrite.

This data structure is merely a convenience structure that implements algorithms that handle certain common operations one may want to perform against a MST.

The structure does not actually load the merkle search tree into memory or perform any deep copies. The tree itself lives entirely inside of the provided backing storage. This also carries the implication that any operation performed against the tree will have performance that reflects that of accesses to the backing storage.

If your backing storage is implemented by a cloud service, such as a database or block storage service, you will likely want to insert a caching layer in your block storage to ensure that performance remains fast.

---

There are two factors that determine the placement of nodes inside of a merkle search tree:

• The number of leading zeroes in the SHA256 hash of the key
• The key’s lexicographic position inside of a layer

Reference

• Official documentation: https://atproto.com/guides/data-repos
• Useful reading: https://interjectedfuture.com/crdts-turned-inside-out/

Implementations

impl<S: AsyncBlockStoreRead + AsyncBlockStoreWrite> Tree<S>

pub async fn create(storage: S) -> Result<Self, Error>

Create a new MST with an empty root node

pub async fn add(&mut self, key: &str, value: Cid) -> Result<(), Error>

Add a new key with the specified value to the tree.

pub async fn update(&mut self, key: &str, value: Cid) -> Result<(), Error>

Update an existing key with a new value.

pub async fn delete(&mut self, key: &str) -> Result<(), Error>

Delete a key from the tree.

impl<S: AsyncBlockStoreRead> Tree<S>

pub fn open(storage: S, root: Cid) -> Self

Open a pre-existing merkle search tree.

This is a very cheap operation that does not actually load the MST or check its validity. You should only use this with data from a trusted source.

pub fn root(&self) -> Cid

Return the CID of the root node.

pub async fn depth(&mut self, node: Option<Cid>) -> Result<Option<usize>, Error>

Compute the depth of the merkle search tree from either the specified node or the root

pub fn export(&mut self) -> impl Stream<Item = Result<Cid, Error>> + '_

Returns a stream of all CIDs in the tree or referenced by the tree.

pub fn entries( &mut self, ) -> impl Stream<Item = Result<(String, Cid), Error>> + '_

Returns a stream of all entries in this tree, in lexicographic order.

This function will not work with a partial MST, such as one received from a firehose record.

pub fn entries_prefixed<'a>( &'a mut self, prefix: &'a str, ) -> impl Stream<Item = Result<(String, Cid), Error>> + 'a

Returns a stream of all keys starting with the specified prefix, in lexicographic order.

This function will not work with a partial MST, such as one received from a firehose record.

pub fn keys(&mut self) -> impl Stream<Item = Result<String, Error>> + '_

Returns a stream of all keys in this tree, in lexicographic order.

This function will not work with a partial MST, such as one received from a firehose record.

pub fn keys_prefixed<'a>( &'a mut self, prefix: &'a str, ) -> impl Stream<Item = Result<String, Error>> + 'a

Returns a stream of all keys in this tree with the specified prefix, in lexicographic order.

This function will not work with a partial MST, such as one received from a firehose record.

pub async fn get(&mut self, key: &str) -> Result<Option<Cid>, Error>

Returns the specified record from the repository, or None if it does not exist.

pub async fn extract_path( &mut self, key: &str, ) -> Result<impl Iterator<Item = Cid>, Error>

Returns the full path to a node that contains the specified key (including the containing node).

If the key is not present in the tree, this will return the path to the node that would’ve contained the key.

This is useful for exporting portions of the MST for e.g. generating firehose records.

Trait Implementations

impl<S: Clone> Clone for Tree<S>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<S> Debug for Tree<S>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.