SNB-index: a SkipNet and B+ tree based auxiliary Cloud index

摘要

Distributed data management plays an essential part in internet applications. With benefits of scalability and reliability, the Cloud storage systems have become an attractive choice for large-scale data processing. However, most Cloud storage systems currently adopt a hash-like approach to retrieve data that only support simple keyword-based enquiries, but lack various forms of information search. In this paper, we propose a novel SkipNet and B+ tree based index structure, called SNB-index, for Cloud computing systems. SNB-index adopts a two-layer architecture. In the lower layer, it uses the B+ tree to construct efficient local index. In the upper layer, it adaptively selects among local index nodes to form a SkipNet based global overlay. Our scalable auxiliary Cloud index can efficiently support a variety of types of queries (e.g. point-query, range-query, similarityquery), and provide high availability. Some new routing algorithms and mapping processing algorithms are designed to enhance performance. Experimental results show that SNB-index is valid and can be an alternative approach for constructing an auxiliary index in Cloud computing systems.