Re: [boost] Interest in B-tree library for Boost?

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Francesco Nidito (francesco.nidito_at_[hidden])
Date: 2010-09-16 08:19:27

On Wed, Sep 15, 2010 at 7:23 PM, Giorgio Zoppi <giorgio.zoppi_at_[hidden]> 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