Crate hibit_tree

Source
Expand description

§Hibit tree1

Fixed-depth, K-ary2 tree3 with integer keys, that form bitmap hierarchy4.

  • Branchless O(1) access.
  • No tree balancing.
  • Ordered.
  • Tree act as a bitset/bitmap hierarchy. Bitmap hierarchy is a natural acceleration structure for intersection. Allows super-fast set-like operations: intersection, merge, etc.

§Data structure

See readme.

§Performance

Accessing element by index act as dereferencing N pointers (where N - number of levels in hierarchy). This is significantly faster then traversing tree with dynamic depth, since it does not involve any kind of branching.

Random insert have the same logic as random access, but with branching at each level.

Ordered iteration is fast. Traversing each hierarchy node is fast O(1) operation, which basically is just BMI’s pop_cnt/trail_cnt. There is no “scan” across node child items, for finding non-empty child/sub-tree.

Iteration of intersection between N trees in worst case scenario, where trees have keys located nearby (fit same terminal blocks), take N/block_width times of usual ordered iteration. In the best case scenario where nothing intersects, and this happens at the first levels - basically free. Hierarchical bitmap acts as acceleration structure for intersection. Branches/sub-trees that have no keys in common index-range discarded early.

§Inter HibitTree operations

As you can see HibitTree is a form of set/map, and hence, can be used for inter set operations, such as intersection, union, etc.

Due to the fact, that each hierarchy block supplemented with bitmask, finding intersection is just a matter of ANDing bitmasks.

§Laziness

All ops are LazyHibitTrees. Which means that tree is computed on the fly. If you need to iterate the result once or twice, or get() a few times - there is no need to save result into a concrete container. Otherwise - you may want to materialize it. Obviously, there is no need to materialize map that just return reference to object field.

Due to current limitations you can’t materialize references5.

§Exact hierarchy

“Exact hierarchy” - is a bitmap hierarchy, where each bitmask have exact emptiness info. All raised bits in bitmasks corresponds to non-empty childs. Or from the tree view: there can be no empty node in tree, except root.

You can have non-EXACT_HIERARCHY in LazyHibitTree. For example, lazy intersection.

Speeds up following operations:

§Flags

§simd

Enabled by default. Allow to use 128, 256 bit configurations.

§may_dangle

Requires nightly. Allow to store references in containers (TODO: not implemented). See rustonomicon.

  1. Hibit stands for hierarchical bitmap. ↩

  2. A.k.a. “N-ary”, a.k.a. “M-ary”. ↩

  3. Also, may be considered as form of radix tree, a.k.a. “prefix tree”, a.k.a. “trie”. ↩

  4. Bitmap hierarchy - is a hierarchy of bitmasks, where each raised bit in bitmask means, that child at corresponding bit index have data. See hi_sparse_bitset, hibitset. ↩

  5. But you can have &T containers in general. You’ll need may_dangle flag. ↩

Modules§

bit_queue
config
const_utils
ops
utils

Macros§

fun
Generates stateless generic UnaryFunction. Ala generic closure.

Structs§

HierarchyIndex
Range checked index, interpreted as a tree path.
Iter
HibitTree iterator.
ReqDefault
Marker for container’s item Default requirement.
Tree

Traits§

BitBlock
FromHibitTree
Construct a HibitTree collection from any HibitTree.
HibitTree
Hierarchical bitmap tree interface.
HibitTreeCursor
Stateful HibitTree traverse interface.
HibitTreeCursorTypes
HibitTreeCursor lifetime-dependent types.
HibitTreeTypes
HibitTree lifetime-dependent types.
LazyHibitTree
HibitTree that is not a concrete collection.
MultiHibitTree
HibitTree, where all Data types are Iterator<Self::IterItem>.
MultiHibitTreeTypes
MultiHibitTree lifetime-dependent types.
RegularHibitTree
HibitTree where all Data types are the same. Data = DataUnchecked = Cursor::Data.
RegularHibitTreeTypes
RegularHibitTree lifetime-dependent types.

Functions§

intersection
map
Maps each HibitTree element with UnaryFunction.
map_w_default
Same as map, but allows access to data_or_default methods.
multi_intersection
Intersection between multiple &RegularHibitTrees.
multi_union
Union between multiple &RegularHibitTrees.
multi_union_w_default
Same as multi_union but iterator will use data_or_default.
union
union_w_default
Same as union but iterator will use data_or_default.

Type Aliases§

HibitTreeData
MultiHibitTreeIterItem