On 2015-03-22 16:40, Phil Endecott wrote:
And you can compact ("vacuum") a B-tree, if you want.
I see.
(a) When it's important to have no pointers at all, so that I can store the data in a memory-mapped file or perhaps in interprocess shared memory. (Though most recently I decided to use offset pointers from Boost.Interprocess along with a Boost.Intrusive map, and that worked well.)
(b) When the data has a "life cycle" with different phases, e.g. an initial phase of bulk creation, followed by a phase of random lookup. In this case you only sort once so the computational complexity is optimal.
I would not want to use them when either you have fine-grained mixing of insertion and lookup, or when the amount of data is large enough that the poor locality of reference starts to dominate.
You make a good point here! From your silence on the "sorted vs non sorted" issue, I am positive we are on the same page about that, regardless its relevance. Best Giacomo