Crate wabi_tree 

Order-statistic B-tree collections for Rust.

This crate provides OSBTreeMap and OSBTreeSet, which are drop-in replacements for the standard library’s BTreeMap and BTreeSet with additional O(log n) order-statistic operations:

• get_by_rank - Get the element at a given sorted position
• rank_of - Get the sorted position of a key
• Indexing by Rank - e.g., map[Rank(0)] for the first element

Example

use wabi_tree::{OSBTreeMap, Rank};

let mut scores = OSBTreeMap::new();
scores.insert("Alice", 100);
scores.insert("Bob", 85);
scores.insert("Carol", 92);

// Standard BTreeMap operations work as expected
assert_eq!(scores.get(&"Bob"), Some(&85));
assert_eq!(scores.len(), 3);

// Order-statistic operations (O(log n))
// Get the median (rank 1 = second element in sorted order)
let (name, score) = scores.get_by_rank(1).unwrap();
assert_eq!(*name, "Bob"); // Keys are sorted alphabetically

// Find the rank of a key
assert_eq!(scores.rank_of(&"Carol"), Some(2)); // Carol is third alphabetically

// Index by rank
assert_eq!(scores[Rank(0)], 100); // Alice's score (first alphabetically)

Features

• no_std compatible - Only requires alloc, no standard library dependency
• Drop-in replacement - API mirrors std::collections::BTreeMap/BTreeSet
• O(log n) rank operations - Efficient order-statistic queries via subtree size augmentation
• Cache-efficient - B+tree structure with contiguous node storage

Implementation

The collections are implemented as B+trees (all data in leaves, linked leaf chain) with subtree size augmentation. Each internal node tracks the sizes of its subtrees, enabling O(log n) rank-based access without full traversal.

Re-exports

pub use osbtree_map::OSBTreeMap;

pub use osbtree_set::OSBTreeSet;

Modules

osbtree_map

osbtree_set

Structs

Rank

A zero-based rank into the sorted order of a map or set.