Expand description
SharedBTreeMap - cross-process MMF B-tree ordered map.
A cross-process MMF ordered key/value map with a cache-friendly layout:
each node packs up to B sorted keys (fanout B + 1), so a lookup
touches ~log_{B+1}(N) nodes. The per-node binary search reads a
contiguous key array (prefetcher-friendly) rather than chasing scattered
single-cache-line nodes, which is what wins once the map far exceeds L3
and lookups go to RAM. It is the substrate’s ordered-map primitive.
Minimum degree T = 8 => up to B = 2T - 1 = 15 keys per node, 2T = 16
children. Insert uses CLRS proactive top-down splitting (full children
are split before descent), so it is single-pass and never overflows.
Storage: self-contained MMF [BTreeHeader | BTreeNode array] with bump
allocation. Concurrency model: single-writer for insert / remove
(serialise externally); reads are consistent
against a quiescent tree (build-then-query), which is what the cold
benchmark exercises.
Structs§
Enums§
Constants§
- B
- Max keys per node.
- BTREE_
MAGIC - NIL
- Sentinel “no node”.
- T
- Minimum degree.