Write-Optimized Skip Lists
Write-Optimized Skip Lists
复制标题
DOI：
10.1145/3034786.3056117
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
M. A. Bender;Martín Farach-Colton;Rob Johnson;Simon Mauras;Tyler Mayer;C. Phillips;Helen Xu
中科院分区：
文献类型：
--
作者：
M. A. Bender;Martín Farach-Colton;Rob Johnson;Simon Mauras;Tyler Mayer;C. Phillips;Helen Xu
跳表是一种优雅的字典数据结构，通常在随机存取存储器（RAM）中使用。一个具有N个元素的跳表大概率（w.h.p.）以O(log N)的操作次数支持搜索、插入和删除操作，并且大概率以O(log N + K)的操作次数支持返回K个元素的范围查询。一种将跳表推广到块大小为B的外部存储器的看似自然的方法是，以1/B的概率而不是1/2进行“提升”。然而，要使跳表保持其高效性能、空间界限和大概率保证，存在实际和理论上的障碍。我们给出了一种实现写优化界限的外部存储器跳表。也就是说，对于0 < ε < 1，范围查询大概率需要O(logBε N + K/B)次I/O操作，插入和删除操作大概率需要O((logBε N) / B1 - ε)的平摊I/O操作。我们的写优化跳表继承了RAM跳表的简单性优点。此外，它达到或优于先前的写优化数据结构（如Bε - 树或LSM树，这些结构在高性能数据库和文件系统中使用）的渐近界限。证明我们的界限的主要技术挑战来自于跳表中的层数很少这一事实，而这是获得强外部存储器界限的数据结构的一个关键方面。我们使用极值图着色来表明，无论插入/删除模式如何，都有可能将跳表中的路径分解为不相关的组。因此，我们通过对这些不相关的路径求平均而不是像标准跳表那样对不相关的层求平均来达到我们的界限。
The skip list is an elegant dictionary data structure that is commonly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(log N) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p. A seemingly natural way to generalize the skip list to external memory with block size B is to "promote" with probability 1/B, rather than 1/2. However, there are practical and theoretical obstacles to getting the skip list to retain its efficient performance, space bounds, and high-probability guarantees. We give an external-memory skip list that achieves write-optimized bounds. That is, for 0 < ε < 1, range queries take O(logBε N + K/B) I/Os w.h.p. and insertions and deletions take O((logBε N) / B1-ε) amortized I/Os w.h.p. Our write-optimized skip list inherits the virtue of simplicity from RAM skip lists. Moreover, it matches or beats the asymptotic bounds of prior write-optimized data structures such as the Bε & tree or LSM trees, which are deployed in high-performance databases and file systems. The main technical challenge in proving our bounds comes from the fact that there are so few levels in the skip list, an aspect of the data structure that is essential to getting strong external-memory bounds. We use extremal-graph coloring to show that it is possible to decompose paths in the skip list into uncorrelated groups, regardless of the insertion/deletion pattern. Thus, we achieve our bounds by averaging over these uncorrelated paths rather than by averaging over uncorrelated levels, as in the standard skip list.