Also, unless you play nasty allocation tricks with the red-
black trees, it seems reasonable to conjecture that B-trees
have better caching behavior (it accesses an array, not
pointers strewn about all over the place, and has less
allocation overhead increasing memory locality even more),
which might help it in the speed race.
That's not exactly the reference I was thinking of, but it says what I remember about it.
Again, not taking away from what you're saying and not disagreeing with you in any way, more backing up what I originally said ;)
Ugh, yes, sorry about that. I meant that they are more cache friendly.
Not to disagree with anything you've said and only to back up what I was trying to get at is this SO answer:
http://stackoverflow.com/questions/647537/b-tree-faster-than...
The part I'm talking about is:
That's not exactly the reference I was thinking of, but it says what I remember about it.Again, not taking away from what you're saying and not disagreeing with you in any way, more backing up what I originally said ;)