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!newspeer1.nac.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!news.stack.nl!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 19:54:21 +0200 Organization: cbb software GmbH Message-ID: <16j5s1k75li8a.1nilj2ewsr44x.dlg@40tude.net> References: <1x1p8c1ys7ely$.d0rvczpoa0kb$.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:189050 Date: 2014-09-18T19:54:21+02:00 List-Id: On Thu, 18 Sep 2014 09:53:50 -0700, Jeffrey Carter wrote: > On 09/18/2014 12:41 AM, Dmitry A. Kazakov wrote: >> >> Can skip list made fit into a series fixed-size blocks? > > I don't understand the question. 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. 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. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de