Computer Science – Data Structures and Algorithms
Scientific paper
2010-05-05
Computer Science
Data Structures and Algorithms
13 pages, 2 figures
Scientific paper
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(log_B (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.
No associations
LandOfFree
The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-436122