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

史太齊，劉 亮，秦小麟

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

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

史太齊+，劉 亮，秦小麟

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

2.1 緩存

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

2.2 緩存感知型索引

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

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

Fig.2 CST-tree圖2 CST-樹

3 DCST-樹

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

3.1 兩級結(jié)點布局

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 復(fù)雜度分析

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

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

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

4 算法

4.1 查找操作

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

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

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

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

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

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

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

4.2 插入算法

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

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

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

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

5 實驗結(jié)果與分析

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

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

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

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

5.2 實驗結(jié)果

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

附中文參考文獻：

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

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

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

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

[21]伍秋平,劉波,林偉偉.一種面向云存儲數(shù)據(jù)容錯的ARC緩存淘汰機制[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é)計算機科學(xué)與技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)庫查詢，緩存感知，主存數(shù)據(jù)庫等。

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)域為傳感器網(wǎng)絡(luò)數(shù)據(jù)庫，分布式數(shù)據(jù)庫等。

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高級會員，主要研究領(lǐng)域為空間與時空數(shù)據(jù)庫，分布式數(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(國家自然科學(xué)基金);the PriorityAcademic Development Program of Jiangsu Higher Education Institutions(江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目).

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.