Re: B-Tree v Skip-List Insertion Benchmark

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Wed, 17 Sep 2014 18:15:15 -0700, Jeffrey Carter wrote:

> 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).

Thanks for pointing this.

Can skip list made fit into a series fixed-size blocks?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de