索引基于多维查询的云平台高效搜索探析

摘要本文提出-个有效的方法來建立一个针对云计算系统的多维索引把R树和KD树向结合来组织数据记录提供快速查询进程和有效的索引维护。这种方法能够提供典型的多维查询包括高效的点查询和范围查询。而且机器大量数据频繁的改变使得索引的维护成为一个巨大的挑战并且为了解决这个问题提岀基于索引更新策略的耗费评估可以有效的更新索引结构。该方法比较综合并独立于基础实施能够很好的在各种云计算平台上实施。

关键词云计算分布式文件系统节点边界技术

最近云计算平台作为一个新的数据管理局势正在得到越来越多的关注。 当前有许多云计算产品可以提供各种服务。然而 当前的云平台仅仅支持简单的基于关键字搜索并且由于缺乏有效的索引技术而不能有效回答复杂索引。

一、 网络的发展和云计算的意义

网络正在以一个惊人的速度发展。每天大量数据以数字数据的形式被放在互联网上。很多新的网络应用出现并且他们中的大多数需要处理网络数据的效率然而传统的数据管理工具已经不能满足需要。 例如数据库系统软件经常是多重用户的这就意味着在线网络用户必须同时共享相同的软件资源。 当不被期望的尖刻问题出现时用户可能要面临资源的短缺或是服务质量的下降。所以可扩展性对未来网络的应用是很重要的需求。在这些环境下一个新的计算基础设施, 云计算 出现了。然而统一的云计算的定义还没有被确认 它被认为是一场IT业的革命系统支持云计算根据用户需求动态分配计算资源存在的云计

算系统包括亚马逊弹性计算云 IBM的蓝云和谷歌的映射化简云。采用灵活的资源管理机制并且提供好的可仲缩性可伸缩的数据结构可以满足云系统用户的需求。云计算系统经常由大量计算机组成存储大量的数据并且为成千上万的用户提供服务。在云系统中资源的分配有典型的可仲缩性使得每一个用户都感觉自 己占有无限的资源。

当前 多数的云实施是基于分布式文件系统。 DFS经常使用关键字存储模式来存储数据在云计算系统中数据时通过关键字对来存储的。当一个搜索到来时结果数据根据包含的关键字被重新取回。 虽然很多有名的云系统使用这个信息存储模式例如谷歌的GFS和Hadoop的HDFS,他们仅仅为用户提供关键字搜索服务。所以用户仅仅能通过耍点搜索来访问数据这种访问通过匹配数据来满足口头或数据值。

云计算平台包括成百上千的机器节点并且他们并行的处理任务和负载。这是云计算基础设施的典型特性。 当一个用户提交了一个查询结果数据被从底层的存储列表和用来并行扫描的一系列分布式进程中取岀。没有有效的索引结构支持搜索进程是很耗费时间的特别对于复杂的查询。所以建立更有效的索引结构是一个紧迫的需求。 此外 因为在云系统中的大量数据的存在索引应该能提供高的检索速率。

二、云基础设施建设方案

到目前为止提岀了许多为云基础设施建立有效索引的方案。Agui lera等人为云系统提出了一个可伸缩的分布式B树。其他研究工作人员提出了一个以哈希索引结构为基础的索引。然而这些索引仅仅能搜索单柱数据。他们不能有效的为多维数据提供有效的查询。

为了在云系统中提供有效的多维数据查询通过在R树和KD树结合的基础上提出了一个可伸缩和灵活的多维检索结构。

1 、 提出了一个有效的和灵活的多维索引结构。使用这种结构能使得典型的和有效的索引有效的执行。索引可以平衡数据容量或簇尺寸增长。

2、 提出了一个索引成本评估的更新策略。通过这个策略可以保证只有在必要和更新的利益被确保的时候更新才被执行。

通过在装有大量数据的很多机器节点上做了一系列实验。实验证实了索引结构很高效而且有扩展性。通过评价在云计算系统中本文的多维索引的性能和可伸缩性。测试的设施包括六台相连的机器来模拟云计算平台。通信带宽是1GpSo每个机器有主频为2.33GHz Intel Core2处理器 4GB主存和320G硬盘。作为云平台基本的特性, 一个簇包括成百上千个PC机这些机器负责计算和存储数据。在簇中的机器节点可以分为两类 主节点和从节点。主节点和从节点不是很不同除了如果机器充当主节点 它将存储整个系统中子节点必须存储的变化数据。从节点存储数据和它们效率和安全的复制。尽管云平台的和客户服务器建构的系统的一个不同点是云系统不需要中央服务器 它仍然需要…系列机器来维护整个系统的变化数据这使得很多操作更有效率。在云平台中客户请求经常与主节点对立起来。 在主节点决定哪个从节点和请求相关后客户将和这些节点直接通信所以作为一个典型的请求在云平台中的查询进程被分为两阶段:定位相关节点和在被选择节点上处理请求。

当一个数据要被插入首先检查它是否能被已有的立方体包含。 如果查找立方体失败扩大最近的立方体来包含数据。 当一个数据需要被删除 它所在的立方体并且检查数据是否是立方体中的顶点 如果答案肯定节点立方体将收缩。通过这种方式实现了分布式的快速索引能够很好的适应现在高速度化查询的要求。

三、结论

这篇文章提出了为云平台建立有效多维索引。通过使用R树和KD树的结合來支持索引结构开发了节点边界技术用来在云平台中降低查询进程的耗费。为了维持索引的高效通过为索引的更新提岀 了一个成本评估方法。通过大量的实验证明了方法的有效性。未来的工作将根据数据在立方体中的分布来确定如何划分节点立方体 以获得更好的性能包括索引建立的性能和索引查询过程的性能。

参考文献

[1]Hadoop. [Onl ine].Avai lable: http://hadoop.apache.org

[2]M.K.Agui lera,W.Golab,and M.A.Shah, "A practicalscalable distributed b-tree," in Proceedings of VLDB'08,Auckland,NewZealand,August2008,pp.598-609.