columnar/adts/art.rs
1//! Adaptive Radix Trees (https://db.in.tum.de/~leis/papers/ART.pdf).
2//!
3//! This ADT represents an unordered collection of byte sequences as a tree.
4//! Like a trie, the paths down the tree correspond to byte sequences, and
5//! the membership of a byte sequence is determined by the a viable path.
6
7/// An ART node exists in the context of a sequence of bytes, and indicates
8/// the possible options based on the next byte in the sequence.
9pub enum ArtNode {
10 /// Some of the bytes continue to further nodes, but many do not.
11 Some(Box<[(u8, ArtNode)]>),
12 /// Many of the bytes continue to further nodes, although some may not.
13 /// If a node is `None`, it didn't actually go anywhere.
14 /// The representation exists to be more economical than the `Some` variant.
15 /// This is especially true if the associated `ArtNode` size is small, which
16 /// it is not in this case, but will be once we flatten it.
17 Many(Box<[ArtNode; 256]>),
18 /// Indicates that there are no branching points for the next few bytes,
19 /// after which the next node is provided.
20 Path(Box<[u8]>, Box<ArtNode>),
21 /// Nothing to see here.
22 None,
23}
24
25/// A mock-up of what you would store for each `ArtNode` above, when columnar.
26pub enum ArtIdx {
27 Some(usize),
28 Many(usize),
29 Path(usize),
30 None,
31}
32
33
34pub struct ArtNodes {
35 // pub inner: Results<Results< , >, Results< , >>,
36}