1 Introduction

2 Skiplist Basics  
2.1 Basic Structure  
2.2 Operations and Cost Analysis  
2.3 Analysis of p

3 Contrast with B/B+ -trees  
3.1 Deterministic Skiplists  
3.2 Corresponding Trees

4 Concurrent Skiplists  
4.1 The Lock-based Skiplist  
4.2 The Lock-free Skiplist  
4.3 A Concurrent Priority Query Implementation Using a Skiplist  
4.4 Concurrent Skiplist Java Implementations  
4.5 Contention-Friendly Skiplist Concurrency Techniques  
4.6 The Rotating Skiplist  
4.7 Multi-Versioned Skiplist

5 Variants of the Skiplist: Taxonomy and Related Systems  
5.1 Skiplists as Database Indexes  
5.2 Skiplists as Part of an Index  
5.3 Skiplists In Operating Systems  
5.4 Skiplist Versatility

6 Enforcing Determinism

7 Accommodating for Skewed Data Access Patterns in Skiplists

8 Skiplists with Unrolling Nodes

9 Hardware Implications  
9.1 External Memory Storage  
9.2 NUMA Environment  
9.3 Other Hardware

10 The Multi-dimensional Skiplist  
10.1 Multi-dimensional Skiplist  
10.2 The Skip QuadTree

11 The Interval Skiplist

12 The Skiplist as a Priority Queue

13 Skiplist Applications  
13.1 LSMT-based Systems  
13.2 Skiplist-based Key-Value Stores  
13.3 Network Overlay Algorithms  
13.4 Hierarchical Navigable Small World Graphs

14 Concluding Remarks