论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　根据全局索引的组织方式，双层索引可以分成两类：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仅支持一些基本的数据插入和获取接口。随后很多公司和研究机构在丰富查询语句上开展了工作并提出一些"类-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].下面我们分别介绍这两类工作。
　　(1)基于原始MapReduce的连接算法
　　这类算法通过设计Map函数、Reduce函数和数据流来完成连接，涉及到的连接方式包括两表等值连接[9,25,28-29]、两表0连接[3°]、多表等值连接[1-32]和两表集合相似性连接[3°]3种类型。如表3所示，我们首先对两表等值连接的算法进行分析比较.设参加连接的两个表分别为只和S，并且只为其中数据量较小的表标准重分区算法[9'25'28_29].该算法类似于〇8皿3中的排序合并算法，由一个MapReduce作业构成.Mapper读入两个表的数据文件，并根据查询条件对数据进行过滤.输出的键值对中，键值是连接的列值，数值部分包括记录值和标签两部分，标签用于标识该记录来自哪个表.在reduce的混洗（shuffle)过程中，具有相同连接值的记录被分区到同一个reducer上.针对每一个连接值，reducer根据标签把记录分成两个集合，然后计算两个集合元素的向量积从而完成连接.标准重分区算法在现有云数据管理系统比较常见，Pig、Hive和Jaql均实现了这种算法[8,5,8].该算法的一个潜在问题是针对某个连接键值计算向量积时，两个表的相关数据都要放入内存进行缓存.当连接键值基数比较少或者出现数据倾斜时，会导致某个连接键值对应的数据量较大，一方面可能会造成内存溢出，另一方面造成计算资源分布不均匀。
　　改进的重分区算法[29].为了解决标准重分区算法的内存缓存问题，该算法从两个方面进行了改进：首先，map阶段输出的键值由连接的列值和表名的标签值混合构成，标签值放到键值中可以保证在reduce阶段进行排序时，来自其中一个表的数据总是排在另一个表的前面.其次，在计算卡氏积时，内存中只缓存较小表的数据，而另一个大表的数据以数据流的方式读入内存.这样，算法对内存大小的要求大大降低。