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.5.0` the in-memory ordered-map surface is complete and the public
38//! API is frozen: search, insert, delete (with merge and redistribute), forward
39//! and reverse range scans, and bulk construction from sorted input. The tree is
40//! [`Sync`], so any number of threads may read it at once. Node access runs
41//! through an internal storage seam so that a page-backed, concurrent backend
42//! over `page-db` can be added without changing the tree algorithm; that backend
43//! is the planned next step. 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;