云計(jì)算環(huán)境下的數(shù)據(jù)索引方法

精選優(yōu)質(zhì)文檔-----傾情為你奉上精選優(yōu)質(zhì)文檔-----傾情為你奉上專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-----傾情為你奉上專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)云計(jì)算環(huán)境下的數(shù)據(jù)索引方法1.摘要云計(jì)算和大數(shù)據(jù)時(shí)代的到來(lái)使得計(jì)算機(jī)產(chǎn)生和處理的數(shù)據(jù)量急劇增加。為了方便云環(huán)境下的數(shù)據(jù)存儲(chǔ)和檢索，必須為數(shù)據(jù)建立索引。傳統(tǒng)的索引方法，如B+樹(shù)等，在傳統(tǒng)的數(shù)據(jù)庫(kù)系統(tǒng)中已經(jīng)得到了深入的研究和廣泛的應(yīng)用。但是云環(huán)境下，由于數(shù)據(jù)模型發(fā)生了根本改變，傳統(tǒng)的索引技術(shù)已經(jīng)無(wú)法直接應(yīng)用在云計(jì)算環(huán)境中，找到一種適合特定云應(yīng)用下的索引結(jié)構(gòu)變得越來(lái)越重要。為了適應(yīng)索引結(jié)構(gòu)的新需求，前人已經(jīng)進(jìn)行了很多研究，探索出了適應(yīng)于云應(yīng)用環(huán)境下的數(shù)據(jù)索引技術(shù)。本文綜述云計(jì)算環(huán)境下的索引技術(shù)，對(duì)比各種索引技術(shù)的優(yōu)缺點(diǎn)，并指出各種索引技術(shù)的應(yīng)用范圍，為針對(duì)特定的應(yīng)用環(huán)境選擇合適的索引技術(shù)指出方向。關(guān)鍵字：云計(jì)算；索引結(jié)構(gòu)；分布式索引

AbstractTheeraofcloudcomputingandbigdatahavewitnessedthesharpincreaseintheamountofdatageneratedandprocessed.Inordertofacilitatedatastorageandtheretrievalofcloudenvironment,anefficientindexmustbecreated.Traditionalindexingmethods,suchasB+trees,whicharecommonlyusedinexistingdatabasemanagementsystem,havealreadybeenextensivelystudied.Butincloudenvironment,datamodelchangesfundamentally,thetraditionalindexingtechnologycan'tbeapplieddirectlytoapplicationsinthecloudcomputingenvironment.Tofindasuitableindexstructureunderspecificcloudapplicationsisbecomingincreasinglyimportant.Inordertomeetthenewdemandsofthecloudenvironment,ourpredecessorshaveconductedalotofresearch,manyindexingtechnologiesthatcanbeappliedincloudcomputingenvironmenthavebeeninvented.Thispaperconductsacomprehensivesurveyontheformerlystudiedindexingtechnologyofthiskindandgivessomeguidanceonhowtochooseappropriateindexingschemaforspecificapplication.Keywords:cloudcomputing;indexschema;distributedindex;

2.概述云計(jì)算是一種利用互聯(lián)網(wǎng)實(shí)現(xiàn)隨時(shí)隨地、按需、便捷地訪問(wèn)共享資源池(如計(jì)算設(shè)施、存儲(chǔ)設(shè)備、應(yīng)用程等)的計(jì)算模式．計(jì)算機(jī)資源服務(wù)化是云計(jì)算重要的表現(xiàn)形式，它為用戶(hù)屏蔽了數(shù)據(jù)中心管理、大規(guī)模數(shù)據(jù)處理、應(yīng)用程序部署等問(wèn)題．通過(guò)云計(jì)算，用戶(hù)可以根據(jù)其業(yè)務(wù)負(fù)載快速申請(qǐng)或釋放資源，并以按需支付的方式對(duì)所使用的資源付費(fèi)，在提高服務(wù)質(zhì)量的同時(shí)降低運(yùn)維成本。目前許多大型公司都構(gòu)建了自己的數(shù)據(jù)中心，一些IT公司如百度等，還提供了針對(duì)中小企業(yè)的企業(yè)級(jí)的云存儲(chǔ)解決方案以及針對(duì)終端用戶(hù)的個(gè)人云存儲(chǔ)解決方案，收到了很好的效果。索引技術(shù)是數(shù)據(jù)統(tǒng)一訪問(wèn)的基礎(chǔ)，索引構(gòu)建的優(yōu)劣將直接影響到數(shù)據(jù)的統(tǒng)一訪問(wèn)。索引最早出現(xiàn)在文獻(xiàn)系統(tǒng)中，它是將文獻(xiàn)系統(tǒng)中的內(nèi)容，按照可檢索的順序排列成條目表達(dá)出來(lái)。由于索引可以大大加快查詢(xún)速度，因此被廣泛的應(yīng)用于于書(shū)籍、文獻(xiàn)資料的查詢(xún)。隨著計(jì)算機(jī)技術(shù)的出現(xiàn)，索引技術(shù)也有了進(jìn)一步的發(fā)展，特別是數(shù)據(jù)庫(kù)系統(tǒng)中的索引技術(shù)。傳統(tǒng)數(shù)據(jù)庫(kù)的索引是對(duì)數(shù)據(jù)庫(kù)表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，使用索引可以大大提高數(shù)據(jù)庫(kù)中數(shù)據(jù)的查詢(xún)和處理速度。在云計(jì)算環(huán)境下的，索引往往采用二級(jí)索引結(jié)構(gòu)即全局索引以及局部索引。全局索引的使用，體現(xiàn)了分治策略的思想。全局索引由整個(gè)集群的節(jié)點(diǎn)共同維護(hù)，全局索引是整個(gè)應(yīng)用數(shù)據(jù)的一個(gè)概要描述，主要用于將數(shù)據(jù)的查詢(xún)修改等操作定位到集群中的特定節(jié)點(diǎn)，減輕集群中傳遞查詢(xún)消息的網(wǎng)絡(luò)傳輸量，并減輕集群中不包含查詢(xún)信息的節(jié)點(diǎn)的處理工作量。局部索引是由單個(gè)集群中的節(jié)點(diǎn)維護(hù)的，針對(duì)本地?cái)?shù)據(jù)的索引，局部索引可以采用與傳統(tǒng)數(shù)據(jù)庫(kù)索引類(lèi)似的解決方案。云環(huán)存儲(chǔ)環(huán)境中的數(shù)據(jù)最終都保存在單個(gè)節(jié)點(diǎn)上，局部索引的使用，方便了集群中的節(jié)點(diǎn)管理自己的本地?cái)?shù)據(jù)，減少相應(yīng)查詢(xún)和修改的IO和計(jì)算時(shí)間消耗。根據(jù)全局索引管理方式的不同，目前云計(jì)算環(huán)境下分布式存儲(chǔ)系統(tǒng)的數(shù)據(jù)索引主要分為兩類(lèi)：集中式索引和分布式索引，集中式索引一般采用單個(gè)節(jié)點(diǎn)管理全局索引，目前流行的分布式存儲(chǔ)系統(tǒng)如Google文件系統(tǒng)[1](GFS)和Hadoop分布式文件系統(tǒng)[2](HDFS)都是使用集中式索引結(jié)構(gòu)。在集中式下，數(shù)據(jù)索引將占用管理節(jié)點(diǎn)極大的內(nèi)存空間，與此同時(shí)，單一的管理節(jié)點(diǎn)存在單點(diǎn)失效的問(wèn)題，且容易成為系統(tǒng)性能瓶頸。分布式索引機(jī)制[3-6]將全局索引分布在集群中的多個(gè)節(jié)點(diǎn)上，由集群中所有包含了全局索引數(shù)據(jù)的節(jié)點(diǎn)共同協(xié)調(diào)完成處理請(qǐng)求時(shí)的節(jié)點(diǎn)定位工作，有效避免了負(fù)載過(guò)重和單點(diǎn)失效的問(wèn)題。目前使用分布式索引方式的存儲(chǔ)系統(tǒng)有Amazon公司的Dynamo[3]和Yahoo!的PNUTS等。另外，針對(duì)索引的維度數(shù)的不同，索引又可以分為一維索引和高維索引。一維索引針對(duì)記錄中的某一個(gè)屬性或合成一個(gè)屬性的屬性組建立索引。針對(duì)一維索引的查詢(xún)只支持針對(duì)索引屬性的單點(diǎn)查詢(xún)或區(qū)間查詢(xún)。多維索引可以針對(duì)記錄的多個(gè)屬性建立索引，支持針對(duì)多個(gè)屬性的點(diǎn)查詢(xún)、區(qū)間查詢(xún)、K近鄰等操作。接下來(lái)的章節(jié)安排如下：第3章、第4章和第5章分別對(duì)集中式索引方式和分布式索引方式以及復(fù)合式索引方式中的各個(gè)有代表性的實(shí)現(xiàn)做詳細(xì)的介紹，介紹各自的工作機(jī)制，找出他們優(yōu)點(diǎn)和存在的問(wèn)題，并給出適用范圍。第6章總結(jié)全文，提出需要根據(jù)特定分布式應(yīng)用環(huán)境尋找合適的索引方案的觀點(diǎn)，并對(duì)在具體應(yīng)用環(huán)境下選擇索引方案時(shí)的注意事項(xiàng)做簡(jiǎn)要的介紹。3.集中式索引機(jī)制HadoopFileSystem文件目錄HadoopFileSystem文件目錄[2]是一種典型的集中式索引方式。HDFS集群由名稱(chēng)節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)兩類(lèi)節(jié)點(diǎn)組成。名稱(chēng)節(jié)點(diǎn)管理著文件系統(tǒng)中的所有元數(shù)據(jù)信息，這些元數(shù)據(jù)包括文件名、訪問(wèn)控制信息、副本個(gè)數(shù)、塊與其副本塊的映射信息等等。數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)著文件的數(shù)據(jù)塊，維護(hù)著本數(shù)據(jù)節(jié)點(diǎn)中的數(shù)據(jù)塊的索引信息列表，并定期以心跳形式向名稱(chēng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)塊的信息列表。圖1.Hadoop文件系統(tǒng)結(jié)構(gòu)HDFS文件系統(tǒng)架構(gòu)是采用管理者-工作者（Master-Slave）的結(jié)構(gòu)，也就是一個(gè)名稱(chēng)節(jié)點(diǎn)（Master）和多個(gè)的數(shù)據(jù)節(jié)點(diǎn)（Slave）。名稱(chēng)節(jié)點(diǎn)其實(shí)就是一個(gè)主服務(wù)器，負(fù)責(zé)管理和維護(hù)集群中文件系統(tǒng)的全局索引信息，主要向客戶(hù)端提供創(chuàng)建、打開(kāi)、刪除和重命名文件或目錄的功能。數(shù)據(jù)節(jié)點(diǎn)是文件系統(tǒng)的工作者，主要是存儲(chǔ)文件，管理分布式文件系統(tǒng)存儲(chǔ)在本地的文件塊索引信息，并負(fù)責(zé)處理對(duì)數(shù)據(jù)塊的讀寫(xiě)請(qǐng)求。一般是一臺(tái)計(jì)算機(jī)作為一個(gè)數(shù)據(jù)節(jié)點(diǎn)。實(shí)際上一個(gè)大文件存儲(chǔ)在HDFS文件系統(tǒng)中時(shí)，被分成一個(gè)或者多個(gè)數(shù)據(jù)塊（默認(rèn)為64MB），這些塊受名稱(chēng)節(jié)點(diǎn)的調(diào)度被分布存儲(chǔ)在指定的數(shù)據(jù)節(jié)點(diǎn)上，數(shù)據(jù)節(jié)點(diǎn)在名稱(chēng)節(jié)點(diǎn)調(diào)度下對(duì)塊進(jìn)行創(chuàng)建、復(fù)制及刪除操作（修改操作在HDFS中不支持）。數(shù)據(jù)節(jié)點(diǎn)也要定期向名稱(chēng)節(jié)點(diǎn)上報(bào)心跳，名稱(chēng)節(jié)點(diǎn)響應(yīng)心跳來(lái)控制數(shù)據(jù)節(jié)點(diǎn)。心跳是指數(shù)據(jù)節(jié)點(diǎn)向名稱(chēng)節(jié)點(diǎn)傳遞索引信息。在HDFS這種方式下，名稱(chēng)節(jié)點(diǎn)存儲(chǔ)了整個(gè)文件系統(tǒng)的索引信息，所有的外部訪問(wèn)請(qǐng)求都要先通過(guò)名稱(chēng)節(jié)點(diǎn)才能定位到數(shù)據(jù)節(jié)點(diǎn)，而后由數(shù)據(jù)節(jié)點(diǎn)在本地文件索引中找到響應(yīng)的數(shù)據(jù)塊，服務(wù)外部請(qǐng)求。為了提高文件訪問(wèn)的速度，名稱(chēng)節(jié)點(diǎn)不僅需要有足夠的內(nèi)存將文件目錄信息保留在內(nèi)存中，而且還要有足夠的帶寬和處理能力響應(yīng)所有的文件請(qǐng)求。當(dāng)文件系統(tǒng)存儲(chǔ)信息量上升，或者文件訪問(wèn)請(qǐng)求量增加時(shí)，名稱(chēng)節(jié)點(diǎn)容易成為整個(gè)系統(tǒng)的性能瓶頸，而且整個(gè)系統(tǒng)對(duì)名稱(chēng)節(jié)點(diǎn)的故障敏感，存在單點(diǎn)失效的問(wèn)題。這種方式的優(yōu)勢(shì)在于存在一個(gè)節(jié)點(diǎn)擁有被索引對(duì)象的全局信息，可以有效避免不必要的查詢(xún)開(kāi)銷(xiāo)。4.分布式索引機(jī)制分布式Hash表(HDT)分布式散列表[3]（簡(jiǎn)稱(chēng)DHT）是分布式計(jì)索引中的一類(lèi)，以鍵值對(duì)的形式組織資源的索引，其中K鍵為資源的Hash碼，值就是資源的存儲(chǔ)位置索引。每個(gè)存儲(chǔ)在索引系統(tǒng)中的資源位置標(biāo)識(shí)都被映射到一個(gè)唯一的Key值上。分布式Hash表用來(lái)將一個(gè)關(guān)鍵值（key）的集合分散到所有在分布式系統(tǒng)中的節(jié)點(diǎn)，以選擇索引的存儲(chǔ)節(jié)點(diǎn)。并且可以有效地將消息轉(zhuǎn)送到唯一一個(gè)擁有查詢(xún)者提供的關(guān)鍵字的節(jié)點(diǎn)（Peers）。這里的節(jié)點(diǎn)類(lèi)似散列表中的存儲(chǔ)位置。分布式散列表以鍵值對(duì)的形式組織索引，定位資源。在收到資源查詢(xún)請(qǐng)求后，系統(tǒng)先用分布式Hash函數(shù)確定資源的key。然后使用分布式Hash表全局索引定位存儲(chǔ)了資源索引信息的節(jié)點(diǎn)，返回節(jié)點(diǎn)編號(hào)。隨后請(qǐng)求的發(fā)出者再到相應(yīng)的節(jié)點(diǎn)查詢(xún)局部索引，確定資源的位置。一致性Hash是MIT提出的對(duì)分布式散列表的算法實(shí)現(xiàn)，它的提出使得DHT在P2P環(huán)境中真正得以應(yīng)用。目前一致性Hash有多種實(shí)現(xiàn)算法，其中最具有代表性的包括Chord、CAN、Tapestry和Pastry。本文以Chord為例來(lái)描述構(gòu)建數(shù)據(jù)中心存儲(chǔ)節(jié)點(diǎn)間覆蓋網(wǎng)絡(luò)的一致性Hash算法。Chord采用環(huán)作為其靜態(tài)拓?fù)鋱D，系統(tǒng)中每個(gè)節(jié)點(diǎn)和關(guān)鍵字的標(biāo)識(shí)符都是一個(gè)m位的二進(jìn)制串，分別通過(guò)對(duì)節(jié)點(diǎn)IP地址和關(guān)鍵字散列運(yùn)算獲得，所有節(jié)點(diǎn)根據(jù)標(biāo)識(shí)符大小順時(shí)針構(gòu)成一個(gè)環(huán)形的拓?fù)浣Y(jié)構(gòu)。Chord環(huán)上所有節(jié)點(diǎn)都維護(hù)以下鄰居信息：前驅(qū)節(jié)點(diǎn)predecessor(n)、后繼節(jié)點(diǎn)successor(n)和finger表。Chord實(shí)現(xiàn)了兩種對(duì)關(guān)鍵字是的重要操作：關(guān)鍵字插Insert(k)和關(guān)鍵字查詢(xún)Lookup(k)。Insert(k)實(shí)現(xiàn)以下過(guò)程：對(duì)k進(jìn)行散列運(yùn)算，設(shè)id—Hash(k)，Chord將是插入到其在Chord環(huán)上的后繼節(jié)點(diǎn)s=successor(id)(環(huán)中沿順時(shí)針?lè)较虻?個(gè)不小于id的節(jié)點(diǎn))上。Lookup(k)實(shí)現(xiàn)以下過(guò)程：資源查詢(xún)時(shí)每個(gè)節(jié)點(diǎn)都通過(guò)查詢(xún)指針表，將查詢(xún)請(qǐng)求轉(zhuǎn)發(fā)到離k最近的節(jié)點(diǎn)上．圖1是優(yōu)一4的Chord網(wǎng)絡(luò)，網(wǎng)絡(luò)中有5個(gè)節(jié)點(diǎn)：0，1，5，8和1．Hash(k)=10的后繼節(jié)點(diǎn)是11，因此Insert(k)=11．圖l給出了節(jié)點(diǎn)1和節(jié)點(diǎn)5的指針表，虛線給出了從節(jié)點(diǎn)1開(kāi)始對(duì)k的查詢(xún)過(guò)程，消息最終停止于節(jié)點(diǎn)11，即Lookup(k)一11。圖2.Chord示意圖分布式散列表(DHT)數(shù)據(jù)索引通常是為了擁有極大節(jié)點(diǎn)數(shù)量的系統(tǒng)，而且在系統(tǒng)的節(jié)點(diǎn)常常會(huì)加入或離開(kāi)（例如網(wǎng)絡(luò)斷線）而設(shè)計(jì)的。在一個(gè)結(jié)構(gòu)性的延展網(wǎng)絡(luò)（overlaynetwork）中，參加的節(jié)點(diǎn)需要與系統(tǒng)中一小部份的節(jié)點(diǎn)溝通，這也需要使用分布式散列表。分布式散列表索引技術(shù)可以用于創(chuàng)建更復(fù)雜的服務(wù)，例如分布式文件系統(tǒng)、點(diǎn)對(duì)點(diǎn)技術(shù)文件分享系統(tǒng)、合作的網(wǎng)頁(yè)高速緩存、多播、任播、域名系統(tǒng)以及實(shí)時(shí)通信等。分布式散列構(gòu)建的兩級(jí)索引中，所有的資源都可以用一個(gè)唯一的主鍵來(lái)標(biāo)示，這種索引往往只支持單點(diǎn)查詢(xún)，即通過(guò)資源的鍵定位資源所在的位置。然而云端用戶(hù)提交的數(shù)據(jù)查詢(xún)請(qǐng)求往往包含更加復(fù)雜的查詢(xún)模式，如多維查詢(xún)(multidimensionalquery)和區(qū)間查詢(xún)(rangequery)例如在YouTube等在線視頻應(yīng)用中，一個(gè)視頻數(shù)據(jù)往往需要用挖維向量(‰，點(diǎn)z，?，也一：)表示，每一維向量分別表示視頻的維屬性，如主題、作者、創(chuàng)建日期、清晰度等．查詢(xún)請(qǐng)求Q=(≤Date≤，480≤Definition≤720)表示用戶(hù)需要獲取日期和清晰度兩維元數(shù)據(jù)屬于上述區(qū)間內(nèi)的所有視頻。由于分布式Hash表中的主鍵只包含一維元數(shù)據(jù)，因此其分布式索引機(jī)箭無(wú)法支持多維查詢(xún)；與此同時(shí)，分布式Hash表為了保證數(shù)據(jù)分布的負(fù)載均衡在散列過(guò)程中會(huì)破壞數(shù)據(jù)的主鍵順序，查詢(xún)區(qū)間內(nèi)的兩個(gè)數(shù)值相鄰的主鍵在散列運(yùn)算后可能產(chǎn)生兩個(gè)差值很大的標(biāo)識(shí)符，進(jìn)而被分配到兩個(gè)存儲(chǔ)節(jié)點(diǎn)上，因此DHT的分布式索引機(jī)制無(wú)法支持區(qū)間查詢(xún)。M-Index索引針對(duì)云計(jì)算環(huán)境下分布式存儲(chǔ)系統(tǒng)的數(shù)據(jù)索引不支持復(fù)雜查詢(xún)的問(wèn)題，朱夏[4]等人提出了一種多維數(shù)據(jù)索引機(jī)制M-Index，采用金字塔技術(shù)(pyramid-technique)將數(shù)據(jù)的多維元數(shù)據(jù)描述成一維索引，在此基礎(chǔ)上首次提出前綴二叉樹(shù)(prefixbinarytree，PBT)的概念，通過(guò)提取一維索引PBT有效節(jié)點(diǎn)的前綴作為數(shù)據(jù)在存儲(chǔ)系統(tǒng)中的主鍵。數(shù)據(jù)根據(jù)主鍵和一致性Hash機(jī)制發(fā)布到存儲(chǔ)節(jié)點(diǎn)組成的覆蓋網(wǎng)絡(luò)。設(shè)計(jì)了基于M-Index的數(shù)據(jù)查詢(xún)算法，將復(fù)雜查詢(xún)請(qǐng)求轉(zhuǎn)換成一維查詢(xún)鍵值，支持多維查詢(xún)和區(qū)間查詢(xún)等復(fù)雜查詢(xún)模式。4.2.1索引降維云端用戶(hù)提交的數(shù)據(jù)在存儲(chǔ)系統(tǒng)中一般具有多維元數(shù)據(jù)屬性。在一致性Hash過(guò)程中數(shù)據(jù)的主鍵只能包含某一維元數(shù)據(jù)，這導(dǎo)致了諸如DHT等分布式存儲(chǔ)索引結(jié)構(gòu)無(wú)法支持多維查詢(xún)．其解決思路是利用金字塔技術(shù)構(gòu)建多維數(shù)據(jù)索引M-Index，將表示元數(shù)據(jù)的d維向量M(v0,v1,……,vd-1)降維成一維索引id。M-Index能夠保證多維元數(shù)據(jù)在降維過(guò)程中不丟失各維信息，從而保證數(shù)據(jù)查詢(xún)結(jié)果的完備性.M-Index以點(diǎn)P(0.5，?，0.5)為中心點(diǎn)，將d維空間0,1d等分成2d個(gè)子空間，同時(shí)將子空間命名為金字塔，將點(diǎn)P命名為金字塔的頂點(diǎn)，將d-1維空間命名為金字塔的底面。M—Index對(duì)金字塔的編號(hào)規(guī)則如下：在d維空間中任意一維向量D。(O≤m<d)都會(huì)與2個(gè)金字塔底面垂直，如果金字塔內(nèi)任意一點(diǎn)的第m維坐標(biāo)u0<0.5，則將該金字塔編號(hào)為m，否則將金字塔編號(hào)為m+d。計(jì)算點(diǎn)V與中心點(diǎn)P在第i(i≤4.2.2處理區(qū)間查詢(xún)由于一致性Hash可能會(huì)破壞一維索引值域區(qū)間[idmin,idmax]內(nèi)的數(shù)值順序，因此以一維索引id。為主鍵的存儲(chǔ)系統(tǒng)仍然無(wú)法實(shí)現(xiàn)對(duì)區(qū)間查詢(xún)的支持．然而我們觀察發(fā)現(xiàn)，數(shù)值臨近的二進(jìn)制數(shù)具有共同前綴的概率往往較高，考慮將區(qū)間[idmin,idmax]劃分成n+1個(gè)子區(qū)間δ0,δ1δ4.2.3復(fù)雜查詢(xún)請(qǐng)求轉(zhuǎn)換根據(jù)查詢(xún)請(qǐng)求的維數(shù)和區(qū)間，將查詢(xún)請(qǐng)求分為4類(lèi)：一維單值查詢(xún)(Q1)一維區(qū)間查詢(xún)(Q2)、多維單值查詢(xún)(Q3)和多維區(qū)間查詢(xún)(Q基于主鍵的存儲(chǔ)系統(tǒng)顯然無(wú)法直接識(shí)別諸如Q4的復(fù)雜查詢(xún)請(qǐng)求，因此和數(shù)據(jù)的索引過(guò)程類(lèi)似，需要根據(jù)M-Index將查詢(xún)請(qǐng)求轉(zhuǎn)換成存儲(chǔ)系統(tǒng)可以識(shí)別的一維單值查詢(xún)．首先引將Q4轉(zhuǎn)換成一維區(qū)間查詢(xún)請(qǐng)求Q2．在此基礎(chǔ)上根據(jù)PBT將Q2轉(zhuǎn)換成一維單值查詢(xún)請(qǐng)求4.2.4查詢(xún)請(qǐng)求轉(zhuǎn)發(fā)Q4在提交至存儲(chǔ)系統(tǒng)時(shí)會(huì)隨機(jī)選擇任一節(jié)點(diǎn)作為查詢(xún)的初始節(jié)點(diǎn)Ninit。Ninit根據(jù)其索引節(jié)點(diǎn)INinit。上維護(hù)的M-Index將Q4轉(zhuǎn)換成查詢(xún)鍵值kij(o≤i<m，O≤j<ai)，并將i=0m-1ai個(gè)kij分別提交至覆蓋網(wǎng)絡(luò)轉(zhuǎn)發(fā)．根據(jù)Chord的關(guān)鍵字查詢(xún)操作Lookup，kij最終會(huì)被轉(zhuǎn)發(fā)至索引節(jié)點(diǎn)IN。(n=Lookup(kij))(0≤i<m，O≤j<ai))．對(duì)于滿(mǎn)足查詢(xún)條件kij=這種方法的總體思路是將多為索引降維為一維索引，將多維索引的區(qū)間查詢(xún)轉(zhuǎn)化為一維索引的區(qū)間查詢(xún)，但是這種方法不能維持索引結(jié)構(gòu)的局部性，例如在高維空間中一個(gè)矩形的區(qū)間對(duì)應(yīng)著一維映射區(qū)間中許多不連續(xù)的區(qū)域，當(dāng)維數(shù)增加時(shí)會(huì)出現(xiàn)“維數(shù)災(zāi)難”4.3 MIDAS索引GeorgeTsatsanifos[5]在他的文章中提出一種基于peer-to-peerd的高維索引方法。MIDAS索引采用兩層索引結(jié)構(gòu)，以一種結(jié)構(gòu)化覆蓋的方式組織計(jì)算節(jié)點(diǎn)。在實(shí)際存儲(chǔ)數(shù)據(jù)的物理節(jié)點(diǎn)上建立本地索引，然后在服務(wù)器端建立全局的索引。當(dāng)用戶(hù)查詢(xún)數(shù)據(jù)時(shí)，通過(guò)服務(wù)器端的全局索引定位到本地索引，然后進(jìn)行數(shù)據(jù)的查詢(xún)。MIDAS采用分布式的K-D樹(shù)索引作為全局索引，文章中作者給出了點(diǎn)查詢(xún)和區(qū)間查詢(xún)的實(shí)現(xiàn)算法。由于MIDAS采用peer-to-peer架構(gòu)存儲(chǔ)全局索引，每個(gè)索引節(jié)點(diǎn)只擁有全局索引中的一部分，索引節(jié)點(diǎn)可以隨時(shí)加入和離開(kāi)索引集群，具有很高的可擴(kuò)展性。對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為n的覆蓋網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)只需要維護(hù)O(logn)個(gè)狀態(tài)，實(shí)現(xiàn)簡(jiǎn)單，每一個(gè)請(qǐng)求在4.4RT-CAN索引JinbaoWang[6]在它的文章中提出RT-CAN多維索引模型，RT-CAN模型結(jié)合了基于CAN的路由選擇協(xié)議和基于R-Tree的索引模型用以在云計(jì)算環(huán)境中支持高效的多維查詢(xún)處理。RT-CAN在擴(kuò)展CAN協(xié)議的基礎(chǔ)上將存儲(chǔ)節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)組織成一個(gè)覆蓋網(wǎng)絡(luò)。在這種協(xié)議中，每個(gè)節(jié)點(diǎn)都使用R-Tree式索引來(lái)索引局部數(shù)據(jù)。在文章中他還提出了一種面向查詢(xún)的代價(jià)模型用以選擇最優(yōu)的局部R-Tree節(jié)點(diǎn)來(lái)發(fā)布。通過(guò)小數(shù)目維持持續(xù)連接的節(jié)點(diǎn)和一個(gè)全局的多維索引，該索引模式能夠在很少的跳數(shù)內(nèi)定為包含了查詢(xún)結(jié)果的節(jié)點(diǎn)，使得這種索引在數(shù)據(jù)容量和節(jié)點(diǎn)數(shù)量上具有較好的可伸縮性。在集中式索引結(jié)構(gòu)中，查詢(xún)進(jìn)行的過(guò)程中，所有的查詢(xún)被送到主服務(wù)器來(lái)查詢(xún)?nèi)炙饕缓蟛樵?xún)被傳遞到包含有查詢(xún)結(jié)果的服務(wù)器。由于全局索引的只包含了索引數(shù)據(jù)的一部分而且并發(fā)的查詢(xún)量巨大，主服務(wù)器很可能成為性能瓶頸，RT-CAN將全局索引分布到多個(gè)節(jié)點(diǎn)中，每一個(gè)節(jié)點(diǎn)只保存全局索引的一部分，這種索引組織方式提高了可擴(kuò)展性和容錯(cuò)能力。RT-CAN的具體組織方式如下，為了將全局索引分布在紀(jì)尊眾，服務(wù)器被組織成一種覆蓋網(wǎng)絡(luò)的形式，特別地全局索引節(jié)點(diǎn)之間的通信CAN協(xié)議，因?yàn)镃AN適合多維查詢(xún)。為了高效檢索局部數(shù)據(jù)，數(shù)據(jù)節(jié)點(diǎn)上的數(shù)據(jù)庫(kù)中都建立了R-Tree索引。將數(shù)據(jù)節(jié)點(diǎn)的局部R-Tree索引的索引節(jié)點(diǎn)發(fā)布到全局索引中，而不是為每條記錄建立全局索引。因而，由來(lái)自不同數(shù)據(jù)的R-Tree節(jié)點(diǎn)局部索引組成的全局索引在系統(tǒng)中扮演一個(gè)“概要索引”的角色。為局部R-Tree索引節(jié)點(diǎn)建立索引減少了全局索引的數(shù)據(jù)量，減輕了索引維護(hù)帶來(lái)的開(kāi)銷(xiāo)。在查詢(xún)的過(guò)程中一旦我們?cè)谌炙饕卸ㄎ涣薘-Tree索引節(jié)點(diǎn)，我們只需要從注冊(cè)在全局索引中的R-Tree節(jié)點(diǎn)處開(kāi)始搜索局部的R-Tree。將每一個(gè)R-Tree節(jié)點(diǎn)發(fā)布到全局索引中是不現(xiàn)實(shí)的，因?yàn)檫@會(huì)導(dǎo)致很高的索引維護(hù)代價(jià)。因此必須選擇一部分對(duì)于路由有幫助的局部R-Tree節(jié)點(diǎn)，然后將他們發(fā)布到全局索引中。由于不同的選擇方案會(huì)導(dǎo)致不同的代價(jià)，文章提出了一種評(píng)估所有可能的選擇方案的模型，這種模型基于對(duì)查詢(xún)和更新分布的統(tǒng)計(jì)，能夠動(dòng)態(tài)調(diào)整索引策略，最小化索引維護(hù)代價(jià)。目前這種索引技術(shù)在P2P環(huán)境中收到了很好的效果，但是在云環(huán)境中存在著同步低和一致性弱的問(wèn)題。5.復(fù)合索引機(jī)制分片位圖索引集中式方案和分布式方案各有優(yōu)勢(shì)．集中式方案擁有被索引字段的全局信息，可以有效地避免不必要的查詢(xún)開(kāi)銷(xiāo)，但是，全局信息的維護(hù)與訪問(wèn)也帶來(lái)了額外的代價(jià)，致使查詢(xún)的響應(yīng)速度受到影響．分布式方案能夠充分利用并行計(jì)算資源的優(yōu)勢(shì)，但是由于缺乏被索引字段上值的整體分布信息，即使對(duì)于目標(biāo)值僅局部分布在少數(shù)幾個(gè)數(shù)據(jù)節(jié)點(diǎn)上的檢索請(qǐng)求，也會(huì)導(dǎo)致觸發(fā)整個(gè)集群上的并行檢索．而事實(shí)上，其中大部分?jǐn)?shù)據(jù)節(jié)點(diǎn)上返回的命中集合都將是空集．因而，大量的并行計(jì)算資源被白白浪費(fèi)了．孟必平等人[7]介紹了一種折中的解決方案：分片位索引(regionalbitmapindex)。該方法既具有分布式方案的高并行度特點(diǎn)，從而帶來(lái)了快速的請(qǐng)求響應(yīng)，同時(shí)又擁有如同在集中式方案中那樣了解全局的數(shù)據(jù)分布信息的優(yōu)勢(shì)，進(jìn)而盡最大努力避免了不必要的檢索代價(jià)，提高了系統(tǒng)的查詢(xún)吞吐量．相比使用特殊的通信協(xié)議而實(shí)現(xiàn)的分布式方案的諸擴(kuò)展方法，該方法通過(guò)引入屬性值的全局排序機(jī)制來(lái)徹底避免不同數(shù)據(jù)節(jié)點(diǎn)之間的通信．從而，使得開(kāi)發(fā)人員能夠從設(shè)計(jì)復(fù)雜通信協(xié)議的任務(wù)中解放出來(lái)．這一特點(diǎn)降低了本方法對(duì)網(wǎng)絡(luò)拓?fù)浜屯ㄐ畔到y(tǒng)的依賴(lài)，從而提高了查詢(xún)效率．另外，通過(guò)這種方式，本方法將無(wú)需訪問(wèn)目標(biāo)云環(huán)境所暴露的網(wǎng)絡(luò)通信接口，因此能夠適用于更廣泛的云存儲(chǔ)環(huán)境。字段值上的全局排序機(jī)制以及位圖索引的分片機(jī)制（全局排序機(jī)制能夠?yàn)楦鲾?shù)據(jù)節(jié)點(diǎn)提供一定的全局信息，即局部數(shù)據(jù)在全局值域中的分布情況；而位圖索引的分片機(jī)制使得索引結(jié)構(gòu)局部化，從而使不同數(shù)據(jù)節(jié)點(diǎn)上的檢索任務(wù)充分獨(dú)立，以便并發(fā)執(zhí)行）．然后綜合運(yùn)用上述技術(shù)給出了分片位圖索引技術(shù)的構(gòu)造方法及其存儲(chǔ)結(jié)構(gòu)。5.1.1字段值全局排序考慮在數(shù)值屬性A1,A2,,A3,…,Af共f個(gè)屬性上建立索引，首先將各屬性Ai的值域切割為ci個(gè)子域．如果屬性取值為離散值，則可將每一個(gè)取值單獨(dú)劃分為一個(gè)子域；如果為其它類(lèi)型，則可將其二進(jìn)制表示作為其位串值，例如字符串中各字符的ＡＳＣＩ碼組成的二進(jìn)制位串；并按照二進(jìn)制位串的數(shù)值大小對(duì)屬性值域進(jìn)行劃分．設(shè)值域切割所得子域所構(gòu)成的集合為Ci，那么子域的笛卡爾積Des1.b給定一個(gè)任意的元組t及其所對(duì)應(yīng)的位串，?i∈[1,f]有且僅有唯一一個(gè)j∈1,ci使得bij=1，因此該位串的所有合法的取值可以一一對(duì)應(yīng)上述子域笛卡爾積Des1…5.1.2索引的分片類(lèi)似于上述分布式方案，本方法同樣采用各數(shù)據(jù)節(jié)點(diǎn)獨(dú)立管理局部數(shù)據(jù)上索引的方式，以便提高檢索執(zhí)行時(shí)的并行度．在每個(gè)數(shù)據(jù)節(jié)點(diǎn)上，對(duì)該節(jié)點(diǎn)上存在的元組所對(duì)應(yīng)的位串的全局排序值建立Ｂ＋樹(shù)．樹(shù)的葉結(jié)點(diǎn)中的每個(gè)鍵都對(duì)應(yīng)于一個(gè)排序值，并記錄一個(gè)長(zhǎng)度為本數(shù)據(jù)節(jié)點(diǎn)所管理的元組總數(shù)的位圖，其中擁有該排序值的元組所對(duì)應(yīng)的位被置１，其它位被置０．這里將其稱(chēng)為元組位圖．易見(jiàn)，單個(gè)數(shù)據(jù)節(jié)點(diǎn)上的Ｂ＋樹(shù)的所有葉子結(jié)點(diǎn)上最多擁有Ｂ個(gè)鍵，因此最多存在Ｂ個(gè)不同的元組位圖。5.1.3索引的創(chuàng)建綜合運(yùn)用以上兩項(xiàng)技術(shù)，在云環(huán)境中分片位圖索引的各組成部分以及其創(chuàng)建流程．該方法的動(dòng)機(jī)來(lái)源于吸取并綜合集中式方案與分布式方案的優(yōu)點(diǎn)．首先對(duì)于給定的被索引屬性上的取值，其對(duì)應(yīng)位串存在唯一的全局排序值．據(jù)此，利用局部存在于各數(shù)據(jù)節(jié)點(diǎn)上的數(shù)據(jù)所對(duì)應(yīng)的排序值為其構(gòu)造局部的指示位圖．該指示位圖的長(zhǎng)度為子域笛卡爾積的大?。拢绻摂?shù)據(jù)節(jié)點(diǎn)上存在排序值為ｒ的元組，則該數(shù)據(jù)節(jié)點(diǎn)上指示位圖的第ｒ位為1，反之則為0．指示位圖記錄了局部屬性值的存在情況．檢索請(qǐng)求到達(dá)各數(shù)據(jù)節(jié)點(diǎn)時(shí)，首先通過(guò)比對(duì)指示位圖來(lái)確定本數(shù)據(jù)節(jié)點(diǎn)是否包含目標(biāo)元組，如果不存在，則直接返回空值，而不執(zhí)行檢索任務(wù)．除了為每個(gè)數(shù)據(jù)節(jié)點(diǎn)構(gòu)造指示位圖之外，還應(yīng)當(dāng)建立局部數(shù)據(jù)上的位圖索引．該局部位圖索引由兩部分構(gòu)成：以全局排序值為鍵的Ｂ＋樹(shù)以及Ｂ＋樹(shù)葉子結(jié)點(diǎn)上所附著的相應(yīng)字段值上的局部元組位圖．在執(zhí)行檢索任務(wù)時(shí)，如果與指示位圖進(jìn)行比對(duì)的結(jié)果不為全零串，則需要觸發(fā)Ｂ＋樹(shù)上的檢索操作．指示位圖的創(chuàng)建過(guò)程中需要掃描局部節(jié)點(diǎn)上所存在的所有元組，此過(guò)程的計(jì)算代價(jià)正比于局部數(shù)據(jù)節(jié)點(diǎn)上元組的數(shù)量；對(duì)于局部位圖索引，Ｂ＋樹(shù)的規(guī)模正比于子域笛卡爾積的大?。?，與元組數(shù)量無(wú)關(guān)，元組位圖的創(chuàng)建過(guò)程也需要掃描局部節(jié)點(diǎn)上所存在的所有元組，因此其代價(jià)亦正比于節(jié)點(diǎn)所管理的元組數(shù)量．通常情況下子域笛卡爾積的大小遠(yuǎn)小于元組數(shù)量，因此整個(gè)分片位圖索引的創(chuàng)建代價(jià)正比于局部數(shù)據(jù)節(jié)點(diǎn)上所管理元組數(shù)量的最大值．5.1.4單個(gè)索引上的檢索條件對(duì)于查詢(xún)請(qǐng)求中的單個(gè)索引上檢索條件，主節(jié)點(diǎn)首先將檢索條件轉(zhuǎn)換為條件位串．注意生成的條件位串應(yīng)當(dāng)覆蓋檢索條件所包含的所有可能性．然后主節(jié)點(diǎn)將條件位串并行地發(fā)送到所有的數(shù)據(jù)節(jié)點(diǎn)上，各數(shù)據(jù)節(jié)點(diǎn)分別將條件位串轉(zhuǎn)換為對(duì)應(yīng)的排序值的范圍，接著生成長(zhǎng)度等于B的全0位串cｂ，并將屬于排序值范圍內(nèi)的位置為１．檢查按位邏輯與eb＆cb的計(jì)算結(jié)果是否為０．如果為０則在該數(shù)據(jù)節(jié)點(diǎn)上直接返回空集作為計(jì)算結(jié)果；否則，在該數(shù)據(jù)節(jié)點(diǎn)的局部B+樹(shù)上依次搜索各符合條件的排序值，將找到元組位圖進(jìn)行按位邏輯與，一一檢查其計(jì)算結(jié)果中被置為１的位所對(duì)應(yīng)的元組是否滿(mǎn)足檢索條件，最后返回所有滿(mǎn)足條件的結(jié)果作為計(jì)算結(jié)果5.1.5檢索條件的復(fù)合通過(guò)將在同一數(shù)據(jù)節(jié)點(diǎn)上的不同屬性上檢索得到的元組位圖進(jìn)行相應(yīng)的按位邏輯運(yùn)算，可以實(shí)現(xiàn)多個(gè)檢索條件的快速?gòu)?fù)合．這充分利用了現(xiàn)代計(jì)算機(jī)能夠?qū)ξ粓D快速操作的計(jì)算優(yōu)勢(shì)．具體而言，其執(zhí)行步驟為：首先主節(jié)點(diǎn)將各簡(jiǎn)單檢索條件分別轉(zhuǎn)換為條件位串，并將這些條件位串以及條件之間的復(fù)合關(guān)系分發(fā)到各個(gè)數(shù)據(jù)節(jié)點(diǎn)．然后，各數(shù)據(jù)節(jié)點(diǎn)分別依次執(zhí)行各簡(jiǎn)單檢索條件上的檢索流程，從而查找到各簡(jiǎn)單條件所對(duì)應(yīng)的元組位圖，并將這些元組位圖依照檢索條件復(fù)合方法執(zhí)行按位邏輯運(yùn)算，得到最終的元組結(jié)果位圖．最后，掃描該位圖中為被置為１的位，并向主節(jié)點(diǎn)返回相應(yīng)的滿(mǎn)足檢索條件的元組。5.1.6索引效果分析這種方式充分發(fā)揮集中式方案和分布式方案兩種基本方案中的優(yōu)勢(shì)，既能夠使云環(huán)境中并行計(jì)算資源得到很好的利用，從而提高了單條查詢(xún)的響應(yīng)速度，又能夠通過(guò)局部節(jié)點(diǎn)所掌握的全局信息而規(guī)避不必要的檢索代價(jià)從而使在大量檢索請(qǐng)求并發(fā)到達(dá)時(shí)查詢(xún)吞吐量得以保證。6.總結(jié) 云計(jì)算環(huán)境下，數(shù)據(jù)模型以及數(shù)據(jù)的組織方式發(fā)生了根本的改變，適用于傳統(tǒng)數(shù)據(jù)庫(kù)的數(shù)據(jù)索引不能夠被簡(jiǎn)單地移植到云環(huán)境中，例如B+樹(shù)索引在傳統(tǒng)的數(shù)據(jù)庫(kù)中，通過(guò)將樹(shù)接近根節(jié)點(diǎn)的幾層駐留在內(nèi)存中的方式減少查詢(xún)時(shí)的磁盤(pán)IO，但是在云環(huán)境中過(guò)度密集地訪問(wèn)索引中的某一個(gè)部分容易照成索引過(guò)熱的現(xiàn)象，產(chǎn)生性能瓶頸和單點(diǎn)失效的問(wèn)題。隨著云計(jì)算的興起，前人在為云計(jì)算環(huán)境下設(shè)計(jì)高效的索引方面做了許多研究，這些索引大多采用雙層索引結(jié)構(gòu)，即同時(shí)擁有保存在索引節(jié)點(diǎn)上的全局索引和數(shù)據(jù)節(jié)點(diǎn)上的局部索引。本文按照全局索引組織方式的不同，將前人的研究成果分為集中式索引和分布式索引兩大類(lèi)，各列舉了一些有代表性的索引方案進(jìn)行分析。集中式索引方式下，集群中存在某個(gè)節(jié)點(diǎn)擁有整個(gè)集群的全局索引信息，通過(guò)查詢(xún)?cè)摴?jié)點(diǎn)，查詢(xún)可以很方便地被定位到擁有被查詢(xún)信息的節(jié)點(diǎn)，而不需要在多個(gè)保存了全局索引的節(jié)點(diǎn)之間進(jìn)行轉(zhuǎn)發(fā)，具有較高的查詢(xún)處理效率，而且不容易產(chǎn)生全局索引信息與局部索引信息不一致的問(wèn)題，但是由于每次查詢(xún)都要從某個(gè)節(jié)點(diǎn)開(kāi)始，隨著查詢(xún)次數(shù)的增加，而存在著難以避免的性能瓶頸，并有單點(diǎn)失效的風(fēng)險(xiǎn)。分布式索引機(jī)制將全局索引分布到集群中的多個(gè)索引節(jié)點(diǎn)上，通過(guò)特定的更新策略來(lái)維護(hù)全局索引的一致性。查詢(xún)?nèi)炙饕龝r(shí)，查詢(xún)請(qǐng)求在全局索引節(jié)點(diǎn)之間按一定的策略轉(zhuǎn)發(fā)，直到被擁有被查詢(xún)索引的節(jié)點(diǎn)處理。這種索引方式能夠發(fā)揮集群中多個(gè)集群的并行處理能力，可以根據(jù)索引數(shù)據(jù)量和請(qǐng)求數(shù)量增加或減少節(jié)點(diǎn)，具有比較強(qiáng)的可伸縮性和容錯(cuò)能力，但是存在著全局索引不一致，和查詢(xún)效率低，網(wǎng)絡(luò)帶寬消耗大的問(wèn)題。在針對(duì)特定的云應(yīng)用環(huán)境選擇索引時(shí)需要考慮需要處理的數(shù)據(jù)量、集群的性能、并發(fā)訪問(wèn)量、訪問(wèn)數(shù)據(jù)的實(shí)時(shí)性要求以及可靠性等因數(shù)，選擇合適的索引機(jī)制。

參考文獻(xiàn)[1]GhemawatS,GobioffH,LeungST.TheGooglefilesystem[C]//ACMSIGOPSOperatingSystemsReview.ACM,2003,37(5):29-43.[2]BorthakurD.Theh