pub struct PersistentBTreeMap<K, V> { /* private fields */ }Expand description
A persistent ordered map. Clone is O(1); insert returns a new handle
that shares unaffected subtrees with the old via Arc::clone.
Implementations§
Source§impl<K, V> PersistentBTreeMap<K, V>
impl<K, V> PersistentBTreeMap<K, V>
Source§impl<K: Ord, V> PersistentBTreeMap<K, V>
impl<K: Ord, V> PersistentBTreeMap<K, V>
Sourcepub fn get(&self, key: &K) -> Option<&V>
pub fn get(&self, key: &K) -> Option<&V>
O(log₈ N). Per-node search at each level; on hit returns the
value, on miss descends into the child between adjacent entries.
v7.37.43 (INSUBQ B-3) — every node holds ≤ MAX_ENTRIES = 7
(K, V) pairs, so the inner search is over at most 7 elements.
binary_search_by issues a data-dependent branch per probe;
for n ≤ 7 a straight linear scan with a single ordering compare
per element wins on modern branch predictors and has tighter
codegen (no early-exit on found-vs-bisect handling). Probing a
100k-entry index on 1k keys (the INSUBQ shape) cuts ~30-60 ns
per descent × ~5 levels × 1k keys ≈ 150-300 µs off the loop.
Sourcepub fn predecessor(&self, key: &K) -> Option<(&K, &V)>
pub fn predecessor(&self, key: &K) -> Option<(&K, &V)>
v7.39 (round 215) — the entry with the largest key STRICTLY less than
key (the in-order predecessor of key), or None when every key is
≥ key. O(log₈ N): descend once toward key; at each internal node
the entries left of the descent slot are all < key, and the rightmost
of them is the best candidate at that level — but the child we descend
into holds keys strictly between it and key, so a deeper hit always
overrides. The building block for the range-exclusion overlap probe
(find the existing range whose lower bound sits just below a candidate).
Sourcepub fn from_sorted(entries: Vec<(K, V)>) -> Self
pub fn from_sorted(entries: Vec<(K, V)>) -> Self
In-order key-then-value iterator. Used by PartialEq and any caller
that needs to walk the whole map (e.g. catalog deserialization).
v7.39 (round 170) — bulk-build from PRE-SORTED entries, bottom-up.
The per-row insert_mut path pays a path-copy allocation per
element (~300ns each), which made every rebuild_indices pass
O(n) allocations per index (the dominant cost of a VACUUM on an
indexed table). This builds leaves in ~ORDER-sized runs and
levels them up with the run separators as the internal entries —
zero path copies. Groups are cut evenly so no node is left
pathologically underfull for the later insert/remove rebalance.
Debug builds assert the input is strictly sorted by K.
pub fn iter(&self) -> Iter<'_, K, V> ⓘ
Sourcepub fn iter_rev(&self) -> IterRev<'_, K, V> ⓘ
pub fn iter_rev(&self) -> IterRev<'_, K, V> ⓘ
v7.34.4 — descending-order iterator. Mirrors iter() but the
per-node walk visits child-then-entry pairs right-to-left.
Used by the ORDER BY <indexed col> DESC + LIMIT N executor
path to walk only the first N matches off the rightmost leaf
instead of materialising every row + partial-sorting.
Sourcepub fn range<'a>(&'a self, lo: Bound<&K>, hi: Bound<&K>) -> RangeIter<'a, K, V> ⓘwhere
K: Clone,
pub fn range<'a>(&'a self, lo: Bound<&K>, hi: Bound<&K>) -> RangeIter<'a, K, V> ⓘwhere
K: Clone,
v7.38 (perf, index range scan) — in-order iterator over the entries
whose keys fall in (lo, hi) (each end honoured per core::ops::Bound).
Descends to lo in O(log₈ N) (skipping the subtrees entirely below
it) by building the same (node, child_index) cursor stack iter()
uses, positioned at the first key ≥/> lo; then walks forward and stops
at the first key past hi. O(log N + k) for k hits — the building
block for Index::lookup_range (BETWEEN / > / < seeks).
Source§impl<K: Ord + Clone, V: Clone> PersistentBTreeMap<K, V>
impl<K: Ord + Clone, V: Clone> PersistentBTreeMap<K, V>
Sourcepub fn insert(&self, key: K, value: V) -> (Self, Option<V>)
pub fn insert(&self, key: K, value: V) -> (Self, Option<V>)
O(log₈ N). Path-copy insert; replaces if key exists, otherwise
inserts and grows by 1. Returns (new_map, previous_value).
Sourcepub fn get_by<Q>(&self, key: &Q) -> Option<&V>
pub fn get_by<Q>(&self, key: &Q) -> Option<&V>
O(log₈ N) transient insert. v4.40.1 perf path: walks
Arc::make_mut down the spine — when the spine Arcs are uniquely
owned (the common case in Table::insert outside a TX wrap), every
touched node mutates in place at roughly std::BTreeMap::insert
cost. When a cloned handle is outstanding (e.g. a Catalog snapshot
inside a TX wrap), Arc::make_mut path-copies just the affected
node and the snapshot stays untouched. Either way, callers see the
same end state as the immutable insert followed by reassignment.
r1019 — get / get_mut addressed by a BORROWED form of the key.
The GIN maps are keyed by String, and their maintenance now holds
trigrams as [u8; 3] on the stack. Without this, every lookup would
have to allocate a String just to be allowed to ask — which is the
allocation r1019 exists to remove. map.get_mut_by(trigram_str(&t))
asks with a &str and allocates only when a genuinely new key has to
be inserted.
Same descent as Self::get / Self::get_mut, same copy-on-write
discipline; K: Borrow<Q> is what guarantees the two orderings agree.
Sourcepub fn get_mut_by<Q>(&mut self, key: &Q) -> Option<&mut V>
pub fn get_mut_by<Q>(&mut self, key: &Q) -> Option<&mut V>
See Self::get_by. Walks Arc::make_mut, like get_mut.
Sourcepub fn get_mut(&mut self, key: &K) -> Option<&mut V>
pub fn get_mut(&mut self, key: &K) -> Option<&mut V>
r1018 — O(log₈ N) mutable borrow of an existing value, under the
same copy-on-write discipline as Self::insert_mut: uniquely-owned
spine nodes mutate in place, an outstanding snapshot path-copies only
the spine it touches.
The map is the posting-list store for every GIN index kind, whose maintenance had no way to APPEND to a list. It read the list out, cloned it, pushed one locator and inserted the clone back — so a trigram already present in k rows cost a k-element copy to record the (k+1)-th, and a text column’s common trigrams are present in nearly every row. Measured on mailrs’s schema (2026-08-13): four trigram GIN indexes over message text took 93 % of a 14,000-row load, superlinearly — 43.6 s with them, 2.9 s without.
Returns None when the key is absent; the caller inserts a fresh
single-element list in that case, which is the only path that needs to
grow the tree.
pub fn insert_mut(&mut self, key: K, value: V) -> Option<V>
Sourcepub fn remove_mut(&mut self, key: &K) -> Option<V>
pub fn remove_mut(&mut self, key: &K) -> Option<V>
O(log₈ N) transient remove. Returns the value that was stored
under key, or None when the key was absent (the map is then
untouched).
v7.39 (round 465) — the map had no removal at all: new / get / predecessor / from_sorted / iter / iter_rev / range / insert / insert_mut. That is why dropping a single index entry meant
rebuilding the whole map from the rows, and why one autovacuum tick
costs 11 ms on a 50k-row table with one secondary index — five
times the INSERT it exists to protect, all of it under the engine
write lock. Round 464 measured a filtered rebuild and it lost to
the existing from-the-rows rebuild, because iterating a
structurally-shared tree is pointer chasing while the rebuild is a
linear scan plus one sort. Removal is the operation that was
missing; with it, reclaiming k rows touches k spines instead of
rebuilding n entries.
Walks Arc::make_mut down the spine like insert_mut, so a
uniquely-owned tree mutates in place and an outstanding snapshot
(a Catalog clone inside a TX wrap) path-copies only the spine.
Sourcepub fn remove(&self, key: &K) -> (Self, Option<V>)
pub fn remove(&self, key: &K) -> (Self, Option<V>)
Immutable removal, for symmetry with Self::insert. Returns
(new_map, previous_value); the receiver is untouched.
Trait Implementations§
Source§impl<K, V> Clone for PersistentBTreeMap<K, V>
impl<K, V> Clone for PersistentBTreeMap<K, V>
Source§fn clone(&self) -> Self
fn clone(&self) -> Self
O(1) — Arc bump on the root. The whole reason this type exists in
v4.40 is to make Table::indices: Vec<Index> cheap to clone once
the inner BTreeMap is replaced.
1.0.0 (const: unstable) · Source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source. Read more