2010/05/05 by Daniel Golovin, Golovin, Daniel · 2 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #cs.DB #cs.DS
paper · pdf · doi:10.48550/arxiv.1005.0662
13 pages, 2 figures
arxiv created 2010/05/05 · openalex publication_date 2010/05/05 · arxiv updated 2015/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In previous work, the author introduced the B-treap, a uniquely represented B-tree analogue, and proved strong performance guarantees for it. However, the B-treap maintains complex invariants and is very complex to implement. In this paper we introduce the B-skip-list, which has most of the guarantees of the B-treap, but is vastly simpler and easier to implement. Like the B-treap, the B-skip-list may be used to construct strongly history-independent index structures and filesystems; such constructions reveal no information about the historical sequence of operations that led to the current logical state. For example, a uniquely represented filesystem would support the deletion of a file in a way that, in a strong information-theoretic sense, provably removes all evidence that the file ever existed. Like the B-tree, the B-skip-list has depth O(logB (n)) where B is the block transfer size of the external memory, uses linear space with high probability, and supports efficient one-dimensional range queries.