Re: B-Tree v Skip-List Insertion Benchmark

[Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org>]

On 09/18/2014 10:54 AM, Dmitry A. Kazakov wrote:
> 
> The structure must be chunked into blocks in order to be stored. When you
> update the container, the change should be localized to one block when
> possible. This is a property B-trees have. You make its buckets of the file
> block size and then insert or delete would update just one block, most of
> the time.

So you store the tree structure in the file, as well as the data? A node in a
skip list has a variable number of links to other nodes, so as implemented in
PragmARC.Skip_List_Unbounded would probably not lend itself to that. It could be
implemented with a fixed number of links, of which only a certain number are
actually used, which might work better.

I was only interested in checking the claim that insertion in a skip list is
quicker than in a B tree.

> If, say, a doubly-linked list element is inserted or deleted this would
> involve, most likely, tree blocks (to fix the links), which would devaluate
> the fact that these operations have O(1) complexity.

Insertion and deletion in a skip list are O(log N), since you have to search for
where to insert the new node. The time savings comes from not having a
re-balancing step.

-- 
Jeff Carter
"From this day on, the official language of San Marcos will be Swedish."
Bananas
28