Expand description
Adaptive radix trie implementation
References
- Leis, V., Kemper, A., & Neumann, T. (2013, April). The adaptive radix tree: ARTful indexing for main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE) (pp. 38-49). IEEE. Link to PDF
Modules
Module containing implementations of the
TreeMap and associated
iterators/etc.A tagged pointer is a pointer (concretely a memory address) with additional
data associated with it, such as an indirection bit or reference count. This
additional data is often “folded” into the pointer, meaning stored inline in
the data representing the address, taking advantage of certain properties of
memory addressing.
Utilities for inspecting the trie structure.
Structs
The results of a successful delete operation
The common header for all inner nodes
Node that references between 17 and 49 children
An iterator over all the children of a
InnerNode48.Node that references between 49 and 256 children
An iterator over all the children of a
InnerNode256.Node type that has a compact representation for key bytes and children
pointers.
An iterator all the children of an
InnerNodeCompressed.An iterator over all the
LeafNodes in a non-singleton tree.Attempted to insert a key which was a prefix of an existing key in
the tree.
The results of a successful tree insert
This struct contains the results from searching for an insert point for
a new node in the tree.
Node that contains a single leaf value.
An opaque pointer to a
Node.A restricted index only valid from 0 to LIMIT - 1.
An ordered map based on an adaptive radix tree.
The error type returned when attempting to construct an index outside the
accepted range of a PartialNodeIndex.
Enums
An enum that encapsulates pointers to every type of Node
A generic iterator that uses specific iterators for each
NodeType (excluding leaves) inside.The type of insert
The representation of inner nodes
An iterator over all the leaves in a tree.
Constants
The number of bytes stored for path compression in the node header.
Traits
Any type implementing
AsBytes can be decomposed into bytes.Common methods implemented by all inner node.
This trait is used to mark types which have a byte representation which is
guaranteed to not be a prefix of any other value of the same type.
All nodes which contain a runtime tag that validates their type.
This trait is used to mark types where the lexicographic ordering of their
byte representation (as output by
AsBytes::as_bytes) matches their
normal ordering (as determined by Ord).Functions
Deallocate the given node and all children of the given node.
Find and delete the maximum leaf in the tree, returning the maximum
LeafNode.Find and delete the minimum leaf in the tree, returning the minimum
LeafNode.Removes a key from the tree, returning the
LeafNode corresponding to the
key if the key was previously in the tree.Insert the given key-value pair into the tree.
Search for the leaf with the maximum key, by lexicographic ordering.
Search for the leaf with the minimum key, by lexicographic ordering.
Perform an iterative search for the insert point for the given key,
starting at the given root node.
Search in the given tree for the value stored with the given key.
Type Definitions
Node that references between 2 and 4 children
Node that references between 5 and 16 children