按年被提到
20242024 · 1 次2026
系统、数据库与网络›数据库与向量检索·arXiv:2403.04582 · cs.DB

The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Big Data Systems

Lu Xing, Venkata Sai Pavan Kumar Vadrevu, Walid G. Aref · 2024
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2024-03-09 · 最近 2026-04-19
2不同的人
2活跃月份
2讨论串
3被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Skiplists have become prevalent in systems. The main advantages of skiplists are their simplicity and ease of implementation, and the ability to support operations in the same asymptotic complexities as their tree-based counterparts. In this survey, we explore skiplists and their many variants. We highlight many scenarios about how skiplists are useful, and how they fit well in these usage scenarios. We also compare skiplists with other data structures, especially tree-based structures. Extensions to skiplists include structural modifications, as well as algorithmic enhancements and operations. We categorize the existing extensions, and summarize the skiplist variants that belong to each category. We present how data systems incorporate skiplist variants into many different application scenarios to serve various purposes. These data systems cover a wide range of applications, from data indexing to block-chain, from network algorithms to deterministic skiplists, etc. It illustrates an impactful and diverse applications of skiplists in various domains of data systems.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论ozgrakkurt · 2026-04

“Some more links that are inside the article: - More info about skiplists: https://arxiv.org/pdf/2403.04582 - Performance comparison with B-tree ?: https://db.cs.cmu.edu/papers/2018/mod342-wangA.pdf - Other blog from Anthithesis about writing their own db: https://antithesis.com/blog/2025/testing_pangolin/ Also I find it a bit hard to understand the pe…”

What Are Skiplists Good For?原评论 ↗
被提交为 story · 1 次