MST.Tree (mst v0.1.0)

An in-memory Merkle Search Tree.

MST.Tree is the primary interface for building and querying MSTs. It pairs a root CID (or nil for an empty tree) with a block store that maps CIDs to decoded MST.Node structs.

All mutation operations (put/3, delete/3) return a new MST.Tree — the data structure is persistent/immutable. The underlying store accumulates all written nodes across mutations; stale nodes are not removed (no GC).

Example

store = MST.Store.Memory.new()
tree  = MST.Tree.new(store)

val = DASL.CID.compute("my record data")
{:ok, tree} = MST.Tree.put(tree, "collection/record-key", val)
{:ok, ^val} = MST.Tree.get(tree, "collection/record-key")

{:ok, tree} = MST.Tree.delete(tree, "collection/record-key")
{:error, :not_found} = MST.Tree.get(tree, "collection/record-key")

Summary

Types

store()

t()

tree_error()

Functions

collect_blocks(tree)

Collects all MST nodes reachable from the root into a map of CID → encoded bytes.

delete(tree, key)

Removes key from the tree.

from_root(root, store)

Returns a tree referencing an existing root node CID in the given store.

get(tree, key)

Looks up key in the tree.

length(tree)

Returns the number of key-value pairs in the tree.

new(store)

Returns a new, empty tree backed by the given store.

put(tree, key, value)

Inserts or updates key → value in the tree.

stream(tree)

Returns a lazy stream of {key, value_cid} pairs in sorted order.

to_list(tree)

Returns all key-value pairs in the tree as a sorted list.

Types

store()

@type store() :: MST.Store.t()

t()

@type t() :: %MST.Tree{root: DASL.CID.t() | nil, store: store()}

tree_error()

@type tree_error() :: {:error, atom()}

Functions

collect_blocks(tree)

@spec collect_blocks(t()) ::
  {:ok, %{required(DASL.CID.t()) => binary()}} | tree_error()

Collects all MST nodes reachable from the root into a map of CID → encoded bytes.

Useful for serialising the tree to a CAR file.

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> val = DASL.CID.compute("x")
iex> {:ok, tree} = MST.Tree.put(tree, "col/a", val)
iex> {:ok, blocks} = MST.Tree.collect_blocks(tree)
iex> map_size(blocks) >= 1
true

delete(tree, key)

@spec delete(t(), binary()) :: {:ok, t()} | {:error, :not_found} | tree_error()

Removes key from the tree.

Returns {:ok, new_tree} on success, {:error, :not_found} if the key does not exist.

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> val = DASL.CID.compute("data")
iex> {:ok, tree2} = MST.Tree.put(tree, "col/key", val)
iex> {:ok, tree3} = MST.Tree.delete(tree2, "col/key")
iex> MST.Tree.get(tree3, "col/key")
{:error, :not_found}

from_root(root, store)

@spec from_root(DASL.CID.t() | nil, store()) :: t()

Returns a tree referencing an existing root node CID in the given store.

Use this to wrap an already-populated store (e.g. after loading from a CAR file).

Examples

iex> store = MST.Store.Memory.new()
iex> node = MST.Node.empty()
iex> {:ok, cid} = MST.Node.cid(node)
iex> store = MST.Store.put(store, cid, node)
iex> tree = MST.Tree.from_root(cid, store)
iex> tree.root == cid
true

get(tree, key)

@spec get(t(), binary()) :: {:ok, DASL.CID.t()} | {:error, :not_found} | tree_error()

Looks up key in the tree.

Returns {:ok, value_cid} if found, {:error, :not_found} otherwise.

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> MST.Tree.get(tree, "col/key")
{:error, :not_found}

length(tree)

@spec length(t()) :: {:ok, non_neg_integer()} | tree_error()

Returns the number of key-value pairs in the tree.

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> {:ok, 0} = MST.Tree.length(tree)
iex> val = DASL.CID.compute("x")
iex> {:ok, tree} = MST.Tree.put(tree, "col/a", val)
iex> MST.Tree.length(tree)
{:ok, 1}

new(store)

@spec new(store()) :: t()

Returns a new, empty tree backed by the given store.

Examples

iex> tree = MST.Tree.new(MST.Store.Memory.new())
iex> tree.root
nil

put(tree, key, value)

@spec put(t(), binary(), DASL.CID.t()) :: {:ok, t()} | tree_error()

Inserts or updates key → value in the tree.

Returns {:ok, new_tree} on success. The new tree shares the store with the old tree, but both may be used independently — nodes are append-only.

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> val = DASL.CID.compute("data")
iex> {:ok, tree2} = MST.Tree.put(tree, "col/key", val)
iex> MST.Tree.get(tree2, "col/key")
{:ok, val}

stream(tree)

@spec stream(t()) :: Enumerable.t()

Returns a lazy stream of {key, value_cid} pairs in sorted order.

The stream reads nodes from the store on demand. Raises on missing nodes (consistent with lazy stream semantics).

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> val = DASL.CID.compute("x")
iex> {:ok, tree} = MST.Tree.put(tree, "col/a", val)
iex> tree |> MST.Tree.stream() |> Enum.to_list()
[{"col/a", val}]

to_list(tree)

@spec to_list(t()) :: {:ok, [{binary(), DASL.CID.t()}]} | tree_error()

Returns all key-value pairs in the tree as a sorted list.

Examples

iex> store = MST.Store.Memory.new()
iex> tree = MST.Tree.new(store)
iex> val = DASL.CID.compute("data")
iex> {:ok, tree} = MST.Tree.put(tree, "col/b", val)
iex> {:ok, tree} = MST.Tree.put(tree, "col/a", val)
iex> {:ok, pairs} = MST.Tree.to_list(tree)
iex> Enum.map(pairs, &elem(&1, 0))
["col/a", "col/b"]