Skip List estimate number of elements less than (or greater than) a value

Question

I am looking for a thread safe data structure where

1. an element can be searched in $O(\log n)$,
2. for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,
3. an element can be inserted in $O(\log n)$, and
4. an element can be removed in $O(\log n)$.

Can a skip list or some modification of it be used? Is there an alternative data structures (Parallel Red-Black Tree for example) that can be used?

Answer 1

Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach. Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.). Annotate each node with the size of the subtree under that node. Then, make this data structure persistent. This can be done in a straightforward way using path copying.

Because the data structure is persistent, it handles concurrency nicely. In particular, immutable data structures are inherently good for concurrency; you don't have to worry about two threads writing to it concurrently, since it is immutable. Instead, updates essentially work by creating a new copy of the data structure. Thus, each thread has its own copy of the tree. The only shared variable you need is a single global variable that holds a pointer to the current copy of the tree. To update the tree, a thread reads the pointer in that global variable; makes a new copy of the tree with the update; then does a compare-and-swap to update the value of the global variable (unless it has changed since last reading it, in which case you cancel the operation and retry). Because each thread works on its own local copy of the tree during updates, you don't have to worry about some other thread concurrently accessing that copy.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.

Answer 2

It is possible to extend skip lists with so called "width of the link". For each link it says how many elements are skipped by follow this link. From Wikipedia (section Indexable skiplist):

   1                               10
 o---> o---------------------------------------------------------> o    Top level
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    Level 3
   1        2        1        2              3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
   1     1     1     1     1     1     1     1     1     1     1
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level

Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

These links are easy to update during (non-concurrent) traversals of insert and delete operations. It is as well easy to keep track of total number of skipped elements.

So yes, one can extend skip lists to find the position of the element in the list. But concurrent updates of the counters still might be a problem.