index_db/tree.rs
1//! The [`BPlusTree`] public type: an ordered map laid out as a B+tree.
2
3use alloc::vec::Vec;
4use core::ops::RangeBounds;
5
6use crate::iter::Iter;
7use crate::node::{Insert, Internal, Node};
8
9/// Smallest fan-out a node may have. With fewer than three children a split
10/// cannot leave both halves non-empty, so the tree could not stay balanced.
11const MIN_ORDER: usize = 3;
12
13/// Default fan-out: up to 64 children per node, so up to 63 keys. A binary
14/// search over a node is then at most six comparisons, and a tree of a million
15/// keys stands four levels tall.
16const DEFAULT_ORDER: usize = 64;
17
18/// An ordered map backed by a B+tree.
19///
20/// Keys are kept in sorted order across a tree of fixed-fan-out nodes. Point
21/// operations — [`get`](BPlusTree::get), [`insert`](BPlusTree::insert),
22/// [`contains_key`](BPlusTree::contains_key) — run in time logarithmic in the
23/// number of entries: each level is one binary search over a node, and the
24/// height grows with the logarithm of the entry count.
25///
26/// The structure is the same one storage engines use for an on-disk index, laid
27/// out so each node maps onto a fixed-size page. This release keeps the tree in
28/// memory; the node layout is the durable one a pager will later persist.
29///
30/// `K` must be [`Ord`]; [`insert`](BPlusTree::insert) additionally needs
31/// [`Clone`], because splitting a leaf copies a separator key up into the parent.
32///
33/// # Examples
34///
35/// ```
36/// use index_db::BPlusTree;
37///
38/// let mut index = BPlusTree::new();
39/// index.insert(3_u32, "three");
40/// index.insert(1, "one");
41/// index.insert(2, "two");
42///
43/// assert_eq!(index.get(&2), Some(&"two"));
44/// assert_eq!(index.len(), 3);
45/// ```
46pub struct BPlusTree<K, V> {
47 /// Root of the tree. A fresh tree's root is an empty leaf.
48 root: Node<K, V>,
49 /// Maximum fan-out: the most children an internal node may hold, and one
50 /// more than the most keys any node may hold.
51 order: usize,
52 /// Number of entries in the tree.
53 len: usize,
54}
55
56impl<K, V> BPlusTree<K, V> {
57 /// Create an empty tree with the default node fan-out.
58 ///
59 /// # Examples
60 ///
61 /// ```
62 /// use index_db::BPlusTree;
63 ///
64 /// let index: BPlusTree<u32, &str> = BPlusTree::new();
65 /// assert!(index.is_empty());
66 /// ```
67 #[must_use]
68 pub fn new() -> Self {
69 Self::with_order(DEFAULT_ORDER)
70 }
71
72 /// Create an empty tree with an explicit node fan-out, clamped up to the
73 /// minimum a balanced tree requires. Used by the test suite to force splits
74 /// at small key counts; the public surface fixes the fan-out via [`new`].
75 ///
76 /// [`new`]: BPlusTree::new
77 #[must_use]
78 pub(crate) fn with_order(order: usize) -> Self {
79 BPlusTree {
80 root: Node::empty_leaf(),
81 order: if order < MIN_ORDER { MIN_ORDER } else { order },
82 len: 0,
83 }
84 }
85
86 /// The number of entries in the tree.
87 ///
88 /// # Examples
89 ///
90 /// ```
91 /// use index_db::BPlusTree;
92 ///
93 /// let mut index = BPlusTree::new();
94 /// index.insert("k", 1);
95 /// assert_eq!(index.len(), 1);
96 /// ```
97 #[must_use]
98 #[inline]
99 pub fn len(&self) -> usize {
100 self.len
101 }
102
103 /// Whether the tree holds no entries.
104 ///
105 /// # Examples
106 ///
107 /// ```
108 /// use index_db::BPlusTree;
109 ///
110 /// let mut index = BPlusTree::new();
111 /// assert!(index.is_empty());
112 /// index.insert("k", 1);
113 /// assert!(!index.is_empty());
114 /// ```
115 #[must_use]
116 #[inline]
117 pub fn is_empty(&self) -> bool {
118 self.len == 0
119 }
120
121 /// The height of the tree in levels: a tree whose root is a leaf has height
122 /// one, and every level of internal nodes above the leaves adds one more.
123 ///
124 /// Because the tree is balanced, this is the number of nodes touched on any
125 /// root-to-leaf path, and so the cost of a point lookup in node visits.
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// use index_db::BPlusTree;
131 ///
132 /// let mut index = BPlusTree::new();
133 /// assert_eq!(index.height(), 1); // just the root leaf
134 /// for k in 0..1_000_u32 {
135 /// index.insert(k, k);
136 /// }
137 /// assert!(index.height() >= 2); // splits have grown the tree taller
138 /// ```
139 #[must_use]
140 pub fn height(&self) -> usize {
141 let mut height = 1;
142 let mut node = &self.root;
143 while let Node::Internal(internal) = node {
144 height += 1;
145 node = &internal.children[0];
146 }
147 height
148 }
149
150 /// Remove every entry, returning the tree to its empty state.
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// use index_db::BPlusTree;
156 ///
157 /// let mut index = BPlusTree::new();
158 /// index.insert(1_u32, "a");
159 /// index.clear();
160 /// assert!(index.is_empty());
161 /// assert_eq!(index.get(&1), None);
162 /// ```
163 pub fn clear(&mut self) {
164 self.root = Node::empty_leaf();
165 self.len = 0;
166 }
167
168 /// An iterator over every entry, in ascending key order.
169 ///
170 /// The iterator is double-ended: call [`rev`](Iterator::rev) for descending
171 /// order, or drive it from both ends.
172 ///
173 /// # Examples
174 ///
175 /// ```
176 /// use index_db::BPlusTree;
177 ///
178 /// let mut index = BPlusTree::new();
179 /// index.insert(2_u32, "b");
180 /// index.insert(1, "a");
181 /// index.insert(3, "c");
182 ///
183 /// let collected: Vec<_> = index.iter().map(|(&k, &v)| (k, v)).collect();
184 /// assert_eq!(collected, vec![(1, "a"), (2, "b"), (3, "c")]);
185 ///
186 /// // Reverse with `.rev()`.
187 /// let keys: Vec<_> = index.iter().rev().map(|(&k, _)| k).collect();
188 /// assert_eq!(keys, vec![3, 2, 1]);
189 /// ```
190 #[must_use]
191 pub fn iter(&self) -> Iter<'_, K, V> {
192 Iter::full(&self.root)
193 }
194}
195
196impl<K: Ord, V> BPlusTree<K, V> {
197 /// Look up the value stored under `key`, or `None` if the key is absent.
198 ///
199 /// # Examples
200 ///
201 /// ```
202 /// use index_db::BPlusTree;
203 ///
204 /// let mut index = BPlusTree::new();
205 /// index.insert(10_u32, "ten");
206 /// assert_eq!(index.get(&10), Some(&"ten"));
207 /// assert_eq!(index.get(&11), None);
208 /// ```
209 #[must_use]
210 #[inline]
211 pub fn get(&self, key: &K) -> Option<&V> {
212 self.root.get(key)
213 }
214
215 /// Whether the tree holds an entry for `key`.
216 ///
217 /// # Examples
218 ///
219 /// ```
220 /// use index_db::BPlusTree;
221 ///
222 /// let mut index = BPlusTree::new();
223 /// index.insert(10_u32, "ten");
224 /// assert!(index.contains_key(&10));
225 /// assert!(!index.contains_key(&11));
226 /// ```
227 #[must_use]
228 #[inline]
229 pub fn contains_key(&self, key: &K) -> bool {
230 self.get(key).is_some()
231 }
232
233 /// An iterator over the entries whose keys fall in `range`, in ascending key
234 /// order.
235 ///
236 /// `range` is any standard range expression — `a..b`, `a..=b`, `..b`, `a..`,
237 /// or `..` — interpreted over the key order. Like [`iter`](Self::iter) the
238 /// result is double-ended, so a range can be walked forward or in reverse
239 /// with [`rev`](Iterator::rev).
240 ///
241 /// # Examples
242 ///
243 /// ```
244 /// use index_db::BPlusTree;
245 ///
246 /// let mut index = BPlusTree::new();
247 /// for k in 0..10_u32 {
248 /// index.insert(k, k);
249 /// }
250 ///
251 /// // Half-open range [3, 7).
252 /// let keys: Vec<_> = index.range(3..7).map(|(&k, _)| k).collect();
253 /// assert_eq!(keys, vec![3, 4, 5, 6]);
254 ///
255 /// // Inclusive range, walked in reverse.
256 /// let rev: Vec<_> = index.range(2..=4).rev().map(|(&k, _)| k).collect();
257 /// assert_eq!(rev, vec![4, 3, 2]);
258 ///
259 /// // Open-ended range.
260 /// let tail: Vec<_> = index.range(8..).map(|(&k, _)| k).collect();
261 /// assert_eq!(tail, vec![8, 9]);
262 /// ```
263 #[must_use]
264 pub fn range<R: RangeBounds<K>>(&self, range: R) -> Iter<'_, K, V> {
265 Iter::range(&self.root, range.start_bound(), range.end_bound())
266 }
267}
268
269impl<'a, K, V> IntoIterator for &'a BPlusTree<K, V> {
270 type Item = (&'a K, &'a V);
271 type IntoIter = Iter<'a, K, V>;
272
273 fn into_iter(self) -> Self::IntoIter {
274 self.iter()
275 }
276}
277
278impl<K: Ord + Clone, V> BPlusTree<K, V> {
279 /// Insert `key` with `value`. If the key was already present its previous
280 /// value is replaced and returned; otherwise the entry is added and `None`
281 /// is returned.
282 ///
283 /// # Examples
284 ///
285 /// ```
286 /// use index_db::BPlusTree;
287 ///
288 /// let mut index = BPlusTree::new();
289 /// assert_eq!(index.insert(1_u32, "a"), None); // new key
290 /// assert_eq!(index.insert(1, "b"), Some("a")); // replaced
291 /// assert_eq!(index.get(&1), Some(&"b"));
292 /// ```
293 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
294 match self.root.insert(key, value, self.order) {
295 Insert::Replaced(old) => Some(old),
296 Insert::Inserted => {
297 self.len = self.len.saturating_add(1);
298 None
299 }
300 Insert::Split { sep, right } => {
301 self.grow_root(sep, right);
302 self.len = self.len.saturating_add(1);
303 None
304 }
305 }
306 }
307
308 /// Remove `key`, returning its value if it was present, or `None` if the
309 /// tree held no such key.
310 ///
311 /// Removing keeps the tree balanced: an under-full node borrows an entry
312 /// from a sibling or merges with one, and when the root is left with a single
313 /// child the tree collapses a level. Every leaf stays at the same depth.
314 ///
315 /// # Examples
316 ///
317 /// ```
318 /// use index_db::BPlusTree;
319 ///
320 /// let mut index = BPlusTree::new();
321 /// index.insert(1_u32, "a");
322 /// index.insert(2, "b");
323 ///
324 /// assert_eq!(index.remove(&1), Some("a")); // returns the removed value
325 /// assert_eq!(index.remove(&1), None); // already gone
326 /// assert_eq!(index.get(&1), None);
327 /// assert_eq!(index.len(), 1);
328 /// ```
329 pub fn remove(&mut self, key: &K) -> Option<V> {
330 let removed = self.root.remove(key, self.min_keys());
331 if removed.is_some() {
332 self.len -= 1;
333 self.shrink_root();
334 }
335 removed
336 }
337
338 /// The minimum number of keys a non-root node must hold: a node is at least
339 /// half full, so two under-full siblings always fit in one node on merge.
340 #[inline]
341 fn min_keys(&self) -> usize {
342 self.order.div_ceil(2) - 1
343 }
344
345 /// Collapse the root when it is an internal node left with a single child:
346 /// that child becomes the new root, lowering the tree by one level. This is
347 /// the only operation that decreases the tree's height.
348 fn shrink_root(&mut self) {
349 let only_child = match &mut self.root {
350 Node::Internal(internal) if internal.children.len() == 1 => internal.children.pop(),
351 _ => None,
352 };
353 if let Some(child) = only_child {
354 self.root = child;
355 }
356 }
357
358 /// Replace the root with a new internal node over the old root and the right
359 /// half promoted by a split. This is the only operation that increases the
360 /// tree's height, and it keeps every leaf at the same depth.
361 fn grow_root(&mut self, sep: K, right: Node<K, V>) {
362 let old_root = core::mem::replace(&mut self.root, Node::empty_leaf());
363 let mut keys = Vec::with_capacity(self.order);
364 keys.push(sep);
365 let mut children = Vec::with_capacity(self.order + 1);
366 children.push(old_root);
367 children.push(right);
368 self.root = Node::Internal(Internal { keys, children });
369 }
370}
371
372impl<K, V> Default for BPlusTree<K, V> {
373 fn default() -> Self {
374 Self::new()
375 }
376}
377
378#[cfg(test)]
379#[allow(clippy::unwrap_used, clippy::expect_used, reason = "test assertions")]
380mod tests {
381 use alloc::vec::Vec;
382
383 use proptest::prelude::*;
384
385 use super::*;
386
387 /// Recursively verify the structural invariants of the subtree rooted at
388 /// `node`, returning its `(min_key, max_key, height)` for the parent to
389 /// check separators against. Panics with a description on the first
390 /// violation so a failing property shrinks to a readable case.
391 fn check<K: Ord + Clone + core::fmt::Debug, V>(
392 node: &Node<K, V>,
393 order: usize,
394 min_keys: usize,
395 is_root: bool,
396 ) -> (K, K, usize) {
397 match node {
398 Node::Leaf(leaf) => {
399 assert!(!leaf.keys.is_empty(), "non-root leaf is empty");
400 assert!(
401 leaf.keys.len() < order,
402 "leaf over capacity: {} >= {order}",
403 leaf.keys.len()
404 );
405 assert!(
406 is_root || leaf.keys.len() >= min_keys,
407 "non-root leaf under capacity: {} < {min_keys}",
408 leaf.keys.len()
409 );
410 assert_eq!(
411 leaf.keys.len(),
412 leaf.vals.len(),
413 "keys/vals length mismatch"
414 );
415 for w in leaf.keys.windows(2) {
416 assert!(w[0] < w[1], "leaf keys not strictly ascending");
417 }
418 (
419 leaf.keys[0].clone(),
420 leaf.keys[leaf.keys.len() - 1].clone(),
421 1,
422 )
423 }
424 Node::Internal(internal) => {
425 assert!(!internal.keys.is_empty(), "internal node has no separators");
426 assert!(
427 internal.keys.len() < order,
428 "internal node over capacity: {} >= {order}",
429 internal.keys.len()
430 );
431 assert!(
432 is_root || internal.keys.len() >= min_keys,
433 "non-root internal node under capacity: {} < {min_keys}",
434 internal.keys.len()
435 );
436 assert_eq!(
437 internal.children.len(),
438 internal.keys.len() + 1,
439 "child count must be separator count + 1"
440 );
441 for w in internal.keys.windows(2) {
442 assert!(w[0] < w[1], "separators not strictly ascending");
443 }
444
445 let mut child_height = None;
446 let mut subtree_min = None;
447 let mut last_max: Option<K> = None;
448 for (i, child) in internal.children.iter().enumerate() {
449 let (cmin, cmax, h) = check(child, order, min_keys, false);
450 match child_height {
451 None => child_height = Some(h),
452 Some(prev) => assert_eq!(prev, h, "subtrees differ in height (unbalanced)"),
453 }
454 if subtree_min.is_none() {
455 subtree_min = Some(cmin.clone());
456 }
457 // Separator i - 1 sits between child i - 1 and child i. It
458 // routes: everything left of it is below it, everything in
459 // and under the right child is at or above it. (After a
460 // delete the separator may be strictly below the right min,
461 // so this is `<=`, not equality.)
462 if i > 0 {
463 let sep = &internal.keys[i - 1];
464 assert!(
465 last_max.as_ref().is_some_and(|m| m < sep),
466 "left subtree max not below separator"
467 );
468 assert!(sep <= &cmin, "separator above right subtree's min key");
469 }
470 last_max = Some(cmax);
471 }
472 let height = child_height.map_or(1, |h| h + 1);
473 // Internal nodes always carry at least two children, so both
474 // accumulators are populated by the loop above.
475 match (subtree_min, last_max) {
476 (Some(min), Some(max)) => (min, max, height),
477 _ => panic!("internal node with no children"),
478 }
479 }
480 }
481 }
482
483 /// `check` entry point: derives `min_keys` from `order` and treats the tree
484 /// root as exempt from the minimum-occupancy rule.
485 fn check_tree<K: Ord + Clone + core::fmt::Debug, V>(tree: &BPlusTree<K, V>) {
486 let _bounds = check(&tree.root, tree.order, tree.min_keys(), true);
487 }
488
489 /// Walk the leaves left to right and collect every entry key in order.
490 fn collect_keys<K: Clone, V>(node: &Node<K, V>, out: &mut Vec<K>) {
491 match node {
492 Node::Leaf(leaf) => out.extend(leaf.keys.iter().cloned()),
493 Node::Internal(internal) => {
494 for child in &internal.children {
495 collect_keys(child, out);
496 }
497 }
498 }
499 }
500
501 #[test]
502 fn test_get_empty_returns_none() {
503 let tree: BPlusTree<u32, u32> = BPlusTree::new();
504 assert_eq!(tree.get(&0), None);
505 assert!(tree.is_empty());
506 assert_eq!(tree.height(), 1);
507 }
508
509 #[test]
510 fn test_insert_duplicate_key_replaces_value() {
511 let mut tree = BPlusTree::new();
512 assert_eq!(tree.insert(1_u32, "a"), None);
513 assert_eq!(tree.insert(1, "b"), Some("a"));
514 assert_eq!(tree.get(&1), Some(&"b"));
515 assert_eq!(tree.len(), 1);
516 }
517
518 #[test]
519 fn test_insert_many_splits_and_stays_balanced() {
520 let mut tree = BPlusTree::with_order(4);
521 for k in 0..256_u32 {
522 assert_eq!(tree.insert(k, k * 10), None);
523 }
524 check_tree(&tree);
525 assert!(
526 tree.height() > 1,
527 "tree should have split into multiple levels"
528 );
529 for k in 0..256_u32 {
530 assert_eq!(tree.get(&k), Some(&(k * 10)));
531 }
532 assert_eq!(tree.get(&256), None);
533 }
534
535 #[test]
536 fn test_insert_reverse_order_keeps_keys_sorted() {
537 let mut tree = BPlusTree::with_order(3);
538 for k in (0..100_u32).rev() {
539 assert_eq!(tree.insert(k, k), None);
540 }
541 let mut keys = Vec::new();
542 collect_keys(&tree.root, &mut keys);
543 assert_eq!(keys.len(), 100);
544 assert!(keys.windows(2).all(|w| w[0] < w[1]), "leaf order broken");
545 }
546
547 proptest! {
548 #[test]
549 fn prop_matches_reference_map(
550 order in 3_usize..8,
551 ops in prop::collection::vec((0_u32..200, 0_u32..1_000_000), 0..400),
552 ) {
553 use std::collections::BTreeMap;
554
555 let mut tree = BPlusTree::with_order(order);
556 let mut reference = BTreeMap::new();
557 for (k, v) in ops {
558 let got = tree.insert(k, v);
559 let want = reference.insert(k, v);
560 prop_assert_eq!(got, want);
561 }
562
563 prop_assert_eq!(tree.len(), reference.len());
564 // The structural check assumes a populated tree; the empty tree's
565 // root is a legitimately empty leaf, which `check` would reject.
566 if !tree.is_empty() {
567 check_tree(&tree);
568 }
569
570 // Every key in the reference is found with the same value.
571 for (k, v) in &reference {
572 prop_assert_eq!(tree.get(k), Some(v));
573 }
574 // A key the reference lacks is absent from the tree too.
575 for k in 0_u32..200 {
576 if !reference.contains_key(&k) {
577 prop_assert_eq!(tree.get(&k), None);
578 }
579 }
580
581 // The leaves, read left to right, are exactly the sorted key set.
582 let mut keys = Vec::new();
583 collect_keys(&tree.root, &mut keys);
584 let expected: Vec<u32> = reference.keys().copied().collect();
585 prop_assert_eq!(keys, expected);
586 }
587 }
588
589 #[test]
590 fn test_remove_absent_key_returns_none() {
591 let mut tree = BPlusTree::new();
592 assert_eq!(tree.insert(1_u32, "a"), None);
593 assert_eq!(tree.remove(&2), None);
594 assert_eq!(tree.len(), 1);
595 }
596
597 #[test]
598 fn test_remove_present_key_returns_value() {
599 let mut tree = BPlusTree::new();
600 assert_eq!(tree.insert(1_u32, "a"), None);
601 assert_eq!(tree.insert(2, "b"), None);
602 assert_eq!(tree.remove(&1), Some("a"));
603 assert_eq!(tree.get(&1), None);
604 assert_eq!(tree.get(&2), Some(&"b"));
605 assert_eq!(tree.len(), 1);
606 }
607
608 #[test]
609 fn test_remove_all_empties_tree_and_collapses_root() {
610 let mut tree = BPlusTree::with_order(4);
611 for k in 0..200_u32 {
612 let _ = tree.insert(k, k);
613 }
614 assert!(tree.height() > 1);
615 // Remove in an order unrelated to insertion to drive merges/borrows.
616 for k in (0..200_u32).step_by(2) {
617 assert_eq!(tree.remove(&k), Some(k));
618 }
619 for k in (1..200_u32).step_by(2) {
620 assert_eq!(tree.remove(&k), Some(k));
621 }
622 assert!(tree.is_empty());
623 assert_eq!(tree.height(), 1, "root should collapse back to a leaf");
624 }
625
626 #[test]
627 fn test_remove_keeps_tree_balanced() {
628 let mut tree = BPlusTree::with_order(3);
629 for k in 0..500_u32 {
630 let _ = tree.insert(k, k);
631 }
632 for k in (0..500_u32).filter(|k| k % 3 == 0) {
633 assert_eq!(tree.remove(&k), Some(k));
634 }
635 check_tree(&tree);
636 for k in 0..500_u32 {
637 assert_eq!(tree.get(&k), if k % 3 == 0 { None } else { Some(&k) });
638 }
639 }
640
641 #[test]
642 fn test_iter_empty_yields_nothing() {
643 let tree: BPlusTree<u32, u32> = BPlusTree::new();
644 assert_eq!(tree.iter().count(), 0);
645 assert_eq!(tree.iter().next_back(), None);
646 assert_eq!(tree.range(..).count(), 0);
647 }
648
649 #[test]
650 fn test_iter_forward_and_reverse() {
651 let mut tree = BPlusTree::with_order(4);
652 for k in 0..50_u32 {
653 let _ = tree.insert(k, k * 10);
654 }
655 let fwd: Vec<_> = tree.iter().map(|(&k, &v)| (k, v)).collect();
656 let expected: Vec<_> = (0..50_u32).map(|k| (k, k * 10)).collect();
657 assert_eq!(fwd, expected);
658
659 let rev: Vec<_> = tree.iter().rev().map(|(&k, _)| k).collect();
660 let expected_rev: Vec<_> = (0..50_u32).rev().collect();
661 assert_eq!(rev, expected_rev);
662 }
663
664 #[test]
665 fn test_iter_from_both_ends_meets_in_middle() {
666 let mut tree = BPlusTree::with_order(3);
667 for k in 0..9_u32 {
668 let _ = tree.insert(k, k);
669 }
670 let mut it = tree.iter();
671 let mut seq = Vec::new();
672 let mut take_front = true;
673 loop {
674 let item = if take_front {
675 it.next()
676 } else {
677 it.next_back()
678 };
679 match item {
680 Some((&k, _)) => seq.push(k),
681 None => break,
682 }
683 take_front = !take_front;
684 }
685 // Pulled alternately from each end, the entries interleave and meet.
686 assert_eq!(seq, vec![0, 8, 1, 7, 2, 6, 3, 5, 4]);
687 }
688
689 #[test]
690 fn test_range_bounds() {
691 let mut tree = BPlusTree::with_order(4);
692 for k in 0..20_u32 {
693 let _ = tree.insert(k, k);
694 }
695 let collect = |it: Iter<'_, u32, u32>| it.map(|(&k, _)| k).collect::<Vec<_>>();
696 assert_eq!(collect(tree.range(5..10)), vec![5, 6, 7, 8, 9]);
697 assert_eq!(collect(tree.range(5..=10)), vec![5, 6, 7, 8, 9, 10]);
698 assert_eq!(collect(tree.range(..3)), vec![0, 1, 2]);
699 assert_eq!(collect(tree.range(17..)), vec![17, 18, 19]);
700 assert_eq!(collect(tree.range(100..200)), Vec::<u32>::new());
701 // A bound that falls between existing keys.
702 let mut sparse = BPlusTree::with_order(3);
703 for k in [0_u32, 10, 20, 30, 40] {
704 let _ = sparse.insert(k, k);
705 }
706 assert_eq!(collect(sparse.range(5..35)), vec![10, 20, 30]);
707 }
708
709 proptest! {
710 /// Forward iteration, reverse iteration, and arbitrary ranges all match
711 /// `BTreeMap` over the same data.
712 #[test]
713 fn prop_iter_and_range_match_reference(
714 order in 3_usize..8,
715 keys in prop::collection::vec(0_u32..200, 0..300),
716 lo in 0_u32..200,
717 hi in 0_u32..200,
718 ) {
719 use std::collections::BTreeMap;
720
721 let mut tree = BPlusTree::with_order(order);
722 let mut reference = BTreeMap::new();
723 for k in keys {
724 let _ = tree.insert(k, k.wrapping_mul(7));
725 let _ = reference.insert(k, k.wrapping_mul(7));
726 }
727
728 let tree_fwd: Vec<_> = tree.iter().map(|(&k, &v)| (k, v)).collect();
729 let ref_fwd: Vec<_> = reference.iter().map(|(&k, &v)| (k, v)).collect();
730 prop_assert_eq!(&tree_fwd, &ref_fwd);
731
732 let tree_rev: Vec<_> = tree.iter().rev().map(|(&k, &v)| (k, v)).collect();
733 let ref_rev: Vec<_> = reference.iter().rev().map(|(&k, &v)| (k, v)).collect();
734 prop_assert_eq!(tree_rev, ref_rev);
735
736 let (lo, hi) = (lo.min(hi), lo.max(hi));
737 let tree_range: Vec<_> = tree.range(lo..hi).map(|(&k, _)| k).collect();
738 let ref_range: Vec<_> = reference.range(lo..hi).map(|(&k, _)| k).collect();
739 prop_assert_eq!(tree_range, ref_range);
740
741 let tree_incl: Vec<_> = tree.range(lo..=hi).rev().map(|(&k, _)| k).collect();
742 let ref_incl: Vec<_> = reference.range(lo..=hi).rev().map(|(&k, _)| k).collect();
743 prop_assert_eq!(tree_incl, ref_incl);
744 }
745
746 /// A mixed insert/remove workload tracks `BTreeMap` exactly, and the tree
747 /// stays a valid, balanced, minimally-occupied B+tree throughout.
748 #[test]
749 fn prop_insert_remove_matches_reference(
750 order in 3_usize..8,
751 ops in prop::collection::vec((any::<bool>(), 0_u32..150), 0..600),
752 ) {
753 use std::collections::BTreeMap;
754
755 let mut tree = BPlusTree::with_order(order);
756 let mut reference = BTreeMap::new();
757 for (is_insert, k) in ops {
758 if is_insert {
759 prop_assert_eq!(tree.insert(k, k), reference.insert(k, k));
760 } else {
761 prop_assert_eq!(tree.remove(&k), reference.remove(&k));
762 }
763 prop_assert_eq!(tree.len(), reference.len());
764 if !tree.is_empty() {
765 check_tree(&tree);
766 }
767 }
768
769 let mut keys = Vec::new();
770 collect_keys(&tree.root, &mut keys);
771 let expected: Vec<u32> = reference.keys().copied().collect();
772 prop_assert_eq!(keys, expected);
773 }
774 }
775}