> As far as I can tell it is a very good alternative to balanced binary
> trees (much easier implementation being prime advantage I believe) -
> performance wise they are much the same. I read somewhere that database
> implementations still might prefer Btrees because of some property that
> make them more efficient when it comes to distribution on secondary
> memory - but I don't know the details on that.
> 

On disk, the exact number of dereferences makes a big difference.  With
a binary tree, you divide your search space by 2 with each dereference;
with a btree, you divide it by a larger number.  I'd guess it's similar
for skip lists, though I've only heard about them, not studied them.

Hmm, with "main" memory being so much slower than cache, btrees might
even start making sense for in-memory structures.  But not necessarily
for Squeak, where an "array of foo's" won't necessarily have all of the
foo's next to each other, anyway, and thus where accessing items within
a node still causes fetches to distant parts of memory.

Anyway, I'd rather work on something higher-level.  This
hyper-optimization stuff is only useful on small portions of most of the
programs I ever work on.


-Lex