SkipTree: A scalable range-queryable distributed data structure for multidimensional data This paper presents the SkipTree, a new balanced, distributed data structure for storing data with multidimensional keys in a peer-to-peer network. The SkipTree supports range queries as well as single point queries which are routed in O(logn) hops. SkipTree is fully decentralized with each node being connected to O(logn) other nodes. The memory usage for maintaining the links at each node is O(lognloglogn) on average and O(log 2 n) in the worst case. Load balance is also guaranteed to be within a constant factor