劉勇 奚建清 黃東平 賈連印 苗德成

(華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006)

在數(shù)據(jù)庫(kù)系統(tǒng)中，索引是加快檢索表中數(shù)據(jù)的一種直接有效的方法.由于索引項(xiàng)的空間比記錄小，因此減少查詢(xún)讀取的數(shù)據(jù)量，可以提高查詢(xún)效率.自?xún)?nèi)存數(shù)據(jù)庫(kù)的概念被提出以來(lái)［1］，為適應(yīng)內(nèi)存數(shù)據(jù)庫(kù)及硬件環(huán)境的要求，人們除了繼續(xù)引用一些傳統(tǒng)的索引到內(nèi)存數(shù)據(jù)庫(kù)中之外，還提出了多種新的內(nèi)存索引技術(shù)和改進(jìn)方案.Rao 等［2］在傳統(tǒng)B+-樹(shù)索引的基礎(chǔ)上，提出了基于緩存敏感技術(shù)的CSS-樹(shù)索引，具有比傳統(tǒng)內(nèi)存數(shù)據(jù)庫(kù)索引(如T-樹(shù)和B+-樹(shù))查找速度更快且空間占用率更小的性能.針對(duì)CSS-樹(shù)無(wú)法解決索引數(shù)據(jù)的有效更新問(wèn)題，Rao 等［3］提出了CSB+-樹(shù)索引，它既具有與CSS-樹(shù)相似的緩存性能，又具有B+-樹(shù)的更新操作性能.

CSB+-樹(shù)的結(jié)構(gòu)與傳統(tǒng)B+-樹(shù)的結(jié)構(gòu)類(lèi)似，區(qū)別在于:CSB+-樹(shù)的每個(gè)父節(jié)點(diǎn)只保留指向第一個(gè)孩子節(jié)點(diǎn)的指針，其他孩子節(jié)點(diǎn)的地址可通過(guò)計(jì)算與第一個(gè)孩子節(jié)點(diǎn)的偏移量得出;在CSB+-樹(shù)中，一個(gè)節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)按序存儲(chǔ)并構(gòu)成一個(gè)邏輯上的節(jié)點(diǎn)組.由于只保留一個(gè)指向孩子節(jié)點(diǎn)的指針，對(duì)于同樣大小的內(nèi)部節(jié)點(diǎn)，CSB+-樹(shù)的扇出率比B+-樹(shù)提高近1 倍，因此在一個(gè)緩存行里可存放更多的索引鍵，從而既提高了緩存的命中率，又節(jié)省了存儲(chǔ)空間.

目前，基于圖形處理器(GPU)的索引技術(shù)已有相關(guān)的研究，但它們?cè)谒饕牟⑿袆?chuàng)建和可操作性等方面存在著一定的不足.Fix 等［4］提出了基于GPU 的B+-樹(shù)并行遍歷算法，但因B+樹(shù)是直接從CPU 上拷入GPU 端而未能利用GPU 的并行處理能力;Christensen 等［5］提出了優(yōu)化的CSS-樹(shù)多線(xiàn)程并行構(gòu)建算法，但僅實(shí)現(xiàn)了單個(gè)節(jié)點(diǎn)內(nèi)部鍵值的并行創(chuàng)建，而且在其基于線(xiàn)程塊查詢(xún)的優(yōu)化算法中，也未考慮線(xiàn)程塊出現(xiàn)線(xiàn)程分支的情形，從而影響程序的性能且若采用線(xiàn)程同步命令時(shí)還會(huì)引起程序出錯(cuò)等問(wèn)題;Kaczmarski［6］根據(jù)傳統(tǒng)B+樹(shù)的批量裝載算法，提出了一種基于樹(shù)層的自底向上并行構(gòu)建算法，該算法的并行度較文獻(xiàn)［5］中算法有所提高，然而其思想是建立在傳統(tǒng)CPU 平臺(tái)上，因此未能充分利用GPU 的并行計(jì)算資源.Liu 等［7］在GPU 平臺(tái)上實(shí)現(xiàn)了多維線(xiàn)性動(dòng)態(tài)哈希表的記錄批量插入，大大提高了索引的操作性能，但須借助GPU 的原子鎖函數(shù)才能完成并行處理，因此并行度不高.Kim 等［8］在CPU 和GPU 平臺(tái)上實(shí)現(xiàn)了完全二叉樹(shù)的快速構(gòu)建和遍歷算法，盡管創(chuàng)建索引樹(shù)的速度極快，但該算法比較簡(jiǎn)單，不適用于解決復(fù)雜的問(wèn)題.

近年來(lái)，GPU 的通用計(jì)算(GPGPU)［9］已經(jīng)在科學(xué)計(jì)算和數(shù)據(jù)庫(kù)技術(shù)等領(lǐng)域中得到廣泛的應(yīng)用.為此，文中在GPU 平臺(tái)上研究緩存敏感樹(shù)索引CSB+-樹(shù)的并行構(gòu)建和查詢(xún)的操作性能.

1 基于GPU 的CSB+-樹(shù)并行方案

1.1 數(shù)據(jù)結(jié)構(gòu)

目前NVIDIA CUDA 編程模型［10］尚未支持在GPU 上動(dòng)態(tài)分配顯存空間，而傳統(tǒng)CSB+-樹(shù)的存儲(chǔ)結(jié)構(gòu)可支持索引數(shù)據(jù)的動(dòng)態(tài)增減.為此，文中采用結(jié)構(gòu)體數(shù)組預(yù)分配的方式存儲(chǔ)CSB+-樹(shù)數(shù)據(jù)，數(shù)組的每個(gè)元素表示CSB+-樹(shù)的一個(gè)節(jié)點(diǎn)，并通過(guò)兩層數(shù)據(jù)結(jié)構(gòu)［11］實(shí)現(xiàn)結(jié)構(gòu)體數(shù)組的動(dòng)態(tài)伸縮，其結(jié)構(gòu)如圖1所示.

圖1 動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)Fig.1 Data structure of dynamic array

在此結(jié)構(gòu)中，將存儲(chǔ)CSB+-樹(shù)數(shù)據(jù)的動(dòng)態(tài)數(shù)組劃分成若干大小固定的數(shù)據(jù)段，每個(gè)數(shù)據(jù)段的首地址保存在目錄數(shù)組中;當(dāng)數(shù)組需要擴(kuò)大時(shí)，則根據(jù)所需的數(shù)據(jù)量增加新的數(shù)據(jù)段和相應(yīng)數(shù)量的目錄數(shù)組存儲(chǔ)空間;當(dāng)數(shù)組需要收縮時(shí)，則釋放多余的數(shù)據(jù)段和對(duì)應(yīng)的目錄數(shù)組存儲(chǔ)空間.假定每個(gè)數(shù)據(jù)段大小為S，則動(dòng)態(tài)數(shù)組第i 個(gè)元素的段地址(sa)和段內(nèi)地址(sia)為

它在數(shù)組的地址為directory［sa］.element［sia］.

由此可知，基于GPU 平臺(tái)的CSB+-樹(shù)的數(shù)據(jù)結(jié)構(gòu)由葉子節(jié)點(diǎn)結(jié)構(gòu)、內(nèi)部節(jié)點(diǎn)結(jié)構(gòu)和它們相應(yīng)的段結(jié)構(gòu)構(gòu)成，其程序代碼如下:

在CSBplusStruct 結(jié)構(gòu)中，leaf_dir 和inter_dir 分別為存儲(chǔ)葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)數(shù)據(jù)的目錄數(shù)組，leaf_dirlen和inter_dirlen 分別為當(dāng)前葉子目錄數(shù)組和內(nèi)部節(jié)點(diǎn)目錄數(shù)組的長(zhǎng)度，leaf_SP 和inter_SP 分別指向各自目錄數(shù)組中下一個(gè)待分配的0 地址.葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)采用不同的結(jié)構(gòu)，可減少不必要的指針空間浪費(fèi).

1.2 CSB +-樹(shù)的并行構(gòu)建算法

傳統(tǒng)B+-樹(shù)的批量裝載算法是將一組已排序的記錄從距根節(jié)點(diǎn)最右的路徑起逐個(gè)插入直至結(jié)束.然而，如果按此算法構(gòu)建CSB+-樹(shù)，由于同一個(gè)節(jié)點(diǎn)組內(nèi)的節(jié)點(diǎn)不是按順序建立，因此需要重新分配內(nèi)存以構(gòu)建節(jié)點(diǎn)組，其操作代價(jià)極大.為此，Rao 等［2］提出了一種效率更高的CSB+-樹(shù)批量裝載算法，該算法可以自底向上、一層層地構(gòu)建CSB+-樹(shù)，具體步驟如下:

(1)對(duì)待插入的索引記錄按關(guān)鍵字排序;

(2)根據(jù)記錄數(shù)分配CSB+-樹(shù)的葉子節(jié)點(diǎn)空間，并將記錄依次按序插入葉子節(jié)點(diǎn)內(nèi)，在樹(shù)的底層建立葉子層;

(3)根據(jù)CSB+-樹(shù)的階和下層的節(jié)點(diǎn)數(shù)計(jì)算上一層所需的內(nèi)部節(jié)點(diǎn)數(shù)，并為上層節(jié)點(diǎn)分配連續(xù)的存儲(chǔ)空間，節(jié)點(diǎn)內(nèi)的鍵值為其對(duì)應(yīng)下一層節(jié)點(diǎn)的最大鍵值，同時(shí)設(shè)置每個(gè)節(jié)點(diǎn)的第一個(gè)孩子指針;

(4)返回步驟(3)直至上一層的節(jié)點(diǎn)數(shù)為1，即該節(jié)點(diǎn)為CSB+-樹(shù)的根節(jié)點(diǎn).

由于在整個(gè)構(gòu)建過(guò)程，同一層的所有節(jié)點(diǎn)地址都是連續(xù)分配的，因此無(wú)需進(jìn)行任何額外的數(shù)據(jù)復(fù)制操作即可構(gòu)成一個(gè)節(jié)點(diǎn)組.由此可見(jiàn)，CSB+-樹(shù)的構(gòu)建包括葉子節(jié)點(diǎn)的構(gòu)建和內(nèi)部節(jié)點(diǎn)的構(gòu)建.

1.2.1 葉子節(jié)點(diǎn)的并行構(gòu)建算法

為保證CSB+-樹(shù)的存儲(chǔ)利用率，在初次建樹(shù)時(shí)可通過(guò)設(shè)置節(jié)點(diǎn)的填充因子α 來(lái)控制每個(gè)節(jié)點(diǎn)的記錄數(shù).假設(shè)M 是每個(gè)節(jié)點(diǎn)的記錄容量，則構(gòu)建N個(gè)數(shù)據(jù)的CSB+-樹(shù)所需分配的葉子節(jié)點(diǎn)數(shù)為

因此，可根據(jù)X 在GPU 上為葉子節(jié)點(diǎn)分配動(dòng)態(tài)數(shù)組空間，然后將已排好序的數(shù)據(jù)從主機(jī)端傳輸至設(shè)備端，再將記錄并行插入到CSB+-樹(shù)的葉子節(jié)點(diǎn)中.由于線(xiàn)程的編號(hào)順序與葉子節(jié)點(diǎn)的編號(hào)順序相對(duì)應(yīng)，因此創(chuàng)建的CSB+-樹(shù)的相鄰葉子節(jié)點(diǎn)要按序存儲(chǔ).

1.2.2 內(nèi)部節(jié)點(diǎn)的并行構(gòu)建算法

基于樹(shù)層的B+-樹(shù)內(nèi)部節(jié)點(diǎn)并行構(gòu)建算法［6］的思想與CSB+-樹(shù)的批量裝載算法相似，即節(jié)點(diǎn)內(nèi)的每一個(gè)鍵值由獨(dú)立的線(xiàn)程并行計(jì)算，并行的線(xiàn)程數(shù)由下一層的節(jié)點(diǎn)數(shù)決定，并根據(jù)樹(shù)的高度需要多次調(diào)用CUDA 核函數(shù).由于每次調(diào)用核函數(shù)后還需要線(xiàn)程的同步操作且這些操作需要耗費(fèi)幾百個(gè)GPU時(shí)鐘.

為此，文中提出了一種基于鍵的內(nèi)部節(jié)點(diǎn)并行構(gòu)建算法，該算法通過(guò)計(jì)算樹(shù)中內(nèi)部節(jié)點(diǎn)的每個(gè)鍵與最終葉子節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系來(lái)實(shí)現(xiàn)一次性并行構(gòu)建所有內(nèi)部節(jié)點(diǎn)的鍵值.首先自下而上、自左向右地對(duì)內(nèi)部節(jié)點(diǎn)進(jìn)行編號(hào)，接著計(jì)算每個(gè)線(xiàn)程所代表的鍵在索引樹(shù)中的層節(jié)點(diǎn)編號(hào)layerNode 以及它在該節(jié)點(diǎn)內(nèi)的鍵編號(hào)nodeKey，然后計(jì)算該層的節(jié)點(diǎn)與節(jié)點(diǎn)之間的葉子偏移量nodeLeafs、節(jié)點(diǎn)內(nèi)部鍵之間的葉子偏移量keyLeafs，最后計(jì)算該鍵對(duì)應(yīng)的目標(biāo)葉子節(jié)點(diǎn)leaf:

leaf 的最大值為該線(xiàn)程所代表的內(nèi)部節(jié)點(diǎn)的鍵值.該算法的偽代碼如下:

1.3 CSB +-樹(shù)的并行查詢(xún)算法

傳統(tǒng)CSB+-樹(shù)的查詢(xún)算法主要是通過(guò)二分查找的方式，從根節(jié)點(diǎn)開(kāi)始搜索，直至目標(biāo)葉子節(jié)點(diǎn).由于二分查找并不適合并行處理，因此一種比較合理的方法就是在每個(gè)節(jié)點(diǎn)的內(nèi)部采用多線(xiàn)程并行查找的算法.為此，Christensen 等［5］提出了一種基于線(xiàn)程塊的CSS-樹(shù)查詢(xún)算法，按該算法思路設(shè)計(jì)的基于線(xiàn)程塊的CSB+-樹(shù)內(nèi)部節(jié)點(diǎn)的并行查詢(xún)算法的偽代碼如下:

在上述算法中，為防止數(shù)組的越界訪(fǎng)問(wèn)，當(dāng)線(xiàn)程tid=0 時(shí)需要進(jìn)行特殊處理，從而在線(xiàn)程塊中產(chǎn)生一個(gè)分支.CUDA 的指令執(zhí)行模式是SIMT 方式，warp 是CUDA 的最小調(diào)度單位，當(dāng)一個(gè)warp 內(nèi)的線(xiàn)程出現(xiàn)分支時(shí)，warp 將沿著每個(gè)分支調(diào)度串行化指令，直至warp 內(nèi)所有的線(xiàn)程可執(zhí)行相同的指令為止［12］.由此可見(jiàn)，當(dāng)warp 內(nèi)的線(xiàn)程走向不同的分支時(shí)，需要的時(shí)間是不同分支的執(zhí)行時(shí)間之和，并且分支影響了并行計(jì)算的吞吐量.為避免程序出現(xiàn)分支的情況，文中在CSB+-樹(shù)每個(gè)內(nèi)部節(jié)點(diǎn)的最左邊添加一個(gè)填充位，新的節(jié)點(diǎn)結(jié)構(gòu)如圖2 所示.

圖2 帶左填充位的節(jié)點(diǎn)結(jié)構(gòu)Fig.2 Structure of node with left padding bit

每個(gè)節(jié)點(diǎn)填充位的值可設(shè)為所有索引數(shù)據(jù)的最小值－1，修改節(jié)點(diǎn)結(jié)構(gòu)后基于線(xiàn)程塊的CSB+-樹(shù)內(nèi)部節(jié)點(diǎn)的查找(BlockSearchNode)算法的偽代碼如下:

2 性能分析

傳統(tǒng)緩存敏感技術(shù)的思想是利用高速存儲(chǔ)器來(lái)解決CPU 運(yùn)算速度快與訪(fǎng)存速度慢不匹配的瓶頸問(wèn)題.在GPU 中常用的CUDA 程序優(yōu)化方法是利用共享存儲(chǔ)器來(lái)減少訪(fǎng)問(wèn)全局存儲(chǔ)器的次數(shù)，從而獲得更高的內(nèi)存帶寬，如GPU 上的稀疏矩陣乘法運(yùn)算等.文中根據(jù)建立CUDA 程序計(jì)算模型的方法［13-14］來(lái)分析GPU 上使用共享存儲(chǔ)器加速CSB+-樹(shù)查詢(xún)性能的可行性.

假設(shè)CSB+-樹(shù)每個(gè)節(jié)點(diǎn)的索引鍵數(shù)為m，N 是待并行查詢(xún)的記錄數(shù)，GPU 共有NSM個(gè)流處理器(SM)，則使用BlockSearchNode 算法并行查詢(xún)N 個(gè)記錄的時(shí)間t 為

式中:tblock為每個(gè)線(xiàn)程塊完成一次查詢(xún)?nèi)蝿?wù)的時(shí)間，tblock= tglobal+ tsyn+ tcomupter，tglobal為一個(gè)線(xiàn)程塊內(nèi)讀取全局存儲(chǔ)器數(shù)據(jù)的總時(shí)間，tsyn為線(xiàn)程塊內(nèi)線(xiàn)程同步的總時(shí)間，tcomputer為計(jì)算指令執(zhí)行的總時(shí)間;Nblock為GPU 每次可并行計(jì)算的線(xiàn)程塊數(shù)，Nblock=SSMNBLP，SSM為每個(gè)SM 的共享存儲(chǔ)器容量，NBLP為每個(gè)SM 的活動(dòng)線(xiàn)程塊數(shù)，它受GPU 的硬件和核函數(shù)使用的資源(共享存儲(chǔ)器容量和寄存器數(shù)等)的限制，NBLP＜SSM/Sshare，Sshare是CUDA 核函數(shù)使用的共享存儲(chǔ)器大小.

由此可見(jiàn)，若能減少tglobal或增大NBLP，則可以使t 值變小.如果使用共享存儲(chǔ)器的查詢(xún)方式，則線(xiàn)程塊內(nèi)訪(fǎng)存的總時(shí)間t'global為

式中，tsg為將CSB+-樹(shù)部分或全部?jī)?nèi)部節(jié)點(diǎn)的數(shù)據(jù)從全局存儲(chǔ)器拷貝至共享存儲(chǔ)器的時(shí)間，tsh為線(xiàn)程訪(fǎng)問(wèn)共享存儲(chǔ)器的時(shí)間，tgl為數(shù)據(jù)不在共享存儲(chǔ)器時(shí)線(xiàn)程到全局存儲(chǔ)器的訪(fǎng)問(wèn)時(shí)間.由式(4)可知:若能減少tblock，則可提高CSB+-樹(shù)的查詢(xún)速度;在每個(gè)線(xiàn)程塊需要處理的數(shù)據(jù)量不變(即tsyn與tcomputer均不變)的情況下，如果通過(guò)利用共享存儲(chǔ)器來(lái)實(shí)現(xiàn)t'global＜tglobal，則一個(gè)線(xiàn)程塊內(nèi)的共享存儲(chǔ)器必須裝入足夠多的節(jié)點(diǎn)數(shù)據(jù)，而且還需要有一定的查詢(xún)量才能攤銷(xiāo)tsg的代價(jià).

現(xiàn)假定CSB+-樹(shù)每個(gè)節(jié)點(diǎn)的鍵容量m=128，并且每個(gè)鍵值占4B 的存儲(chǔ)空間，SM 的共享存儲(chǔ)器容量為16kB，則該共享存儲(chǔ)器可裝入的最大節(jié)點(diǎn)數(shù)為32.

這意味著在NBLP取最小值1 的極端情況下，對(duì)于一棵較大數(shù)據(jù)規(guī)模的CSB+-樹(shù)，共享存儲(chǔ)器尚不能裝滿(mǎn)2 層樹(shù)的節(jié)點(diǎn)數(shù)據(jù)，這顯然無(wú)法攤銷(xiāo)tsg的代價(jià).由此可見(jiàn)，由于GPU 共享存儲(chǔ)器架構(gòu)設(shè)計(jì)的特殊性，通過(guò)高速共享存儲(chǔ)器來(lái)提高數(shù)據(jù)讀取的速度以提高程序的性能，在CSB+-樹(shù)的并行查詢(xún)中并不適用.

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

實(shí)驗(yàn)硬件平臺(tái):GPU 為NVIDIA GTX 550Ti，CPU 為Intel core i5 2.53 GHz;軟件環(huán)境:操作系統(tǒng)Windows 7，GPU 編程使用CUDA 4.0 的開(kāi)發(fā)包;編譯器是Visual Studio 2010.為驗(yàn)證文中提出的并行構(gòu)建CSB+-樹(shù)內(nèi)部節(jié)點(diǎn)算法的性能，在GPU 平臺(tái)上分別進(jìn)行索引數(shù)據(jù)規(guī)模從500 萬(wàn)至2 500 萬(wàn)的建樹(shù)實(shí)驗(yàn)，其中內(nèi)部節(jié)點(diǎn)的鍵容量m 為64，并與文獻(xiàn)［5-6］中算法的性能進(jìn)行對(duì)比，結(jié)果如圖3 所示.實(shí)驗(yàn)采用NVIDIA 提供的CUDA Profiler 工具統(tǒng)計(jì)每個(gè)核函數(shù)的運(yùn)行時(shí)間.

圖3 3 種算法的性能對(duì)比Fig.3 Performance comparison of three algorithms

從圖3 可以看出，當(dāng)處理的數(shù)據(jù)規(guī)模為2500 萬(wàn)時(shí)，使用文獻(xiàn)［5］算法構(gòu)建樹(shù)內(nèi)部節(jié)點(diǎn)需要22 ms，而文中算法僅需0.7 ms，相對(duì)于其他兩種算法，文中算法的加速比分別達(dá)到了31.0 和1.4 倍.在CSB+-樹(shù)只有一個(gè)內(nèi)部節(jié)點(diǎn)的情況下，3 種算法使用的時(shí)間是相同的.

圖4 給出了在GPU 上使用帶分支和無(wú)分支線(xiàn)程塊查詢(xún)算法的性能對(duì)比.由圖可知，查詢(xún)5 ×1 024和25 ×1024 條數(shù)據(jù)時(shí)，帶分支線(xiàn)程塊查詢(xún)算法分別需要185 和900 μs，而無(wú)分支線(xiàn)程塊查詢(xún)算法分別只需156 和750 μs.

圖4 帶分支和無(wú)分支線(xiàn)程塊查詢(xún)算法的性能對(duì)比Fig.4 Performance comparison of thread block search algorithms with branch or no-branch

通過(guò)CUDA Profiler 工具觀(guān)察文獻(xiàn)［5］算法和文中算法的線(xiàn)程分支指標(biāo)“divergent branch”，發(fā)現(xiàn)文中算法的分支總數(shù)比文獻(xiàn)［5］中算法減少近1/3.由此可見(jiàn)，在GPU 的并行計(jì)算中，減少線(xiàn)程塊內(nèi)的線(xiàn)程分支數(shù)可有效地提高程序的性能.

4 結(jié)論

文中在GPU 平臺(tái)上提出了一種一次性并行創(chuàng)建CSB+-樹(shù)所有內(nèi)部節(jié)點(diǎn)鍵值的算法，以充分利用GPU 強(qiáng)大的并行計(jì)算吞吐量.對(duì)CSB+-樹(shù)查找算法使用共享存儲(chǔ)器進(jìn)行可行性分析，發(fā)現(xiàn)傳統(tǒng)的緩存敏感樹(shù)技術(shù)不適用于復(fù)雜的GPU 內(nèi)存框架.文中通過(guò)增加節(jié)點(diǎn)的填充位來(lái)減少GPU 線(xiàn)程塊內(nèi)的線(xiàn)程分支數(shù)，有效地提高了CUDA 程序的性能.今后將進(jìn)一步研究GPU 在數(shù)據(jù)庫(kù)技術(shù)中的其他高性能并行計(jì)算.

［1］DeWitt David J，Katz Randy H，Olken Frank，et al.Implementation techniques for main memory database systems［C］∥Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data.Boston:ACM，1984:1-8.

［2］Rao J，Ross K A.Cache conscious indexing for decisionsupport in main memory ［C］∥Proceedings of the 25th Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc，1999:78-89.

［3］Rao J，Ross K A.Making B+-trees cache conscious in main memory［C］∥Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.New York:ACM，2000:475-486.

［4］Fix J，Wilkes A，Skadron K.Accelerating braided B+tree searches on a GPU with CUDA［C］∥Proceedings of the 2nd Workshop on Applications for Multi and Many Core Processors:Analysis，Implementation，and Performance.San Jose:Springer-Verlag，2011:1-11

［5］Christensen D，Hansen H O，Juul L，et al.Efficient implementation of CSS-trees on GPGPUs［R］.Aalborg:Department of Computer Science，Aalborg University，2010.

［6］Kaczmarski K.B+-tree optimized for GPGPU［M］∥On the Move to Meaningful Internet Systems:OTM 2012.Berlin/Heidelberg:Springer-Verlag，2012:843-854.

［7］Liu Yong，Xi Jianqing，Lai Zhengwen，et al.Batch records insertion into multidimensional linear dynamic hashing table on GPU ［J］.Journal of Computational Information Systems，2012，8(10):4293-4301.

［8］Kim Changkyu，Chhugani Jatin，Satish Nadathur，et al.FAST:fast architecture sensitive tree search on modern CPUs and GPUs ［C］∥Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.New York:ACM，2010:339-350.

［9］Owens J D，Luebke D，Govindaraju N，et al.A survey of general-purpose computation on graphics hardware ［J］.Computer Graphics Forum，2007，26(1):80-113.

［10］NVIDIA.NVIDIA CUDA programming guide［EB/OL］.(2009-09-27)［2012-08-30］.http:∥developer.nvidia.com/object/cuda.html.

［11］Larson Per-Ake.Dynamic hash tables［J］.Communications of the ACM，1988，31(4):446-457.

［12］張舒，褚艷利，趙開(kāi)勇，等.GPU 高性能運(yùn)算之CUDA［M］.北京:中國(guó)水利水電出版社，2009:68-70.

［13］Ryoo S，Rodrigues C I，Stone Sam S，et al.Program optimization space pruning for a multithreaded GPU［C］∥Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization.New York:ACM，2008:195-204.

［14］袁良，張?jiān)迫垏?guó)平，等.基于延遲隱藏因子的GPU計(jì)算模型［J］.軟件學(xué)報(bào)，2010，21(12):251-262.Yuan Liang，Zhang Yun-quan，Long Guo-ping，et al.A GPU computational model based on latency hidden factor［J］.Chinese Journal of Software，2010，21(12):251-262.