A Framework for Supporting Tree-Like Indexes on the Chord Overlay
A Framework for Supporting Tree-Like Indexes on the Chord Overlay
复制标题
DOI：
10.1007/s11390-013-1391-8
复制
发表时间：
2013-11
影响因子：
0.7
通讯作者：
Mingdong Zhu;Derong Shen;Yue Kou;Tiezheng Nie;Ge Yu
中科院分区：
文献类型：
--
作者：
Mingdong Zhu;Derong Shen;Yue Kou;Tiezheng Nie;Ge Yu
随着数据的爆炸式增长，为了支持包括查询和更新在内的高效数据管理，数据库系统期望根据不同的数据类型提供树状索引，如R树、M树、B+树等。在分布式环境中，索引必须分散在计算节点上，以提高可靠性和可扩展性。索引可以加快查询速度，但更新时会产生维护成本。在分布式环境中，每个计算节点都维护一个索引树的子集，因此保持通信成本较小更为关键，否则会占用大量网络带宽，影响数据库系统的可扩展性和可用性。此外，为了实现查询的可靠性和可扩展性，需要索引的多个副本，但保持副本一致并不简单。在本文中，我们提出了一种基于 Chord 覆盖（一种流行的 P2P 结构）的支持树状索引的框架。该框架动态调整索引的副本数量以平衡查询成本和更新成本。设计了多种技术来提高更新效率，而不影响查询性能。我们在框架中实现了 M 树和 R 树，并对现实生活和合成数据集进行了大量实验，验证了我们框架的效率和可扩展性。
With the explosive growth of data, to support efficient data management including queries and updates, the database system is expected to provide tree-like indexes, such as R-tree, M-tree, B+-tree, according to different types of data. In the distributed environment, the indexes have to be scattered across the compute nodes to improve reliability and scalability. Indexes can speed up queries, but they incur maintenance cost when updates occur. In the distributed environment, each compute node maintains a subset of an index tree, so keeping the communication cost small is more crucial, or else it occupies lots of network bandwidth and the scalability and availability of the database system are affected. Further, to achieve the reliability and scalability for queries, several replicas of the index are needed, but keeping the replicas consistent is not straightforward. In this paper, we propose a framework supporting tree-like indexes, based on Chord overlay, which is a popular P2P structure. The framework dynamically tunes the number of replicas of index to balance the query cost and the update cost. Several techniques are designed to improve the efficiency of updates without the cost of performance of the queries. We implement M-tree and R-tree in our framework, and extensive experiments on real- life and synthetic datasets verify the efficiency and scalability of our framework.