1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//! Configuration for the learned index.
/// Configuration parameters for [`LearnedMap`](crate::LearnedMap).
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Config {
/// Expansion factor for node arrays.
///
/// Controls the ratio of array size to key count. A factor of 2.0 means
/// the array is twice as large as the number of keys (50% gaps), leaving
/// room for future inserts without conflicts.
///
/// Higher values reduce conflicts but use more memory.
///
/// Default: `2.0`. Must be `>= 1.0`.
pub expansion_factor: f64,
/// Whether to automatically rebuild the tree after a threshold of inserts.
///
/// When enabled, the map periodically rebuilds with optimal FMCD model
/// fitting to keep the tree shallow and lookups fast. The rebuild threshold
/// is `(len / 4).clamp(16, 10_000)`.
///
/// Default: `true`.
pub auto_rebuild: bool,
/// Maximum subtree depth before a localized rebuild is triggered.
///
/// When an insert descends through more child nodes than this threshold,
/// the inserting thread rebuilds the degraded subtree inline. Only applies
/// when `auto_rebuild` is `true`. Set to `usize::MAX` to disable.
///
/// Default: `8`.
pub rebuild_depth_threshold: usize,
/// Maximum tombstone ratio before a localized rebuild is triggered.
///
/// When a node's tombstone count (slots nulled by remove) exceeds this
/// fraction of its capacity, the removing thread rebuilds the parent
/// subtree inline. Only applies when `auto_rebuild` is `true`.
///
/// Set to `1.0` to disable tombstone compaction.
///
/// Default: `0.5` (compact when >50% of slots are tombstones).
pub tombstone_ratio_threshold: f64,
/// Extra key range headroom for model fitting.
///
/// When greater than 0, the model covers `(1 + range_headroom)` times the
/// actual key range, leaving space for keys beyond the current max. This
/// prevents all out-of-range keys from clamping to the last slot.
///
/// The array size grows proportionally to maintain per-key slot density.
/// Only applies during model fitting (bulk load and rebuild).
///
/// Default: `0.0` (no headroom). Root rebuilds internally use `1.0`.
pub range_headroom: f64,
}
impl Config {
/// Create a new configuration with default values.
pub fn new() -> Self {
Self::default()
}
/// Set the expansion factor.
///
/// # Panics
///
/// Panics if `factor < 1.0`.
pub fn expansion_factor(mut self, factor: f64) -> Self {
assert!(factor >= 1.0, "expansion_factor must be >= 1.0");
self.expansion_factor = factor;
self
}
/// Enable or disable automatic rebuilds.
pub fn auto_rebuild(mut self, enabled: bool) -> Self {
self.auto_rebuild = enabled;
self
}
/// Set the maximum subtree depth before localized rebuild triggers.
pub fn rebuild_depth_threshold(mut self, threshold: usize) -> Self {
self.rebuild_depth_threshold = threshold;
self
}
/// Set the tombstone ratio threshold for compaction.
///
/// # Panics
///
/// Panics if `threshold` is not in `(0.0, 1.0]`.
pub fn tombstone_ratio_threshold(mut self, threshold: f64) -> Self {
assert!(
threshold > 0.0 && threshold <= 1.0,
"tombstone_ratio_threshold must be in (0.0, 1.0], got {threshold}"
);
self.tombstone_ratio_threshold = threshold;
self
}
/// Set the key range headroom for model fitting.
///
/// # Panics
///
/// Panics if `headroom < 0.0`.
pub fn range_headroom(mut self, headroom: f64) -> Self {
assert!(headroom >= 0.0, "range_headroom must be >= 0.0");
self.range_headroom = headroom;
self
}
}
impl Default for Config {
fn default() -> Self {
Self {
expansion_factor: 2.0,
auto_rebuild: true,
rebuild_depth_threshold: 8,
tombstone_ratio_threshold: 0.5,
range_headroom: 0.0,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn default_config() {
let config = Config::default();
assert!((config.expansion_factor - 2.0).abs() < f64::EPSILON);
}
#[test]
fn builder_pattern() {
let config = Config::new().expansion_factor(3.0);
assert!((config.expansion_factor - 3.0).abs() < f64::EPSILON);
}
#[test]
#[should_panic(expected = "expansion_factor must be >= 1.0")]
fn reject_low_expansion() {
Config::new().expansion_factor(0.5);
}
#[test]
fn tombstone_threshold_builder() {
let config = Config::new().tombstone_ratio_threshold(0.75);
assert!((config.tombstone_ratio_threshold - 0.75).abs() < f64::EPSILON);
}
#[test]
fn tombstone_threshold_default() {
let config = Config::default();
assert!((config.tombstone_ratio_threshold - 0.5).abs() < f64::EPSILON);
}
#[test]
#[should_panic(expected = "tombstone_ratio_threshold must be in (0.0, 1.0]")]
fn reject_zero_tombstone_threshold() {
Config::new().tombstone_ratio_threshold(0.0);
}
#[test]
#[should_panic(expected = "tombstone_ratio_threshold must be in (0.0, 1.0]")]
fn reject_high_tombstone_threshold() {
Config::new().tombstone_ratio_threshold(1.5);
}
}