Re: B-Tree v Skip-List Insertion Benchmark

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Thu, 18 Sep 2014 12:33:16 -0700, Jeffrey Carter wrote:

> 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?

Yes. Everything is in the same file.

> 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.

There is a persistent memory pool, so it would be no problem to allocate
variable-length nodes. The concern is the case when the nodes become too
large for one block. The memory pool supports a stream interface. So a node
can be read from a chain of blocks and reconstructed in the memory then
updated and written back (in other blocks), no matter how many blocks it
spans. But it would be a considerable performance hit, I guess.

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

Yes, there are many structures more efficient than B-tree, but they might
be difficult to apply to the case of segmented (as blocks) storage rather
than flat storage. It is interesting to learn if skip lists could be used
this way. Which is why I asked.

>> 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.

No, I consider search as another operation. Let the location be already
determined. Then maintaining the structure gets a hit when not localized to
few blocks.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de