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//! `v1.0.0` is the stable in-memory ordered map. The public API is frozen until
38//! 2.0: search, insert, delete (with merge and redistribute), forward and reverse
39//! range scans, and bulk construction from sorted input. The tree is [`Sync`], so
40//! any number of threads may read it at once. Node access runs through an
41//! internal storage seam so that a page-backed, concurrent (write-side) backend
42//! over `page-db` can be added in a 1.x release without changing the tree
43//! algorithm or breaking this API. See `dev/ROADMAP.md`.
44
45#![cfg_attr(not(feature = "std"), no_std)]
46#![cfg_attr(docsrs, feature(doc_cfg))]
47#![deny(missing_docs)]
48#![deny(unused_must_use)]
49#![deny(unused_results)]
50#![deny(clippy::unwrap_used)]
51#![deny(clippy::expect_used)]
52#![deny(clippy::todo)]
53#![deny(clippy::unimplemented)]
54#![deny(clippy::print_stdout)]
55#![deny(clippy::print_stderr)]
56#![deny(clippy::dbg_macro)]
57#![forbid(unsafe_code)]
58
59extern crate alloc;
60
61mod iter;
62mod node;
63mod ops;
64mod store;
65mod tree;
66
67pub use crate::iter::Iter;
68pub use crate::tree::BPlusTree;