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
173
174
175
176
177
178
179
180
181
182
183
184
185
//! Read-path operations: point lookups and value resolution.
use std::sync::Arc;
use crate::pager::{PageGuard, Pager};
use crate::vfs::Vfs;
use crate::{RealmId, Result};
use bytes::Bytes;
use crate::btree::internal::InternalAccessor;
use crate::btree::leaf::{Leaf, LeafAccessor, LeafValue, LeafValueLoc};
use crate::btree::node::NodeKind;
use crate::btree::overflow;
use super::core::{BTree, SeenPageIds};
impl<V: Vfs> BTree<V> {
/// Get a value by key. Returns `None` if not found.
///
/// Zero-allocation tree descent: each level reads the page through a
/// [`PageGuard`], builds a borrowed accessor over the decrypted body, and
/// either descends or extracts the value. An inline value is returned as a
/// slice sharing the cached page's buffer, so the hit path allocates
/// nothing; only an overflow chain, which is reassembled from several
/// pages, needs a buffer of its own.
pub async fn get(&self, key: &[u8]) -> Result<Option<Bytes>> {
if self.root_page_id == 0 {
return Ok(None);
}
// Root could itself be a fresh leaf (single-leaf tree mutated in
// this txn). Pull the value from the cache instead of the pager.
if let Some(leaf) = self.fresh_leaves.get(&self.root_page_id) {
return Self::value_from_cached_leaf(&self.pager, self.realm_id, leaf, key).await;
}
let (root_guard, root_kind) = self.read_node_guard(self.root_page_id).await?;
self.get_from_node(key, self.root_page_id, &root_guard, root_kind)
.await
}
/// Resolve `key` against an in-memory `Leaf` (from `fresh_leaves` /
/// `dirty_leaves`), following any overflow chain via the pager.
async fn value_from_cached_leaf(
pager: &Arc<Pager<V>>,
realm_id: RealmId,
leaf: &Leaf,
key: &[u8],
) -> Result<Option<Bytes>> {
match leaf.get(key) {
None => Ok(None),
// Uncommitted: held by the decoded leaf rather than by a page, but
// still shared rather than copied.
Some(LeafValue::Inline(v)) => Ok(Some(v.clone())),
Some(LeafValue::Overflow {
total_len,
root_page_id,
}) => {
let v = overflow::read_chain(pager, realm_id, *root_page_id, *total_len).await?;
Ok(Some(Bytes::from(v)))
}
}
}
/// Variant of [`get`](Self::get) that takes a caller-owned, already-pinned
/// root [`PageGuard`]. Lets read transactions cache the root for the
/// lifetime of the txn so subsequent gets skip the root cache lookup.
pub async fn get_with_cached_root(
&self,
key: &[u8],
root_guard: &PageGuard,
root_kind: NodeKind,
) -> Result<Option<Bytes>> {
if self.root_page_id == 0 {
return Ok(None);
}
self.get_from_node(key, self.root_page_id, root_guard, root_kind)
.await
}
/// Descend from `start_guard` (the page at `start_page_id`) toward a
/// leaf, extracting the value at `key` if present. Consults the
/// dirty-leaf cache at the leaf level — within a write txn, leaves
/// mutated by `put`/`delete` shadow the buffer-pool bytes.
async fn get_from_node(
&self,
key: &[u8],
start_page_id: u64,
start_guard: &PageGuard,
start_kind: NodeKind,
) -> Result<Option<Bytes>> {
// Handle the first level using the borrowed guard.
let next_page_id = match start_kind {
NodeKind::Leaf => {
return self
.extract_leaf_value(key, start_page_id, start_guard)
.await;
}
NodeKind::Internal => InternalAccessor::from_guard(start_guard)?.child_for(key),
};
// Descend from the first child onward. Subsequent guards are owned.
let mut seen = SeenPageIds::new("btree_descent");
seen.insert(start_page_id)?;
let mut page_id = next_page_id;
loop {
seen.insert(page_id)?;
// Fresh-from-split leaves only live in `fresh_leaves` until
// flush. If the next child is one, resolve from cache.
if let Some(leaf) = self.fresh_leaves.get(&page_id) {
return Self::value_from_cached_leaf(&self.pager, self.realm_id, leaf, key).await;
}
let (guard, kind) = self.read_node_guard(page_id).await?;
match kind {
NodeKind::Leaf => return self.extract_leaf_value(key, page_id, &guard).await,
NodeKind::Internal => {
let next = InternalAccessor::from_guard(&guard)?.child_for(key);
drop(guard);
page_id = next;
}
}
}
}
async fn extract_leaf_value(
&self,
key: &[u8],
leaf_page_id: u64,
leaf_guard: &PageGuard,
) -> Result<Option<Bytes>> {
// Within a write txn, the dirty + fresh caches shadow the buffer-pool
// bytes. The cached decoded form is the source of truth for any leaf
// they hold.
if let Some(leaf) = self
.fresh_leaves
.get(&leaf_page_id)
.or_else(|| self.dirty_leaves.get(&leaf_page_id))
{
return match leaf.get(key) {
None => Ok(None),
// Uncommitted: held by the decoded leaf rather than by a page,
// but still shared rather than copied.
Some(LeafValue::Inline(v)) => Ok(Some(v.clone())),
Some(LeafValue::Overflow {
total_len,
root_page_id,
}) => {
let v =
overflow::read_chain(&self.pager, self.realm_id, *root_page_id, *total_len)
.await?;
Ok(Some(Bytes::from(v)))
}
};
}
let leaf = LeafAccessor::from_guard(leaf_guard)?;
let Some(idx) = leaf.find(key) else {
return Ok(None);
};
match leaf.value_loc(idx) {
// Shares the pinned page's buffer; no copy of the value at all.
LeafValueLoc::Inline(range) => Ok(Some(leaf_guard.body_slice(range))),
LeafValueLoc::Overflow {
total_len,
root_page_id,
} => {
let v = overflow::read_chain(&self.pager, self.realm_id, root_page_id, total_len)
.await?;
Ok(Some(Bytes::from(v)))
}
}
}
/// Resolve a `LeafValue` to its raw bytes. Follows overflow chains as
/// needed.
pub(super) async fn resolve_leaf_value(&self, v: &LeafValue) -> Result<Bytes> {
match v {
// Refcount bump, not a copy.
LeafValue::Inline(b) => Ok(b.clone()),
LeafValue::Overflow {
total_len,
root_page_id,
} => overflow::read_chain(&self.pager, self.realm_id, *root_page_id, *total_len)
.await
.map(Bytes::from),
}
}
}