From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!feeder.erje.net!eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org>
Newsgroups: comp.lang.ada
Subject: Re: B-Tree v Skip-List Insertion Benchmark
Date: Thu, 18 Sep 2014 12:33:16 -0700
Organization: Also freenews.netfront.net; news.tornevall.net;
 news.eternal-september.org
Message-ID: <lvfc1s$9bl$3@dont-email.me>
References: <lvdbn4$99j$1@dont-email.me>
 <1x1p8c1ys7ely$.d0rvczpoa0kb$.dlg@40tude.net> <lvf2mv$s7h$1@dont-email.me>
 <16j5s1k75li8a.1nilj2ewsr44x.dlg@40tude.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 18 Sep 2014 19:33:18 +0000 (UTC)
Injection-Info: mx05.eternal-september.org;
 posting-host="5b4eadb0ecf28f7f740a0e18f3715b8f";
 logging-data="9589"; mail-complaints-to="abuse@eternal-september.org";
 posting-account="U2FsdGVkX19168ohPP0A3StTr2XzryWcqLrducUsgyM="
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.1.0
In-Reply-To: <16j5s1k75li8a.1nilj2ewsr44x.dlg@40tude.net>
Cancel-Lock: sha1:SbNJW/V7wzmFCbyiZTWVDi55aq4=
Xref: number.nntp.dca.giganews.com comp.lang.ada:189052
Date: 2014-09-18T12:33:16-07:00
List-Id: <comp.lang.ada>

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