Ittai Abraham, James Aspnes, and Jian Yuan. Skip B-trees. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 366–380.
We describe a new data structure, the Skip B-Tree, that combines the advantages of skip graphs with features of traditional B-trees. A skip B-Tree provides efficient search, insertion and deletion operations. The data structure is highly fault tolerant even to adversarial failures, and allows for particularly simple repair mechanisms. Related resource keys are kept in blocks near each other enabling efficient range queries. Using this data structure, we describe a new distributed peer-to-peer network, the Distributed Skip B-Tree. Given m data items stored in a system with n nodes, the network allows to perform a range search operation for r consecutive keys that costs only O(logb m + r/b) where b=Θ(m/n). In addition, our distributed Skip B-tree search network has provable polylogarithmic costs for all its other basic operations like insert, delete, and node join. To the best of our knowledge, all previous distributed search networks either provide a range search operation whose cost is worse than ours or may require a linear cost for some basic operation like insert, delete, and node join.
@inproceedings(AbrahamAY2005,
title="Skip {B}-trees",
author="Ittai Abraham and James Aspnes and Jian Yuan",
booktitle="Principles of Distributed Systems;
9th International Conference, OPODIS 2005;
Pisa, Italy; December 2005; Revised Selected Papers",
series="Lecture Notes in Computer Science",
volume=3974,
month=dec,
year=2005,
pages={366--380}
)