index_db/lib.rs
1//! # index-db
2//!
3//! A B+tree indexing primitive for storage engines: ordered keys mapped to
4//! values, with fast point lookups, laid out as a tree of fixed-fan-out nodes
5//! rather than on the heap one entry at a time.
6//!
7//! The one public type is [`BPlusTree`], an ordered map. Keys are kept sorted
8//! across the tree, so a lookup is a binary search at each level and the height
9//! grows only with the logarithm of the entry count. Beyond point operations it
10//! supports ordered iteration and range scans, forward and in reverse. The node
11//! layout — sorted keys packed into fixed-capacity arrays, internal nodes routing
12//! to children — is the same structure a storage engine persists as an on-disk
13//! index; this release keeps the tree in memory.
14//!
15//! ## Example
16//!
17//! ```
18//! use index_db::BPlusTree;
19//!
20//! let mut index = BPlusTree::new();
21//! index.insert(42_u32, "answer");
22//! index.insert(7, "lucky");
23//!
24//! assert_eq!(index.get(&42), Some(&"answer"));
25//! assert_eq!(index.get(&13), None);
26//!
27//! // Ordered range scan.
28//! let keys: Vec<_> = index.range(0..50).map(|(&k, _)| k).collect();
29//! assert_eq!(keys, vec![7, 42]);
30//!
31//! assert_eq!(index.remove(&7), Some("lucky"));
32//! assert_eq!(index.len(), 1);
33//! ```
34//!
35//! ## Scope
36//!
37//! As of `v0.3.0` the ordered-map surface is complete: search, insert, delete
38//! (with merge and redistribute), and forward and reverse range scans.
39//! Latch-coupled concurrent access lands in `v0.4.0`. See `dev/ROADMAP.md`.
40
41#![cfg_attr(not(feature = "std"), no_std)]
42#![cfg_attr(docsrs, feature(doc_cfg))]
43#![deny(missing_docs)]
44#![deny(unused_must_use)]
45#![deny(unused_results)]
46#![deny(clippy::unwrap_used)]
47#![deny(clippy::expect_used)]
48#![deny(clippy::todo)]
49#![deny(clippy::unimplemented)]
50#![deny(clippy::print_stdout)]
51#![deny(clippy::print_stderr)]
52#![deny(clippy::dbg_macro)]
53#![forbid(unsafe_code)]
54
55extern crate alloc;
56
57mod iter;
58mod node;
59mod tree;
60
61pub use crate::iter::Iter;
62pub use crate::tree::BPlusTree;