3.2云数据管理系统关键技术研究
　　依据云数据管理系统的整体框架，可以看出云数据的查询领域存在许多研究问题：数据存储与索引设计、基于MapReduce的查询处理、查询优化、在线聚集过程中的数据采样与置信区间计算等.目前索引管理、查询处理、查询优化以及在线聚集等问题已经得到了初步的研究，本节对目前已有的相关工作进行分析总结.
　　3.2.1索引技术
　　现有的云数据管理系统大都以key-value方式存储数据，能够提供基于键值的快速查询，但是对于非键值的查询只能通过全表扫描来完成.尽管可以通过MapReduce实现并发扫描，但是面对海量数据，对于选择度比较高的查询来说，全表扫描的效率仍然比较低.目前很多学者对云数据管理系统中的索引技术进行了研究.根据索引的实现方式，本文把已有的索引分成3类：双层索引[17-21、二级索引①②[22]和基于线性化技术的全局索引[23].
　　(1)双层索引
　　云数据管理系统中的双层索引框架由Wu等人[17]在2009年提出，后续双层索引方案的研究工作大都基于该框架，其结构如图2所示.索引由局部索引和全局索引两部分构成.为每个节点的数据建立局部索弓I，该索引只负责本地节点上的数据.除局部索引外，每个计算节点还要共享一部分存储空间来存储全局索引.全局索引依据局部索引构建，由于存储空间的限制和查询效率的要求，并不是所有的局部索引都发布到全局索引中，而是按照一定的规则对索引节点进行选择.
　　根据全局索引的组织方式，双层索引可以分成两类：P2P结构的双层索引和集中式结构的双层索引.如表2所示，前3种方案的全局索引均采用P2P结构的覆盖网络[17-19]，这种方式易于实现可扩展性，使系统能够同时支持大规模的查询.但是也存在一些不足：首先，维护P2P网络需要一定的代价，查询时往往需要较高的网络传输代价；其次，对于主从结构（masterslave)的云数据管理系统，实现这种索引要重新构建一个P2P网络，会增加原有系统的负担.基于上述原因，文献[20-21]在全局索引中采用了集中式的索引方式.EMINC[2°]在每个节点建立KD树作为局部索引，其中每个索引节点被看成一个多维度的立方体，全局索引利用R树对这些立方体进行索引.当索引维度比较高，或者索引数据量比较大时，R树各个节点之间的重叠部分较多，查询时会产生大量的误判（falsepositive)结果.为解决这一问题，文献[21]的全局索引采用带bloomfilter的R树.进行查询时，首先通过bloomfilter来验证，如果查询点不在其中，则不再进行R树查询.这样减少了误判的几率，从而提高查询效率.上述各种索引技术方案具有较好的扩展性，但总的来说实现过程比较复杂，索引更新维护的代价比较高.特别是对于数据更新比较频繁的应用，对系统性能的影响较大.
　　(2)二级索引
　　二级索引（secondaryindex)方案主要应用于key-value存储的云数据库管理系统中，如Bigtbale、HBase等.在这类系统中，针对非键值列的二级索引通过为索引列构建索引表实现.索引表中的键值由原数据表中键值和索引列的组合构成，实现索引列与原有键值的映射.查询过程中，首先根据查询条件在索引表找到相应键值的列表，然后根据这些键值到原数据表中定位所需数据.目前基于二级索引的实现方案主要有ITHBase①、IHBase②和CCIndex?.其中ITHBase和IHBase均是开源的实现方案，二者实现方式相似，都从HBase源码级别进行扩展，重新定义和实现了客户端和服务端的处理逻辑，具有强侵入性.与IHBase相比，ITHbase更关注数据一致性，其重要特性之一是事务性.
　　ITHBase和IHBase两种方案中的索引表仅存放索引列与原表的键值信息.在查询过程中，先通过查询索引表得到键值，再根据键值到原表查找数据.由于得到的键值大都是随机的，所以需要进行大量的随机查找才能得到最终的查询结果，效率较低.为了减少随机查询带来的开销，Z〇u等人提出了另外
　　一种二级索引方案：互补聚簇式索引（ComplementalClusteringIndex),简称CCIndex[22].CCIndex把数据的详细信息也存放在索引表中，查询时可以直接在索引表中通过顺序扫描找到相应的数据，从而大大减少查询时间.然而把详细信息存储在索引表中会造成存储空间的增加.为了尽可能地减少存储空间的开销，作者把HDFS文件块备份数设为1来保证存储空间不会增加太多，但同时数据的容错性又成了新的问题.为了解决这一问题，作者创建了聚簇检验表（clusteringchecktable),和索引表一起来实现错误发生后的快速恢复.同时，CCIndex还给出了一种查询优化机制以支持多维查询.该优化机制主要利用HBase中的一些元数据信息（region-tc-serverinformation)来估算子查询结果的大小，根据估算结果生成合适的查询计划，从而减少查询时间.
　　二级索引方案易于实现，维护代价较低，但也存在一些不足：当索引列较多时，存储开销比较大；索引更新代价比较高，会影响系统的吞吐量；索引对多维查询的支持效率较低.
　　(3)基于线性化技术的全局索引
　　上述两类索引方案均需维护特定的索引结构，当数据更新十分频繁时，索引更新维护的代价很高.在保证系统性能的前提下，为降低索引更新维护的代价，文献[23]提出了一种基于空间目标排序的索引方案.其基本思想是：按照一定的规则将覆盖整个研究区域的范围划分为大小相等的格子，并给每一个格子分配相应的编号，用这些编号为空间目标生成一组具有代表意义的数字.其思想是将々维空间的实体映射到一维空间，从而可以利用比较成熟的一维索引技术.常见的用一维数值对多维空间目标进行排序的方法有Z排序、HUber曲线、位置键等.这些技术的思路基本相同，利用一个线性序列来填充空间，构造一种空间填充曲线.文献[23]以HBase作为数据存储方案，用Z排序技术对数据进行排序，以Zialue作为每条记录的键值.单纯的Z排序方法在搜索过程中会带来一些不必要的搜索空间（falsepositivesearch),作者在此基础上利用KD树或四叉树对多维数据空间进行划分，根据最长公共前缀计算每个子空间的名称，并以此作为索引项对各个子空间的数据进行索引，从而提高搜索效率.但是，该方法在进行空间划分的过程中会产生数据一致性的问题.虽然目前有相应的解决方案[24]，但是实现起来仍比较复杂，并且带来额外的负担.而且当数据分布不均匀时，KD树和四叉树的深度会很大，影响查询效率.
　　3.2.2查询处理
　　从支持的查询接口和查询语言来看，早期的云数据管理系统，例如BigTTable、HBase和Cassandra仅支持一些基本的数据插入和获取接口31°].随后很多公司和研究机构在丰富查询语句上开展了工作并提出一些"类-SQL语言，，，例如Yahoo丨的PigLatin[25]，Facebook的HQL[9]，微软的SCOPE[26]和Dryad-LINQ[27]以及IBM的JAQL[28]等等.从查询处理算法来看，目前针对云数据的查询处理和优化主要集中在基于MapReduce框架的查询处理.MapReduce天然地支持分组聚集操作和选择操作，而连接操作的实现则比较复杂.在分布式环境下数据传输和数据倾斜等问题的出现使得在MapReduce上实现连接成为一个非常具有挑战性的问题，下面主要对云数据的连接查询工作进行深入的总结分析.已有的相关工作主要分为两类，一类是直接在MapReduce上实现连接[9,25,28-33]，一类是修改MapReduce框架使之更利于连接的实现3-35].下面我们分别介绍这两类工作.

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。