On the equivalence of B-trees and deterministic skip list

Description

In this paper we show the functional and structural equivalence of B-trees and deterministic skip lists by defining two new B-tree structures, the Bd-tree and Bd[superscript +] -tree, which we use to provide an explicit mapping between deterministic skip lists (DSLs) and B-trees. This mapping is invertible and formalizes the correspondence that exists between the structures, allowing us to prove the equivalence of B-tree and deterministic skip list data structures. This result is important for a number of reasons. It validates the use of deterministic skip lists as index structures while allowing one to determine the relationship of deterministic skip lists to other balanced search tree structures. This equivalence provides further insight into a comparison of the 1-3 deterministic skip list to the red-black tree and to the 1-d range tree. We now know that we can interchange between the red-black tree and the 1-3 DSL and that the dynamic 1-d range tree and 1-3 DSL are equivalent structures. Keywords: B-trees, deterministic skip lists, equivalent data structures, balanced search tree structures, Bd-trees, Bd[superscript +]-trees