云计算环境下的数据索引方法.doc

云计算环境下的数据索引方法
1.摘要
云计算和大数据时代的到来使得计算机产生和处理的数据量急剧增加。为了方便云环境下的数据存储和检索，必须为数据建立索引。传统的索引方法，如B+树等，在传统的数据库系统中已经得到了深入的研究和广泛的应用。但是云环境下，由于数据模型发生了根本改变，传统的索引技术已经无法直接应用在云计算环境中，找到一种适合特定云应用下的索引结构变得越来越重要。为了适应索引结构的新需求，前人已经进行了很多研究，探索出了适应于云应用环境下的数据索引技术。本文综述云计算环境下的索引技术，对比各种索引技术的优缺点，并指出各种索引技术的应用范围，为针对特定的应用环境选择合适的索引技术指出方向。
关键字：云计算； 索引结构； 分布式索引

Abstract
The era of cloud computing and big data have witnessed the sharp increase in the amount of data generated and processed. In order to facilitate data storage and the retrieval of cloud environment, an efficient index must be created. Traditional indexing methods, such as B+ trees, which are commonly used in existing database management system, have already been extensively studied. But in cloud environment, data model changes fundamentally, the traditional indexing technology can't be applied directly to applications in the cloud computing environment. To find a suitable index structure under specific cloud applications is becoming increasingly important. In order to meet the new demands of the cloud environment, our predecessors have conducted a lot of research, many indexing technologies that can be applied in cloud computing environment have been invented. This paper conducts a comprehensive survey on the formerly studied indexing technology of this kind and gives some guidance on how to choose appropriate indexing schema for specific application.
Keywords: cloud computing; index schema; distributed index;

2.概述
云计算是一种利用互联网实现随时随地、按需、便捷地访问共享资源池(如计算设施、存储设备、应用程等)的计算模式．计算机资源服务化是云计算重要的表现形式，它为用户屏蔽了数据中心管理、大规模数据处理、应用程序部署等问题．通过云计算，用户可以根据其业务负载快速申请或释放资源，并以按需支付的方式对所使用的资源付费，在提高服务质量的同时降低运维成本。目前许多大型公司都构建了自己的数据中心，一些IT公司如百度等，还提供了针对中小企业的企业级的云存储解决方案以及针对终端用户的个人云存储解决方案，收到了很好的效果。
索引技术是数据统一访问的基础，索引构建的优劣将直接影响到数据的统一访问。索引最早出现在文献系统中，它是将文献系统中的内容，按照可检索的顺序排列成条目表达出来。由于索引可以大大加快查询速度，因此被广泛的应用于于书籍、文献资料的查询。随着计算机技术的出现，索引技术也有了进一步的发展，特别是数据库系统中的索引技术。传统数据库的索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可以大大提高数据库中数据的查询和处理速度。在云计算环境下的，索引往往采用二级索引结构即全局索引以及局部索引。全局索引的使用，体现了分治策略的思想。全局索引由整个集群的节点共同维护，全局索引是整个应用数据的一个概要描述，主要用于将数据的查询修改等操作定位到集群中的特定节点，减轻集群中传递查询消息的网络传输量，并减轻集群中不包含查询信息的节点的处理工作量。局部索引是由单个集群中的节点维护的，针对本地数据的索引，局部索引可以采用与传统数据库索引类似的解决方案。云环存储环境中的数据最终都保存在单个节点上，局部索引的使用，方便了集群中的节点管理自己的本地数据，减少相应查询和修改的IO和计算时间消耗。
根据全局索引管理方式的不同，目前云计算环境下分布式存储系统的数据索引主要分为两类：集中式索引和分布式索引，集中式索引一般采用单个节点管理全局索引，目前流行的分布式存储系统如Google文件系统[1](GFS)和Hadoop分布式文件系统[2](HDFS)都是使用集中式索引结构。在集中式下，数据索引将占用管理节点极大的内存空间，与此同时，单一的管理节点存在单点失效的问题，且容易成为系统性能瓶颈。分布式索引机制[3-6]将全局索引分布在集群中的多个节点上，由集群中所有包含了全局索引数据的节点共同协调完成处理请求时的节点定位工作，有效避免了负载过重和单点失效的问题。目前使用分布式索引方式的存储系统有Amazon公司的Dynamo[3]和Yahoo!的PNUTS等。
另外，针对索引的维度数的不同，索引又可以分为一维索引和高维索引。一维索引针对记录中的某一个属性或合成一个属性的属性组建立索引。针对一维索引的查询只支持针对索引属性的单点查询或区间查询。多维索引可以针对记录的多个属性建立索引，支持针对多个属性的点查询、区间查询、K近邻等操作。
接下来的章节安排如下：第3章、第4章和第5章分别对集中式索引方式和分布式索引方式以及复合式索引方式中的各个有代表性的实现做详细的介绍，介绍各自的工作机制，找出他们优点和存在的问题，并给出适用范围。第6章总结全文，提出需要根据特定分布式应用环境寻找合适的索引方案的观点，并对在具体应用环境下选择索引方案时的注意事项做简要的介绍。
3.集中式索引机制
3.1 Hadoop File System文件目录
Hadoop File System文件目录[2]是一种典型的集中式索引方式。HDFS集群由名称节点和数据节点两类节点组成。名称节点管理着文件系统中的所有元数据信息，这些元数据包括文件名、访问控制信息、副本个数、块与其副本块的映射信息等等。数据节点存储着文件的数据块，维护着本数据节点中的数据块的索引信息列表，并定期以心跳形式向名称节点发送数据块的信息列表。

图1.Hadoop文件系统结构
HDFS 文件系统架构是采用管理者-工作者（Master-Slave）的结构，也就是一个名称节点（Master）和多个的数据节点（Slave）。名称节点其实就是一个主服务器，负责管理和维护集群中文件系统的全局索引信息，主要向客户端提供创建、打开、删除和重命名文件或目录的功能。数据节点是文件系统的工作者，主要是存储文件，管理分布式文件系统存储在本地的文件块索引信息，并负责处理对数据块的读写请求。一般是一台计算机作为一个数据节点。实际上一个大文件存储在 HDFS 文件系统中时，被分成一个或者多个数据块（默认为 64MB），这些块受名称节点的调度被分布存储在指定的数据节点上，数据节点在名称节点调度下对块进行创建、复制及删除操作（修改操作在 HDFS 中不支持）。数据节点也要定期向名称节点上报心跳，名称节点响应心跳来控制数据节点。心跳是指数据节点向名称节点传递索引信息。
在HDFS这种方式下，名称节点存储了整个文件系统的索引信息，所有的外部访问请求都要先通过名称节点才能定位到数据节点，而后由数据节点在本地文件索引中找到响应的数据块，服务外部请求。为了提高文件访问的速度，名称节点不仅需要有足够的内存将文件目录信息保留在内存中，而且还要有足够的带宽和处理能力响应所有的文件请求。当文件系统存储信息量上升，或者文件访问请求量增加时，名称节点容易成为整个系统的性能瓶颈，而且整个系统对名称节点的故障敏感，存在单点失效的问题。这种方式的优势在于存在一个节点拥有被索引对象的全局信息，可以有效避免不必要的查询开销。
4.分布式索引机制
4.1 分布式Hash表(HDT)
分布式散列表[3]（简称DHT）是分布式计索引中的一类，以键值对的形式组织资源的索引，其中K键为资源的Hash码，值就是资源的存储位置索引。每个存储在索引系统中的资源位置标识都被映射到一个唯一的Key值上。分布式Hash表用来将一个关键值（key）的集合分散到所有在分布式系统中的节点，以选择索引的存储节点。并且可以有效地将消息转送到唯一一个拥有查询者提供的关键字的节点（Peers）。这里的节点类似散列表中的存储位置。分布式散列表以键值对的形式组织索引，定位资源。在收到资源查询请求后，系统先用分布式Hash函数确定资源的key。然后使用分布式Hash表全局索引定位存储了资源索引信息的节点，返回节点编号。随后请求的发出者再到相应的节点查询局部索引，确定资源的位置。
一致性Hash是MIT提出的对分布式散列表的算法实现，它的提出使得DHT在P2P环境中真正得以应用。目前一致性Hash有多种实现算法，其中最具有代表性的包括Chord、CAN、Tapestry和Pastry。本文以Chord为例来描述构建数据中心存储节点间覆盖网络的一致性Hash算法。
Chord采用环作为其静态拓扑图，系统中每个节点和关键字的标识符都是一个m位的二进制串，分别通过对节点IP地址和关键字散列运算获得，所有节点根据标识符大小顺时针构成一个环形的拓扑结构。Chord环上所有节点都维护以下邻居信息：前驱节点predecessor(n)、后继节点successor(n)和finger表。Chord实现了两种对关键字是的重要操作：关键字插Insert(k)和关键字查询Lookup(k)。Insert(k)实现以下过程：对k进行散列运算，设id—Hash(k)，Chord将是插入到其在Chord环上的后继节点s=successor(id)(环中沿顺时针方向第1个不小于id的节点)上。Lookup(k)实现以下过程：资源查询时每个节点都通过查询指针表，将查询请求转发到离k最近的节点上．图1是优一4的Chord网络，网络中有5个节点：0，1，5，8和1．Hash(k)=10的后继节点是11，因此Insert(k)=11．图l给出了节点1和节点5的指针表，虚线给出了从节点1开始对k的查询过程，消息最终停止于节点11，即Lookup(k)一11。

图2.Chord示意图
分布式散列表(DHT)数据索引通常是为了拥有极大节点数量的系统，而且在系统的节点常常会加入或离开（例如网络断线）而设计的。在一个结构性的延展网络（overlay network）中，参加的节点需要与系统中一小部份的节点沟通，这也需要使用分布式散列表。分布式散列表索引技术可以用于创建更复杂的服务，例如分布式文件系统、点对点技术文件分享系统、合作的网页高速缓存、多播、任播、域名系统以及实时通信等。
分布式散列构建的两级索引中，所有的资源都可以用一个唯一的主键来标示，这种索引往往只支持单点查询，即通过资源的键定位资源所在的位置。然而云端用户提交的数据查询请求往往包含更加复杂的查询模式，如多维查询(multidimensional query)和区间查询(range query)例如在YouTube等在线视频应用中，一个视频数据往往需要用挖维向量(‰，点z，⋯，也一：)表示，每一维向量分别表示视频的维属性，如主题、作者、创建日期、清晰度等．查询请求Q=(20110101≤Date≤20110120，480≤Definition≤720)表示用户需要获取日期和清晰度两维元数据属于上述区间内的所有视频。由于分布式Hash表中的主键只包含一维元数据，因此其分布式索引机箭无法支持多维查询；与此同时，分布式Hash表为了保证数据分布的负载均衡在散列过程中会破坏数据的主键顺序，查询区间内的两个数值相邻的主键在散列运算后可能产生两个差值很大的标识符，进而被分配到两个存储节点上，因此DHT的分布式索引机制无法支持区间查询。
4.2 M-Index索引
针对云计算环境下分布式存储系统的数据索引不支持复杂查询的问题，朱夏[4]等人提出了一种多维数据索引机制M-Index，采用金字塔技术(pyramid-technique)将数据的多维元数据描述成一维索引，在此基础上首次提出前缀二叉树(prefix binary tree，PBT)的概念，通过提取一维索引PBT有效节点的前缀作为数据在存储系统中的主键。数据根据主键和一致性Hash机制发布到存储节点组成的覆盖网络。设计了基于M-Index的数据查询算法，将复杂查询请求转换成一维查询键值，支持多维查询和区间查询等复杂查询模式。
4.2.1索引降维
云端用户提交的数据在存储系统中一般具有多维元数据属性。在一致性Hash过程中数据的主键只能包含某一维元数据，这导致了诸如DHT等分布式存储索引结构无法支持多维查询．其解决思路是利用金字塔技术构建多维数据索引M-Index，将表示元数据的d维向量M(v0,v1,……,vd-1)降维成一维索引id。M-Index能够保证多维元数据在降维过程中不丢失各维信息，从而保证数据查询结果的完备性.M-Index以点P(0.5，⋯，0.5)为中心点，将d维空间0,1d等分成2d个子空间，同时将子空间命名为金字塔，将点P命名为金字塔的顶点，将d-1维空间命名为金字塔的底面。M—Index对金字塔的编号规则如下：在d维空间中任意一维向量D。(O≤m<d)都会与2个金字塔底面垂直，如果金字塔内任意一点的第m维坐标u0<0.5，则将该金字塔编号为m，否则将金字塔编号为m+d。计算点V与中心点P在第i(i≤d)或i-d(i>d)维的坐标差值hv=0.5-vi，再计算V的一维索引idv=i+hv。
4.2.2处理区间查询
由于一致性Hash可能会破坏一维索引值域区间[idmin,idmax]内的数值顺序，因此以一维索引id。为主键的存储系统仍然无法实现对区间查询的支持．然而我们观察发现，数值临近的二进制数具有共同前缀的概率往往较高，考虑将区间[idmin,idmax]划分成n+1个子区间δ0,δ1δ1,δ2,…,δn,δn+1，属于区间δi,δi+1内的一维索引选择区间上下界的二进制值δi2和δi+12的共同前缀prefixi=PREFIX(δi2,δi+12)作为主键。据查询过程根据查询区间与子区间的交集将区间查询转化成关于prefixi的单值查询．与此同时，为了保证数据发布的负载均衡，作者选择共同前缀作为主键的数据量动态调整子区问大小，并采用树形结构管理子区间的共同前缀。
4.2.3复杂查询请求转换
根据查询请求的维数和区间，将查询请求分为4类：一维单值查询(Q1)一维区间查询(Q2)、多维单值查询(Q3)和多维区间查询(Q4)，其中Q1~Q3。均可看作Q4的特例。d维区间查询请求的形式化定义为：
Q4={q0min,q0max,…,qjmin,qjmax,…,qd-1min,qd-1maz}
基于主键的存储系统显然无法直接识别诸如Q4的复杂查询请求，因此和数据的索引过程类似，需要根据M-Index将查询请求转换成存储系统可以识别的一维单值查询．首先引将Q4转换成一维区间查询请求Q2．在此基础上根据PBT将Q2转换成一维单值查询请求Q1．在降维过程中可能会出现查询结果冗余．为了解决该问题，我们在将查询请求索引成一维键值的同时仍然保留索引前的查询请求，通过匹配原始查询请求在冗余结果中筛选出正确结果。
4.2.4查询请求转发
Q4在提交至存储系统时会随机选择任一节点作为查询的初始节点Ninit。Ninit根据其索引节点INinit。上维护的M-Index将Q4转换成查询键值kij(o≤i<m，O≤j<ai)，并将i=0m-1ai个kij分别提交至覆盖网络转发．根据Chord的关键字查询操作Lookup，kij最终会被转发至索引节点IN。(n=Lookup(kij))(0≤i<m，O≤j<ai))．对于满足查询条件kij=k的数据D，如果同时满足∀O≤t<d,vi∈qtmin,qtmax，则查询成功，存储节点SN。将数据传输给查询请求者。
这种方法的总体思路是将多为索引降维为一维索引，将多维索引的区间查询转化为一维索引的区间查询，但是这种方法不能维持索引结构的局部性，例如在高维空间中一个矩形的区间对应着一维映射区间中许多不连续的区域，当维数增加时会出现“维数灾难”
4.3 MIDAS索引
George Tsatsanifos[5]在他的文章中提出一种基于peer-to-peerd的高维索引方法。MIDAS索引采用两层索引结构，以一种结构化覆盖的方式组织计算节点。在实际存储数据的物理节点上建立本地索引，然后在服务器端建立全局的索引。当用户查询数据时，通过服务器端的全局索引定位到本地索引，然后进行数据的查询。MIDAS采用分布式的K-D树索引作为全局索引，文章中作者给出了点查询和区间查询的实现算法。由于MIDAS采用peer-to-peer架构存储全局索引，每个索引节点只拥有全局索引中的一部分，索引节点可以随时加入和离开索引集群，具有很高的可扩展性。对于一个节点数为n的覆盖网络，每个节点只需要维护O(logn)个状态，实现简单，每一个请求在O(logn)的跳数内能够被处理，节省网络资源。
4.4 RT-CAN索引
Jinbao Wang[6]在它的文章中提出RT-CAN多维索引模型，RT-CAN模型结合了基于CAN的路由选择协议和基于R-Tree的索引模型用以在云计算环境中支持高效的多维查询处理。RT-CAN在扩展CAN协议的基础上将存储节点和计算节点组织成一个覆盖网络。在这种协议中，每个节点都使用R-Tree式索引来索引局部数据。在文章中他还提出了一种面向查询的代价模型用以选择最优的局部R-Tree节点来发布。通过小数目维持持续连接的节点和一个全局的多维索引，该索引模式能够在很少的跳数内定为包含了查询结果的节点，使得这种索引在数据容量和节点数量上具有较好的可伸缩性。
在集中式索引结构中，查询进行的过程中，所有的查询被送到主服务器来查询全局索引然后查询被传递到包含有查询结果的服务器。由于全局索引的只包含了索引数据的一部分而且并发的查询量巨大，主服务器很可能成为性能瓶颈，RT-CAN将全局索引分布到多个节点中，每一个节点只保存全局索引的一部分，这种索引组织方式提高了可扩展性和容错能力。
RT-CAN的具体组织方式如下，为了将全局索引分布在纪尊众，服务器被组织成一种覆盖网络的形式，特别地全局索引节点之间的通信CAN协议，因为CAN适合多维查询。为了高效检索局部数据，数据节点上的数据库中都建立了R-Tree索引。将数据节点的局部R-Tree索引的索引节点发布到全局索引中，而不是为每条记录建立全局索引。因而，由来自不同数据的R-Tree节点局部索引组成的全局索引在系统中扮演一个“概要索引”的角色。为局部R-Tree索引节点建立索引减少了全局索引的数据量，减轻了索引维护带来的开销。在查询的过程中一旦我们在全局索引中定位了R-Tree索引节点，我们只需要从注册在全局索引中的R-Tree节点处开始搜索局部的R-Tree。
将每一个R-Tree节点发布到全局索引中是不现实的，因为这会导致很高的索引维护代价。因此必须选择一部分对于路由有帮助的局部R-Tree节点，然后将他们发布到全局索引中。由于不同的选择方案会导致不同的代价，文章提出了一种评估所有可能的选择方案的模型，这种模型基于对查询和更新分布的统计，能够动态调整索引策略，最小化索引维护代价。
目前这种索引技术在P2P环境中收到了很好的效果，但是在云环境中存在着同步低和一致性弱的问题。
5.复合索引机制
5.1 分片位图索引
集中式方案和分布式方案各有优势．集中式方案拥有被索引字段的全局信息，可以有效地避免不必要的查询开销，但是，全局信息的维护与访问也带来了额外的代价，致使查询的响应速度受到影响．分布式方案能够充分利用并行计算资源的优势，但是由于缺乏被索引字段上值的整体分布信息，即使对于目标值仅局部分布在少数几个数据节点上的检索请求，也会导致触发整个集群上的并行检索．而事实上，其中大部分数据节点上返回的命中集合都将是空集．因而，大量的并行计算资源被白白浪费了．孟必平等人[7]介绍了一种折中的解决方案：分片位索引(regional bitmap index)。该方法既具有分布式方案的高并行度特点，从而带来了快速的请求响应，同时又拥有如同在集中式方案中那样了解全局的数据分布信息的优势，进而尽最大努力避免了不必要的检索代价，提高了系统的查询吞吐量．相比使用特殊的通信协议而实现的分布式方案的诸扩展方法，该方法通过引入属性值的全局排序机制来彻底避免不同数据节点之间的通信．从而，使得开发人员能够从设计复杂通信协议的任务中解放出来．这一特点降低了本方法对网络拓扑和通信系统的依赖，从而提高了查询效率．另外，通过这种方式，本方法将无需访问目标云环境所暴露的网络通信接口，因此能够适用于更广泛的云存储环境。字段值上的全局排序机制以及位图索引的分片机制（全局排序机制能够为各数据节点提供一定的全局信息，即局部数据在全局值域中的分布情况；而位图索引的分片机制使得索引结构局部化，从而使不同数据节点上的检索任务充分独立，以便并发执行）．然后综合运用上述技术给出了分片位图索引技术的构造方法及其存储结构。
5.1.1字段值全局排序
考虑在数值属性A1,A2,,A3,…,Af共f个属性上建立索引，首先将各属性Ai的值域切割为ci个子域．如果属性取值为离散值，则可将每一个取值单独划分为一个子域；如果为其它类型，则可将其二进制表示作为其位串值，例如字符串中各字符的ＡＳＣＩ码组成的二进制位串；并按照二进制位串的数值大小对属性值域进行划分．设值域切割所得子域所构成的集合为Ci，那么子域的笛卡尔积Des1.。。f=C1×C2×C3×…×Cf的大小为B=i=1fci。使用一个长为i=1fci的位串来表示每一个元组。设元组t的属性Ai的第j个子域对应的位为bi,j，那么该元组所对应的位串可以表示为:
b1,1b1,2b1,3…b2,1,b2,2b2,3…,bf,1bf,2bf,3..bf,cf
给定一个任意的元组t及其所对应的位串，∀i∈[1,f]有且仅有唯一一个j∈1,ci使得bij=1，因此该位串的所有合法的取值可以一一对应上述子域笛卡尔积Des1…f中的元素．从而，任意元组所对应的位串将拥有B=i=1fci个可能的取值．在给定属性列及其上的子域划分的情况下，将元组对应的位串的所有可能取值按照从小到大的顺序排序．位串的所有可能的取值可一一对应到一个排序值ｒ∈[1,B]上．这样，任意元组在被考察的数据字段上的取值均对应于一个唯一的排序值ｒ．至此，完成了对所有元组上的索引值的全局排序。
5.1.2索引的分片
类似于上述分布式方案，本方法同样采用各数据节点独立管理局部数据上索引的方式，以便提高检索执行时的并行度．在每个数据节点上，对该节点上存在的元组所对应的位串的全局排序值建立Ｂ＋树．树的叶结点中的每个键都对应于一个排序值，并记录一个长度为本数据节点所管理的元组总数的位图，其中拥有该排序值的元组所对应的位被置１，其它位被置０．这里将其称为元组位图．易见，单个数据节点上的Ｂ＋ 树的所有叶子结点上最多拥有Ｂ 个键，因此最多存在Ｂ 个不同的元组位图。
5.1.3索引的创建
综合运用以上两项技术，在云环境中分片位图索引的各组成部分以及其创建流程．该方法的动机来源于吸取并综合集中式方案与分布式方案的优点．首先对于给定的被索引属性上的取值，其对应位串存在唯一的全局排序值．据此，利用局部存在于各数据节点上的数据所对应的排序值为其构造局部的指示位图．该指示位图的长度为子域笛卡尔积的大小Ｂ．如果该数据节点上存在排序值为ｒ的元组，则该数据节点上指示位图的第ｒ位为1，反之则为0．
指示位图记录了局部属性值的存在情况．检索请求到达各数据节点时，首先通过比对指示位图来确定本数据节点是否包含目标元组，如果不存在，则直接返回空值，而不执行检索任务．除了为每个数据节点构造指示位图之外，还应当建立局部数据上的位图索引．该局部位图索引由两部分构成：以全局排序值为键的Ｂ＋ 树以及Ｂ＋ 树叶子结点上所附着的相应字段值上的局部元组位图．在执行检索任务时，如果与指示位图进行比对的结果不为全零串，则需要触发Ｂ＋ 树上的检索操作．指示位图的创建过程中需要扫描局部节点上所存在的所有元组，此过程的计算代价正比于局部数据节点上元组的数量；对于局部位图索引，Ｂ＋ 树的规模正比于子域笛卡尔积的大小Ｂ，与元组数量无关，元组位图的创建过程也需要扫描局部节点上所存在的所有元组，因此其代价亦正比于节点所管理的元组数量．通常情况下子域笛卡尔积的大小远小于元组数量，因此整个分片位图索引的创建代价正比于局部数据节点上所管理元组数量的最大值．
5.1.4单个索引上的检索条件
对于查询请求中的单个索引上检索条件，主节点首先将检索条件转换为条件位串．注意生成的条件位串应当覆盖检索条件所包含的所有可能性．然后主节点将条件位串并行地发送到所有的数据节点上，各数据节点分别将条件位串转换为对应的排序值的范围，接着生成长度等于B的全0位串cｂ，并将属于排序值范围内的位置为１．检查按位逻辑与eb＆cb的计算结果是否为０．如果为０则在该数据节点上直接返回空集作为计算结果；否则，在该数据节点的局部B+ 树上依次搜索各符合条件的排序值，将找到元组位图进行按位逻辑与，一一检查其计算结果中被置为１的位所对应的元组是否满足检索条件，最后返回所有满足条件的结果作为计算结果．
5.1.5检索条件的复合
通过将在同一数据节点上的不同属性上检索得到的元组位图进行相应的按位逻辑运算，可以实现多个检索条件的快速复合．这充分利用了现代计算机能够对位图快速操作的计算优势．具体而言，其执行步骤为：首先主节点将各简单检索条件分别转换为条件位串，并将这些条件位串以及条件之间的复合关系分发到各个数据节点．然后，各数据节点分别依次执行各简单检索条件上的检索流程，从而查找到各简单条件所对应的元组位图，并将这些元组位图依照检索条件复合方法执行按位逻辑运算，得到最终的元组结果位图．最后，扫描该位图中为被置为１的位，并向主节点返回相应的满足检索条件的元组。
5.1.6索引效果分析
这种方式充分发挥集中式方案和分布式方案两种基本方案中的优势，既能够使云环境中并行计算资源得到很好的利用，从而提高了单条查询的响应速度，又能够通过局部节点所掌握的全局信息而规避不必要的检索代价从而使在大量检索请求并发到达时查询吞吐量得以保证。
6.总结
云计算环境下，数据模型以及数据的组织方式发生了根本的改变，适用于传统数据库的数据索引不能够被简单地移植到云环境中，例如B+树索引在传统的数据库中，通过将树接近根节点的几层驻留在内存中的方式减少查询时的磁盘IO，但是在云环境中过度密集地访问索引中的某一个部分容易照成索引过热的现象，产生性能瓶颈和单点失效的问题。随着云计算的兴起，前人在为云计算环境下设计高效的索引方面做了许多研究，这些索引大多采用双层索引结构，即同时拥有保存在索引节点上的全局索引和数据节点上的局部索引。
本文按照全局索引组织方式的不同，将前人的研究成果分为集中式索引和分布式索引两大类，各列举了一些有代表性的索引方案进行分析。集中式索引方式下，集群中存在某个节点拥有整个集群的全局索引信息，通过查询该节点，查询可以很方便地被定位到拥有被查询信息的节点，而不需要在多个保存了全局索引的节点之间进行转发，具有较高的查询处理效率，而且不容易产生全局索引信息与局部索引信息不一致的问题，但是由于每次查询都要从某个节点开始，随着查询次数的增加，而存在着难以避免的性能瓶颈，并有单点失效的风险。分布式索引机制将全局索引分布到集群中的多个索引节点上，通过特定的更新策略来维护全局索引的一致性。查询全局索引时，查询请求在全局索引节点之间按一定的策略转发，直到被拥有被查询索引的节点处理。这种索引方式能够发挥集群中多个集群的并行处理能力，可以根据索引数据量和请求数量增加或减少节点，具有比较强的可伸缩性和容错能力，但是存在着全局索引不一致，和查询效率低，网络带宽消耗大的问题。在针对特定的云应用环境选择索引时需要考虑需要处理的数据量、集群的性能、并发访问量、访问数据的实时性要求以及可靠性等因数，选择合适的索引机制。

参考文献
[1] Ghemawat S, Gobioff H, Leung S T. The Google file system[C]//ACM SIGOPS Operating Systems Review. ACM, 2003, 37(5): 29-43.
[2]Borthakur D. The hadoop distributed file system: Architecture and design[J]. 2007.
[3] DeCandia G, Hastorun D, Jampani M, et al. Dynamo: amazon's highly available key-value store[C]//SOSP. 2007, 7: 205-220.
[4]朱夏,罗军舟,宋爱波等.云计算环境下支持复杂查询的多维数据索引机制[J].计算机研究与发展,2013,50(8):1592-1603.
[5] Tsatsanifos G, Sacharidis D, Sellis T. Midas: multi-attribute indexing for distributed architecture systems[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg, 2011: 168-185.
[6] Wang J, Wu S, Gao H, et al. Indexing multi-dimensional data in a cloud system[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 2010: 591-602.
[7]孟必平,王腾蛟,李红燕等.分片位图索引:一种适用于云数据管理的辅助索引机制[J].计算机学报,2012,35(11):2306-2316.DOI:10.3724/SP.J.1016.2012.02306.
[8] Aguilera M K, Golab W, Shah M A. A practical scalable distributed b-tree[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 598-609.
[9]孙春菊.云环境下数据模型和索引技术研究[D].南京邮电大学,2013.
[10]于戈,谷峪,鲍玉斌等.云计算环境下的大规模图数据处理技术[J].计算机学报,2011,34(10):1753-1767.DOI:10.3724/SP.J.1016.2011.01753.
[11]陈占龙,吴信才,谢忠等.分布式空间数据索引机制研究[J].微电子学与计算机,2007,24(10):54-57.DOI:10.3969/j.issn.1000-7180.2007.10.016.
[12]乐璐.基于Hadoop的高级计量架构平台海量数据的处理方法研究[D].北京邮电大学,2011. [13]程彬.海量数据组织中的索引机制研究与实现[D].华中科技大学,2008.DOI:10.7666/d.d064844.
[14]旷文科.基于分布式计算的搜索引擎关键技术研究与实现[D].西安电子科技大学,2013.