董紹嬋, 周敏奇, 張 蓉, 周傲英

(華東師范大學(xué) 軟件學(xué)院;數(shù)據(jù)科學(xué)與工程研究院，上海 200062)

?

內(nèi)存數(shù)據(jù)索引：以處理器為核心的性能優(yōu)化技術(shù)

董紹嬋, 周敏奇, 張 蓉, 周傲英

(華東師范大學(xué) 軟件學(xué)院;數(shù)據(jù)科學(xué)與工程研究院，上海 200062)

隨著單機(jī)內(nèi)存容量的持續(xù)上升，內(nèi)存數(shù)據(jù)庫(kù)技術(shù)逐漸取代傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)為數(shù)據(jù)管理提供更快速的支持.本文分析了設(shè)計(jì)內(nèi)存索引結(jié)構(gòu)所需要考慮的基本要素；對(duì)目前的內(nèi)存索引結(jié)構(gòu)進(jìn)行了分類總結(jié)，并分析各結(jié)構(gòu)的優(yōu)缺點(diǎn)；針對(duì)當(dāng)前應(yīng)用發(fā)展趨勢(shì)，指出內(nèi)存索引未來(lái)發(fā)展的機(jī)遇與挑戰(zhàn)；最后介紹了我們正在研發(fā)的分布式集群感知內(nèi)存數(shù)據(jù)庫(kù)(CLAIMS)中的內(nèi)存索引結(jié)構(gòu).

內(nèi)存索引; cache利用率; 分布式內(nèi)存數(shù)據(jù)庫(kù); 索引壓縮

0 引 言

在20世紀(jì)70—80年代，由于硬盤(pán)技術(shù)的不成熟，導(dǎo)致計(jì)算機(jī)磁盤(pán)空間增長(zhǎng)緩慢，數(shù)據(jù)訪問(wèn)性能低下.當(dāng)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)所處理的數(shù)據(jù)規(guī)模并不大，所以有人曾設(shè)想過(guò)在數(shù)據(jù)庫(kù)處理過(guò)程中，將磁盤(pán)上的數(shù)據(jù)全部常駐在內(nèi)存[1]，以提高數(shù)據(jù)訪問(wèn)和處理的速度.1980年，IBM提出“薄膜”磁頭技術(shù)，這為進(jìn)一步減小硬盤(pán)體積、增大容量提高讀寫(xiě)速度提供了可能；1980年代末期發(fā)明了磁阻磁頭，使得盤(pán)片的存儲(chǔ)密度較以往提高了數(shù)十倍；隨后推出了首個(gè)容量超過(guò)1 GB的硬盤(pán)“IBM 3380直連存儲(chǔ)設(shè)備(DASD)”(每個(gè)容量為2.5 GB)[2].從此，磁盤(pán)容量的增長(zhǎng)速率遠(yuǎn)遠(yuǎn)超過(guò)了內(nèi)存容量的增長(zhǎng)，“內(nèi)存數(shù)據(jù)庫(kù)”的想法看似已無(wú)可能.對(duì)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)的研究也止步不前；研究人員或者轉(zhuǎn)向?qū)崟r(shí)系統(tǒng)領(lǐng)域，或者致力于對(duì)磁盤(pán)數(shù)據(jù)庫(kù)性能的改進(jìn).

在傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)中，數(shù)據(jù)從磁盤(pán)加載到內(nèi)存的過(guò)程成為提高整個(gè)數(shù)據(jù)庫(kù)系統(tǒng)性能的瓶頸所在.為了減少數(shù)據(jù)訪問(wèn)時(shí)的I/O開(kāi)銷，各種基于磁盤(pán)的數(shù)據(jù)索引結(jié)構(gòu)應(yīng)運(yùn)而生；其中，由于對(duì)數(shù)據(jù)的增刪改有非常好的性能支持，本身結(jié)構(gòu)可以進(jìn)行范圍查詢等優(yōu)勢(shì)，B+樹(shù)[3]索引得到了廣泛的應(yīng)用.

近十幾年來(lái)，隨著RAM價(jià)格的不斷下降，計(jì)算機(jī)內(nèi)存的容量飛速上升.在當(dāng)今的主流服務(wù)器中，TB級(jí)的內(nèi)存容量已隨處可見(jiàn).這使得完全可以將所有數(shù)據(jù)常駐內(nèi)存，以實(shí)現(xiàn)快速的數(shù)據(jù)訪問(wèn)和更新，基于內(nèi)存的數(shù)據(jù)庫(kù)系統(tǒng)再次得到人們的重視.

在內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中，所有的數(shù)據(jù)操作任務(wù)都可直接在內(nèi)存中得到響應(yīng)；因此，困擾傳統(tǒng)數(shù)據(jù)庫(kù)的I/O瓶頸不復(fù)存在.類似于內(nèi)存-磁盤(pán)間的性能差異，CPU與內(nèi)存對(duì)數(shù)據(jù)的不同處理能力導(dǎo)致內(nèi)存數(shù)據(jù)庫(kù)的瓶頸轉(zhuǎn)變?yōu)镃PU-memory代價(jià).由于處理器廠商與內(nèi)存廠商相互分離的產(chǎn)業(yè)格局，導(dǎo)致內(nèi)存技術(shù)與處理器技術(shù)發(fā)展的不同步.圖1給出了20世紀(jì)最后20年間CPU和DRAM性能增長(zhǎng)的趨勢(shì)；從圖中可明顯看出，在這段時(shí)間內(nèi)，處理器的性能每年大約有60%的提升，而內(nèi)存性能的提升速度則每年只有10%左右.這種不均衡的發(fā)展使得當(dāng)前內(nèi)存的存取速度嚴(yán)重滯后于處理器的計(jì)算速度，內(nèi)存訪問(wèn)瓶頸導(dǎo)致高性能處理器難以發(fā)揮應(yīng)有的效率，并且直接制約了內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)操作性能的提升.事實(shí)上，早在1994年就有研究人員分析和預(yù)測(cè)了這一問(wèn)題，并將這種嚴(yán)重阻礙處理器性能發(fā)揮的內(nèi)存瓶頸命名為"內(nèi)存墻"(Memory Wall)[4].在很長(zhǎng)一段時(shí)間內(nèi)，對(duì)內(nèi)存索引的研究都圍繞著如何減弱“內(nèi)存墻”問(wèn)題對(duì)數(shù)據(jù)獲取的延遲進(jìn)行.一系列“緩存敏感性”[5]索引的提出(例如CSB-Tree[6]、CST-Tree[7]等)使得該問(wèn)題得到了緩解.

圖1 CPU與DRAM性能增長(zhǎng)對(duì)比[6]

在現(xiàn)今的CPU-Cache-Memory處理架構(gòu)下，已有實(shí)驗(yàn)結(jié)果表明[8]：數(shù)據(jù)庫(kù)執(zhí)行時(shí)間的一半用于等待內(nèi)存，而且90%的等待時(shí)間是由二級(jí)數(shù)據(jù)cache失效和一級(jí)指令cache失效造成的——這就意味著數(shù)據(jù)放置即數(shù)據(jù)模型對(duì)二級(jí)數(shù)據(jù)cache、一級(jí)指令cache有重要的影響.因此,如何有效地利用cache的特征設(shè)計(jì)高效算法，成為內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中亟待解決的一個(gè)重要問(wèn)題.類比于傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)中對(duì)I/O瓶頸的索引處理方式，在內(nèi)存數(shù)據(jù)庫(kù)中，同樣需要建立針對(duì)內(nèi)存數(shù)據(jù)的索引結(jié)構(gòu)，以避免對(duì)其進(jìn)行全部掃描或大量隨機(jī)讀取，從而加快數(shù)據(jù)訪問(wèn)與處理的速度，盡可能減弱“內(nèi)存墻”問(wèn)題對(duì)數(shù)據(jù)庫(kù)處理性能的影響.

除此之外，新的硬件架構(gòu)也對(duì)內(nèi)存索引的結(jié)構(gòu)設(shè)計(jì)提出了各種要求.由于多核技術(shù)的發(fā)展及內(nèi)存容量的增大，單臺(tái)計(jì)算機(jī)中的內(nèi)存被分配給了不同的處理器，從而催生了非一致性內(nèi)存訪問(wèn)(Non-Uniform Memory Access，NUMA)[9]系統(tǒng)的出現(xiàn).由于處理器訪問(wèn)直接掛載內(nèi)存與遠(yuǎn)端內(nèi)存的時(shí)間消耗存在差異，針對(duì)內(nèi)存中數(shù)據(jù)的索引結(jié)構(gòu)可增添新的標(biāo)識(shí)信息以使得數(shù)據(jù)盡量被其所在內(nèi)存直接掛載的處理器所處理，從而加快數(shù)據(jù)的訪問(wèn)處理時(shí)間.另外，隨著處理器與內(nèi)存間緩存層數(shù)的增加，各處理器對(duì)一級(jí)、二級(jí)緩存的私有化導(dǎo)致數(shù)據(jù)訪問(wèn)過(guò)程中的相干性沖突增加，在多線程處理環(huán)境下，當(dāng)多個(gè)處理器同時(shí)對(duì)某一特定的索引結(jié)構(gòu)進(jìn)行遍歷搜索時(shí)，如何有效的避免對(duì)特定結(jié)點(diǎn)訪問(wèn)所造成的相干性沖突也是提升內(nèi)存數(shù)據(jù)訪問(wèn)效率的一個(gè)有效手段.

除了在單機(jī)環(huán)境下要解決的“內(nèi)存墻”問(wèn)題之外，大數(shù)據(jù)時(shí)代的到來(lái)，它所具有的“3V”(即海量(Valume)、高速(Velocity)、多樣(Variety)[10])特性，對(duì)數(shù)據(jù)庫(kù)的分析和處理能力提出了新的挑戰(zhàn).傳統(tǒng)的單機(jī)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)并不能夠很好地滿足要求，于是分布式數(shù)據(jù)管理系統(tǒng)受到重視并被廣泛研究.基于Key-Value Store的分布式內(nèi)存數(shù)據(jù)管理系統(tǒng)(例如Spark[11]、RAMCloud[12]等)已經(jīng)取得較好的應(yīng)用.分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)的研究也如火如荼.SAP的HANA[13]已經(jīng)有相對(duì)穩(wěn)定高效的分布式版本；MinSQL[14]作為一個(gè)實(shí)驗(yàn)室產(chǎn)物，是用JAVA搭建的，一個(gè)較為完善的分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng).在分布式環(huán)境下，源數(shù)據(jù)的存儲(chǔ)策略直接影響數(shù)據(jù)在集群中的分布；而之前的基于單機(jī)內(nèi)存的索引結(jié)構(gòu)，也必然要針對(duì)分布式的數(shù)據(jù)存儲(chǔ)作出新的調(diào)整.整個(gè)數(shù)據(jù)在集群中數(shù)據(jù)結(jié)點(diǎn)間的分布式存儲(chǔ)策略與在每個(gè)數(shù)據(jù)結(jié)點(diǎn)內(nèi)部的部分?jǐn)?shù)據(jù)的局部索引的結(jié)合，將導(dǎo)致分布式環(huán)境下索引的多層架構(gòu).目前，針對(duì)內(nèi)存數(shù)據(jù)的分布式索引結(jié)構(gòu)的研究并不是很成熟，仍有很多的工作值得去做.

圖2列出了內(nèi)存索引技術(shù)近30年來(lái)的開(kāi)展.從20世紀(jì)80年代開(kāi)始，內(nèi)存索引結(jié)構(gòu)被首次提出并開(kāi)始針對(duì)其獨(dú)立于傳統(tǒng)的磁盤(pán)索引結(jié)構(gòu)的特征進(jìn)行研究改進(jìn).隨著計(jì)算機(jī)硬件的不斷變化，內(nèi)存索引結(jié)構(gòu)也產(chǎn)生了相對(duì)應(yīng)的改變.從傳統(tǒng)的基于B樹(shù)類型的索引到Trie結(jié)構(gòu)的引進(jìn)，從對(duì)磁盤(pán)hash結(jié)構(gòu)的直接應(yīng)用到針對(duì)cache及TLB的特性進(jìn)行的敏感性改進(jìn)，直到后來(lái)針對(duì)不同的索引結(jié)構(gòu)特性進(jìn)行復(fù)合利用，逐步提升內(nèi)存索引對(duì)數(shù)據(jù)掃描的性能影響.

在過(guò)去的30多年中，已有很多學(xué)者致力于研究如何對(duì)內(nèi)存數(shù)據(jù)建立高效的索引結(jié)構(gòu)，但是這部分的研究工作主要針對(duì)集中式環(huán)境，對(duì)分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)并沒(méi)有作相關(guān)的索引工作探討.本文嘗試全面回顧內(nèi)存數(shù)據(jù)庫(kù)索引工作在近30年來(lái)的研究進(jìn)展與已有成果，并展望其未來(lái)可能的發(fā)展方向.此外，華東師范大學(xué)數(shù)據(jù)科學(xué)與工程院在分布式內(nèi)存數(shù)據(jù)庫(kù)的數(shù)據(jù)存儲(chǔ)及索引建立方面也做了一些探索，本文也會(huì)給出簡(jiǎn)要的介紹.

圖2 內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)索引發(fā)展概覽

本文的后續(xù)內(nèi)容組織如下：第1節(jié)介紹內(nèi)存索引結(jié)構(gòu)需要考慮的基本要素；第2節(jié)和第3節(jié)分別介紹單機(jī)和分布式環(huán)境下內(nèi)存數(shù)據(jù)庫(kù)索引結(jié)構(gòu)的研究進(jìn)展；第4節(jié)總結(jié)當(dāng)今數(shù)據(jù)及應(yīng)用的發(fā)展趨勢(shì)并展望未來(lái)內(nèi)存大數(shù)據(jù)索引的發(fā)展方向，同時(shí)簡(jiǎn)介華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院在CLAIMS系統(tǒng)中的分布式內(nèi)存索引研究；最后，第5節(jié)總結(jié)全文.

1 內(nèi)存索引結(jié)構(gòu)要考慮的基本要素

已有的研究成果表明，在傳統(tǒng)的磁盤(pán)行數(shù)據(jù)庫(kù)系統(tǒng)中，最大的性能瓶頸在于對(duì)大量磁盤(pán)數(shù)據(jù)的訪問(wèn)和獲取.因此，產(chǎn)生了各種磁盤(pán)數(shù)據(jù)索引方式，用以避免對(duì)原始數(shù)據(jù)的全盤(pán)掃描，精準(zhǔn)定位數(shù)據(jù)；然而，隨著內(nèi)存容量的上升及列存儲(chǔ)方式的出現(xiàn)，基于內(nèi)存的數(shù)據(jù)庫(kù)系統(tǒng)可以將查詢所需的原始數(shù)據(jù)全部緩存在內(nèi)存中以便在查詢到來(lái)時(shí)可以快速地獲取到對(duì)應(yīng)于查詢的數(shù)據(jù).

由圖3給出的計(jì)算機(jī)中各級(jí)存儲(chǔ)介質(zhì)數(shù)據(jù)訪問(wèn)效率的對(duì)比可看出，當(dāng)傳統(tǒng)的磁盤(pán)瓶頸消失之后，內(nèi)存訪問(wèn)延遲將會(huì)變成制約內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)查詢處理性能提升的新瓶頸，如何加速數(shù)據(jù)從內(nèi)存獲取到CPU處理的過(guò)程已經(jīng)成為內(nèi)存數(shù)據(jù)庫(kù)性能提升的一個(gè)重要研究方向.總結(jié)上述情況并結(jié)合近年來(lái)出現(xiàn)的新的硬件架構(gòu)形式及分布式環(huán)境的發(fā)展，以下給出在設(shè)計(jì)內(nèi)存數(shù)據(jù)索引時(shí)需要重點(diǎn)考慮的基本要素.

圖3 各級(jí)存儲(chǔ)介質(zhì)的訪問(wèn)延遲說(shuō)明

1.1 提升cache利用率

類似于傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)中內(nèi)存buffer與磁盤(pán)的關(guān)系，在內(nèi)存數(shù)據(jù)庫(kù)中數(shù)據(jù)cache可看作是內(nèi)存中原始數(shù)據(jù)的更高一層存儲(chǔ)buffer.cache與內(nèi)存之間數(shù)據(jù)的交換以cache line為單位；每次不論實(shí)際所需的數(shù)據(jù)占用多少空間，一旦在cache中不能找到所需數(shù)據(jù)，訪問(wèn)內(nèi)存獲取的數(shù)據(jù)規(guī)模必定填充滿一個(gè)完整的cache line.因此，盡量提高cache中的空間利用率，使得每次加載到cache中的索引數(shù)據(jù)能夠全部有效地用于查詢處理中對(duì)結(jié)果集的prune或直接指示，是設(shè)計(jì)內(nèi)存索引結(jié)構(gòu)的一個(gè)主要考慮因素.

以傳統(tǒng)的B樹(shù)[15]類索引為例，雖然該類索引在磁盤(pán)數(shù)據(jù)庫(kù)中得到了非常廣泛的應(yīng)用并且也被證明可以取得很好的性能提升，但是顯然這類結(jié)構(gòu)并不能直接用于對(duì)內(nèi)存數(shù)據(jù)進(jìn)行索引.Ross提出了“緩存敏感(cache conscious)”的概念，形式化地說(shuō)明了對(duì)cache line利用率的優(yōu)化問(wèn)題，并在文獻(xiàn)[5]中以傳統(tǒng)B樹(shù)結(jié)構(gòu)為基礎(chǔ)，在OLAP(在線分析系統(tǒng)，On-Line Analysis Processing)環(huán)境下提升cache利用率，通過(guò)對(duì)其進(jìn)行緩存敏感性改進(jìn)使得其變體結(jié)構(gòu)最終能被應(yīng)用到內(nèi)存數(shù)據(jù)索引結(jié)構(gòu)中.

1.2 減少cache失效及TLB失效

通過(guò)已有的實(shí)驗(yàn)已經(jīng)知道，數(shù)據(jù)庫(kù)執(zhí)行時(shí)間的一半是CPU在等待內(nèi)存，而90%的等待時(shí)間是由二級(jí)數(shù)據(jù)cache失效和一級(jí)指令cache失效造成的.因此，減少二級(jí)數(shù)據(jù)cache失效的發(fā)生概率顯得尤為重要.對(duì)于樹(shù)型索引，如果整個(gè)結(jié)構(gòu)沒(méi)有被加載到cache，那么每次層間偏移都對(duì)應(yīng)一次數(shù)據(jù)cache失效.因此如何提高其結(jié)點(diǎn)的扇出分支數(shù)目，降低樹(shù)高，減少索引搜索過(guò)程中cache失效發(fā)生的概率是內(nèi)存索引要考慮的另一個(gè)重要因素.

對(duì)hash類索引而言，數(shù)據(jù)的定位只需一次hash值的計(jì)算，理想情況下搜索代價(jià)為O(1).但是由于TLB空間局限性，對(duì)于大規(guī)模分散hash而言，絕大多數(shù)數(shù)據(jù)桶的物理地址都不在TLB中，這使得在數(shù)據(jù)定位過(guò)程中TLB失效頻發(fā)，嚴(yán)重影響索引效率.針對(duì)這種情況，如何組織hash的層次以減少在尋址過(guò)程中出現(xiàn)的TLB失效問(wèn)題是設(shè)計(jì)內(nèi)存hash類索引要考慮的一個(gè)重要方面.其中，將Radix[16]技術(shù)引入索引結(jié)構(gòu)而提出的分層hash算法得到廣泛的認(rèn)可.

1.3 索引結(jié)構(gòu)壓縮

對(duì)于傳統(tǒng)的行存儲(chǔ)磁盤(pán)數(shù)據(jù)庫(kù)而言，表的所有屬性以記錄為單位按行存儲(chǔ)，在沒(méi)有索引的情況下對(duì)任一列的查詢都將引發(fā)整個(gè)數(shù)據(jù)表的全部掃描，這極大地增加了系統(tǒng)的I/O開(kāi)銷，不利于查詢性能的提升.傳統(tǒng)磁盤(pán)索引通過(guò)避免對(duì)數(shù)據(jù)的全部掃描來(lái)提高查詢性能，其壓縮比率以一列的索引空間對(duì)比整個(gè)完整表數(shù)據(jù)；因此，即使沒(méi)有任何壓縮技術(shù)，索引的壓縮率也非常高.

當(dāng)前，針對(duì)常駐內(nèi)存的大量列數(shù)據(jù)建立索引結(jié)構(gòu)，其壓縮性能就成為一個(gè)非常重要的考量因素：首先，新的列存儲(chǔ)數(shù)據(jù)組織形式使得原始表中的數(shù)據(jù)按屬性進(jìn)行組織存儲(chǔ)，這樣一來(lái)在針對(duì)某列操作時(shí)可以有針對(duì)性的只掃描該列的原始數(shù)據(jù)，大大縮小了對(duì)原始數(shù)據(jù)掃描的范圍(相比行數(shù)據(jù)庫(kù)而言).因此，索引結(jié)構(gòu)的壓縮比率也由對(duì)比之前行存儲(chǔ)的整個(gè)數(shù)據(jù)表變成僅與所要建立索引結(jié)構(gòu)的列進(jìn)行對(duì)比.這種情況下，由于索引中添加了許多指示數(shù)據(jù)位置的信息，原來(lái)未經(jīng)壓縮的稠密索引所占用的空間必然大于原始該列數(shù)據(jù)所占用空間；因此，對(duì)于索引結(jié)構(gòu)的精簡(jiǎn)和壓縮在列存儲(chǔ)的環(huán)境下就必不可少.其次，由于源數(shù)據(jù)已全部在內(nèi)存中放置，其全部掃描相比磁盤(pán)而言本身已經(jīng)非常迅速，要使索引結(jié)構(gòu)發(fā)生效力，必定通過(guò)查詢索引結(jié)構(gòu)直接定位數(shù)據(jù)要快于有cache預(yù)取加速下的數(shù)據(jù)順序掃描.而如上一小節(jié)所說(shuō)，不論是樹(shù)型結(jié)構(gòu)還是基于hash的索引結(jié)構(gòu)，其在訪問(wèn)過(guò)程中都會(huì)不可避免的產(chǎn)生cache失效和TLB失效，類比于傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)的內(nèi)存維護(hù)，最好的處理策略是能夠讓針對(duì)磁盤(pán)的索引結(jié)構(gòu)直接維護(hù)在cache中，這樣對(duì)索引結(jié)構(gòu)的訪問(wèn)不會(huì)產(chǎn)生任何cache失效問(wèn)題，整個(gè)數(shù)據(jù)的訪問(wèn)過(guò)程只會(huì)產(chǎn)生直接獲取數(shù)據(jù)一次cache失效.為了使整個(gè)索引結(jié)構(gòu)能夠在cache中維護(hù)，該結(jié)構(gòu)所占用的空間量必須足夠小，針對(duì)大規(guī)模數(shù)據(jù)集，索引的壓縮就顯得尤為重要.

1.4 新的硬件特性帶來(lái)的索引結(jié)構(gòu)改進(jìn)

在傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)中，系統(tǒng)的性能瓶頸主要在磁盤(pán)I/O上，而單位時(shí)間內(nèi)系統(tǒng)能從磁盤(pán)上讀取的數(shù)據(jù)量與配置磁頭數(shù)目，磁盤(pán)轉(zhuǎn)速等物理因素直接相關(guān)，這導(dǎo)致只能通過(guò)改變物理架構(gòu)來(lái)提升I/O吞吐量.而在內(nèi)存中，隨著當(dāng)今計(jì)算機(jī)硬件的發(fā)展，多核、多線程的處理模式完全能夠支持處理性能的成倍提升.圖4給出了計(jì)算機(jī)存儲(chǔ)架構(gòu)示意圖，結(jié)合新的結(jié)構(gòu)特性及技術(shù)發(fā)展，為了充分利用硬件性能，內(nèi)存中的索引結(jié)構(gòu)應(yīng)充分考慮到以下幾個(gè)因素.

圖4 各級(jí)存儲(chǔ)層架構(gòu)示意圖

(1) 隨著cache層數(shù)的增加以及多核技術(shù)的使用，在多線程環(huán)境下，核與核間L3 cache對(duì)內(nèi)存中數(shù)據(jù)訪問(wèn)產(chǎn)生的相干性沖突，以及核內(nèi)不同處理器間更高層cache對(duì)L3 cache中數(shù)據(jù)訪問(wèn)的相干性沖突，都會(huì)導(dǎo)致訪問(wèn)過(guò)程中處理器的等待，使得最終的總體性能下降；

(2) 由于內(nèi)存容量的上升以及多核技術(shù)的應(yīng)用，“非一致性內(nèi)存訪問(wèn)”[9]結(jié)構(gòu)使得CPU訪問(wèn)不同內(nèi)存中的數(shù)據(jù)所需要的時(shí)間不盡相同；如何設(shè)計(jì)索引算法，使得在數(shù)據(jù)搜索過(guò)程中CPU所遍歷的數(shù)據(jù)恰好在其直接掛載的內(nèi)存中，這也是提升性能的一個(gè)有效途徑；

(3) 同時(shí)單指令多數(shù)據(jù)流(Single Instruction Multiple Data，SIMD)[17]技術(shù)的合理利用也能夠使索引的搜索性能得到進(jìn)一步的提升；傳統(tǒng)的單個(gè)key值比較指令可直接擴(kuò)展到對(duì)整個(gè)數(shù)據(jù)結(jié)點(diǎn)的處理，從而節(jié)約key值在索引結(jié)點(diǎn)中比較過(guò)程的時(shí)間消耗，進(jìn)一步加快索引訪問(wèn)的速度.

1.5 分布式內(nèi)存集群特性

從圖2中對(duì)近30年來(lái)的索引結(jié)構(gòu)的初步總結(jié)可看出，內(nèi)存索引結(jié)構(gòu)的研究一直都孤立于內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)之外單獨(dú)存在；并且?guī)缀跛械乃饕Y(jié)構(gòu)所注重的只是在單機(jī)內(nèi)存中的性能優(yōu)化策略，對(duì)于現(xiàn)今應(yīng)用越來(lái)越廣泛的分布式集群系統(tǒng)并沒(méi)有太多的研究.

隨著數(shù)據(jù)庫(kù)所處理的數(shù)據(jù)規(guī)模的急劇增大，實(shí)時(shí)處理需求的不斷提升，對(duì)集中式環(huán)境下服務(wù)器結(jié)點(diǎn)的要求也日益提高.相較于配置極高的單臺(tái)服務(wù)器，基于分布式架構(gòu)的集群更易被接受.內(nèi)存數(shù)據(jù)處理系統(tǒng)發(fā)展的下一階段必然會(huì)向分布式環(huán)境拓展，目前已經(jīng)有許多較為成熟的分布式內(nèi)存系統(tǒng)：基于Key-Value存儲(chǔ)的Spark、RamCloud；基于Hadoop的存儲(chǔ)結(jié)構(gòu)拓展而來(lái)的Impala；以及分布式的內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)memSQL、HANA等等.相較于分布式內(nèi)存系統(tǒng)的蓬勃發(fā)展，在其上的索引技術(shù)并沒(méi)有隨之興起.而由于網(wǎng)絡(luò)間內(nèi)存訪問(wèn)的額外開(kāi)銷，分布式內(nèi)存索引技術(shù)的研究也對(duì)傳統(tǒng)的單機(jī)內(nèi)存索引結(jié)構(gòu)提出了新的要求：建立分布式索引必須結(jié)合考慮數(shù)據(jù)在分布式系統(tǒng)中的存儲(chǔ)策略；索引結(jié)構(gòu)與原始數(shù)據(jù)的一致性存儲(chǔ)與否對(duì)數(shù)據(jù)訪問(wèn)時(shí)間的影響不可忽略.而在分布式環(huán)境下應(yīng)用廣泛的基于HASH的數(shù)據(jù)分布策略與傳統(tǒng)的比較性索引結(jié)構(gòu)的結(jié)合效率并不理想.因此，如何在分布式環(huán)境下建立高效的內(nèi)存索引結(jié)構(gòu)需要考慮的因素更加復(fù)雜.

2 現(xiàn)有的內(nèi)存索引結(jié)構(gòu)

回顧內(nèi)存索引結(jié)構(gòu)的發(fā)展，其每一次改進(jìn)都與CPU-Cache-Memory架構(gòu)的發(fā)展變化密切相關(guān).由于源數(shù)據(jù)的內(nèi)存存放，使得處理器及memory的架構(gòu)對(duì)索引結(jié)構(gòu)的影響逐漸增大.從傳統(tǒng)的單核單處理器單線程架構(gòu)到SIMD指令集的出現(xiàn)，到多線程多處理器多核時(shí)代的到來(lái)，每次CPU-Cache-Memory架構(gòu)的改進(jìn)都引起針對(duì)內(nèi)存索引結(jié)構(gòu)的改革.

2.1 基于樹(shù)型結(jié)構(gòu)的內(nèi)存索引

鑒于B-tree一族的索引結(jié)構(gòu)在傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)索引中取得良好的效果，目前大部分內(nèi)存索引結(jié)構(gòu)也是以B-Tree類的Key值比較樹(shù)為原型，再針對(duì)CPU-Cache-Memory架構(gòu)下的新特性進(jìn)行性能優(yōu)化.

(1) “內(nèi)存索引”的首次提出——T-Tree

在20世紀(jì)90年代，B-Tree作為一種被廣泛接受的磁盤(pán)索引結(jié)構(gòu)被直接用于內(nèi)存索引；但是，由于當(dāng)時(shí)cache的容量較小，B-Tree的結(jié)點(diǎn)結(jié)構(gòu)中指針數(shù)據(jù)過(guò)多，導(dǎo)致整個(gè)結(jié)構(gòu)太過(guò)龐大；并且索引結(jié)構(gòu)對(duì)cache的利用率明顯不高，不能很好地滿足Cache-Memory架構(gòu)對(duì)索引的新要求.

針對(duì)B-Tree的不足，結(jié)合AVL樹(shù)[18]和B樹(shù)[15]的各自特性進(jìn)行改進(jìn)得到的T-Tree[19]被認(rèn)為是最早出現(xiàn)的針對(duì)內(nèi)存數(shù)據(jù)建立的索引結(jié)構(gòu).該結(jié)構(gòu)由威斯康星大學(xué)的Lehman和Carey共同提出，并在后來(lái)被應(yīng)用于MonetDB[20]中索引更新區(qū)的數(shù)據(jù)，取得了較好的查詢性能提升.但是，由于其平衡的調(diào)整仍然借鑒AVL樹(shù)的結(jié)點(diǎn)旋轉(zhuǎn)規(guī)則，導(dǎo)致其失衡后的再平衡過(guò)程非常繁瑣；并且插入的上溢出及刪除的下溢出算法過(guò)于復(fù)雜，也導(dǎo)致T-Tree更新操作的平均消耗過(guò)大.

(2) “cache敏感性”概念提出及索引結(jié)構(gòu)的改進(jìn)

盡管T-Tree的改進(jìn)探索并不是很成功，但T-Tree的提出使得人們認(rèn)識(shí)到，由于Cache-Memory架構(gòu)與Memory-Disk架構(gòu)之間的性能及容量等各方面的差異，所以內(nèi)存索引結(jié)構(gòu)并不能完全照搬磁盤(pán)索引結(jié)構(gòu).

當(dāng)數(shù)據(jù)從磁盤(pán)全部轉(zhuǎn)移到內(nèi)存中后，cache的結(jié)構(gòu)特性對(duì)內(nèi)存數(shù)據(jù)索引的建立影響重大，其涉及的最重要的一個(gè)問(wèn)題是cache的敏感性.CPU及cache對(duì)數(shù)據(jù)處理和訪問(wèn)速度的差異成為內(nèi)存數(shù)據(jù)庫(kù)的主要性能瓶頸.已有實(shí)驗(yàn)結(jié)果表明，在內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中，半數(shù)的CPU等待時(shí)間消耗在二級(jí)cache的數(shù)據(jù)失效和一級(jí)cache的指令失效處理上[8].所以，如何合理地利用cache特征設(shè)計(jì)cache敏感算法已經(jīng)成為內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中要解決的一個(gè)重要問(wèn)題.

針對(duì)內(nèi)存數(shù)據(jù)索引和cache的架構(gòu)特性，人們提出了“緩存敏感(Cache-Sensitive)技術(shù)”[5].研究表明，對(duì)傳統(tǒng)的磁盤(pán)索引進(jìn)行緩存敏感改造得到的內(nèi)存索引結(jié)構(gòu)能夠較為顯著地提升內(nèi)存數(shù)據(jù)的查詢性能.“緩存敏感性”主要解決的問(wèn)題是針對(duì)cache的容量較小、以cache Line為數(shù)據(jù)交換的最小單位以及cache 失效所帶來(lái)的巨大的時(shí)間消耗等特性；通過(guò)盡量提高cache Line的利用率來(lái)降低在索引搜索過(guò)程中Cache Miss發(fā)生的概率，從而提高查詢的性能.

針對(duì)Cache敏感性問(wèn)題，Ross等人對(duì)傳統(tǒng)面向磁盤(pán)的B+-Tree類索引結(jié)構(gòu)作了一系列的改進(jìn)，提出了新的緩存敏感的內(nèi)存索引結(jié)構(gòu)： 基于OLAP應(yīng)用的CSS-Tree[5]及添加OLTP(在線事務(wù)系統(tǒng)，On-Line Transaction Processing)的更新操作的CSB+-Tree[6].其中CSS-Tree與B+-Tree的索引結(jié)構(gòu)類似，利用索引結(jié)點(diǎn)的連續(xù)順序存放特性，容易得出任意索引結(jié)點(diǎn)的任意子結(jié)點(diǎn)所存放的位置，從而完全省略B+Tree中用于指示子結(jié)點(diǎn)位置的指針空間，最大化索引結(jié)點(diǎn)的扇出分支數(shù)目，達(dá)到提高cache利用率的最終目的.并對(duì)索引結(jié)點(diǎn)大小與cache line的對(duì)應(yīng)關(guān)系的改變導(dǎo)致的索引結(jié)構(gòu)遍歷過(guò)程中產(chǎn)生的cache失效次數(shù)給出了詳細(xì)的理論論證，從而確立了索引結(jié)點(diǎn)大小與cache line容量相等的最優(yōu)索引結(jié)點(diǎn)配置.

在當(dāng)時(shí)的硬件環(huán)境下，針對(duì)OLAP應(yīng)用，CSS-Tree已經(jīng)達(dá)到了接近最優(yōu)的查詢性能優(yōu)化；然而，為此付出的更新代價(jià)極大：由于該索引結(jié)構(gòu)中沒(méi)有任何指針數(shù)據(jù)的存在，所有的結(jié)點(diǎn)按順序連續(xù)存放，使得該索引結(jié)構(gòu)的更新變得非常困難；在OLAP應(yīng)用的定期批量更新操作中，索引結(jié)構(gòu)只能通過(guò)重新構(gòu)建的方式進(jìn)行維護(hù)，并不具備實(shí)時(shí)插入更新的能力.為了解決OLTP系統(tǒng)中的實(shí)時(shí)增刪改操作，必須對(duì)CSS-Tree的結(jié)構(gòu)進(jìn)行合理化的改進(jìn)——適當(dāng)?shù)厝菰S位置標(biāo)示指針的存在.針對(duì)該應(yīng)用需求，結(jié)合傳統(tǒng)B+Tree在處理增刪改操作時(shí)的規(guī)范，CSB+-Tree在每個(gè)索引結(jié)點(diǎn)組(Node Group)中增加了一個(gè)位置指針，使得整個(gè)索引結(jié)構(gòu)只需以結(jié)點(diǎn)組為單位連續(xù)存放即可；增加了索引結(jié)構(gòu)的位置靈活性，并借鑒B+Tree的增刪調(diào)節(jié)算法加以改進(jìn)，實(shí)現(xiàn)了實(shí)時(shí)的動(dòng)態(tài)索引項(xiàng)增刪操作.改進(jìn)后的CSB+Tree在提升OLTP應(yīng)用中的數(shù)據(jù)查找性能上展示了較大的優(yōu)勢(shì).在文獻(xiàn)[6]中,除了提出針對(duì)基于內(nèi)存的OLTP應(yīng)用有較好性能提升的CSB+Tree索引結(jié)構(gòu)外，對(duì)其索引結(jié)點(diǎn)組的規(guī)模也進(jìn)行了形式化的討論：通過(guò)Segmented CSB+Tree的結(jié)點(diǎn)塊劃分來(lái)調(diào)節(jié)整個(gè)索引結(jié)點(diǎn)組的空間占用大小及數(shù)量規(guī)模，從而調(diào)節(jié)索引項(xiàng)增刪造成結(jié)點(diǎn)或結(jié)點(diǎn)組分裂時(shí)的維護(hù)開(kāi)銷.

在當(dāng)時(shí)的CPU-Cache-Memory架構(gòu)形式下，充分考慮cache敏感性問(wèn)題所提出的CS-類索引無(wú)疑極大提升了內(nèi)存數(shù)據(jù)查找效率，最大化地發(fā)揮了內(nèi)存索引在數(shù)據(jù)檢索中的作用.到2007年，韓國(guó)的一組研究人員對(duì)T-Tree做了緩存敏感性改進(jìn)，提出基于T-Tree的CST-Tree[7]，以改善數(shù)據(jù)所消耗的索引樹(shù)層數(shù)較大且沒(méi)有進(jìn)行cache line對(duì)齊等問(wèn)題；與此同時(shí)，合理避免了傳統(tǒng)T-Tree在查找過(guò)程中可能發(fā)生結(jié)點(diǎn)誤載入cache的情況；從而使經(jīng)過(guò)改進(jìn)的CST-Tree在數(shù)據(jù)查詢的時(shí)間性能上大幅度優(yōu)于之前的CSB+Tree.

(3) 針對(duì)內(nèi)存索引的優(yōu)化技術(shù)

① SIMD指令技術(shù)

當(dāng)代計(jì)算機(jī)的CPU提供“單指令流多數(shù)據(jù)流”(SIMD)的指令集支持，以實(shí)現(xiàn)一條指令同時(shí)作用于多個(gè)操作數(shù)，從而加快數(shù)據(jù)處理的速度.文獻(xiàn) [21]給出了將傳統(tǒng)數(shù)據(jù)庫(kù)操作進(jìn)行SIMD推廣的實(shí)現(xiàn)，并說(shuō)明SIMD指令集對(duì)索引結(jié)構(gòu)的支持給不同索引的構(gòu)建或遍歷帶來(lái)性能提升.

有了SIMD指令集在數(shù)據(jù)庫(kù)索引結(jié)構(gòu)中的應(yīng)用基礎(chǔ)，2009年Schlegel等人提出了K-Ary Search算法[22].該算法在傳統(tǒng)的二分查找的基礎(chǔ)上，對(duì)其進(jìn)行SIMD拓展，使其每個(gè)比較指令針對(duì)k個(gè)操作數(shù)進(jìn)行，將要查找的原始有序數(shù)據(jù)分為k+1個(gè)區(qū)間;對(duì)比于原來(lái)的折半查找，單條指令過(guò)濾掉的數(shù)據(jù)成倍增加，從而加快有序數(shù)據(jù)的查找效率.隨后，由Kim等人提出的FAST(Fast Architecture Sensitive Tree)[23]索引結(jié)構(gòu)正式將SIMD技術(shù)應(yīng)用于內(nèi)存索引中：該結(jié)構(gòu)以K-Ary Search為基礎(chǔ)，充分考慮cache層的架構(gòu)特性，平衡索引頁(yè)塊、cache line塊及SIMD指令塊三者之間的關(guān)系，通過(guò)page blocking-cache line blocking-SIMD blocking三層架構(gòu)的索引樹(shù)存儲(chǔ)方式，使得在兼顧、cache敏感性問(wèn)題的同時(shí)將SIMD指令運(yùn)用于內(nèi)存索引結(jié)構(gòu).

② 查詢緩存技術(shù)[24]

在建立內(nèi)存索引結(jié)構(gòu)的基本考慮因素中除了，盡量提升cache利用率和考慮cache敏感性之外，減少cache失效所帶來(lái)的額外時(shí)間損耗也是提升性能的有效方法之一.在對(duì)海量數(shù)據(jù)建立內(nèi)存索引時(shí)，并不能保證整個(gè)索引結(jié)構(gòu)在任意時(shí)刻都在cache中緩存；因此在對(duì)基于樹(shù)型結(jié)構(gòu)的索引進(jìn)行搜索時(shí)，也需要盡量避免cache失效所帶來(lái)的性能損失.Kenneth A. Ross團(tuán)隊(duì)以B-Tree和CSB+Tree為基礎(chǔ)，提出的針對(duì)批量查詢的緩存技術(shù)，在很大程度上減少了系統(tǒng)冷啟動(dòng)或索引結(jié)構(gòu)被替換出cache時(shí)對(duì)其搜索產(chǎn)生的cache失效次數(shù).該算法基于已有的內(nèi)存索引結(jié)構(gòu)，在結(jié)點(diǎn)(或結(jié)點(diǎn)組)上新加用于緩存搜索鍵值的數(shù)組空間.當(dāng)大量的查詢來(lái)臨時(shí)，逐層進(jìn)行索引結(jié)構(gòu)的查找將搜索鍵值存放于該層目標(biāo)索引結(jié)點(diǎn)(所在結(jié)點(diǎn)組)對(duì)應(yīng)的緩存數(shù)組中，只有當(dāng)用于緩存鍵值的數(shù)組存滿溢出時(shí)才會(huì)觸發(fā)索引結(jié)構(gòu)向下一層進(jìn)一步查找；同樣的，只有葉子結(jié)點(diǎn)(組)對(duì)應(yīng)的緩存數(shù)組溢出時(shí)才會(huì)返回查詢結(jié)果.

當(dāng)批量查找操作到來(lái)時(shí)，假定數(shù)據(jù)索引結(jié)構(gòu)不在cache中緩存，該算法將原來(lái)單獨(dú)的索引結(jié)構(gòu)中針對(duì)每個(gè)鍵值查找的cache失效次數(shù)進(jìn)行了有效合并，使得一組鍵值的查找只會(huì)產(chǎn)生一次cache失效，大大減少了cache失效帶來(lái)的時(shí)間消耗，從而提升數(shù)據(jù)搜索的效率.需要注意的是，該算法的原始結(jié)構(gòu)并不能保證批量查詢的返回結(jié)果順序與查詢到來(lái)順序一致，需要額外的保序算法；另外，該方案增大了索引結(jié)構(gòu)所占用的空間大小(用于增加鍵值緩存數(shù)組)，因此對(duì)鍵值緩存數(shù)組的選取需進(jìn)行較為完善的空間代價(jià)分析.

2.2 基于字典(trie)結(jié)構(gòu)的內(nèi)存索引

文獻(xiàn)[25]首次形式化的給出了trie(也稱數(shù)字搜索樹(shù)digital search tree[16])結(jié)構(gòu)的概念——一種類似于字典的數(shù)據(jù)索引方式，直接通過(guò)對(duì)要查找的原始數(shù)據(jù)的每一位進(jìn)行索引來(lái)組織整個(gè)索引結(jié)構(gòu)，常被用于對(duì)字符串?dāng)?shù)據(jù)建立索引.在2011年SIGMOD Programming Contest中，德累斯頓工業(yè)大學(xué)的Kissinger等人組成的團(tuán)隊(duì)所提出的針對(duì)內(nèi)存數(shù)據(jù)的廣義前綴搜索樹(shù)(Generalized Prefix Search Tree GPS-Tree)[26,27]索引結(jié)構(gòu)，取得了很好的成績(jī).該結(jié)構(gòu)以傳統(tǒng)trie-tree為基礎(chǔ)，用原始數(shù)據(jù)(限定為數(shù)值類型)對(duì)應(yīng)的二進(jìn)制表示形式建立索引結(jié)構(gòu)，并提出bypass structure和dynamic，prefix-based expansion算法壓縮索引樹(shù)高度從而取得了較好的查詢性能.

文獻(xiàn)[16]提出的GPS-Tree索引結(jié)構(gòu)，在樹(shù)高壓縮上已經(jīng)臻于完美；然而當(dāng)索引數(shù)據(jù)長(zhǎng)度較大并且值域空間分布較小時(shí)，其固定的結(jié)點(diǎn)結(jié)構(gòu)使得結(jié)點(diǎn)中索引值浪費(fèi)的情況非常普遍；并且其特定的針對(duì)二進(jìn)制數(shù)據(jù)進(jìn)行索引的限制條件也極大縮小了該結(jié)構(gòu)能夠處理的數(shù)據(jù)類型種類.為了解決這些問(wèn)題，Leis等人提出了adaptive radix tree(AR-Tree)[28].在AR-tree中針對(duì)GPS-tree的問(wèn)題作了一系列的改進(jìn)：(1)索引結(jié)點(diǎn)的大小并不固定，而是根據(jù)其子結(jié)點(diǎn)的數(shù)目動(dòng)態(tài)變化，從而盡可能地減少結(jié)點(diǎn)載入cache時(shí)導(dǎo)致的利用率下降問(wèn)題；(2)形式化地定義了對(duì)傳統(tǒng)trie-tree高度進(jìn)行壓縮的兩種算法(path compression和lazy expansion)并將其應(yīng)用于AR-tree中；(3)給出了常用的數(shù)據(jù)類型及其復(fù)合形式與二進(jìn)制串的對(duì)應(yīng)轉(zhuǎn)換關(guān)系，拓展了AR-tree可用于索引的數(shù)據(jù)類型范圍.經(jīng)過(guò)如上的算法改進(jìn)，AR-tree在內(nèi)存索引的查找性能相較于GPS-tree取得了進(jìn)一步的提升.

2.3 Hash及復(fù)合型結(jié)構(gòu)的內(nèi)存索引

(1) 基于hash結(jié)構(gòu)的內(nèi)存索引

傳統(tǒng)的Hash索引結(jié)構(gòu)也被廣泛的用于磁盤(pán)數(shù)據(jù)庫(kù)中，其索引結(jié)構(gòu)不需要額外的存儲(chǔ)空間，并且能夠在O(1)的時(shí)間復(fù)雜度下準(zhǔn)確定位到所查找的數(shù)據(jù).將磁盤(pán)數(shù)據(jù)庫(kù)中的數(shù)據(jù)查找時(shí)間代價(jià)優(yōu)化至最小.從chained bucket hash[26]的提出到后來(lái)extendible hash[29]、linear hash[30]、modified linear hash[19]的改進(jìn)，只是對(duì)映射沖突的處理、桶分裂的策略進(jìn)行了性能優(yōu)化，并沒(méi)有針對(duì)內(nèi)存索引的結(jié)構(gòu)特性進(jìn)行任何算法改進(jìn)，直至2007年，由Ross提出的基于現(xiàn)代處理器的Hash預(yù)取算法[31]才將SIMD指令集融入到hash算法中，從內(nèi)存索引的角度提升傳統(tǒng)hash算法的索引構(gòu)造過(guò)程中數(shù)據(jù)組織的效率.

回顧hash算法的發(fā)展史可看出，針對(duì)hash算法的內(nèi)存改進(jìn)與傳統(tǒng)磁盤(pán)hash相比沒(méi)有明顯的區(qū)別，單獨(dú)的基于hash的內(nèi)存索引結(jié)構(gòu)在內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中并不常見(jiàn)，大多被用作分布式環(huán)境下原始數(shù)據(jù)分布的一種平衡性策略.

(2) 復(fù)合型結(jié)構(gòu)的內(nèi)存索引

由于其對(duì)于字符串類型數(shù)據(jù)的完美索引方式，使得Trie索引結(jié)構(gòu)及其變型總能達(dá)到相對(duì)較優(yōu)的性能；但Trie的先天性結(jié)構(gòu)問(wèn)題導(dǎo)致在內(nèi)存索引中對(duì)cache的利用率比較低下.因此，以Trie結(jié)構(gòu)為基礎(chǔ)，添加各種輔助結(jié)構(gòu)優(yōu)化其針對(duì)內(nèi)存數(shù)據(jù)的索引能力成為復(fù)合型內(nèi)存索引結(jié)構(gòu)的主要組成方式.

Trie與hash結(jié)構(gòu)的結(jié)合：眾所周知，trie結(jié)構(gòu)對(duì)字符串類型的數(shù)據(jù)有較好的索引效率，而hash可以根據(jù)數(shù)據(jù)的不同特征將原始數(shù)據(jù)劃分為不同的模塊.正如之前所說(shuō)，由于Trie的基本結(jié)構(gòu)中結(jié)點(diǎn)大小固定，當(dāng)索引數(shù)據(jù)長(zhǎng)度較大并且取值空間分布較小時(shí)，結(jié)點(diǎn)中索引項(xiàng)浪費(fèi)情況明顯；而結(jié)合hash先對(duì)數(shù)據(jù)進(jìn)行分組，使得同一組中的數(shù)據(jù)范圍相對(duì)縮小，可以有效的提升trie結(jié)構(gòu)中索引結(jié)點(diǎn)的有效利用率.文獻(xiàn)[32,33]中分別對(duì)trie和hash結(jié)構(gòu)進(jìn)行了結(jié)合，相較于原始的結(jié)構(gòu)有效的提升了索引的查找效率.

Trie與比較樹(shù)類型索引結(jié)構(gòu)的結(jié)合：由于trie結(jié)構(gòu)本身的不保序性導(dǎo)致其無(wú)法應(yīng)對(duì)范圍查詢，而在現(xiàn)實(shí)應(yīng)用中絕大多數(shù)情況下會(huì)面臨范圍查詢的需求.因此借鑒比較樹(shù)類型索引的特性對(duì)trie進(jìn)行改進(jìn)，使其能夠支持范圍查詢也得到廣泛的研究：文獻(xiàn)[34,35]中給出了trie與B/T-Tree結(jié)合的算法；文獻(xiàn)[36]中給出了trie與CSB+Tree結(jié)合產(chǎn)生的索引結(jié)構(gòu)，在滿足范圍字符串查詢的基礎(chǔ)上綜合考量了緩存敏感性問(wèn)題，對(duì)內(nèi)存索引更具針對(duì)性.

3 分布式內(nèi)存數(shù)據(jù)庫(kù)中索引的應(yīng)用

隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)處理系統(tǒng)所要處理的數(shù)據(jù)規(guī)模日益增大.傳統(tǒng)的單機(jī)式系統(tǒng)已逐漸無(wú)法滿足應(yīng)用對(duì)處理性能的所提出的要求，內(nèi)存數(shù)據(jù)處理系統(tǒng)也逐漸向分布式方向發(fā)展.隨之而來(lái)的針對(duì)內(nèi)存數(shù)據(jù)建立的索引結(jié)構(gòu)必然要針對(duì)分布式數(shù)據(jù)存儲(chǔ)進(jìn)行有效的調(diào)整，使其在分布式環(huán)境下仍然能夠高效進(jìn)行數(shù)據(jù)查找過(guò)程中的過(guò)濾，快速精準(zhǔn)的定位數(shù)據(jù)位置.

目前，對(duì)分布式內(nèi)存數(shù)據(jù)庫(kù)的研究還剛剛開(kāi)始，尚未有非常完善的分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng).memSQL[37]作為一個(gè)分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)，完全遵從傳統(tǒng)的ACID事務(wù)準(zhǔn)則；利用無(wú)鎖的數(shù)據(jù)結(jié)構(gòu)和即時(shí)編譯器(Just-In-Time Compiler，JIT Compiler)處理高負(fù)荷的工作流，使得數(shù)據(jù)處理性能得到很大的提升；然而，其對(duì)數(shù)據(jù)的獲取并沒(méi)有添加任何基于索引算法的加速，仍舊采取簡(jiǎn)單的順序掃描策略.除此之外，以SAP公司開(kāi)發(fā)的商業(yè)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)HANA[13]為例，雖然有分布式版本，但是相較于其單機(jī)版本的性能優(yōu)化仍有一定的差距；并且SAP開(kāi)發(fā)人員并沒(méi)有提供對(duì)HANA的主數(shù)據(jù)建立內(nèi)存索引的功能，只是在其用于處理增刪改等OLTP操作的deta內(nèi)存區(qū)默認(rèn)建立了CSB+Tree的索引結(jié)構(gòu)以便快速定位已被修改的數(shù)據(jù).而對(duì)整個(gè)的未被修改的原始數(shù)據(jù)的搜索，其認(rèn)為在內(nèi)存環(huán)境下的列存儲(chǔ)數(shù)據(jù)，順序掃描的速率已經(jīng)足夠迅速，可以滿足日常應(yīng)用對(duì)數(shù)據(jù)查詢的性能要求.

由于分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)的研究并不成熟，相應(yīng)的分布式內(nèi)存數(shù)據(jù)索引結(jié)構(gòu)的探索也并沒(méi)有系統(tǒng)的展開(kāi).如何結(jié)合當(dāng)前硬件的CPU-Cache-Memory架構(gòu)對(duì)已有的單機(jī)內(nèi)存索引結(jié)構(gòu)進(jìn)行分布式拓展，使其能夠無(wú)縫的融入已有的分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)從而大幅度提升數(shù)據(jù)查找過(guò)程的性能，成為內(nèi)存索引研究領(lǐng)域的難點(diǎn)問(wèn)題之一.

4 未來(lái)展望

當(dāng)今是網(wǎng)絡(luò)極具膨脹發(fā)展的時(shí)代，數(shù)據(jù)產(chǎn)生量日益增多，大規(guī)模數(shù)據(jù)的有效管理問(wèn)題臻待解決，大數(shù)據(jù)的管理技術(shù)也已經(jīng)成為當(dāng)前和未來(lái)一段時(shí)間內(nèi)計(jì)算機(jī)領(lǐng)域的重要研究課題之一[41].

4.1 數(shù)據(jù)及應(yīng)用的發(fā)展趨勢(shì)

隨著云時(shí)代的來(lái)臨,大數(shù)據(jù)也吸引了越來(lái)越多的關(guān)注.2008年Nature上出現(xiàn)“大數(shù)據(jù)”?？痆42]，而時(shí)至今日大數(shù)據(jù)時(shí)代早已開(kāi)啟.盡管傳統(tǒng)的基于磁盤(pán)的數(shù)據(jù)庫(kù)系統(tǒng)在處理傳統(tǒng)的應(yīng)用時(shí)表現(xiàn)出了優(yōu)異的性能，但在不同的時(shí)代所要處理的數(shù)據(jù)規(guī)模也大不相同.例如在Web 1.0時(shí)代，整個(gè)互聯(lián)網(wǎng)的數(shù)據(jù)總規(guī)模較小，數(shù)據(jù)管理較為簡(jiǎn)單；而隨著Web 2.0、Web 3.0時(shí)代的到來(lái)，所有的互聯(lián)網(wǎng)用戶均可在互聯(lián)網(wǎng)上產(chǎn)生數(shù)據(jù)記錄.以社交媒體為例，F(xiàn)aceBook的日數(shù)據(jù)產(chǎn)生量已經(jīng)達(dá)到TB級(jí).日益龐大的網(wǎng)絡(luò)數(shù)據(jù)規(guī)模對(duì)數(shù)據(jù)的有效管理提出了新的挑戰(zhàn)，目前大數(shù)據(jù)處理中最大的困難并非是如何存儲(chǔ)規(guī)模龐大的數(shù)據(jù)，而是如何從這些海量數(shù)據(jù)中高效檢索出所需要的數(shù)據(jù)，并對(duì)其進(jìn)行處理.

隨著數(shù)據(jù)規(guī)模的日益增大，數(shù)據(jù)處理系統(tǒng)也逐步面臨更新改革.在最初的數(shù)據(jù)庫(kù)誕生之際，基于單機(jī)的簡(jiǎn)單的磁盤(pán)數(shù)據(jù)庫(kù)管理系統(tǒng)能夠充分滿足當(dāng)時(shí)數(shù)據(jù)處理的需求；隨著時(shí)間的推移逐步出現(xiàn)了分布式數(shù)據(jù)庫(kù)系統(tǒng).當(dāng)今各個(gè)不同企業(yè)或組織的應(yīng)用不同，系統(tǒng)設(shè)計(jì)的目標(biāo)、所面向的負(fù)載也不盡相同，傳統(tǒng)的面向磁盤(pán)的數(shù)據(jù)庫(kù)系統(tǒng)所支持的數(shù)據(jù)分析處理功能受到前所未有的挑戰(zhàn)，類似于Hadoop[43]，HBase[44]，Cassandra[45]等完全顛覆數(shù)據(jù)庫(kù)的ACID事務(wù)準(zhǔn)則[46]而基于key-value的分布式存儲(chǔ)處理系統(tǒng)也得到廣泛的應(yīng)用，并在海量數(shù)據(jù)的并行處理中取得了非常好的性能提升.另一方面，隨著硬件技術(shù)的革新，內(nèi)存價(jià)格迅速下降導(dǎo)致單機(jī)特別是高性能服務(wù)器的內(nèi)存容量日趨增大，基于內(nèi)存的數(shù)據(jù)處理系統(tǒng)也應(yīng)運(yùn)而生，Spark、Shark[47]等對(duì)Hadoop的內(nèi)存拓展系統(tǒng)也得到廣泛的應(yīng)用.同時(shí)，如何將傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)進(jìn)行內(nèi)存拓展也引起越來(lái)越多人的興趣.與傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)相比，內(nèi)存數(shù)據(jù)庫(kù)并不是單純的增加了緩沖區(qū)的大小.當(dāng)傳統(tǒng)的磁盤(pán)I/O瓶頸消失后，CPU與內(nèi)存間的數(shù)據(jù)獲取時(shí)間差異也成為新的內(nèi)存數(shù)據(jù)庫(kù)中的系統(tǒng)瓶頸.于是，對(duì)內(nèi)存中數(shù)據(jù)快速有效的獲取問(wèn)題成為分布式內(nèi)存數(shù)據(jù)庫(kù)領(lǐng)域中新的研究熱點(diǎn).隨著內(nèi)存數(shù)據(jù)庫(kù)的發(fā)展和分布式數(shù)據(jù)管理技術(shù)的提高，針對(duì)分布式的內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)的研究也成為新的領(lǐng)域熱點(diǎn)問(wèn)題.如何針對(duì)不同的數(shù)據(jù)類型、分布規(guī)律、查詢處理頻率等信息建立相對(duì)應(yīng)的高效的分布式內(nèi)存索引結(jié)構(gòu)引起許多業(yè)內(nèi)人士的討論研究.

嶄新的應(yīng)用需求是推動(dòng)數(shù)據(jù)庫(kù)技術(shù)發(fā)展的源動(dòng)力.企業(yè)中實(shí)際的應(yīng)用需求決定了數(shù)據(jù)庫(kù)系統(tǒng)發(fā)展及性能提升的研究方向.現(xiàn)今時(shí)代，數(shù)據(jù)量爆炸，對(duì)數(shù)據(jù)的實(shí)時(shí)性分析要求越來(lái)越高，例如證券交易所中對(duì)股票行情的實(shí)時(shí)展示，金融機(jī)構(gòu)所提供的人們信用卡的近期消費(fèi)情況統(tǒng)計(jì)分析等，這些應(yīng)用導(dǎo)致企業(yè)對(duì)能夠處理大數(shù)據(jù)量的實(shí)時(shí)分析系統(tǒng)的需求日益緊迫.毫無(wú)疑問(wèn)，新生的分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)在分布式數(shù)據(jù)處理效率上取得了極大的提升，并且依舊兼容傳統(tǒng)的SQL查詢方式，對(duì)上層的應(yīng)用接口并未進(jìn)行任何改變使得其更容易被企業(yè)所接收.同時(shí)，在傳統(tǒng)數(shù)據(jù)庫(kù)中極大提升搜索速率的磁盤(pán)索引結(jié)構(gòu)也被借鑒到內(nèi)存數(shù)據(jù)庫(kù)中，針對(duì)內(nèi)存數(shù)據(jù)的有效索引既要考慮分布式集群內(nèi)存數(shù)據(jù)的分布情況，又要結(jié)合CPU-Cache-Memory的新型架構(gòu)，使得內(nèi)存數(shù)據(jù)索引的結(jié)構(gòu)與傳統(tǒng)的磁盤(pán)索引不盡相同，針對(duì)不同類型的應(yīng)用需求都可以考慮建立相對(duì)應(yīng)的查詢加速索引結(jié)構(gòu).

4.2 未來(lái)內(nèi)存索引研究的機(jī)遇與挑戰(zhàn)

索引的有效cache：Cache-Memory間的訪問(wèn)延遲相較于Memory-Disk間更加微小(圖3)，如何利用有效的索引結(jié)構(gòu)在這更小的訪問(wèn)延遲中加速數(shù)據(jù)的訪問(wèn)效率，這是內(nèi)存索引所要考慮的重要問(wèn)題之一.由于在數(shù)據(jù)訪問(wèn)過(guò)程中cache失效所帶來(lái)的時(shí)間消耗很大，利用有效策略使得在訪問(wèn)內(nèi)存索引結(jié)構(gòu)的過(guò)程中盡量避免cache失效成為提升整個(gè)數(shù)據(jù)訪問(wèn)性能的關(guān)鍵技術(shù).隨著數(shù)據(jù)規(guī)模的增大，如何設(shè)計(jì)高效的索引壓縮算法，以盡可能減少索引所占用的空間，從而使得整個(gè)或者絕大部分的索引結(jié)構(gòu)能夠常駐在L3 cache中，在索引的訪問(wèn)過(guò)程中消除cache失效所產(chǎn)生的性能損耗，這些是未來(lái)設(shè)計(jì)內(nèi)存索引結(jié)構(gòu)所要面對(duì)的重要問(wèn)題.

硬件變化：由于cache結(jié)構(gòu)的特殊性所帶來(lái)的cache敏感性，使得當(dāng)今索引在設(shè)計(jì)的時(shí)候都要充分考慮所針對(duì)集群的具體架構(gòu)；并且為了使得索引的搜索效率達(dá)到最大化，類似于SIMD指令技術(shù)及NUMA架構(gòu)的訪問(wèn)性能等都做了針對(duì)性的優(yōu)化，這使得索引結(jié)構(gòu)在不同配置集群間的可移植性受到限制，從而影響整個(gè)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)的集群可移植性.

分布式索引拓展：從本文第2、3節(jié)可看出，雖然內(nèi)存索引的研究已經(jīng)歷經(jīng)了三十多年，但其研究領(lǐng)域依局限于單機(jī)的環(huán)境，對(duì)現(xiàn)今流行的分布式環(huán)境并沒(méi)有給出較好的拓展策略.而隨著大數(shù)據(jù)時(shí)代的到來(lái)，海量的數(shù)據(jù)規(guī)模對(duì)單機(jī)的處理器性能提出了非常高的要求，使得絕大多數(shù)企業(yè)都選擇了分布式的處理環(huán)境從而減輕對(duì)單機(jī)的性能限制.類似于Hadoop、Shark、Spark等基于Key-Value存儲(chǔ)方式的分布式數(shù)據(jù)處理系統(tǒng)得到廣泛的應(yīng)用.而內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)從原來(lái)的單機(jī)版本(傳統(tǒng)的MonetDB[20])向分布式版本拓展也變得尤為迫切.針對(duì)單機(jī)的內(nèi)存索引結(jié)構(gòu)勢(shì)必要進(jìn)行分布式的改進(jìn)，以便在分布式集群環(huán)境下繼續(xù)有效的提升數(shù)據(jù)查找過(guò)程中的效率.

海量數(shù)據(jù)的地址表示：在傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)中，除非外力進(jìn)行干預(yù)(如人工進(jìn)行數(shù)據(jù)遷徙)否則原始數(shù)據(jù)表格在磁盤(pán)上的位置保持不變；因此，磁盤(pán)索引的葉子結(jié)點(diǎn)可以直接用數(shù)據(jù)所在磁盤(pán)的邏輯地址來(lái)指示數(shù)據(jù)位置.而在內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中，不論內(nèi)存容量如何增大，系統(tǒng)運(yùn)行過(guò)程中總是無(wú)法保證有足夠大的內(nèi)存空間可以使得所有的表數(shù)據(jù)都完全被載入.因此，內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中也會(huì)存在數(shù)據(jù)在內(nèi)存與磁盤(pán)間的交換(swap).一旦內(nèi)存中原始數(shù)據(jù)被swap到磁盤(pán)，當(dāng)其重新被載入內(nèi)存時(shí)，操作系統(tǒng)所分配給它的內(nèi)存地址幾乎不可能與之前的地址完全一致；因此，在內(nèi)存索引結(jié)構(gòu)中，葉子結(jié)點(diǎn)索引數(shù)據(jù)時(shí)并不能直接使用其在內(nèi)存中的邏輯地址.通常情況下，對(duì)小規(guī)模的數(shù)據(jù)而言該問(wèn)題的解決辦法為用數(shù)據(jù)相對(duì)于某些特定標(biāo)志位置的偏移來(lái)指示數(shù)據(jù)在內(nèi)存中的位置，這樣只要原始數(shù)據(jù)的排序保持不變，無(wú)論其是否因內(nèi)存不足被交換到磁盤(pán)過(guò)，只要重新被載入內(nèi)存，都可以根據(jù)其相對(duì)目標(biāo)位置的偏移準(zhǔn)確的進(jìn)行定位.隨著數(shù)據(jù)規(guī)模的增大，使得存儲(chǔ)相對(duì)目標(biāo)偏移所需的空間隨之越來(lái)越大，索引結(jié)構(gòu)葉子結(jié)點(diǎn)的規(guī)模也急劇上升，非常不利于整個(gè)索引結(jié)構(gòu)在L3 cache中的常駐存儲(chǔ)，因此，當(dāng)數(shù)據(jù)規(guī)模龐大時(shí)，如何有效地表示數(shù)據(jù)所處的位置從而高效地定位數(shù)據(jù)也是未來(lái)內(nèi)存索引要考慮的一個(gè)重要因素.

4.3 分布式內(nèi)存索引探索@CLAIMS[48]

當(dāng)今時(shí)代數(shù)據(jù)規(guī)模急劇增長(zhǎng)，對(duì)數(shù)據(jù)的實(shí)時(shí)處理需求日益提高，即使當(dāng)今單臺(tái)服務(wù)器結(jié)點(diǎn)的性能可以達(dá)到非常高的標(biāo)準(zhǔn)，不論是處理器數(shù)目還是內(nèi)存容量都相當(dāng)可觀，集中式的內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)仍然極大的限制了其數(shù)據(jù)處理的能力及規(guī)模.內(nèi)存數(shù)據(jù)庫(kù)的分布式拓展顯得尤為重要.而目前并沒(méi)有相對(duì)成熟的分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)及比較成熟的內(nèi)存索引結(jié)構(gòu).華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院在此類系統(tǒng)的研發(fā)上已經(jīng)開(kāi)展了近兩年的工作，致力于設(shè)計(jì)與實(shí)現(xiàn)一個(gè)集群感知的基于內(nèi)存的分布式數(shù)據(jù)庫(kù)系統(tǒng)(Cluster-Aware In-Memory System， CLAIMS).該系統(tǒng)中也已經(jīng)設(shè)計(jì)了針對(duì)內(nèi)存數(shù)據(jù)的分布式索引結(jié)構(gòu)，該索引基于傳統(tǒng)的B-tree[15]，充分考慮cache的敏感性問(wèn)題；并在此基礎(chǔ)上結(jié)合列存儲(chǔ)及分布式數(shù)據(jù)組織的特點(diǎn)，對(duì)該結(jié)構(gòu)作進(jìn)一步的優(yōu)化：

(1) 考慮“cache敏感性”問(wèn)題，對(duì)傳統(tǒng)的B-tree索引進(jìn)行內(nèi)存改進(jìn)：消除子結(jié)點(diǎn)指針、數(shù)據(jù)指針?lè)謮K存儲(chǔ)、結(jié)點(diǎn)cache line對(duì)齊，得到CSB-tree結(jié)構(gòu).

(2) 結(jié)合分布式hash和NUMA技術(shù)對(duì)數(shù)據(jù)進(jìn)行以chunk為單位的分布式內(nèi)存bounding，并對(duì)每個(gè)chunk建立CSB-tree構(gòu)成分布式環(huán)境下的Clustered CSB-trees.

(3) 利用SIMD指令集對(duì)Clustered CSB-Trees查詢算法進(jìn)行加速，以期達(dá)到更高的訪問(wèn)效率.

(4) 根據(jù)索引數(shù)據(jù)的值域進(jìn)行結(jié)點(diǎn)壓縮，進(jìn)一步增大索引結(jié)點(diǎn)扇出，降低樹(shù)高減少層間偏移產(chǎn)生cache miss的次數(shù).

經(jīng)過(guò)一系列的優(yōu)化，我們所提出的clustered enhanced CSB-trees能夠高效地應(yīng)用于分布式內(nèi)存數(shù)據(jù)索引，并在CLAIMS中得到實(shí)驗(yàn)驗(yàn)證.

5 小 結(jié)

隨著內(nèi)存容量的大幅度增加及價(jià)格的急劇下降，使得單機(jī)的內(nèi)存配置快速提升.內(nèi)存數(shù)據(jù)庫(kù)相較于傳統(tǒng)數(shù)據(jù)庫(kù)的瓶頸的改變，導(dǎo)致之前在傳統(tǒng)磁盤(pán)數(shù)據(jù)庫(kù)中的所有性能優(yōu)化策略都要在內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中重新考慮.本文對(duì)近30年來(lái)內(nèi)存索引結(jié)構(gòu)的技術(shù)發(fā)展，作了詳細(xì)的回顧，在此過(guò)程中也發(fā)現(xiàn)由于內(nèi)存索引的特殊性，所以其結(jié)構(gòu)的發(fā)展與計(jì)算機(jī)CPU-Cache-Memory架構(gòu)的發(fā)展有著密切的聯(lián)系.并且給出大數(shù)據(jù)時(shí)代到來(lái)對(duì)內(nèi)存結(jié)構(gòu)分布式拓展的挑戰(zhàn)，在分布式環(huán)境下，無(wú)論是內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)還是索引結(jié)構(gòu)都還有長(zhǎng)足的發(fā)展空間.本文最后還簡(jiǎn)單介紹了華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院在分布式內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)及分布式內(nèi)存索引方面正在進(jìn)行的探索性工作.

[1] AMMANN A C, HANRAHAN M B, KRISHNAMURTHY R. Design of a memory resident DBMS[C]//Proc IEEE COMPCOM Conf, 1985.

[2] 微硬盤(pán)磁頭彈性臂的研究[R/OL].http://www.docin.com/p-270914249.html

[3] JANNINK J. Implementing deletion in B+-trees[J]. SIGMOD Record, 1995, 24(1).

[4] WOLF W A, MCKEE S A. Hitting the memory wall: Implications of the obvious[C]//ACM SIGARCH, 1995.

[5] RAO J, ROSS K A. Cache conscious indexing for decision-support in main memory[C]//Proceedings of the 25th VLDB Conference, 1999.

[6] RAO J, ROSS K A. Making B+-trees cache conscious in main memory[C]//SIGMOD, 2000.

[7] LEE I, SHIM J, LEE S, et al. CST-Trees: Cache Sensitive T-Trees[C]//DASFAA 2007, LNCS 4443, 2007: 398-409.

[8] AILAMAKI A, et al. DBMSs on a modern processor: Where does time go. In Proceedings of the 25th VLDB Conference, 1999.

[9] WIKIPEDIA. Non-uniform memory access [EB/OL].[2014-08-31]. http://en.wikipedia.org/wiki/Non-uniform_memory_access.

[10] LANEY D. 3D data management: controlling data volume, velocity and variety[R]. Technical Report, Meta Group, 2001.

[11] Amplab spark-lightning-fast cluster computing: https://amplab.cs.berkeley.edu/projects/spark-lightning-fast-cluster-computing.

[12] RAMCloud[EB/OL]. https://ramcloud.stanford.edu/wiki/display/ramcloud/RAMCloud.

[13] Homepage for SAP HANA Database: http://www.saphana.com/welcome.

[14] SWART G. MinSQL: a simple componentized database for the classroom[C]//PPPJ, 2003:129-132.

[15] BAYER R, MCCREIGHT E M. Organization and maintenance of large ordered indices[J]. Acta Inf, 1972(1):173-189.

[16] KNUTH D E. The art of computer programming Volume I: fundamental algorithms[M], 3rd ed. Addison-Wesley, 1997.

[17] Single Instruction Multiple Data: http://en.wikipedia.org/wiki/SIMD

[18] AHO A, HOPCROFT J, ULLMAN J D. The design and analysis of computer algorithms, Addison-Wesley Publishing Company, 1974.

[19] LEHMAN T J, et al. A study of index structures for main memory database management systems[C]//Proceedings of the 12th VLDB Conference, 1986.

[20] Homepage for MonetDB[EB/OL]. http://www.monetdb.org/Home

[21] ZHOU J, ROSS K A. Implementing database operations using SIMD instructions[C]//SIGMOD, 2002.

[22] SCHLEGEL B, GEMULLA R, LEHNER W. k-Ary search on modern processors[C]//DaMoN, 2009.

[23] KIM C, CHUGANI J, SATISH N, et al. FAST: fast architecture sensitive tree search on modern CPUs and GPUs[C]//SIGMOD, 2010:339-350.

[24] ZHOU J, ROSS K A. Buffering accesses to memory-resident index structures[J].VLDB, 2003.

[25] FREDKIN E. Trie Memory[J]. Communications of the ACM, 1960, 3(9):490-499.

[26] BOEHM M, SCHLEGEL B, VOLK P B, et al. Efficient in-memory indexing with generalized prefix trees[J]. BTW, 2011:52-55.

[27] KISSINGER T, SCHLEGEL B, BOEHM M, et al. A high-throughput in-memory index, durable on flash-based SSD[J]. SIGMOD, 2012,41(3):40-50.

[28] LEIS V, KEMPER A, NEUMANN T. The adaptive radix tree: aRTful indexing for main-memory databases[J]. ICDE, 2013.

[29] FAGIN R, NIEVERGELT J, PIPPENGER N, et al. Extendible hashing—A fast access method for dynamic files[J]. ACM Trans Database Syst, 1979, 4(3):315-344.

[30] LARSON P. Linear hashing with separators-a dynamic hashing scheme achieving one-access retrieval[J]. ACM Trans Database Syst, 1988,13(3):366-388.

[31] ROSS K A. Efficient hash probes on modern processors. In ICDE, 2007.

[32] COFFMAN E G, EVE J. File structures using hashing functions[J]. Commun ACM, 1970, 13(7):427-433.

[33] ASKITIS N, SINHA R. HAT-Trie: a cache-conscious trie-based data structure for strings. In ACSC, 2007.

[34] BOHANNON P, MCILROY P, RASTOGI R. Main-memory index structures with fixed-size partial keys. In SIGMOD, 2001.

[35] LUAN H, DU X, WANG S. Prefetching J+-tree: a Cache-optimized main memory database index structure[J]. J Comput Sci Technol, 2009,24(4):687-707.

[36] BINNIG C, HILDENBRAND S, FARBER F. Dictionary-based order preserving string compression for main memory column stores[C]//SIGMOD, 2009.

[37] Homepage for memsql: http://www.memsql.com.

[38] AGUILERA M K, GOLAB W, SHAH M A. A practical scalable distributed b-tree[C]//VLDB, 2008.

[39] WU S, JIANG D, OOI B C, et al. Efficient b-tree based indexing for cloud data processing[C]//Proc VLDB Endow, 2010,3(1): 1207-1218.

[40] MOUZA C, LITWIN W. Sd-rtree: A scalable distributed rtree[C]//ICDE, 2007: 296-305.

[41] 宮學(xué)慶，金澈清，王曉玲，等. 數(shù)據(jù)密集型科學(xué)與工程：需求和挑戰(zhàn)[J]. 計(jì)算機(jī)學(xué)報(bào)，2012, 35(8): 1563-1578.

[42] Big Data Section in Nature: http://www.nature.com/news/specials/bigdata/index.html.

[43] WHITE T.Hadoop權(quán)威指南[M].周敏奇，王曉玲，金澈清，錢(qián)衛(wèi)寧譯.2版. 北京：清華出版社，2011.

[44] Apache HBASE[EB/OL]. http://hbase.apache.org.

[45] Apache Cassandra[EB/OL]. http://cassandra.apache.org.

[46] HAERDER T, REUTER A. Principles of transaction-oriented database recovery[C]//ACM Computing Srveys, 1983, 15(4): 287-317.

[47] XIN R S, ROSEN T, ZAHARIA M, et al. Shark: SQL and rich analytics at scale[C]//SIGMOD, 2013: 13-24.

[48] CLAIMS Homepage at Github[EB/OL]. https://github.com/scdong/Claims/wiki.

(責(zé)任編輯 王善平)

In-memory index: Performance enhancement techniques leveraging on processors

DONG Shao-chan, ZHOU Min-qi, ZHANG Rong, ZHOU Ao-ying

(InstituteforDataScienceandEngineering,SoftwareEngineeringInstitute,EastChinaNormalUniversity,Shanghai200062,China)

As main memory capacities grows larger and larger, the memory era has arrived and in-memory databases have taken the place of traditional disk-based databases to provide efficient data management. In this paper, we analyzed the fundamental elements in in-memory index designing: summarized and evaluated the existing index structures, pointing out the future opportunities and challenges based on the development trend of current applications. Finally, we introduced our on-going distributed in-memory index studies on the Cluster Aware In-Memory System (CLAIMS).

in-memory indexing; cache utility; distributed in-memory database; index compressing

1000-5641(2014)05-0192-15

2014-06

國(guó)家自然科學(xué)基金(61332006)

董紹嬋，女，碩士研究生，研究方向?yàn)閮?nèi)存數(shù)據(jù)庫(kù)系統(tǒng).Email:scdong510@163.com

周敏奇，男，副教授，碩士生導(dǎo)師，研究方向?yàn)閮?nèi)存數(shù)據(jù)庫(kù)系統(tǒng).Email:mqzhou@sei.ecnu.edu.cn.

TP392

A

10.3969/j.issn.1000-5641.2014.05.017