Skip to main content

Crate kevy_ranktree

Crate kevy_ranktree 

Source
Expand description

kevy-ranktree — an order-statistic ordered set: a hand-written B-tree whose every node carries its subtree element count, so rank queries (“what position is this key at?”) and select queries (“what key is at position k?”) are single O(log N) descents instead of linear walks.

This is the structure std::collections::BTreeSet cannot be: std’s tree is not augmentable, so Iterator::position over it is the only way to a rank — O(N). Here each node’s total field turns the same descent that finds a key into the arithmetic that counts everything to its left.

§Why a counted B-tree and not a spanned skiplist

Redis solves the same problem with a skiplist whose forward pointers carry spans. Both give O(log N) rank/select; the B-tree was chosen because:

  • Cache behaviour — a node holds up to node::MAX_KEYS keys in one contiguous buffer, so a descent touches ~log₈(N) cache lines where a skiplist chases one pointer per level and per element during range walks. Ordered full scans (persistence rewrites, snapshots) iterate arrays, not linked nodes.
  • No probabilistic balance — a skiplist needs a random level generator and its worst case is only expected-O(log N); the B-tree’s bounds are deterministic.
  • It matches what it replaces — the callers previously held a BTreeSet and were tuned for its iteration pattern; this keeps that pattern and adds the rank arithmetic.

The price is B-tree deletion (borrow/merge rebalancing), which is more code than a skiplist unlink — it lives in remove.rs and is held down by an exhaustive random-operation oracle test (tests/oracle.rs) that replays thousands of insert/remove/rank/select/range operations against a sorted-Vec reference.

§Complexity

Constraints: pure Rust, zero dependencies, no_std-capable behind the alloc feature, #![forbid(unsafe_code)].

use kevy_ranktree::RankTree;

let t: RankTree<u32> = [50, 10, 40, 20, 30].into_iter().collect();
assert_eq!(t.rank_of(&40), Some(3), "rank: how many keys sort before it");
assert_eq!(t.select(1), Some(&20), "select: the key at a rank");
assert_eq!(t.range(&(15..45)).copied().collect::<Vec<_>>(), vec![20, 30, 40]);
assert_eq!(t.count_in(&(15..45)), 3, "counted, not walked");

Structs§

Iter
Forward (ascending) iterator. Created by crate::RankTree::iter or crate::RankTree::iter_from.
IterRev
Reverse (descending) iterator. Created by crate::RankTree::iter_rev or crate::RankTree::iter_rev_from.
Range
The keys inside a range, ascending. Created by crate::RankTree::range.
RankTree
An ordered set of K with O(log N) order statistics (rank / select).