B-Tree v Skip-List Insertion Benchmark

[Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org>]

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