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_KEYSkeys 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
BTreeSetand 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
| operation | cost |
|---|---|
RankTree::insert, RankTree::remove | O(log N) |
RankTree::rank_of, RankTree::select | O(log N) |
RankTree::partition_point, RankTree::count_in | O(log N) |
RankTree::range, RankTree::iter_from | O(log N) seek + O(1) amortised per item |
RankTree::iter, RankTree::iter_rev | O(1) amortised per item |
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::iterorcrate::RankTree::iter_from. - IterRev
- Reverse (descending) iterator. Created by
crate::RankTree::iter_revorcrate::RankTree::iter_rev_from. - Range
- The keys inside a range, ascending. Created by
crate::RankTree::range. - Rank
Tree - An ordered set of
Kwith O(log N) order statistics (rank / select).