arXiv 2304.09983
Tutorial: The Ubiquitous Skiplist, its Variants, and Applications in Modern Big Data Systems
By Venkata Sai Pavan Kumar Vadrevu, Lu Xing, et al.
Published 2023-04-19
Mindmap
Browse the paper's core ideas, clusters, and relationships in a structured outline.
The Skiplist, or skip list, originally designed as an in-memory data structure, has attracted a lot of attention in recent years as a main-memory component in many NoSQL, cloud-based, and big data systems. Unlike the B-tree, the skiplist does not need complex rebalancing mechanisms, but it still shows expected logarithmic performance. It supports a variety of operations, including insert, point read, and range queri…