數(shù)據(jù)庫索引技術(shù)概述

母鳳雯

摘要：隨著數(shù)據(jù)庫技術(shù)的發(fā)展，數(shù)據(jù)庫索引技術(shù)面臨著巨大的挑戰(zhàn)，為了了解數(shù)據(jù)庫索引技術(shù)的發(fā)展方向，文章對數(shù)據(jù)庫索引技術(shù)的發(fā)展現(xiàn)狀進行了簡要概述。文章從數(shù)據(jù)庫技術(shù)的發(fā)展出發(fā)，闡述了數(shù)據(jù)庫索引技術(shù)發(fā)展的必然方向，簡單說明了傳統(tǒng)的數(shù)據(jù)庫索引技術(shù)，例如ISAM索引、b+樹、Hash索引，并對可能成第三階段數(shù)據(jù)庫主流的面向?qū)ο髷?shù)據(jù)庫的索引技術(shù)，例如結(jié)構(gòu)索引、路徑索引、多重索引進行了闡述。文章重點對當前大數(shù)據(jù)時代下，基于大數(shù)據(jù)的數(shù)據(jù)庫索引技術(shù)進行梳理和總結(jié)，指出大數(shù)據(jù)環(huán)境中為應(yīng)對數(shù)據(jù)容量大、速度快、種類多、價值密度低的4v特點而發(fā)展出的索引機制的特點。文章最后對數(shù)據(jù)庫索引的發(fā)展方向進行思考討論，進一步說明數(shù)據(jù)庫索引技術(shù)下一步的發(fā)展可能方向。

關(guān)鍵詞：數(shù)據(jù)庫索引；ISAM索引；b+樹；Hash索引；結(jié)構(gòu)索引；路徑索引；多重索引；大數(shù)據(jù)

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）25-0009-03

Abstract： With the development of database technology， database indexing technology is facing great challenges. In order to understand the development direction of database indexing technology， this paper gives a brief overview of the development of database indexing technology. Based on the development of database technology， this paper expounds the inevitable direction of the development of database indexing technology， and briefly describes the traditional database indexing technology， such as ISAM index， b + tree， Hash index， and elaborates the indexing techniques of object-oriented database which may be the mainstream of the third stage database， such as structural indexing， path indexing， multiple indexes. This paper focuses on the database indexing technology Based on large data in the current large data age， and points out that the index mechanism developed in the large data environment to cope with the 4v characteristics of data capacity， speed， variety and low value density specialty. Finally， the article discusses the development direction of the database index， and further explains the possible direction of the development of the database indexing technology.

Key words： Database index； ISAM index； b + tree；Hash index； structure index； path index； multiple index； large data

數(shù)據(jù)庫索引是數(shù)據(jù)庫查詢優(yōu)化的重要方法，它的一個主要目的就是加快檢索表中數(shù)據(jù)，亦即能協(xié)助信息搜索者盡快地找到符合限制條件的記錄ID的輔助數(shù)據(jù)結(jié)構(gòu)[1]。數(shù)據(jù)庫自1962年發(fā)展至今，歷時50多年，共三個階段。第一個階段為數(shù)據(jù)獨立性低，編程復(fù)雜度高，用戶使用難度大的層次和網(wǎng)狀數(shù)據(jù)庫。第二個階段也是當前仍然作為主流數(shù)據(jù)庫技術(shù)的關(guān)系數(shù)據(jù)庫，它以1970年E.F.Codd博士提出的關(guān)系模型為數(shù)學(xué)基礎(chǔ)[2]，數(shù)據(jù)獨立性高，用戶使用通用的SQL語言操作簡單。從20世紀80年代以來，關(guān)系數(shù)據(jù)庫系統(tǒng)逐漸代替網(wǎng)狀數(shù)據(jù)庫系統(tǒng)和層次數(shù)據(jù)庫系統(tǒng)而占領(lǐng)了市場[3]。近年，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展以及應(yīng)用領(lǐng)域?qū)?shù)據(jù)庫技術(shù)的需求，層次和網(wǎng)狀數(shù)據(jù)庫和關(guān)系數(shù)據(jù)庫這類傳統(tǒng)的數(shù)據(jù)庫技術(shù)已經(jīng)難以滿足當今的現(xiàn)實需求。為了適應(yīng)數(shù)據(jù)的復(fù)雜性，處理的復(fù)雜性，數(shù)據(jù)結(jié)構(gòu)的動態(tài)性，數(shù)據(jù)的時間性等[4]，產(chǎn)生了新一代數(shù)據(jù)庫技術(shù)，例如：用于存儲二維，三維或更高維空間的空間坐標以及空間范圍相關(guān)的空間數(shù)據(jù)的空間數(shù)據(jù)庫技術(shù)[5]；用于海量交易數(shù)據(jù)，海量交互數(shù)據(jù)，海量處理數(shù)據(jù)的非關(guān)系型數(shù)據(jù)庫[6]；數(shù)據(jù)庫技術(shù)與面向?qū)ο蠹夹g(shù)結(jié)合的面向?qū)ο髷?shù)據(jù)庫技術(shù)[7]；應(yīng)對多媒體信息存取需求日益增多的多媒體數(shù)據(jù)庫[8]等。這些新型數(shù)據(jù)庫在數(shù)據(jù)模型，數(shù)據(jù)存儲方面與傳統(tǒng)型數(shù)據(jù)庫有著本質(zhì)的差別，因此，傳統(tǒng)數(shù)據(jù)庫所用到的索引技術(shù)已經(jīng)不再適合新型數(shù)據(jù)庫。

1 傳統(tǒng)數(shù)據(jù)庫索引技術(shù)

傳統(tǒng)數(shù)據(jù)庫索引技術(shù)根據(jù)數(shù)據(jù)存放的物理結(jié)構(gòu)不同可分為聚集索引和非聚集索引[9]，聚簇索引是按照數(shù)據(jù)存放的物理位置為順序的，而非聚簇索引就不一樣了；聚簇索引能提高多行檢索的速度，而非聚簇索引對于單行的檢索很快[10]。在傳統(tǒng)數(shù)據(jù)庫索引技術(shù)中常用的索引數(shù)據(jù)結(jié)構(gòu)主要有ISAM索引，HASH索引，和B+樹索引[11]。endprint

1.1 ISAM索引

ISAM索引是基于樹組織的索引數(shù)據(jù)結(jié)構(gòu)，既支持等值查找也支持范圍查找的靜態(tài)結(jié)構(gòu)[12]。ISAM樹是一顆二叉樹，其中數(shù)據(jù)全部存儲在樹的葉子頁面，非葉子節(jié)點只存儲索引指針，溢出頁面鏈接到葉子頁面。

1.2 b+樹

B+樹的樹結(jié)構(gòu)是多路搜索的平衡樹，數(shù)據(jù)僅存儲在葉子節(jié)點中，非葉子結(jié)點引導(dǎo)搜索，同時為了有效檢索所有的葉子頁面，葉子節(jié)點間通過指針相互鏈接[12]。B+樹的檢索方式與ISAM索引一樣，但是在進行插入刪除操作的時候樹結(jié)構(gòu)動態(tài)變化以保持樹結(jié)構(gòu)的平衡，故不存在添加溢出頁面。

1.3 Hash索引

哈希索引的核心思想是利用哈希函數(shù)，將搜索數(shù)據(jù)的值映射到一個數(shù)字，然后找到搜索數(shù)據(jù)目錄所在的頁。因此，哈希索引只支持等值檢索不能支持范圍檢索。

2 面向?qū)ο髷?shù)據(jù)庫索引技術(shù)

在關(guān)系數(shù)據(jù)庫系統(tǒng)中，索引建立在單個類（或關(guān)系）的屬性上，以加快搜索。在面向?qū)ο蟮臄?shù)據(jù)庫中，針對類的查詢的訪問范圍不僅包括類，而且還包括類的所有子類，類由集聚關(guān)系和繼承關(guān)系實現(xiàn)[14]。因此，面向?qū)ο髷?shù)據(jù)庫的索引技術(shù)主要涉及支持對象的嵌套屬性和繼承層次結(jié)構(gòu)的查詢[15]。在面向?qū)ο蟮腄BMS框架中定義的索引技術(shù)可以分為結(jié)構(gòu)索引和路徑索引[13]，多重索引。

2.1 結(jié)構(gòu)索引

目前大多數(shù)面向?qū)ο蟮牟樵冋Z言允許針對對象屬性查詢謂詞，因此結(jié)構(gòu)索引基于對象屬性。結(jié)構(gòu)索引技術(shù)可以分為支持嵌套謂詞的嵌套索引技術(shù)，以及支持針對繼承層次結(jié)構(gòu)查詢的類層次索引技術(shù)。嵌套屬性索引查找謂詞可以指定在該類的任意嵌套屬性上，一個查詢返回一個目標類的實例對象集合[16]，其檢索性能很好，但是維護的代價相當高。類層次索引技術(shù)則是一種更新成本不高的索引技術(shù)，類的屬性 [Aa]的類層次索引，是以該類為根的類層次上所有類的屬性的一個單一索引。索引屬性是建立在其上的屬性，而索引類是索引建立在這些類屬性上的類層次的根[17]。

2.2 路徑索引

在嵌套索引中，如果給定一個關(guān)鍵詞，葉結(jié)點只記錄了關(guān)聯(lián)此關(guān)鍵詞路徑中起始對象的對象標識。我們研究路徑索引（PathIndex，簡稱為PX），以記錄所有以該關(guān)鍵詞結(jié)束的路徑[17]。

2.3 多重索引

如果將一條路徑分裂成若干條子路徑，并在每一條路徑上建立嵌套索引，可以在一定程度上降低修改索引所帶來的開銷[17]。

3 基于大數(shù)據(jù)的數(shù)據(jù)庫索引技術(shù)

隨著大數(shù)據(jù)時代的到來，傳統(tǒng)的數(shù)據(jù)處理技術(shù)，如數(shù)據(jù)庫和數(shù)據(jù)倉庫，已不足以處理數(shù)據(jù)容量越來越大；數(shù)據(jù)量增長越來越快，需要處理的速度和響應(yīng)越來越快；數(shù)據(jù)種類多樣的大數(shù)據(jù)[16]。大數(shù)據(jù)存儲方式的根本改變，要求大數(shù)據(jù)的索引機制必須滿足支持多種査詢、支持高效檢索和易于維護等要求。為了解決大數(shù)據(jù)査詢處理問題，需要針對大數(shù)據(jù)環(huán)境建立新的索引結(jié)構(gòu)[27]。下表根據(jù)其索引結(jié)構(gòu)不同將索引技術(shù)分為二級索引，雙層索引，多維索引，基于Hadoop的索引技術(shù)。

3.1 二級索引

二級索引是指大多數(shù)基于key-value模型來存放數(shù)據(jù)的管理系統(tǒng)采用的索引技術(shù)。該類數(shù)據(jù)庫通過key進行數(shù)據(jù)的查詢，修改和刪除等操作，比如HBASE，dyname等數(shù)據(jù)庫均是以key為索引?，F(xiàn)有Key-vlaue型數(shù)據(jù)庫在存儲數(shù)據(jù)時通常采用b+樹索引，該結(jié)構(gòu)對rowkey查詢具有較高效率，但是對于非rowkey查詢效率低下且無法提供復(fù)雜查詢。許多學(xué)者對此提出了改進的索引策略，Parag Agrawal等人提出了Asynchronous View[18]，文章提出了遠程視圖表（remote view tables）和本地視圖表（local view tables）用來實現(xiàn)非rowkey的異步索引方式，其思想是為某個查詢建立一個與原始表一樣的遠程視圖表，并為每個節(jié)點的數(shù)據(jù)建立一個本地視圖表，在查詢時使用遠程視圖表以提高查詢效率，節(jié)點數(shù)據(jù)更改時僅更新本地視圖表以降低索引維護代價。Zou等人提出了complemental clustering index，簡稱 CCIndex[20]，該方案中索引表存放了完整的行數(shù)據(jù)，查詢時通過順序掃描查找數(shù)據(jù)而非當前使用的隨機讀取方式，提高了查詢效率；為每個文件進行備份，提高可靠性；為保證數(shù)據(jù)的容錯性引入聚類檢查表，保證數(shù)據(jù)快速恢復(fù)。針對key-value存儲不支持LBS（location based services）所必需的豐富查詢功能所需的多屬性訪問，Nishimura S提出了MD-HBase[21]。

3.2 雙層索引

雙層索引方案主要是為了滿足數(shù)據(jù)的海量性以及系統(tǒng)的可擴展性而提出來的，其索引部分包括局部索引和全局索引[22]。目前許多學(xué)者對該方向進行了研究，Wu S等人提出了Efficient B-tree[23]，該索引由本地b+樹索引和BATON網(wǎng)構(gòu)成，它首先將數(shù)據(jù)分片后隨機分配到各個節(jié)點，將索引服務(wù)器組織為一個結(jié)構(gòu)化的對等網(wǎng)絡(luò)BATON[24]，使得服務(wù)器之間可以路由查詢，實現(xiàn)全局索引，然后為每個節(jié)點建立b+樹索引實現(xiàn)局部索引。Efficient B-tree[23] 中相同的值可能位于同一個節(jié)點或不同節(jié)點中，如果B + -tree對這些值進行索引，會因數(shù)據(jù)太大導(dǎo)致查詢緩慢。為降低開銷，Huang B等人提出了TLB-index[25]，其基本思想與Efficient B-tree[23]一致，索引也是由b+樹索引和BATON網(wǎng)構(gòu)成，不同點是TLB-index[25]為每個不同的值構(gòu)建一個位圖。然后為所有位圖構(gòu)建一個B +樹。

3.3 多維索引

多維索引主要應(yīng)用處理圖像信息，地理信息數(shù)據(jù)的空間數(shù)據(jù)庫[26]。Zhang X等人提出了EMINC[27]，該方法為每個局部節(jié)點建立RD-tree索引，并為部分局部節(jié)點建立R-tree全局索引，可以為大數(shù)據(jù)管理系統(tǒng)提供快速查詢處理和有效的索引維護。為了增加大數(shù)據(jù)管理系統(tǒng)的可擴展性，支持大規(guī)模的查詢，Jinbao Wang等人提出了RT-CAN[28]，該索引由CAN路由協(xié)議作為全局索引，R-tree作為局部索引，其實現(xiàn)是通過適用于多維搜索的CAN維護基于局部索引的全局索引，全局索引被分配到每個節(jié)點，每個節(jié)點只維護全局索引的一部分，然后為每個節(jié)點的數(shù)據(jù)建立R-tree索引，并將R-tree映射到CAN節(jié)點。該方法具有可擴展性和容錯能力，并支持等值，范圍查詢和KNN查詢。為使多維索引能在極端動態(tài)的環(huán)境下運行，George Tsatsanifos等人提出了MIDAS[29]，它將虛擬節(jié)點作為基本實體，以避免物理節(jié)點離開，故障等造成的不良影響，一個物理節(jié)點對應(yīng)多個虛擬節(jié)點，一個虛擬節(jié)點對應(yīng)分層索引KD-tree的一個葉子，并且每個節(jié)點關(guān)聯(lián)一個從根路徑開始的二進制標識符。endprint

3.4 基于Hadoop的索引技術(shù)

Hadoop已經(jīng)成為大數(shù)據(jù)存儲和處理的標準平臺，Hadoop的HDFS提供大數(shù)據(jù)存儲，MapReduce并行編程模型實現(xiàn)大數(shù)據(jù)并行査詢和處理[30]，為提高其查詢效率，Abouzeid等人提出了Hadoop DB[31]，基本思想是使用Hadoop作為任務(wù)協(xié)調(diào)器和網(wǎng)絡(luò)通信層來連接多個單節(jié)點數(shù)據(jù)庫系統(tǒng)，然后使用MapReduce框架在各節(jié)點間進行查詢并行化，實現(xiàn)了大規(guī)模數(shù)據(jù)的并行處理。為解決Hadoop的性能通常與配置良好的并行數(shù)據(jù)庫管理系統(tǒng)不兼容問題，J Dittrich等人提出了Hadoop++[32]，Hadoop++在不改變Hadoop底層框架的情況下，通過自定義函數(shù)對Hadoop進行非入侵式優(yōu)化。為使Hadoop處理速度更快，Dittrich J等人提出了HAIL[33]（Hadoop Aggressive Indexing Library），HAIL[33]是入侵式方法，它更改HDFS的上傳管道，然后在每個數(shù)據(jù)塊副本上創(chuàng)建不同的聚簇索引，這樣HAIL數(shù)據(jù)上傳和查詢均優(yōu)于 Hadoop。

4 結(jié)束語

隨著大數(shù)據(jù)時代的來臨，以及各個學(xué)科鄰域信息系統(tǒng)的逐步成熟，傳統(tǒng)數(shù)據(jù)庫索引技術(shù)明顯已無法滿足時代的需求，基于大數(shù)據(jù)的數(shù)據(jù)庫索引技術(shù)和面向?qū)ο髷?shù)據(jù)庫索引技術(shù)擁有巨大的潛力。雖然目前有許多學(xué)者對索引技術(shù)領(lǐng)域做出了不少相關(guān)研究，但是成果并不成熟且沒有得到廣泛的應(yīng)用。本文對數(shù)據(jù)索引技術(shù)的發(fā)展變化做出了簡單的梳理，希望能為數(shù)據(jù)庫索引技術(shù)的研究者提供借鑒。

參考文獻：

[1] 歐萍. 數(shù)據(jù)庫索引技術(shù)應(yīng)用[J]. 電子科技，2011（9）：146-148.

[2] Codd E F. A relational model of data for large shared data banks （Reprinted from Communications of the ACM， June， pg 377-87， 1970）[J]. M.d.computing Computers in Medical Practice， 1998， 15（3）：162-166.

[3] 閻同喜. 數(shù)據(jù)庫技術(shù)發(fā)展概述[J]. 機械管理開發(fā)，2004（5）：80-82.

[4] 諸峰，張再躍. 數(shù)據(jù)庫技術(shù)在現(xiàn)代應(yīng)用中的發(fā)展[J]. 世界科技研究與發(fā)展，2002（2）：65-68.

[5] 郭菁，周洞汝，郭薇，胡志勇. 空間數(shù)據(jù)庫索引技術(shù)的研究[J]. 計算機應(yīng)用研究，2003，（12）：12-14.

[6] 申德榮，于戈，王習(xí)特，聶鐵錚，寇月. 支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J]. 軟件學(xué)報，2013（8）：1786-1803.

[7] 汪琛，胡浩民. 面向?qū)ο髷?shù)據(jù)庫技術(shù)的發(fā)展與前景[J]. 福建電腦，2005（5）：17-18.

[8] 王娣. 多媒體數(shù)據(jù)庫技術(shù)綜述[J]. 情報雜志，2001（11）：5-6+9.

[9] 鄧體俊. 數(shù)據(jù)庫索引技術(shù)的應(yīng)用[J]. 電腦知識與技術(shù)，2010（36）：10212-10214.

[10] 數(shù)據(jù)庫索引的實現(xiàn)原理.http：//blog.csdn.net/kennyrose/article/details/7532032/

[11] 胡九龍，趙捧未. 數(shù)據(jù)檢索中索引技術(shù)研究[J]. 科技情報開發(fā)與經(jīng)濟，2004（1）：210-211.

[12] Grillmeyer O. Database Management Systems[M]. 清華大學(xué)出版社， 2000.

[13] Bertino E， Guglielmina C. Path-index： An approach to the efficient execution of object-oriented queries[J]. Data & Knowledge Engineering， 1993， 10（1）：1-27.

[14] Bertino E， Catania B， Chiesa L. Definition and analysis of index organizations for object-oriented database systems ☆[J]. Information Systems， 1998， 23（2）：65-108.

[15] Bertino E， Foscoli P. Index Organizations for Object-Oriented Database Systems[J]. IEEE Transactions on Knowledge & Data Engineering， 1995， 7（2）：193-209.

[16] 陳仲民，王雪. 面向?qū)ο髷?shù)據(jù)庫的索引技術(shù)[J]. 計算機工程與科學(xué)，2000（6）：100-104.

[17] 馮黎，趙治斌. 初探面向?qū)ο髷?shù)據(jù)庫及其索引技術(shù)[J]. 中國科技信息，2009（13）：96-97.

[18] Chen J， Chen Y， Xiaoyong D U， et al. Big data challenge： a data management perspective[J]. Frontiers of Computer Science， 2013， 7（2）：157-164.

[19] Agrawal P， Silberstein A， Cooper B F， et al. Asynchronous view maintenance for VLSD databases[C]// ACM SIGMOD International Conference on Management of Data. ACM， 2009：179-192.endprint

[20] Zou Y， Liu J， Wang S， et al. CCIndex： A Complemental Clustering Index on Distributed Ordered Tables for Multi-dimensional Range Queries[M]// Network and Parallel Computing. Springer Berlin Heidelberg， 2010：247-261.

[21] Nishimura S， Das S， Agrawal D， et al. MD-HBase： A Scalable Multi-dimensional Data Infrastructure for Location Aware Services[C]// IEEE International Conference on Mobile Data Management. IEEE， 2011：7-16.

[22] 馬友忠，孟小峰. 云數(shù)據(jù)管理索引技術(shù)研究[J]. 軟件學(xué)報，2015（1）：145-166.

[23] Wu S， Jiang D， Ooi B C， et al. Efficient B-tree based indexing for cloud data processing[J]. Proceedings of the Vldb Endowment， 2010， 3（1-2）：1207-1218.

[24] H. V. Jagadish， B. C. Ooi， and Q. H. Vu. Baton： A balanced tree structure for peer-to-peer networks. In VLDB， 2005.

[25] Huang B， Peng Y X. An efficient two-level bitmap index for cloud data management[C]// IEEE， International Conference on Communication Software and Networks. IEEE， 2011：509-513.

[26] 譚寧. 基于R-樹多維索引結(jié)構(gòu)的優(yōu)化研究與應(yīng)用[D].湘潭大學(xué)，2009.

[27] Zhang X， Ai J， Wang Z， et al. An efficient multi-dimensional index for cloud data management[C]// International CIKM Workshop on Cloud Data Management， Clouddb 2009， Hong Kong， China， November. DBLP， 2009：17-24.

[28] Wang J， Wu S， Gao H， et al. Indexing multi-dimensional data in a cloud system[C]// ACM SIGMOD International Conference on Management of Data. ACM， 2010：591-602.

[29] Tsatsanifos G， Sacharidis D， Sellis T. MIDAS： multi-attribute indexing for distributed architecture systems[C]// International Conference on Advances in Spatial and Temporal Databases. Springer-Verlag， 2011：168-185.

[30] 甘文婷. 大數(shù)據(jù)索引技術(shù)關(guān)鍵問題研究[D].湖北大學(xué)，2016.

[31] Abouzeid A， Bajda-Pawlikowski K， Abadi D， et al. HadoopDB： an architectural hybrid of MapReduce and DBMS technologies for analytical workloads[J]. Proceedings of the Vldb Endowment， 2009， 2（1）：922-933.

[32] Dittrich J， Quiané-Ruiz J A， Jindal A， et al. Hadoop++： making a yellow elephant run like a cheetah （without it even noticing）[J]. Proceedings of the Vldb Endowment， 2010， 3（1-2）：515-529.

[33] Dittrich J， Richter S， Schuh S， et al. Only aggressive elephants are fast elephants[J]. Proceedings of the Vldb Endowment， 2012， 5（11）：1591-1602.endprint