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.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00
	autolearn=no autolearn_force=no version=3.4.4
Path: 
 border2.nntp.dca1.giganews.com!nntp.giganews.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!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: B-Tree v Skip-List Insertion Benchmark
Date: Wed, 17 Sep 2014 18:15:15 -0700
Organization: Also freenews.netfront.net; news.tornevall.net;
 news.eternal-september.org
Message-ID: <lvdbn4$99j$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 18 Sep 2014 01:15:16 +0000 (UTC)
Injection-Info: mx05.eternal-september.org;
 posting-host="5b4eadb0ecf28f7f740a0e18f3715b8f";
 logging-data="9523"; mail-complaints-to="abuse@eternal-september.org";
 posting-account="U2FsdGVkX18onN9uUBfm5zI6lnKo85xQB6Z/F1NBG7Y="
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.1.0
Cancel-Lock: sha1:iEfnAH+V40lMTJbD9wCvMyt88i0=
Xref: number.nntp.dca.giganews.com comp.lang.ada:189036
Date: 2014-09-17T18:15:15-07:00
List-Id: <comp.lang.ada>

I ran a quick comparison of the insertion times for Kazakov's Generic_B_Tree pkg
against PragmARC.Skip_List_Unbounded from the PragmAda Reusable Components.

Both data structures are used for similar purposes, allowing O(log N) look-up
times. Insertion and deletion are expensive operations on balanced trees due to
re-balancing, and one reason skip lists were invented was to have fast insertion
and deletion times compared to balanced trees. I had never actually compared
times, and Kazakov's recent post comparing DB times got me thinking about it.

A typical run inserting the same 1,000 items into both structures gives times of

1.484 ms for the B tree
0.709 ms for the skip list

(Divide by 1,000 for average per-insertion times.)

The trade off is similar to using heap sort or quick sort. Both are O(N log N),
with quick sort usually being faster. Heap sort is always O(N log N), but in
rare cases, however, quick sort has worst-case performance of O(N**2).

A skip list is probabilistically balanced, and has a worst-case search time of
O(N) in very rare circumstances, almost always for small N (< 256).

-- 
Jeff Carter
"Perfidious English mouse-dropping hoarders."
Monty Python & the Holy Grail
10