wabi_tree

Order-statistic B-tree collections for Rust.

wabi_tree 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(rank) - Get the element at a given sorted position
• rank_of(key) - Get the sorted position of a key
• Indexing by Rank - e.g., map[Rank(0)] for the first element

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 - Contiguous node storage with linked leaves for fast iteration

Installation

Add this to your Cargo.toml:

[dependencies]
wabi_tree = "0.1"

Quick Start

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 by key)
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)

API Overview

OSBTreeMap

All standard BTreeMap methods are supported, plus:

OSBTreeSet

All standard BTreeSet methods are supported, plus:

Core Operations Complexity

Use Cases

Order-statistic trees are useful when you need both:

1. Fast key-based lookups (like a regular map/set)
2. Fast positional access (like an array)

Example applications:

• Leaderboards - Find a player's rank, get the top N players
• Percentile calculations - Find the median or any percentile in O(log n)
• Sliding window statistics - Maintain sorted data with efficient rank queries
• Database indexing - Support both key lookups and OFFSET/LIMIT queries

Implementation

wabi_tree uses a B+tree variant where:

• All keys and values are stored in leaf nodes
• Internal nodes contain only separator keys and child pointers
• Leaves are linked for efficient sequential iteration
• Each internal node stores subtree sizes, enabling O(log n) rank operations

This design provides:

• Better cache locality than traditional binary search trees
• Efficient iteration via the leaf chain
• O(log n) complexity for all rank-based operations

Comparison with std::collections::BTreeMap

License

Licensed under either of:

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.