Write-optimized skip lists

Michael A. Bender, Martín Farach-Colton, Rob Johnson, Simon Mauras, Tyler Mayer, Cynthia A. Phillips, Helen Xu

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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(log N + K/B) I/Os w.h.p. and insertions and deletions take O((log 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 Bϵ trees or LSM trees. These data structures 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.

    Original languageEnglish (US)
    Title of host publicationPODS 2017 - Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
    PublisherAssociation for Computing Machinery
    Pages69-78
    Number of pages10
    ISBN (Electronic)9781450341981
    DOIs
    StatePublished - May 9 2017
    Event36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017 - Chicago, United States
    Duration: May 14 2017May 19 2017

    Publication series

    NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
    VolumePart F127745

    Other

    Other36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017
    Country/TerritoryUnited States
    CityChicago
    Period5/14/175/19/17

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Hardware and Architecture

    Fingerprint

    Dive into the research topics of 'Write-optimized skip lists'. Together they form a unique fingerprint.

    Cite this