Module banyan::index

The index data structures for the tree

In order to have good storage and query efficiency, indexes contain sequences of keys instead of on individual keys. To support a key type in banyan trees, you need to define how a sequence of keys is stored in memory and on persistent storage, by implementing CompactSeq for the key type, and define how keys are combined to compute summaries, by implementing Semigroup for the key type.

If you just want to quickly get things working, you can use SimpleCompactSeq, which is just a vec.

Indexes are structured in such a way that key data is stored closer to the root than value data.

Indexes

Indexes contain an optional link to children/data, and some additonal information. An index that no longer has a link to its children/data is called purged.

There are two kinds of indexes.

Leaf indexes

Leaf indexes contain the actual keys for a leaf. This is not redundant data that can be recomputed from the values. Leaf indexes have a level of 0.

Invariants

A leaf index must contain exactly the same number of keys as there are values.

Branch indexes

Branch indices contain summaries for their children. This is redundant data that can be recomputed from the children. Branch indexes have a level of max(level of children) + 1.

Invariants

For a sealed branch, the level of all its children is exactly level-1. For an unsealed branch, the level of all children must be smaller than the level of the branch.

Structs

Branch	fully in memory representation of a branch node
BranchIndex	index for a branch node, containing summary data for its children
Leaf	fully in memory representation of a leaf node
LeafIndex	index for a leaf node, containing keys and some statistics data for its children

Enums

Index	enum for a leaf or branch index
IndexRef	enum for a leaf or branch index

Traits

CompactSeq

a compact representation of a sequence of 1 or more items