基于KD树和R树的多维云数据索引

Multi-dimensional cloud index based on KD-tree and R-tree

针对云存储系统大多基于键值对<key,value>模型存储数据,多维查询需要对整个数据集进行完全扫描,查询效率较低的问题,提出了一种基于KD树和R树的多维索引结构(简称KD-R索引)。KD-R索引采用双层索引模式,在全局服务器建立基于KD树的多维全局索引,在局部数据节点构建R树多维本地索引。基于性能损耗模型,选取索引代价较小的R树节点发布到全局KD树,从而优化多维查询性能。实验结果表明:与全局分布式R树索引相比,KD-R索引能够有效提高多维范围查询性能,并且在出现服务器节点失效的情况下,KD-R索引同样具有高可用性。

Most existing cloud storage systems are based on the key, value model, which leads to a full dataset scan for multi-dimensional queries and low query efficiency. A KD-tree and R-tree based multi-dimensional cloud data index named KD-R index was proposed. KD-R index adopted two-layer architecture： a KD-tree based global index was built in the global server and R-tree based local indexes were built in local server. A cost model was used to adaptively select appropriate R-tree nodes to publish into global KD-tree index. The experimental results show that, compared with R-tree based global index, KDR index is efficient for multi-dimensional range queries, and it has high availability in the case of server failure.