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=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 Path: 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!news.mixmin.net!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: B-Tree v Skip-List Insertion Benchmark Date: Thu, 18 Sep 2014 22:31:57 +0200 Organization: cbb software GmbH Message-ID: References: <1x1p8c1ys7ely$.d0rvczpoa0kb$.dlg@40tude.net> <16j5s1k75li8a.1nilj2ewsr44x.dlg@40tude.net> Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: ZB2Fb2q1fa4xpMpNKFqV6Q.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: 40tude_Dialog/2.0.15.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: number.nntp.dca.giganews.com comp.lang.ada:189055 Date: 2014-09-18T22:31:57+02:00 List-Id: 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