> Practical B-trees often use fairly large values of k (e.g., 100) and therefore offer tight bounds -- in addition to being more cache-friendly than binary search trees.
That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.
From the looks of it Rust [1] uses a constant branching factor based on number of items whereas ABSEIL generally uses a target of 256 bytes [3] for branching and fits however many elements fit within that [2]. Rust’s approach seems to be more primitive as ABSEIL is optimizing for cache line usage (not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing?)
> not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing?
The AMD64 cache line is only 64 bytes, that would make for very low branching factors given interior nodes need a pointer per child, plus key, plus record pointer if b-tree (as opposed to b+tree).
To be clear, I was examining only leaf nodes. I’m not sure if interior nodes use the same logic. Still, ABSEIL generally uses a larger branching factor than Rust for some undocumented reason.
That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.