From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Subject: Re: B-Tree v Skip-List Insertion Benchmark
Date: Thu, 18 Sep 2014 19:54:21 +0200
Date: 2014-09-18T19:54:21+02:00 [thread overview]
Message-ID: <16j5s1k75li8a.1nilj2ewsr44x.dlg@40tude.net> (raw)
In-Reply-To: lvf2mv$s7h$1@dont-email.me
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
next prev parent reply other threads:[~2014-09-18 17:54 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-09-18 1:15 B-Tree v Skip-List Insertion Benchmark Jeffrey Carter
2014-09-18 7:41 ` Dmitry A. Kazakov
2014-09-18 16:53 ` Jeffrey Carter
2014-09-18 17:54 ` Dmitry A. Kazakov [this message]
2014-09-18 19:33 ` Jeffrey Carter
2014-09-18 20:31 ` Dmitry A. Kazakov
2014-09-18 17:39 ` Jeffrey Carter
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox