merkle-db.index
The data tree in a table is a B+ tree variant which orders the partitions into a sorted branching structure.
The branching factor determines the maximum number of children an index node in the data tree can have. Internal (non-root) index nodes with branching factor b
will have between ceil(b/2)
and b
children.
An empty data tree is represented by a nil link from the table root. A data tree with fewer records than the partition limit is represented directly by a single partition node.
build-tree
(build-tree store params children)
Build an index tree from a sequence of child nodes, using the given parameters. Returns the final, persisted root node data.
find-partition-range
(find-partition-range store node min-k max-k)
Find partitions which cover the range min-k
to max-k
.
read-all
(read-all store node fields)
Read a lazy sequence of key/map tuples which contain the requested field data for every record in the subtree. This function works on both index nodes and partitions.
read-batch
(read-batch store node fields record-keys)
Read a lazy sequence of key/map tuples which contain the requested field data for the records whose keys are in the given collection. This function works on both index nodes and partitions.
read-range
(read-range store node fields min-k max-k)
Read a lazy sequence of key/map tuples which contain the field data for the records whose keys lie in the given range, inclusive. A nil boundary includes all records in that range direction.
update-tree
(update-tree store params root changes)
Apply a set of changes to the index tree rooted in the given node. The changes should be a sequence of record ids to either data maps or patch tombstones. Parameters may include :merkle-db.partition/limit
and :merkle-db.data/families
. Returns an updated persisted root node if any records remain in the tree.