Would you ever use a skip list over a treap?
here is an extensive 13 page analysis of considerations in this area including empirical analysis. coders sometimes ask for "one size fits all" answers. of course "best" implementation depends on the actual "forces" applied on the implementation. a single implementation may even behave ("dramatically") differently on different amounts of data and different conditions. for some data structures there is no significant difference and either can be acceptable. 

raw performance is not the only factor. factors might involve how hard it is to implement/ test the structure vs whether it is already implemented etc. and this paper also considers caching considerations effect on performance. this research finds that skip lists have good variable-node-size performance (ie not all nodes have same size) and paged skip lists outperforms B+-trees in their case.

see p7 and fig6 p 10.


  The AVL tree is the best
  performing fixed-node-size data structure, and
  the paged skip list is the best performing
  variable-node-size data structure. Moreover, the
  gap between the cache-conscious data structures
  and their counterparts is growing, as shown by
  the 100 cycle memory latency configuration.
  The paged skip list outperforms the sequential search
  B+-tree by 12% on the Intel processor. 



T-treap and Cache Performance of Indexing Data Structures /
Joshua P. MacDonald and Ben Y. Zhao