史太齊，劉 亮，秦小麟

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

DCST：主存空間高效的緩存敏感型T-樹(shù)索引研究*

史太齊+，劉 亮，秦小麟

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

已有主存索引通過(guò)指針消除和預(yù)取機(jī)制提升索引結(jié)構(gòu)的緩存感知能力，減少緩存失效次數(shù)，但是并沒(méi)有有效地利用現(xiàn)代計(jì)算機(jī)的CPU性能和內(nèi)存空間。為了進(jìn)一步提升索引結(jié)構(gòu)對(duì)內(nèi)存空間以及CPU性能的利用率，提出了DCST-樹(shù)索引結(jié)構(gòu)。該索引結(jié)構(gòu)采用數(shù)據(jù)壓縮的方式，對(duì)結(jié)點(diǎn)中的關(guān)鍵字進(jìn)行壓縮，提高索引結(jié)構(gòu)對(duì)內(nèi)存空間和緩存空間的利用率，減少內(nèi)存訪問(wèn)次數(shù)，提高緩存命中率。同時(shí)，對(duì)結(jié)點(diǎn)進(jìn)行分區(qū)，增加結(jié)點(diǎn)容量，提高結(jié)點(diǎn)扇出度，降低樹(shù)的高度。實(shí)驗(yàn)結(jié)果表明，所提方案比現(xiàn)有主存索引機(jī)制具有更加高效的空間利用率和緩存感知能力，同時(shí)具有更加優(yōu)秀的查詢(xún)處理能力。

壓縮；主存索引；緩存敏感

1 引言

隨著主存容量不斷增加，主存價(jià)格不斷降低，計(jì)算機(jī)配備超大容量主存成為現(xiàn)實(shí)[1-4]。例如，許多數(shù)據(jù)庫(kù)服務(wù)器都已經(jīng)使用主存作為數(shù)據(jù)的主要存儲(chǔ)介質(zhì)?？梢灶A(yù)見(jiàn)，在不久的將來(lái)，所有數(shù)據(jù)都可以存放在主存當(dāng)中，主存數(shù)據(jù)庫(kù)也因此得以快速發(fā)展。研究人員已經(jīng)對(duì)主存數(shù)據(jù)庫(kù)的各個(gè)方面進(jìn)行了研究，索引作為提升數(shù)據(jù)庫(kù)查詢(xún)性能的重要方式，也是研究人員關(guān)注的重點(diǎn)。

隨著計(jì)算機(jī)硬件的發(fā)展，主存的訪問(wèn)速度成為數(shù)據(jù)庫(kù)新的性能瓶頸[5-6]。如圖1所示，在過(guò)去的三十幾年，處理器速度的提升速率大于主存速度的提升速率，長(zhǎng)期累積下來(lái)，不均衡的發(fā)展速度造成了內(nèi)存的存取速度嚴(yán)重滯后于處理器的計(jì)算速度，內(nèi)存瓶頸導(dǎo)致高性能處理器難以發(fā)揮出應(yīng)有的功效——內(nèi)存墻效應(yīng)[7-10]。因此，現(xiàn)代計(jì)算機(jī)處理器都配備了高速緩存[11]，用于平衡處理器和主存之間的速度差異。緩存是位于處理器和主存之間的低延遲存儲(chǔ)器，存儲(chǔ)了處理器最近訪問(wèn)過(guò)的數(shù)據(jù)。緩存的讀取速率比主存的讀取速率快一到兩個(gè)數(shù)量級(jí)。因此，提升應(yīng)用程序的緩存感知能力，可以有效提高應(yīng)用程序的執(zhí)行效率。索引技術(shù)是數(shù)據(jù)庫(kù)系統(tǒng)的重要組成部分，提升索引技術(shù)的緩存感知能力，對(duì)于提升數(shù)據(jù)庫(kù)系統(tǒng)性能是十分重要的[12-16]。

Fig.1 Comparison of process-memory performance圖1 處理器和主存性能發(fā)展對(duì)比

現(xiàn)有的緩存感知型索引結(jié)構(gòu)，都是通過(guò)調(diào)整索引的數(shù)據(jù)結(jié)構(gòu)來(lái)減少緩存失配的次數(shù)，與傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)索引相比有了很大的性能提升[16-20]。但是這些索引結(jié)構(gòu)并沒(méi)有高效利用主存空間，當(dāng)索引數(shù)據(jù)較多時(shí)，會(huì)消耗大量的存儲(chǔ)空間。高速緩存的容量是十分有限的，通常只有主存容量的幾百分之一，甚至幾千分之一。在進(jìn)行查找時(shí)，會(huì)造成很多次緩存失配，需要頻繁地訪問(wèn)主存。Gray提出“主存是新的磁盤(pán)”。類(lèi)似的，在主存數(shù)據(jù)庫(kù)中，緩存就是新形式的主存，緩存與主存之間的關(guān)系十分類(lèi)似于主存與磁盤(pán)之間的關(guān)系。在傳統(tǒng)數(shù)據(jù)庫(kù)中，基于磁盤(pán)的索引結(jié)構(gòu)使用壓縮的方式減少磁盤(pán)的訪問(wèn)次數(shù)[21]。在主存數(shù)據(jù)庫(kù)中，可以采用壓縮的方式減少主存的訪問(wèn)次數(shù)。在緩存的層次上對(duì)數(shù)據(jù)壓縮，雖然要消耗CPU指令，但可以顯著地減少緩存失效次數(shù)，提高緩存命中率，降低主存的訪問(wèn)頻率[3,12]。與十分有限的緩存容量相比，索引結(jié)構(gòu)經(jīng)常包含幾百萬(wàn)甚至幾億的數(shù)據(jù)，此時(shí)，內(nèi)存墻效應(yīng)會(huì)更加顯著，索引性能的發(fā)揮主要受限于主存訪問(wèn)次數(shù)。Rao等人[18]提出當(dāng)索引結(jié)點(diǎn)大小接近緩存塊大小時(shí)，索引樹(shù)的總體性能接近最優(yōu)。因此，大多數(shù)緩存感知型索引都將結(jié)點(diǎn)大小設(shè)置成緩存塊大小，但是這樣就限制了結(jié)點(diǎn)容量，增加了樹(shù)的高度，使得從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的查找過(guò)程，會(huì)產(chǎn)生更多的緩存失配次數(shù)。

針對(duì)以上問(wèn)題，在現(xiàn)有的緩存感知型索引結(jié)構(gòu)——CST-樹(shù)（cache-sensitive T-tree）的基礎(chǔ)上，采用壓縮和分區(qū)的方法，提出了DCST-樹(shù)。與CST-樹(shù)相比，DCST-樹(shù)主要具有以下特點(diǎn)：

（1）結(jié)點(diǎn)壓縮。對(duì)CST-樹(shù)結(jié)點(diǎn)中存儲(chǔ)的關(guān)鍵字進(jìn)行壓縮，減少索引數(shù)據(jù)對(duì)存儲(chǔ)空間的消耗，提高結(jié)點(diǎn)對(duì)緩存空間的利用率，減少主存訪問(wèn)次數(shù)。

（2）結(jié)點(diǎn)分區(qū)。把CST-樹(shù)結(jié)點(diǎn)分成幾個(gè)連續(xù)的分區(qū)，將結(jié)點(diǎn)中的查找操作限制在特定的分區(qū)中進(jìn)行。通過(guò)分區(qū)，可以增加結(jié)點(diǎn)容量，提高結(jié)點(diǎn)的扇出度，并降低索引樹(shù)的高度。

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)工作；第3章研究DCST-樹(shù)的結(jié)構(gòu)和特點(diǎn)；第4章討論DCST-樹(shù)的相關(guān)算法；第5章給出實(shí)驗(yàn)評(píng)估和結(jié)果分析；第6章進(jìn)行總結(jié)并介紹未來(lái)工作。

2 相關(guān)工作

計(jì)算機(jī)處理器從緩存中讀取數(shù)據(jù)的速度快于從主存中讀取的速度。因此，在主存數(shù)據(jù)庫(kù)中，提升程序的緩存感知能力是非常重要的。這里首先介紹緩存行為特點(diǎn)，隨后介紹緩存感知型主存索引的相關(guān)工作。

2.1 緩存

緩存是介于CPU和主存之間的隨機(jī)存取存儲(chǔ)器，CPU以一個(gè)或者數(shù)個(gè)緩存塊的大小讀寫(xiě)數(shù)據(jù)。緩存能夠保存處理器最近訪問(wèn)過(guò)的數(shù)據(jù)，根據(jù)程序局部性原理[5-7,20]，這些數(shù)據(jù)以后還可能會(huì)被處理器再次訪問(wèn)。此時(shí)，處理器可以直接從緩存中讀取數(shù)據(jù)，不再需要訪問(wèn)主存，因此可以提升程序性能。處理器需要的數(shù)據(jù)在緩存中，稱(chēng)之為一次緩存命中（cache hit），數(shù)據(jù)以近似處理器的速度得到處理。如果訪問(wèn)的數(shù)據(jù)不在緩存中，稱(chēng)之為一次緩存失配（cache miss）。一次緩存失配就會(huì)造成一次主存訪問(wèn)。緩存只有在緩存命中的情況下才能夠提升主存數(shù)據(jù)庫(kù)的性能，緩存命中率主要取決于應(yīng)用程序的數(shù)據(jù)存取模式。索引性能的表現(xiàn)也深受緩存行為的影響。提升索引的緩存感知能力，其本質(zhì)就是減少緩存失配次數(shù)以及提高緩存空間利用率[3,18]。

2.2 緩存感知型索引

CSB+-樹(shù)[18]（cache-sensitive B+-tree）及其變種：B+-樹(shù)在傳統(tǒng)數(shù)據(jù)庫(kù)中占據(jù)著重要的地位，為了提升B+-樹(shù)的緩存感知能力，Rao提出了它的變種CSB+-樹(shù)。CSB+-樹(shù)的更新操作類(lèi)似于B+-樹(shù)，與B+-樹(shù)不同的是，CSB+-樹(shù)的每一個(gè)結(jié)點(diǎn)只保留了很少的指針。通過(guò)減少結(jié)點(diǎn)中指針的數(shù)量，相同的緩存空間可以保留更多的關(guān)鍵字，從而表現(xiàn)出更加優(yōu)秀的性能。

CST-樹(shù)：T-樹(shù)的總體性能表現(xiàn)優(yōu)良，自問(wèn)世以來(lái)就被大部分主存數(shù)據(jù)庫(kù)所采用。但是，正如前文所述，T-樹(shù)的緩存感知能力不如B+樹(shù)。在對(duì)T-樹(shù)進(jìn)行搜索時(shí)，首先比較結(jié)點(diǎn)中的最大值和最小值，然后再?zèng)Q定搜索左右子樹(shù)。當(dāng)T-樹(shù)的一個(gè)結(jié)點(diǎn)被放在緩存中時(shí)，CPU訪問(wèn)其中的最大值和最小值，而緩存塊中剩余的關(guān)鍵字不再被訪問(wèn)。由此可以看出T-樹(shù)的緩存空間利用率非常低。T-樹(shù)已經(jīng)無(wú)法適應(yīng)處理器速度和主存訪問(wèn)速度發(fā)展不平衡的狀況。Lee等人[17]通過(guò)建立結(jié)點(diǎn)組（node group）和數(shù)據(jù)結(jié)點(diǎn)（data node），將T-樹(shù)結(jié)點(diǎn)中的最大值和最小值提取出來(lái)和結(jié)點(diǎn)中剩余的關(guān)鍵字分別存放的方式，增強(qiáng)被頻繁訪問(wèn)數(shù)據(jù)的局部性特性。如圖2所示，結(jié)點(diǎn)組包含對(duì)應(yīng)的數(shù)據(jù)結(jié)點(diǎn)中的最大值，并且結(jié)點(diǎn)組是用數(shù)組表示的二分查找樹(shù)。而數(shù)據(jù)結(jié)點(diǎn)則是原來(lái)T-樹(shù)結(jié)點(diǎn)中的關(guān)鍵字，兩者分開(kāi)存儲(chǔ)。遍歷CST-樹(shù)時(shí)，首先遍歷結(jié)點(diǎn)組，定位到相應(yīng)的關(guān)鍵字之后，再到關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)結(jié)點(diǎn)中搜索。在結(jié)點(diǎn)組中搜索時(shí)，每一個(gè)關(guān)鍵字都是有價(jià)值的，提高了緩存空間的利用率，減少了緩存失配次數(shù)，改善了T-樹(shù)的性能。

Fig.2 CST-tree圖2 CST-樹(shù)

3 DCST-樹(shù)

CST-樹(shù)中的結(jié)點(diǎn)設(shè)置為緩存塊大小，為的是在結(jié)點(diǎn)中查找時(shí)，不會(huì)造成緩存失配，但是這樣會(huì)導(dǎo)致CST-樹(shù)的高度增加，增加從根結(jié)點(diǎn)到葉結(jié)點(diǎn)查找過(guò)程中的緩存失配次數(shù)。同時(shí)，CST-樹(shù)沒(méi)有高效地利用主存空間，當(dāng)索引數(shù)據(jù)較大時(shí)，需要很多次主存訪問(wèn)才能查找到需要的數(shù)據(jù)，尤其當(dāng)今正步入大數(shù)據(jù)時(shí)代，這種問(wèn)題更加顯著。針對(duì)以上問(wèn)題，DCST-樹(shù)在CST-樹(shù)的基礎(chǔ)上，對(duì)CST-樹(shù)中的結(jié)點(diǎn)進(jìn)行分區(qū)，并添加結(jié)點(diǎn)內(nèi)索引的方式，提高結(jié)點(diǎn)的扇出度，增大索引結(jié)點(diǎn)的容量，降低索引樹(shù)的高度。同時(shí)，對(duì)分區(qū)內(nèi)部存儲(chǔ)的關(guān)鍵字進(jìn)行壓縮，提高結(jié)點(diǎn)對(duì)緩存空間的利用率，增加緩存塊可以存儲(chǔ)的關(guān)鍵字?jǐn)?shù)量，提高緩存命中率。同時(shí)，對(duì)關(guān)鍵字進(jìn)行壓縮，可以進(jìn)一步降低樹(shù)的高度，減少查詢(xún)過(guò)程中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)查找時(shí)造成的緩存失配次數(shù)。

3.1 兩級(jí)結(jié)點(diǎn)布局

DCST-樹(shù)結(jié)點(diǎn)采用兩層結(jié)構(gòu)，是為了便于對(duì)CST-樹(shù)結(jié)點(diǎn)進(jìn)行分區(qū)和管理。通過(guò)對(duì)CST-樹(shù)結(jié)點(diǎn)進(jìn)行分區(qū)，可以將查找過(guò)程限制在特定的分區(qū)中，減少查找范圍。同時(shí)，對(duì)結(jié)點(diǎn)進(jìn)行分區(qū)可以提高結(jié)點(diǎn)的容量，增加結(jié)點(diǎn)的扇出度，降低索引樹(shù)的高度。

第一層結(jié)構(gòu)稱(chēng)之為結(jié)點(diǎn)內(nèi)頭部索引區(qū)，第二層結(jié)構(gòu)是由多個(gè)分區(qū)組成的區(qū)域。將原來(lái)T-樹(shù)中的結(jié)點(diǎn)分成幾個(gè)分區(qū)，每個(gè)分區(qū)都保存原來(lái)結(jié)點(diǎn)中部分關(guān)鍵字信息。這些分區(qū)稱(chēng)之為結(jié)點(diǎn)內(nèi)分區(qū)。結(jié)點(diǎn)內(nèi)分區(qū)之間以及結(jié)點(diǎn)內(nèi)分區(qū)中的關(guān)鍵字均是有序排列，保留了原有結(jié)點(diǎn)中關(guān)鍵字的順序。圖3展示了采用兩層結(jié)構(gòu)的DCST-樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)特征。

Fig.3 DCST-tree node structure圖3 DCST-樹(shù)結(jié)點(diǎn)結(jié)構(gòu)

結(jié)點(diǎn)內(nèi)頭部索引區(qū)存儲(chǔ)的是沒(méi)有壓縮的關(guān)鍵字〈H1,H2,…,H13＞，這些關(guān)鍵字有序排列，并且編號(hào)為k的結(jié)點(diǎn)內(nèi)分區(qū)中的任一關(guān)鍵字都小于Hk，編號(hào)為k+1的分區(qū)中的任一關(guān)鍵字都大于或者等于Hk。假設(shè)Keyk,i代表編號(hào)為k的結(jié)點(diǎn)內(nèi)分區(qū)中的任意關(guān)鍵字，Keyk+1,j代表編號(hào)為k+1的結(jié)點(diǎn)內(nèi)分區(qū)中的任意關(guān)鍵字，則有Keyk,i〈Hk≤Keyk+1,j。因此，結(jié)點(diǎn)內(nèi)頭部索引區(qū)如果包含n個(gè)索引項(xiàng)，則結(jié)點(diǎn)中最多包含n+1個(gè)結(jié)點(diǎn)內(nèi)分區(qū)。對(duì)結(jié)點(diǎn)內(nèi)部分區(qū)，是為了限制查找的范圍。在結(jié)點(diǎn)中查找關(guān)鍵字時(shí)，如果能夠限定在某一個(gè)分區(qū)中，就可以減少查找數(shù)量，提高查找效率，也可以減少緩存失效次數(shù)。如果不對(duì)結(jié)點(diǎn)進(jìn)行分區(qū)，當(dāng)結(jié)點(diǎn)大于一個(gè)緩存塊容量時(shí)，由于無(wú)法將結(jié)點(diǎn)一次全部裝入緩存中，在結(jié)點(diǎn)中查找就會(huì)造成比較多的緩存失配。位于結(jié)點(diǎn)頭部的索引區(qū)，能夠快速定位到需要查找的分區(qū)，加快查找速度。在訪問(wèn)結(jié)點(diǎn)時(shí)，首先訪問(wèn)結(jié)點(diǎn)頭部的索引區(qū)，定位到某一個(gè)索引項(xiàng)，再通過(guò)該索引項(xiàng)可以直接定位到與之對(duì)應(yīng)的結(jié)點(diǎn)內(nèi)部分區(qū)。圖3中虛線箭頭表示的指針指向與索引區(qū)中Hk對(duì)應(yīng)的結(jié)點(diǎn)內(nèi)分區(qū)，只是在DCST-樹(shù)中，這些結(jié)點(diǎn)內(nèi)部的指針不是直接存儲(chǔ)在結(jié)點(diǎn)中。分區(qū)地址是結(jié)合結(jié)點(diǎn)基地址，通過(guò)計(jì)算得到的。結(jié)點(diǎn)內(nèi)頭部索引區(qū)和結(jié)點(diǎn)內(nèi)分區(qū)的大小均設(shè)置為兩個(gè)緩存塊大小。因?yàn)樵诂F(xiàn)代計(jì)算機(jī)硬件中，高速緩存在從主存空間中讀取一個(gè)緩存塊大小的空間時(shí)，可以緊接著從相鄰的主存空間中再連續(xù)讀取一個(gè)緩存塊大小的空間。采用這種預(yù)取機(jī)制后，可以減少緩存失效次數(shù)，提高緩存命中率。頭部索引區(qū)和結(jié)點(diǎn)內(nèi)分區(qū)設(shè)置成兩個(gè)緩存塊大小后，可以通過(guò)一次主存訪問(wèn)將頭部索引區(qū)或者結(jié)點(diǎn)內(nèi)分區(qū)裝入緩存中。在結(jié)點(diǎn)中查找時(shí)，除了第一次訪問(wèn)頭部索引區(qū)或者結(jié)點(diǎn)內(nèi)分區(qū)會(huì)造成緩存失效并導(dǎo)致該區(qū)域被裝入緩存之外，在頭部索引區(qū)或者結(jié)點(diǎn)內(nèi)分區(qū)中進(jìn)行查找時(shí)，就不會(huì)造成緩存失效。

3.2 數(shù)據(jù)壓縮機(jī)制

對(duì)索引結(jié)點(diǎn)中的關(guān)鍵字進(jìn)行壓縮，可以減少索引結(jié)點(diǎn)對(duì)空間的消耗，提高索引結(jié)點(diǎn)對(duì)緩存空間的利用率。在緩存塊層次上對(duì)索引結(jié)點(diǎn)進(jìn)行壓縮，可以增大緩存塊中存儲(chǔ)的關(guān)鍵字?jǐn)?shù)量，提高查找過(guò)程中的緩存命中率，減少對(duì)主存的訪問(wèn)次數(shù)。在多數(shù)應(yīng)用場(chǎng)景中，索引中的關(guān)鍵字都是數(shù)值型數(shù)據(jù)，比如4 Byte整型數(shù)據(jù)。本文以數(shù)值型數(shù)據(jù)為基礎(chǔ)，討論如何對(duì)關(guān)鍵字進(jìn)行壓縮存儲(chǔ)。

如圖4所示，在一個(gè)緩存塊中存儲(chǔ)的關(guān)鍵字，其類(lèi)型是4 Byte的整型數(shù)據(jù)，緩存塊大小為64 Byte。假設(shè)一個(gè)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)為n(K[0,1,2,…,n-1])，如果存儲(chǔ)完整的關(guān)鍵字，緩存塊中最多存儲(chǔ)16個(gè)關(guān)鍵字。當(dāng)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)超過(guò)16時(shí)，在一個(gè)結(jié)點(diǎn)中遍歷，就會(huì)引起多次緩存失配，觸發(fā)主存訪問(wèn)。在對(duì)整型數(shù)據(jù)進(jìn)行壓縮的方法中，最常用的就是差分編碼（delta encoding）。對(duì)一個(gè)結(jié)點(diǎn)中的數(shù)據(jù)，除了最后一個(gè)數(shù)值最大的關(guān)鍵字外，其余的關(guān)鍵字并不是存儲(chǔ)本身完整的關(guān)鍵字，而是存儲(chǔ)剩余的關(guān)鍵字和最大關(guān)鍵字之間的差值。即對(duì)關(guān)鍵字序列K[0,1, 2,…,n-1]，除了K[n-1]之外，剩下的關(guān)鍵字K[x]都是存儲(chǔ)其與K[n-1]之間的差值D[x]。式（1）給出了D[x]的計(jì)算方式。

Fig.4 Keys in a cache line圖4 一個(gè)緩存塊中存儲(chǔ)的關(guān)鍵字

式（1）中，D[x]由結(jié)點(diǎn)中最大關(guān)鍵字?jǐn)?shù)值減去原始關(guān)鍵字?jǐn)?shù)值得到，因此D[x]≥0。在計(jì)算機(jī)系統(tǒng)中，一個(gè)字節(jié)可以表示的正整數(shù)范圍是[0,255]，即28-1。同時(shí)，一個(gè)整型數(shù)值，不論數(shù)值大小，在計(jì)算機(jī)中均占用4 Byte。因此當(dāng)數(shù)值范圍較小時(shí)，可以通過(guò)存儲(chǔ)字節(jié)形式，降低存儲(chǔ)數(shù)值消耗的存儲(chǔ)空間，提升緩存行的空間利用率。

D[x]可以用低于4 Byte的空間進(jìn)行存儲(chǔ)，D[x]所占用的最少儲(chǔ)存空間可以通過(guò)函數(shù)space(x)進(jìn)行計(jì)算。式（2）是space(x)的計(jì)算方式：

假設(shè)D[x]需要占用的最少字節(jié)數(shù)為n，則n應(yīng)滿足28×n≥D[x]，即，經(jīng)過(guò)變形可得式（2）。

由space(x)的計(jì)算公式可知，D[x]所占用的實(shí)際存儲(chǔ)空間可能為1 Byte、2 Byte或者4 Byte，由于D[x]的長(zhǎng)度是一個(gè)變量，沒(méi)有固定大小，為了方便對(duì)經(jīng)過(guò)編碼的關(guān)鍵字進(jìn)行查詢(xún)，需要在結(jié)點(diǎn)內(nèi)分區(qū)中的關(guān)鍵字序列前面加上索引信息。索引信息中記錄了不同長(zhǎng)度的D[x]的個(gè)數(shù)，分別表示為x、y、z。其中，x代表D[x]長(zhǎng)度為1 Byte的差值個(gè)數(shù)，y代表D[x]長(zhǎng)度為2 Byte的差值個(gè)數(shù)，z代表D[x]長(zhǎng)度為4 Byte的差值個(gè)數(shù)。如圖5所示，分區(qū)內(nèi)部的儲(chǔ)存結(jié)構(gòu)分為兩部分：第一部分是分區(qū)內(nèi)頭部，存儲(chǔ)關(guān)鍵字編碼信息。其中的3個(gè)字段分別記錄了不同長(zhǎng)度的差值個(gè)數(shù)，用來(lái)定位第二部分內(nèi)容區(qū)域中相應(yīng)的關(guān)鍵字。當(dāng)需要查詢(xún)時(shí)，首先計(jì)算查詢(xún)關(guān)鍵字?jǐn)?shù)值在本結(jié)點(diǎn)中的差值D[x]。然后查找頭部索引信息，通過(guò)累加小于D[x]的差值個(gè)數(shù)，就可以根據(jù)不同差值對(duì)應(yīng)的空間大小，計(jì)算出D[x]在當(dāng)前結(jié)點(diǎn)的偏移量，并從該偏移量開(kāi)始查找與D[x]相等的數(shù)值。

Fig.5 Adelta coded node key structure圖5 編碼后結(jié)點(diǎn)內(nèi)部關(guān)鍵字序列結(jié)構(gòu)

從圖5中可以看出，在內(nèi)容區(qū)域存儲(chǔ)的不再是關(guān)鍵字原始數(shù)值本身，而是其與最大關(guān)鍵字?jǐn)?shù)值之間的差值。如果不存儲(chǔ)關(guān)鍵字50，而是存儲(chǔ)它和最大值191之間的差值，并且兩者之間的差值可以用1 Byte的空間進(jìn)行表示。假設(shè)一個(gè)緩存塊大小為64 Byte，一個(gè)關(guān)鍵字為4 Byte，則緩存塊中最多存儲(chǔ)16個(gè)關(guān)鍵字。但是，在采用壓縮機(jī)制后，一個(gè)緩存塊最多可以存儲(chǔ)56個(gè)關(guān)鍵字。當(dāng)結(jié)點(diǎn)中的關(guān)鍵字之間的差值都在127之內(nèi)時(shí)，差值D[x]可以用一個(gè)字節(jié)表達(dá)，與存儲(chǔ)完整關(guān)鍵字相比，采用壓縮機(jī)制后，結(jié)點(diǎn)內(nèi)部可以存放3.8倍的數(shù)據(jù)。即存儲(chǔ)完整關(guān)鍵字比存儲(chǔ)編碼后的關(guān)鍵字要多消耗3.8倍的存儲(chǔ)空間，從而造成更多的緩存失配，降低了索引的性能表現(xiàn)。

3.3 復(fù)雜度分析

本節(jié)將對(duì)DCST-樹(shù)的插入、刪除、查找的時(shí)間復(fù)雜度進(jìn)行分析。假設(shè)一個(gè)數(shù)據(jù)結(jié)點(diǎn)中包含s個(gè)關(guān)鍵字，DSCT-樹(shù)結(jié)點(diǎn)組中包含m個(gè)結(jié)點(diǎn)。若存儲(chǔ)n個(gè)關(guān)鍵字，則DCST-樹(shù)的高度為height≥logmn/s。結(jié)點(diǎn)組是一個(gè)數(shù)組表示的二叉樹(shù)，樹(shù)的高度為lbm。查找操作需要從DCST-樹(shù)的根結(jié)點(diǎn)組遍歷到葉結(jié)點(diǎn)組，并在相應(yīng)的數(shù)據(jù)結(jié)點(diǎn)中查找關(guān)鍵字key。因此，查找操作需要花費(fèi)lbm×lbn/s定位到特定的數(shù)據(jù)結(jié)點(diǎn)，并花費(fèi)lbs用以在數(shù)據(jù)結(jié)點(diǎn)中搜索關(guān)鍵字。綜上，在DCST-樹(shù)中查找關(guān)鍵字的時(shí)間復(fù)雜度為O(lbm×logmn/s× lbs)=O(lbn)。

DCST-樹(shù)的插入操作首先需要定位到關(guān)鍵字要插入的數(shù)據(jù)結(jié)點(diǎn)。如果該數(shù)據(jù)結(jié)點(diǎn)已經(jīng)滿了，就需要將最小的關(guān)鍵字移除并插入到該結(jié)點(diǎn)的左子樹(shù)的數(shù)據(jù)結(jié)點(diǎn)中。在最壞情況下，定位到要插入的數(shù)據(jù)結(jié)點(diǎn)的時(shí)間為lbn，通過(guò)二分查找需耗時(shí)lbs從數(shù)據(jù)結(jié)點(diǎn)中刪除最小關(guān)鍵字，同時(shí)需要lbn時(shí)間將刪除的最小關(guān)鍵字插入到左子樹(shù)數(shù)據(jù)結(jié)點(diǎn)中。因此，整個(gè)插入操作的時(shí)間復(fù)雜度為O(lbn)+O(lbs)+O(lbn)=O(lbn)。

DCST-樹(shù)的刪除操作也需要定位到包含關(guān)鍵字的數(shù)據(jù)結(jié)點(diǎn)，然后才能在數(shù)據(jù)結(jié)點(diǎn)中搜索關(guān)鍵字并刪除該關(guān)鍵字。與插入操作類(lèi)似，DCST-樹(shù)的刪除操作的時(shí)間復(fù)雜度也為O(lbn)+O(lbs)+O(lbn)=O(lbn)。

4 算法

4.1 查找操作

DCST-樹(shù)的查找過(guò)程分為兩個(gè)部分：第一部分是在結(jié)點(diǎn)組中進(jìn)行查找。結(jié)點(diǎn)組是用數(shù)組表示的二叉樹(shù)，存儲(chǔ)的是原T-樹(shù)中每個(gè)結(jié)點(diǎn)的最大關(guān)鍵字。在一個(gè)結(jié)點(diǎn)組中查找時(shí)，并不會(huì)造成緩存失配，因?yàn)榻Y(jié)點(diǎn)組的大小設(shè)置成一個(gè)緩存塊的大小。查找到結(jié)點(diǎn)組中某一個(gè)關(guān)鍵字時(shí)，就利用該關(guān)鍵字定位到相應(yīng)的數(shù)據(jù)結(jié)點(diǎn)。數(shù)據(jù)結(jié)點(diǎn)中存儲(chǔ)原來(lái)T-樹(shù)中相對(duì)應(yīng)結(jié)點(diǎn)的全部關(guān)鍵字，然后再在數(shù)據(jù)結(jié)點(diǎn)中進(jìn)行搜索，直至找到查找的關(guān)鍵字或者返回失敗，即沒(méi)有找到要查找的關(guān)鍵字。遍歷結(jié)點(diǎn)組的算法如算法1所示。

算法1結(jié)點(diǎn)組查找算法search(key,tree)

結(jié)點(diǎn)組是用數(shù)組表示的二叉樹(shù)，里面存放的是原T-樹(shù)結(jié)點(diǎn)中的最大關(guān)鍵字?jǐn)?shù)值。結(jié)點(diǎn)組中的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)數(shù)據(jù)結(jié)點(diǎn)，數(shù)據(jù)結(jié)點(diǎn)中存放著編碼之后的關(guān)鍵字序列，相當(dāng)于T-樹(shù)的一個(gè)結(jié)點(diǎn)。

算法1第1行首先在第一個(gè)結(jié)點(diǎn)組中查找，通過(guò)將查找的關(guān)鍵字key與根結(jié)點(diǎn)組中的關(guān)鍵字K比較，找到相應(yīng)的葉結(jié)點(diǎn)組，并最終定位到數(shù)據(jù)結(jié)點(diǎn)。算法1第3行到第7行表示的就是遍歷結(jié)點(diǎn)組并最終定位到相應(yīng)葉結(jié)點(diǎn)組的過(guò)程。若結(jié)點(diǎn)組中的關(guān)鍵字K大于查找關(guān)鍵字key，就繼續(xù)遍歷其左子樹(shù)，并將該結(jié)點(diǎn)進(jìn)行標(biāo)記。如果K小于查找關(guān)鍵字key，則繼續(xù)遍歷該結(jié)點(diǎn)的右子樹(shù)，并不做標(biāo)記。遞歸查找結(jié)點(diǎn)組，直至遍歷至葉結(jié)點(diǎn)組。當(dāng)葉結(jié)點(diǎn)組遍歷完成后，若標(biāo)記結(jié)點(diǎn)不為空，則根據(jù)葉結(jié)點(diǎn)組中標(biāo)記結(jié)點(diǎn)定位到相應(yīng)的數(shù)據(jù)結(jié)點(diǎn)。

算法1第9行表示在結(jié)點(diǎn)組中查找完成，并通過(guò)最后一次比較得到的關(guān)鍵字定位到相應(yīng)的數(shù)據(jù)結(jié)點(diǎn)。接下來(lái)開(kāi)始在數(shù)據(jù)結(jié)點(diǎn)中查找關(guān)鍵字。由于數(shù)據(jù)結(jié)點(diǎn)采用兩層結(jié)構(gòu)，并且對(duì)結(jié)點(diǎn)進(jìn)行了壓縮，在數(shù)據(jù)結(jié)點(diǎn)中的查找過(guò)程和CST-樹(shù)不一樣，具體算法如算法2所示。

算法2數(shù)據(jù)結(jié)點(diǎn)關(guān)鍵字查詢(xún)算法

算法2第1、第2行主要是為了定位到包含關(guān)鍵字key的結(jié)點(diǎn)內(nèi)分區(qū)。第1行表示在數(shù)據(jù)結(jié)點(diǎn)頭部索引區(qū)中查找，找到索引項(xiàng)Hk(Hk-1〈key〈Hk)。第2行表示通過(guò)索引Hk計(jì)算包含關(guān)鍵字key的結(jié)點(diǎn)內(nèi)分區(qū)的位置。第3行計(jì)算關(guān)鍵字key與結(jié)點(diǎn)中最大關(guān)鍵字之間的差值de。如果de小于0，則表明查找的關(guān)鍵字大于數(shù)據(jù)結(jié)點(diǎn)中最大鍵值，查找的鍵值不在數(shù)據(jù)結(jié)點(diǎn)中，不需要再遍歷結(jié)點(diǎn)，直接返回。若key小于最大鍵值，則首先計(jì)算差值de所占用的最小字節(jié)數(shù)space(de)，同時(shí)檢查數(shù)據(jù)結(jié)點(diǎn)頭部中的x、y、z字段。如果space對(duì)應(yīng)的字段中記錄的數(shù)目不等于0，表明數(shù)據(jù)結(jié)點(diǎn)中有和de占用同樣大小字節(jié)數(shù)的差值，通過(guò)頭部索引信息可以計(jì)算出de在結(jié)點(diǎn)中的偏移量，并定位到相應(yīng)的區(qū)域進(jìn)行查找，如果找到，返回關(guān)鍵字記錄，否則返回失敗。如果space對(duì)應(yīng)的字段，比如x，其值為0，則表明占用space大小的差值不存在，直接返回查找失敗。

4.2 插入算法

插入操作與CST-樹(shù)類(lèi)似，數(shù)據(jù)結(jié)點(diǎn)中當(dāng)最大關(guān)鍵字被取代時(shí)，需要對(duì)結(jié)點(diǎn)進(jìn)行重構(gòu)。對(duì)于給定的關(guān)鍵字key，首先需要定位到要插入的數(shù)據(jù)結(jié)點(diǎn)，然后將關(guān)鍵字key插入到該數(shù)據(jù)結(jié)點(diǎn)中。如果該數(shù)據(jù)結(jié)點(diǎn)沒(méi)有滿，則直接插入關(guān)鍵字。如果數(shù)據(jù)結(jié)點(diǎn)空間已滿，則需要?jiǎng)h除最小的關(guān)鍵字，然后將key插入到數(shù)據(jù)結(jié)點(diǎn)，并將刪除的最小關(guān)鍵字插入到樹(shù)中。具體過(guò)程如算法3所示。

算法3插入算法insert(key,tree)

算法3第1行表示在結(jié)點(diǎn)組中查找關(guān)鍵字key，在最終的葉結(jié)點(diǎn)組中查找完成后，根據(jù)標(biāo)記可以定位到數(shù)據(jù)結(jié)點(diǎn)。查找過(guò)程的詳細(xì)步驟如算法1所示。算法3第3行首先根據(jù)數(shù)據(jù)結(jié)點(diǎn)的最大關(guān)鍵字?jǐn)?shù)值計(jì)算出key對(duì)應(yīng)的差值D[x]，并根據(jù)D[x]定位到相應(yīng)的結(jié)點(diǎn)位置，然后插入數(shù)據(jù)。

算法3第11行表示將刪除的最小關(guān)鍵字插入到子樹(shù)中。如果數(shù)據(jù)結(jié)點(diǎn)沒(méi)有對(duì)應(yīng)的左子樹(shù)，就需要添加一個(gè)新的數(shù)據(jù)結(jié)點(diǎn)，然后將關(guān)鍵字插入其中。當(dāng)創(chuàng)建新的數(shù)據(jù)結(jié)點(diǎn)時(shí)就必須要?jiǎng)?chuàng)建一個(gè)新的結(jié)點(diǎn)組。而這樣的操作可能會(huì)造成DCST-樹(shù)的不平衡，此時(shí)就需要平衡操作來(lái)保證樹(shù)左右子樹(shù)的高度相對(duì)平衡。

5 實(shí)驗(yàn)結(jié)果與分析

本章主要對(duì)所提方案進(jìn)行驗(yàn)證和評(píng)估，測(cè)試DCST-樹(shù)和當(dāng)前主流緩存感知型索引結(jié)構(gòu)之間的性能對(duì)比。首先介紹實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)設(shè)置，然后根據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

5.1 實(shí)驗(yàn)環(huán)境設(shè)置

所有實(shí)驗(yàn)都運(yùn)行在同一臺(tái)機(jī)器上，處理器是Intel?CoreTMi3-2120 3.3 GHz，主存為4 GB DDR3，裝載Ubuntu 12.04操作系統(tǒng)，該機(jī)器擁有〈256 KB,64 B, 8〉（緩存容量、緩存塊大小、路數(shù)）L2緩存。

實(shí)驗(yàn)中，關(guān)鍵字和指針均設(shè)計(jì)為4 Byte無(wú)符號(hào)整型數(shù)據(jù)。索引包含的信息數(shù)據(jù)來(lái)源于某市采集的交通數(shù)據(jù)。

5.2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)首先測(cè)試了DCST-樹(shù)的查找性能。使用了不同數(shù)量的鍵數(shù)分別進(jìn)行了測(cè)試，插入的鍵值是按照上文描述的交通數(shù)據(jù)中隨機(jī)產(chǎn)生的整型數(shù)據(jù)。實(shí)驗(yàn)將DCST-樹(shù)與CST-樹(shù)和文獻(xiàn)[16]提出的ART-樹(shù)進(jìn)行對(duì)比，測(cè)試它們?cè)诓煌I數(shù)下分別進(jìn)行200 000次關(guān)鍵字查找所消耗的時(shí)間，每次查找的關(guān)鍵字都是從預(yù)先生產(chǎn)的關(guān)鍵字里面隨機(jī)挑選的。如圖6所示，在查找性能上，DCST-樹(shù)的查找性能表現(xiàn)最好，比CST-樹(shù)和ART-樹(shù)分別提升23%和11%。隨著鍵數(shù)的增大，DCST-樹(shù)的優(yōu)勢(shì)更加顯著。

Fig.6 Performance comparison of index search圖6 索引查找性能對(duì)比

隨后，測(cè)試了在隨機(jī)查找關(guān)鍵字過(guò)程中造成的緩存失配次數(shù)。如圖7所示，DCST-樹(shù)在查找過(guò)程中造成的緩存失配次數(shù)是最少的，并且隨著記錄的增加，其優(yōu)勢(shì)也越來(lái)越明顯。DCST-樹(shù)對(duì)結(jié)點(diǎn)中的關(guān)鍵字采用了壓縮機(jī)制，相同存儲(chǔ)空間可以存儲(chǔ)更多的關(guān)鍵字，如前文所述，在最好的情況下可以多存儲(chǔ)3倍的數(shù)據(jù)，從而顯著提高對(duì)緩存空間的利用率。同時(shí)，單個(gè)結(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)量的增大，也降低了索引樹(shù)的高度，使得遍歷索引結(jié)點(diǎn)引起的緩存失配次數(shù)減少，從而提升了索引的查找性能。

Fig.7 Comparison of cache misses圖7 緩存失配次數(shù)對(duì)比

圖8 是壓縮后的索引結(jié)構(gòu)和沒(méi)有壓縮的索引結(jié)構(gòu)之間空間消耗的對(duì)比。本次實(shí)驗(yàn)分別測(cè)試了不同的鍵數(shù)下，索引結(jié)構(gòu)的空間消耗。從圖中可以看出，DCST-樹(shù)的空間利用率是最高的。與CST-樹(shù)、ART-樹(shù)相比，DCST-樹(shù)對(duì)存儲(chǔ)空間的消耗分別降低了30%和26%。

Fig.8 Comparison of space consumption of index圖8 索引空間消耗對(duì)比

圖9 是各個(gè)索引結(jié)構(gòu)插入操作的實(shí)驗(yàn)對(duì)比。在本次實(shí)驗(yàn)中，預(yù)先建立包含100萬(wàn)關(guān)鍵字的索引樹(shù)，然后對(duì)其分別插入不同數(shù)量的鍵值，并計(jì)算時(shí)間。從圖中可以看出，CST-樹(shù)和DCST-樹(shù)的插入效率低于ART-樹(shù)，是因?yàn)檫@兩種樹(shù)在插入的時(shí)候需要保持樹(shù)的平衡而要增加額外的旋轉(zhuǎn)操作。但DCST-樹(shù)依然快于CST-樹(shù)，并且隨著鍵數(shù)的增加，DCST-樹(shù)與ART-樹(shù)之間差距逐漸變小。

Fig.9 Performance comparison of index insertion圖9 索引插入性能對(duì)比

6 結(jié)束語(yǔ)

為了提高主存索引結(jié)構(gòu)的緩存感知能力，本文在CST-樹(shù)的基礎(chǔ)上，通過(guò)調(diào)整結(jié)點(diǎn)結(jié)構(gòu)，改進(jìn)關(guān)鍵字存儲(chǔ)方式，提出了DCST-樹(shù)。DCST-樹(shù)對(duì)結(jié)點(diǎn)進(jìn)行分區(qū)，把結(jié)點(diǎn)劃分成連續(xù)的存儲(chǔ)區(qū)間，并建立結(jié)點(diǎn)內(nèi)頭部索引，以便快速定位包含查找關(guān)鍵字的特定分區(qū)。通過(guò)對(duì)結(jié)點(diǎn)劃分分區(qū)，增加了結(jié)點(diǎn)容量，提高了結(jié)點(diǎn)的扇出度，降低了樹(shù)的高度。同時(shí)，對(duì)于分區(qū)內(nèi)的關(guān)鍵字進(jìn)行壓縮，可以減少數(shù)據(jù)消耗的存儲(chǔ)空間，提高結(jié)點(diǎn)對(duì)緩存空間的利用率，減少失配次數(shù)。在實(shí)驗(yàn)驗(yàn)證階段，從索引查詢(xún)、更新等性能方面進(jìn)行測(cè)試，并統(tǒng)計(jì)索引查詢(xún)過(guò)程中造成的緩存失配次數(shù)以及索引對(duì)儲(chǔ)存空間的消耗。實(shí)驗(yàn)結(jié)果表明，本文提出的DCST-樹(shù)索引結(jié)構(gòu)，可以高效地利用儲(chǔ)存空間，提高了索引結(jié)構(gòu)的緩存感知能力，提升了索引的查詢(xún)處理能力。

隨著信息化的發(fā)展，各個(gè)領(lǐng)域產(chǎn)生的數(shù)據(jù)與日俱增，索引結(jié)構(gòu)的不斷擴(kuò)展，加劇了對(duì)儲(chǔ)存空間的消耗。在保證查詢(xún)效率的同時(shí)，降低空間消耗依然有著迫切需求。在未來(lái)的工作中，將繼續(xù)研究其他的壓縮策略，進(jìn)一步降低對(duì)存儲(chǔ)空間的消耗。同時(shí)，研究基于字符串的壓縮機(jī)制，將DCST-樹(shù)應(yīng)用在更廣泛的場(chǎng)景中。

[1]Bernstein P,Brodie M,Ceri S,et al.The asilomar report on database research[J].ACM SIGMOD Record,1998,27(4): 74-80.

[2]Ailamaki A,DeWitt D J,Hill M D,et al.DBMSs on a modern processor:where does time go?[C]//Proceedings of the 25th International Conference on Very Large Data Bases, Edinburgh,UK,Sep 7-10,1999.San Francisco,USA:Morgan Kaufmann Publishers Inc,1999:266-277.

[3]Silva J,Sklyarov V,Skliarova I.Comparison of on-chip communications in Zynq-7000 all programmable systemson-chip[J].Embedded Systems Letters,2015,7(1):31-34.

[4]Shi Yanan,Su Wenjie.Research and implementation of an inverted index cache replacement algorithm[J].Computer Technology and Development,2015,25(5):60-63.

[5]Kocberber O,Grot B,Picorel J,et al.Meet the walkers: accelerating index traversals for in-memory databases[C]// Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture,Davis,USA,Dec 7-11, 2013.New York:ACM,2013:468-479.

[6]Ding Chen,Li Pengcheng.Cache-conscious memory management[C]//Proceedings of the 2014 ACM SIGPLAN Workshop on Memory System Performance and Correctness,Edinburgh,UK,Jun 9-11,2014.NewYork:ACM,2014.

[7]Yang Tianming,Feng Dan,Chou Wenkuang,et al.A study on disk index design for large scale de-duplication storage systems[J].International Journal of Computational Science and Engineering,2015,10(1/2):171-180.

[8]Chen S,Gibbons P B,Mowry T C.Improving index performance through prefetching[J].ACM SIGMOD Record,2002, 30(2):235-246.

[9]Yang Zhaohui,Wang Lisong.Prefetching T-tree:a cacheoptimized main memory database index structure[J].Computer Science,2011,38(10):161-165.

[10]Zhou J,Cieslewicz J,Ross K A,et al.Improving database performance on simultaneous multithreading processors [C]//Proceedings of the 31st International Conference on Very Large Data Bases,Trondheim,Norway,Aug 30-Sep 2, 2005.New York:ACM,2005:49-60.

[11]Leis V,Kemper A,Neumann T.The adaptive radix tree: ARTful indexing for main-memory databases[C]//Proceedings of the 29th IEEE International Conference on Data Engineering, Brisbane,Australia,Apr 8-12,2013.Washington:IEEE Computer Society,2013:38-49.

[12]Binna R,Pacher D,Meindl T,et al.The DCB-tree:a spaceefficient delta coded cache conscious B-tree[C]//LNCS 8921: Proceedings of the 1st and 2nd International Workshops on In Memory Data Management and Analysis,IMDM 2013, Riva del Garda,Italy,Aug 26,2013,IMDM 2014,Hongzhou,China,Sep 1,2014.Switzerland:Springer International Publishing,2015:126-138.

[13]Rogers T G,O'Connor M,Aamodt T M.Cache-conscious thread scheduling for massively multithreaded processors[J].IEEE Micro,2013,33(3):78-85.

[14]Xi Fang,Mishima T,Yokota H.CARIC-DA:core affinity with a range index for cache-conscious data access in a multicore environment[C]//LNCS 8421:Proceedings of the 19th International Conference on Database Systems for Advanced Applications,Bali,Indonesia,Apr 21-24,2014.Switzerland: Springer International Publishing,2014:282-296.

[15]Kim H,Koltsidas I,Ioannou N,et al.Flash-conscious cache population for enterprise database workloads[C]//Proceedings of the 2014 International Workshop on Accelerating Data Management Systems Using Modern Processor and StorageArchitectures,Hangzhou,China,Sep 1,2014.

[16]Kwon S J.A cache-based flash translation layer for TLC-based multimedia storage devices[J].ACM Transactions on Embedded Computing Systems,2016,15(1):11.

[17]Lee I,Shim J,Lee S,et al.CST-trees:cache sensitive T-trees [C]//LNCS 4443:Advances in Databases:Concepts,Systems and Applications,Proceedings of the 12th International Conference on Database Systems for Advanced Applications,Bangkok,Thailand,Apr 9-12,2007.Berlin,Heidelberg:Springer,2007:398-409.

[18]Rao J,Ross K A.Making B+-trees cache conscious in main memory[J].ACM SIGMOD Record,2000,29(2):475-486.

[19]You Xiaorong,Cao Sheng.Storage research of small files in massive education resource[J].Computer Science,2015, 42(10):76-80.

[20]Wang Guoqing,Huang Tao,Liu Jiang,et al.A new cache policy based on sojourn time in content-centric networking [J].Chinese Journal of Computers,2015,38(3):472-482.

[21]Wu Qiuping,Liu Bo,Lin Weiwei.Adaptive replacement cache mechanism for fault tolerance in cloud storage[J]. Computer Science,2015,42(S1):332-336.

附中文參考文獻(xiàn)：

[4]時(shí)亞南,束文杰.一種倒排索引緩存替代算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(5):60-63.

[9]楊朝輝,王立松.pT-樹(shù):高速緩存優(yōu)化的主存數(shù)據(jù)庫(kù)索引結(jié)構(gòu)[J].計(jì)算機(jī)科學(xué),2011,38(10):161-165.

[19]游小容,曹晟.海量教育資源中小文件的存儲(chǔ)研究[J].計(jì)算機(jī)科學(xué),2015,42(10):76-80.

[20]王國(guó)卿,黃韜,劉江,等.一種基于逗留時(shí)間的新型內(nèi)容中心網(wǎng)絡(luò)緩存策略[J].計(jì)算機(jī)學(xué)報(bào),2015,38(3):472-482.

[21]伍秋平,劉波,林偉偉.一種面向云存儲(chǔ)數(shù)據(jù)容錯(cuò)的ARC緩存淘汰機(jī)制[J].計(jì)算機(jī)科學(xué),2015,42(S1):332-336.

SHI Taiqi was born in 1992.He is an M.S.candidate at Nanjing University of Aeronautics and Astronautics.His research interests include index in database,cache conscious and main memory database,etc.

史太齊（1992—），男，安徽淮南人，南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)查詢(xún)，緩存感知，主存數(shù)據(jù)庫(kù)等。

LIU Liang was born in 1985.He is a lecturer at Nanjing University of Aeronautics and Astronautics.His research interests include sensor network database and distributed database,etc.

劉亮（1985—），男，江西景德鎮(zhèn)人，南京航空航天大學(xué)講師、博士后，主要研究領(lǐng)域?yàn)閭鞲衅骶W(wǎng)絡(luò)數(shù)據(jù)庫(kù)，分布式數(shù)據(jù)庫(kù)等。

QIN Xiaolin was born in 1953.He is a professor and Ph.D.supervisor at Nanjing University of Aeronautics and Astronautics,and the senior member of CCF.His research interests include spatial and spatio-temporal databases, data management and security in distributed environment,etc.

秦小麟（1953—），男，江蘇南京人，南京航空航天大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榭臻g與時(shí)空數(shù)據(jù)庫(kù)，分布式數(shù)據(jù)管理與安全等。

DCST:Main Memory Space-Efficient Delta Coded Cache Conscious T-tree*

SHI Taiqi+,LIU Liang,QIN Xiaolin
College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016, China
+Corresponding author:E-mail:stqhappy@qq.com

Existing main-memory index structures use pointer elimination and prefetching mechanism to improve the cache consciousness of index structure and reduce the number of cache invalidation,but do not make efficient use of main-memory space and CPU performance.To make index structure utilize memory and CPU much better, this paper proposes DCST-tree.DCST-tree implements data compression to use memory and cache space more effectively.This can reduce the number of swap between memory and cache,and improve the rate of cache hit eventually. Meanwhile,node is partitioned into buckets to increase node size and improve the fan-out degree of node,such that the height of index tree can be reduced.The experimental results show that the proposed index structure has higher cache consciousness and space utilization,compared with existing index structures.

compression;main-memory index;cache consciousness

10.3778/j.issn.1673-9418.1603029

A

TP311

*The National Natural Science Foundation of China under Grant Nos.61373015,61300052,41301047(國(guó)家自然科學(xué)基金);the PriorityAcademic Development Program of Jiangsu Higher Education Institutions(江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目).

Received 2016-03,Accepted 2016-05.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-05-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160519.1513.004.html

SHI Taiqi,LIU Liang,QIN Xiaolin.DCST:main memory space-efficient delta coded cache conscious T-tree. Journal of Frontiers of Computer Science and Technology,2017,11(2)：221-230.