alt Hacker NewsOk, maybe someone here can clear this up for me. My understanding of B+tree's is that they are good for implementing indexes on disk because the fanout reduces disk seeks... what I don't understand is in memory b+trees... which most of the implementations I find are. What are the advantages of an in memory b+tree?
Replies
dataflow • last Tuesday at 10:27 PM
Memory also has a seek penalty. It's called a cache miss penalty. It might be easier to think of them in general as penalties for nonlocality.
https://github.com/abseil/abseil-cpp/blob/master/absl/contai... mentions that b-tree maps hold multiple values per node, which makes them more cache-friendly than the red-black trees used in std::map.
You use either container when you want a sorted associative map type, which I have not found many uses cases for in my work. I might have a handful of them versus many instances of vectors and unsorted associative maps, i.e. absl::flat_hash_map.