3 ms·

> 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 sear

> 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.

leni536 2y ago
Interesting, Abseil's btree claims to use a larger value: ... for absl::btree_set<int32_t>, nodes currently have 62 children ... https://abseil.io/about/design/btree https://abseil.io/about/design/btree
- vlovich123 2y ago
  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?) [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/library/alloc/... [2] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/internal/btree.h#L428-L443 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724... [3] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/btree_map.h#L93 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...
  - masklinn 2y ago
    > 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).
    - vlovich123 2y ago
      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.

leni536 2y ago

Interesting, Abseil's btree claims to use a larger value: ... for absl::btree_set<int32_t>, nodes currently have 62 children ... https://abseil.io/about/design/btree https://abseil.io/about/design/btree

vlovich123 2y ago
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?) [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/library/alloc/... [2] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/internal/btree.h#L428-L443 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724... [3] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/btree_map.h#L93 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...
- masklinn 2y ago
  > 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).
  - vlovich123 2y ago
    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.