Module banyan::index [−][src]
Expand description
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
fully in memory representation of a branch node
index for a branch node, containing summary data for its children
fully in memory representation of a leaf node
index for a leaf node, containing keys and some statistics data for its children
A sequence of unit values, in case you want to create a tree without a summary
A trivial implementation of a CompactSeq as just a Seq.
Enums
Traits
a compact representation of a sequence of 1 or more items
An object that can compute a summary of type T of itself