On Wed, Sep 15, 2010 at 7:23 PM, Giorgio Zoppi <giorgio.zoppi@gmail.com> wrote:
It would be interesting see how in this case could work skip-lists in term of time and concurrency. Best Regards
Skip-list are a quite bad "on disk" data structure, since they tend to be sparse. There are canonically two approaches in implementing Skip-lists: - the one with the "next nodes" is implemented as a list, which consumes a reasonable amount of memory but is (very) cache unfriendly (== time consuming) - the one with the "next nodes" is implemented as an array, which is more cache friendly (just the list, not the pointed nodes) but uses too much memory (unless you incrementally increase the size of the array... which is slow) I always had bad performance experiences with Skip-lists and, for this reason, I am biased in my judgment. Cheers, Francesco