[jongjong]

Having implemented a SkipList and compared it to various binary tree implementations, my observation is that they're essentially equivalent in terms of performance for most operations. For insertion, my SkipList implementation was faster than most binary tree implementations but I found a Red-Black Binary Tree implementation which was faster.

Still, my SkipList was much faster with batch-deletion of contiguous records. This is because a SkipList does not require re-balancing after each individual deletion; once you've found a starting point and ending point (which has O(log n) time complexity), the deletion of an arbitrarily large chunk of a SkipList can be done in constant time.

Here is my implementation (Node.js/JavaScript) in case anyone is interested: https://www.npmjs.com/package/proper-skip-list