吳婧雅 盧文巖 鄢貴海 李曉維

1 （處理器芯片全國重點實驗室（中國科學院計算技術(shù)研究所）北京 100190）

2 （中國科學院大學 北京 100049）

索引是數(shù)據(jù)庫中用來加速數(shù)據(jù)查詢的一種常用數(shù)據(jù)結(jié)構(gòu).其中，B+樹憑借其獨特優(yōu)勢成為關(guān)系型數(shù)據(jù)庫中最常用的索引結(jié)構(gòu).相較于其他索引結(jié)構(gòu)，B+樹具有3 個優(yōu)勢：

1）數(shù)據(jù)存儲結(jié)構(gòu)規(guī)則.利用關(guān)鍵字數(shù)據(jù)結(jié)構(gòu)以平衡樹維護，能夠提升數(shù)據(jù)查詢效率.且樹的所有內(nèi)部節(jié)點只存儲索引關(guān)鍵字（即鍵值），索引信息更密集，降低查詢I/O 開銷.

2）查詢開銷穩(wěn)定.關(guān)鍵字指向的實際數(shù)據(jù)只在葉子節(jié)點中存儲.由此，查詢時需要逐層遍歷各層內(nèi)部節(jié)點直到葉子節(jié)點結(jié)束，查詢開銷穩(wěn)定.

3）提升范圍查詢性能.葉子節(jié)點以有序鏈表相連，支持范圍查詢依序訪問葉子節(jié)點，避免對樹的多次遍歷，使范圍查詢更高效.

然而，B+樹索引的高度有序性使得大數(shù)據(jù)場景下索引查詢效率降低、索引維序開銷增加，成為限制數(shù)據(jù)庫性能提升的瓶頸.總結(jié)大數(shù)據(jù)場景下B+樹性能提升面臨的3 個挑戰(zhàn)：

1）訪存性能低.關(guān)鍵字查詢通過逐層定位節(jié)點實現(xiàn).由于節(jié)點內(nèi)關(guān)鍵字比較結(jié)果的不確定性導致對下一層子節(jié)點的訪問是隨機的.這種隨機內(nèi)存訪問使內(nèi)存帶寬利用異常低效.

2）并行性差.由于查詢需要逐層遍歷節(jié)點才能完成，中間結(jié)果的不確定性導致逐層遍歷難以實現(xiàn)并行，索引帶來的優(yōu)勢被削弱.

3）樹的維序難度大.索引維序（索引刪除、插入和修改，其中1 次修改可以看作是1 次刪除和1 次插入的組合）過程會影響樹中間各層節(jié)點鍵值的存儲狀態(tài).索引維序?qū)е氯~子節(jié)點內(nèi)數(shù)據(jù)增加或減少，并改變?nèi)~子節(jié)點內(nèi)關(guān)鍵字順序；取決于節(jié)點內(nèi)存儲空間容量的限制，也有可能導致中間節(jié)點結(jié)構(gòu)的改變.這種不確定的節(jié)點狀態(tài)改變，使葉子節(jié)點內(nèi)關(guān)鍵字維序和中間節(jié)點更新復雜且效率低.

由此，如何平衡B+樹的查詢和維序性能，以及在大數(shù)據(jù)場景下進一步提升索引的查詢和維序效率，成為索引優(yōu)化的關(guān)鍵.

隨著通用計算平臺性能提升放緩[1]，許多研究提出利用GPU 和FPGA 等異構(gòu)計算平臺加速B+樹的查詢和維護操作[2-4].為充分發(fā)揮GPU 異構(gòu)系統(tǒng)的算力，多數(shù)研究從提升索引查詢性能和緩解內(nèi)存帶寬瓶頸等角度提出解決方法.在SIMD 架構(gòu)的平臺中，文獻[5-7]提出了提升多條查詢語句并行效率的策略以提升GPU 對B+樹的查詢效率.文獻[8-9]則優(yōu)化了索引節(jié)點的存儲結(jié)構(gòu)，以緩解GPU 的內(nèi)存帶寬瓶頸.這些研究將重點放在提升索引查詢的性能.利用FPGA 這一類可重構(gòu)計算架構(gòu)，文獻[10-11]利用FPGA 分別設(shè)計了支持索引的查詢和更新操作的專用計算引擎，并評估了利用FPGA 加速不同體量索引對系統(tǒng)整體性能的影響.但是文獻[10-11]方法欠缺對索引查詢和更新的協(xié)同優(yōu)化，沒有提出B+樹索引系統(tǒng)的均衡優(yōu)化方案.

為均衡提升大數(shù)據(jù)場景下數(shù)據(jù)庫索引的查詢和維護性能，本文系統(tǒng)研究了B+樹索引的查詢和維序的操作特性，提出針對索引訪存和計算的協(xié)同優(yōu)化加速器架構(gòu)HyperTree，在大數(shù)據(jù)場景中，兼顧索引的查詢和維序性能的提升.本文的主要貢獻點：

1）提出一種同構(gòu)的流式計算多引擎架構(gòu)，既能夠提升單計算引擎的效率，又支持多索引查詢、更新和維序任務(wù)的并行；

2）提出一種規(guī)則的B+樹節(jié)點存儲格式，同時設(shè)計專用的內(nèi)存管理系統(tǒng)以支持低開銷的并行訪存，進一步提升內(nèi)存帶寬利用效率；

3）提出一種高效靈活的計算控制系統(tǒng)，支持多指令并行和多數(shù)據(jù)并行，在提升計算引擎性能的同時，不會引入額外開銷；

4）提出一種多子樹結(jié)構(gòu)，將復雜的B+樹拆分為幾棵小的子樹，避免葉子節(jié)點的更新沖突，以提升索引的維序效率.

實驗結(jié)果表明，相比于CPU，B+樹索引加速系統(tǒng)HyperTree 能夠提升系統(tǒng)查詢性能6.84 倍；范圍查詢性能提升14.53 倍，且相比單值查詢性能損失很小，平均為單值查詢性能的75.58%；引入子樹存儲管理系統(tǒng)后，索引維序性能提升超過29.14 倍.

1 研究背景

典型的B+樹結(jié)構(gòu)如圖1 所示.內(nèi)部節(jié)點稱為索引節(jié)點，按照升序排列存儲關(guān)鍵字；葉子節(jié)點既存儲關(guān)鍵字又記錄關(guān)鍵字指向的數(shù)據(jù)信息.

Fig.1 Keyword search in B+tree圖1 B+樹的關(guān)鍵字查詢

B+樹查詢操作從根節(jié)點開始，自頂向下逐層比較內(nèi)部節(jié)點的索引關(guān)鍵字范圍，直到找到包含查詢內(nèi)容的葉子節(jié)點.以圖1 所示的等值查詢目標關(guān)鍵字11 為例.從根節(jié)點開始，將11 與關(guān)鍵字2 和10 比較，定位下一層節(jié)點應(yīng)指向根節(jié)點最右側(cè)子節(jié)點.再重復上述范圍比較，定位下一層應(yīng)指向當前節(jié)點最左側(cè)子節(jié)點.此節(jié)點為B+樹的葉子節(jié)點，在葉子節(jié)點中定位關(guān)鍵字11 指向的原數(shù)據(jù)庫表，結(jié)束本次查詢.范圍查詢可以通過等值查詢定位的葉子節(jié)點間的指針依次比較關(guān)鍵字得到查詢結(jié)果.

B+樹查詢性能取決于樹的高度（逐層查找）、節(jié)點大?。ㄖ饌€數(shù)據(jù)比較）及關(guān)鍵字匹配速度.例如：高度為l的B+樹所需查詢時間為l次節(jié)點讀取的I/O 延時和mi×l次計算引擎的關(guān)鍵字比較處理時間（mi為各節(jié)點關(guān)鍵字比較的次數(shù)）.由此，索引節(jié)點的I/O 開銷和關(guān)鍵字比較成為限制索引查詢性能的瓶頸.

B+樹的維序過程由數(shù)據(jù)庫表的插入、刪除和更新操作引起.以索引插入為例，首先通過查詢定位關(guān)鍵字待插入的葉子節(jié)點位置，然后插入關(guān)鍵字.插入前需要判斷插入新關(guān)鍵字后葉子節(jié)點是否超過規(guī)定長度.若沒有超過則結(jié)束本次索引插入，否則將該葉子節(jié)點平均分裂為2 個新葉子節(jié)點，并用新分裂的節(jié)點信息更新其父節(jié)點.更新時，將新分裂的右側(cè)葉子節(jié)點的第1 個索引關(guān)鍵字插入父節(jié)點原關(guān)鍵字，并更新葉子節(jié)點間指針.葉子節(jié)點更新結(jié)束后，依層向上重復節(jié)點更新過程，直到不需要拆分父節(jié)點或找到根節(jié)點，結(jié)束索引插入.刪除與插入過程類似，區(qū)別在于刪除可能導致節(jié)點合并，索引更新由刪除和插入組成.以圖2 所示插入關(guān)鍵字4 為示例.首先定位關(guān)鍵字4 應(yīng)寫入的葉子節(jié)點位置.此時插入新關(guān)鍵字后的葉子節(jié)點超過規(guī)定長度，將該葉子節(jié)點分裂為2 個新節(jié)點，依大小順序在父節(jié)點插入索引值4，同時更新父節(jié)點指針.更新后父節(jié)點長度未超過規(guī)定長度，結(jié)束更新過程.

Fig.2 Keyword insertion in B+tree圖2 B+樹的關(guān)鍵字插入

數(shù)據(jù)表的更新，需要首先對葉子節(jié)點定位，再修改關(guān)鍵字.由于節(jié)點存儲空間的限制還有可能向上分裂或合并中間節(jié)點.不確定的多層節(jié)點操作會引入隨機I/O 讀寫，使得數(shù)據(jù)表維序的開銷相對于查詢來說大大增加.

2 相關(guān)工作

在大數(shù)據(jù)時代，內(nèi)存數(shù)據(jù)庫的出現(xiàn)一定程度上解決了傳統(tǒng)硬盤數(shù)據(jù)庫的讀寫延遲問題[2].然而通用計算卻不足以提供有效算力支持以充分利用內(nèi)存讀寫帶寬資源[1].研究人員轉(zhuǎn)而利用異構(gòu)計算平臺，實現(xiàn)全卸載或半卸載的內(nèi)存數(shù)據(jù)庫加速方案提升數(shù)據(jù)庫的計算效率[2-4].

為提升B+樹的查詢效率，大量研究基于GPU 異構(gòu)計算平臺設(shè)計高效的并行架構(gòu)[2]，主要優(yōu)化方向為加速索引查詢[5-6,8]及索引結(jié)構(gòu)優(yōu)化[7,9,12].GPU 加速索引操作的核心思想是改進查詢的計算模式以充分適配GPU 的SIMD 架構(gòu).文獻[5]基于AMD 的CPU+GPU異構(gòu)系統(tǒng)，提出了粗細粒度2 種并行策略以加速B+樹的查詢.細粒度并行策略將節(jié)點的二分查找替換為K-ary 查找，從而使計算引擎執(zhí)行相同模式的查詢操作；粗粒度并行策略利用同構(gòu)的計算引擎同時執(zhí)行多條查詢.訪存優(yōu)化主要是調(diào)整B+樹內(nèi)部節(jié)點為規(guī)則的數(shù)據(jù)結(jié)構(gòu)，從而充分利用GPU 的高訪存帶寬.文獻[7]設(shè)計了一種將索引關(guān)鍵字和子節(jié)點指針分布存儲的改進樹形結(jié)構(gòu)，以充分利用GPU 的內(nèi)存帶寬；并利用SIMD 計算方法設(shè)計基于排序的并行查詢方法，進一步緩解查詢時的內(nèi)存帶寬瓶頸.文獻[12]優(yōu)化節(jié)點內(nèi)部存儲結(jié)構(gòu)，解決訪存瓶頸，進一步提升查詢并行計算效率.

充分發(fā)揮GPU 的并行性能極強地依賴于計算規(guī)則且訪存對齊[2].然而索引操作天然具有計算并行難度大、訪存隨機性等問題，導致利用GPU 加速索引操作的性能提升效果有限，從而有一些文獻提出利用可重構(gòu)硬件加速器設(shè)計更加靈活高效的方案.文獻[10]利用FPGA 設(shè)計了加速B+樹索引查詢的專用體系結(jié)構(gòu).利用片上BRAM 存儲部分內(nèi)部節(jié)點地址以達到快速訪問內(nèi)部節(jié)點的目的，同時設(shè)計專用并行查詢計算單元，能夠支持節(jié)點內(nèi)關(guān)鍵字的快速定位；而葉子節(jié)點和一些低層內(nèi)部節(jié)點的查詢及全部索引維序依靠CPU 實現(xiàn).文獻[11]補充了文獻[10]的研究工作，設(shè)計并行的節(jié)點更新計算單元，同時在CPU 端增加1 個調(diào)度單元部分卸載索引更新至FPGA，即FPGA 僅處理索引更新的部分操作，一定程度上提升了FPGA 加速B+樹索引的效果.文獻[10-11]利用FPGA 作為通用計算CPU 的補充：CPU 負責數(shù)據(jù)和指令的卸載，將根節(jié)點和部分上層內(nèi)部節(jié)點卸載到FPGA 上加速查詢和更新.但這種方法是半卸載的方案，CPU 仍然需要負責主要的計算，F(xiàn)PGA 僅完成部分協(xié)同工作；且該方法的實現(xiàn)對FPGA 的計算資源和存儲空間利用效率很低，指令并行性差，B+樹索引的性能提升有限.此外，文獻[10-11]將優(yōu)化的CBS+樹結(jié)構(gòu)作為數(shù)據(jù)庫的索引格式，雖然降低數(shù)據(jù)傳輸開銷及FPGA 端地址計算復雜度，但給系統(tǒng)引入了額外的索引格式轉(zhuǎn)換開銷.

近年來，隨著FPGA 板卡內(nèi)存空間和帶寬性能的不斷提升，利用FPGA 加速內(nèi)存數(shù)據(jù)庫性能提升顯著[2,4].鑒于FPGA 結(jié)構(gòu)更加靈活、資源可配置等特性，本文基于FPGA 異構(gòu)計算平臺，設(shè)計并實現(xiàn)了全卸載B+樹索引加速系統(tǒng)HyperTree——將索引的存儲，B+樹構(gòu)建，索引查詢，索引插入、刪除和修改全部寫到FPGA 執(zhí)行.在本文所提出的 CPU-FPGA 構(gòu)成的異構(gòu)計算系統(tǒng)中，CPU 只負責查詢計劃的生成和優(yōu)化以及加速器的啟動運行和管理.

3 B+樹性能瓶頸分析

基于第1 節(jié)對B+樹典型操作的描述，本節(jié)將對B+樹各操作性能瓶頸進行深入分析.

3.1 數(shù)據(jù)隨機訪存造成存儲帶寬利用率低下

B+樹查詢時內(nèi)存帶寬利用非常低效：一是由于節(jié)點的隨機訪存；二是由于樹的訪存管理復雜.在B+樹索引查詢時，下層節(jié)點的訪存地址由當前層節(jié)點內(nèi)部關(guān)鍵字的比較結(jié)果決定.結(jié)果的不確定性導致每層節(jié)點的訪存是隨機的，且中間節(jié)點在內(nèi)存中依靠指針相連，每個節(jié)點的數(shù)據(jù)結(jié)構(gòu)不完全相同，節(jié)點的物理地址也是隨機的，進一步增加訪存隨機性.B+樹的存儲管理需要對內(nèi)存空間動態(tài)維護.當執(zhí)行索引插入和刪除操作時，可能需要動態(tài)申請或釋放內(nèi)存空間.為維護節(jié)點的樹形結(jié)構(gòu)，需要動態(tài)修改對應(yīng)的內(nèi)存空間狀態(tài)，該過程的存儲訪存也是隨機的.此外，數(shù)據(jù)量的增加導致實際應(yīng)用中B+樹標準格式規(guī)定的節(jié)點存儲空間無法完整保存1 個數(shù)據(jù)表內(nèi)的全部索引信息.從而維護1 個數(shù)據(jù)表索引需要管理多棵B+樹，進一步加劇了內(nèi)存空間管理的困難.這種數(shù)據(jù)訪存隨機性導致的問題無論是CPU 還是GPU 都無法直接解決，也是導致GPU 的高訪存帶寬無法被直接有效利用的根本原因.

為驗證隨機內(nèi)存訪問帶寬的性能，通過實驗在實際數(shù)據(jù)庫中測試DDR4-3200 內(nèi)存訪存特性（其標稱內(nèi)存帶寬為204.8 Gbps）.隨著讀寫地址空間范圍的增加，實際讀寫帶寬有一定提升，但只有訪存達到突發(fā)讀寫長度時，理論最大帶寬才能被充分利用.如圖3 的實驗結(jié)果顯示，單字讀寫、隨機讀寫帶寬實際只能將近標稱性能的60%，甚至更低.

Fig.3 Practical efficient read/write bandwidth of DDR4圖3 DDR4 的實際有效讀寫帶寬

3.2 查詢并行度低下影響查詢性能

單節(jié)點的查詢和比較難以并行，是大數(shù)據(jù)量下查詢性能下降的關(guān)鍵原因.在B+樹設(shè)計中，為優(yōu)化中間節(jié)點訪存帶寬，可以通過盡可能擴大中間節(jié)點容量（節(jié)點內(nèi)數(shù)據(jù)連續(xù)存儲）的方法實現(xiàn).然而，中間節(jié)點數(shù)據(jù)量的增加加劇了節(jié)點內(nèi)關(guān)鍵字查找的難度.有研究表明，利用GPU 加速索引操作，即使是改進的算法，例如順序查找、二分查找、并行查找，單條查詢的性能提升仍然十分有限[6].

多查詢語句并行是進一步提升系統(tǒng)性能的關(guān)鍵.但現(xiàn)有的CPU-GPU 異構(gòu)系統(tǒng)由于無法在隨機訪存時充分利用內(nèi)存帶寬，且查詢時計算結(jié)果隨機性強，從而難以提升并行度[5-6,12].對于樹的訪存來說，有限的內(nèi)存帶寬無法滿足多處理引擎對數(shù)據(jù)讀寫速度的需求；且每次訪存的地址空間范圍有限，進一步降低讀寫效率.對于計算來說，處理引擎的比較和查找能力決定了單條查詢語句的效率，而處理引擎的數(shù)目決定了查詢的并行度上限.當單引擎的計算性能受限時，并行帶來的性能提升十分有限.

3.3 更新維序復雜大大降低插入性能

索引提升了數(shù)據(jù)查詢的效率，但樹形結(jié)構(gòu)的高度有序性使索引維序操作復雜.修改數(shù)據(jù)庫表記錄，包括記錄的增加、刪除或更新，需要同時修改索引.索引的維序?qū)π薷臄?shù)據(jù)庫表記錄造成額外開銷.以索引的插入為例，受限于節(jié)點容量的限制，關(guān)鍵字插入可能引起節(jié)點分裂.節(jié)點內(nèi)數(shù)據(jù)量一旦超過容量閾值，節(jié)點的分裂可能自葉子節(jié)點出現(xiàn)，并向上逐級影響父節(jié)點直到根節(jié)點.但這一過程是否出現(xiàn)取決于節(jié)點內(nèi)原有關(guān)鍵字的容量和分裂后的節(jié)點關(guān)鍵字，難以提前預判計算和預取數(shù)據(jù)，導致索引插入的執(zhí)行效率很低.這種計算的不確定性對GPU 的SIMD架構(gòu)極不友好.

索引的維序會阻塞對同一棵樹的其他操作，影響指令并行性能.在本條維序操作結(jié)束前，節(jié)點內(nèi)數(shù)據(jù)容量的差異和樹形結(jié)構(gòu)的數(shù)據(jù)依賴性導致無法預測其結(jié)構(gòu)變化.索引維序過程對正在執(zhí)行的樹具有獨占性，即阻塞對同一棵樹的其他操作，從而當索引維序請求發(fā)生時，無法實現(xiàn)多指令并行，進一步降低B+樹索引維序的性能.

4 B+樹索引的優(yōu)化

第3 節(jié)的分析表明：訪存效率低和計算并行難是造成B+樹查詢性能差的主要原因；維序的復雜操作以及維序操作的數(shù)據(jù)依賴使得加速索引維序更加困難.本節(jié)將從訪存效率提升、單節(jié)點計算效率提升、計算并行優(yōu)化及解除維序的數(shù)據(jù)依賴4 個方面，提出提升B+樹查詢和維序性能的設(shè)計思想.

訪存優(yōu)化的關(guān)鍵是利用主存 DRAM 突發(fā)讀寫帶寬高的特性來提升帶寬利用率.DRAM 存儲器的特點是連續(xù)地址讀寫性能高效，即可以利用突發(fā)讀寫機制實現(xiàn)對B+樹各節(jié)點的讀寫.在B+樹中，節(jié)點內(nèi)在關(guān)鍵字比較時被反復訪問，這也意味著B+樹中間節(jié)點數(shù)據(jù)量越大，數(shù)據(jù)讀寫效率越高.因此，中間節(jié)點的數(shù)據(jù)量大小、存儲格式以及讀寫方式是本文優(yōu)化的重點.

然而單節(jié)點的數(shù)據(jù)量增加意味著在查找過程中需要進行更多次數(shù)據(jù)比較才能找到指向下一級滿足條件的節(jié)點指針，對計算引擎的查詢性能提出了更高的要求，從而提升單節(jié)點計算效率成為提高計算性能的首要保證.為進一步提升查詢性能，語句級并行是提升系統(tǒng)性能的另一個重點.由此提出設(shè)計一種高性能的同構(gòu)流式計算處理引擎架構(gòu)以提升單查詢語句的執(zhí)行效率，并進一步提升多查詢語句的并行度.

大節(jié)點引入使得索引維序的過程更加復雜.一方面，定位待修改的關(guān)鍵字位置的查詢過程延遲變長；另一方面，節(jié)點內(nèi)數(shù)據(jù)量增加導致更高的數(shù)據(jù)修改開銷.上述2 步驟的延遲和開銷進一步加劇了索引維序?qū)е碌臄?shù)據(jù)依賴，阻塞其他對同一棵樹的索引操作.因此，提出解除語句間數(shù)據(jù)依賴以提升索引維序性能的方法，其核心思想是將單棵B+樹拆分成多棵子樹，能夠支持對單棵 B+樹操作轉(zhuǎn)為對不同子樹的操作.由于子樹間彼此獨立，從而實現(xiàn)多插入更新操作并行.具體地，我們采取了5 個關(guān)鍵優(yōu)化.

4.1 節(jié)點訪存優(yōu)化

為了提升節(jié)點數(shù)據(jù)的訪存效率，首先要確定樹節(jié)點的存儲格式.樹節(jié)點存儲格式設(shè)計需要解決2 個核心問題：1）單節(jié)點的訪存效率，節(jié)點大小要符合DDR控制器的特性；2）存儲可擴展性設(shè)計滿足不同大小樹的存儲需求.

設(shè)計節(jié)點大小的原則以DDR 控制器所支持突發(fā)（burst）長度為基準，規(guī)定單個節(jié)點的大小為突發(fā)長度的整數(shù)倍.比如Xilinx FPGA 板卡突發(fā)傳輸為512 B，可以設(shè)計節(jié)點大小為512 B 或1024 B 或其他1 次突發(fā)讀寫大小的整數(shù)倍空間.但一般來說，為降低單節(jié)點存儲可能造成的存儲空間浪費，單節(jié)點的設(shè)計不宜過大.同時規(guī)定每次內(nèi)存讀寫都以1 個節(jié)點大小為單位，從而保證在對索引存儲節(jié)點的每次數(shù)據(jù)讀寫都充分利用內(nèi)存帶寬.

為簡化B+樹的存儲管理，規(guī)定以內(nèi)存塊的方式維護單棵B+樹，一個完整的索引可以由單棵樹或者多棵樹構(gòu)成，樹的組織結(jié)構(gòu)在內(nèi)存塊中完成.每個內(nèi)存塊（即1 棵樹）包含多個節(jié)點，每個節(jié)點存儲多個索引關(guān)鍵字.多樹的可擴展性設(shè)計的關(guān)鍵是進行樹的動態(tài)維護.規(guī)定內(nèi)存空間的動態(tài)申請和回收也按照塊進行，即創(chuàng)建新B+樹時，按塊申請內(nèi)存空間構(gòu)建索引；刪除B+樹，也相應(yīng)地按塊釋放內(nèi)存空間.以內(nèi)存塊為最小訪存管理對象，使得內(nèi)存管理更加簡潔高效.

4.2 高效的訪存管理

確定了樹的存儲結(jié)構(gòu)，接下來要解決的是如何實現(xiàn)處理引擎對樹和節(jié)點的數(shù)據(jù)訪問，即如何快速實現(xiàn)樹和節(jié)點從邏輯編號到物理存儲的映射，以及如何高效地將內(nèi)存數(shù)據(jù)加載到處理單元.訪存管理需要解決2 個關(guān)鍵問題：1）邏輯樹和節(jié)點到物理存儲的映射，包括物理空間的申請和釋放；2）為多處理引擎提供有效的計算數(shù)據(jù).

規(guī)則的節(jié)點設(shè)計能夠簡化B+樹節(jié)點的地址空間管理.定義一棵B+樹在內(nèi)存中存儲的數(shù)據(jù)格式為樹表，每棵樹表對應(yīng)特定的內(nèi)存塊.樹表的最小數(shù)據(jù)組織單位為行，行大小一致，每行表示1 個節(jié)點.計算引擎直接對節(jié)點內(nèi)的索引關(guān)鍵字進行操作，其訪存過程首先確定樹表的內(nèi)存空間，然后定位節(jié)點的內(nèi)存地址.由于索引的查詢和維序操作均在1 個或多個節(jié)點內(nèi)完成，為充分利用內(nèi)存讀寫帶寬，每次I/O 讀寫均以1 個節(jié)點為單位.然而，由于索引維序時節(jié)點的動態(tài)修改對每個節(jié)點的地址管理仍然很復雜，需要解決新節(jié)點物理地址的申請或原節(jié)點物理空間的釋放.

執(zhí)行查詢操作時，內(nèi)存訪問均以B+樹根節(jié)點開始，并依層次順序訪問內(nèi)部節(jié)點，直到葉子節(jié)點結(jié)束.為降低節(jié)點內(nèi)存訪問的控制成本，提出構(gòu)建專用的樹表存儲管理單元（tree-table memory manage unit, TMMU）實現(xiàn)快速從B+樹邏輯地址到樹表節(jié)點內(nèi)存物理地址的映射，以降低內(nèi)存空間維護的復雜度，并提升計算訪存的效率.TMMU 記錄 B+樹和內(nèi)部節(jié)點的相關(guān)狀態(tài)信息，保證在樹或節(jié)點創(chuàng)建或刪除時，能夠動態(tài)維護樹和節(jié)點的有效性.

4.3 流式計算架構(gòu)

利用流式計算的原則設(shè)計專用處理引擎從而提升節(jié)點內(nèi)關(guān)鍵字查詢的性能.相比于其他批量計算，流式計算有2 個主要的優(yōu)勢：1）無狀態(tài)執(zhí)行，控制簡單，數(shù)據(jù)驅(qū)動有利于多任務(wù)并行；2）全流水執(zhí)行，效率高，部分數(shù)據(jù)到達即可進行處理.圖4 示例了流式計算與批量計算的區(qū)別.與傳統(tǒng)的批量計算不同，流式計算每次只對規(guī)定窗口大小的數(shù)據(jù)進行計算，而無需等待全部數(shù)據(jù)輸入到計算節(jié)點.圖4 示例表明，流式計算的控制簡單，計算僅以數(shù)據(jù)流為驅(qū)動，沒有復雜的控制邏輯結(jié)構(gòu).

Fig.4 Difference between streaming computing and batch computing圖4 流式計算與批量計算的區(qū)別

4.4 多查詢語句并行

規(guī)則的節(jié)點存儲結(jié)構(gòu)和高效的數(shù)據(jù)管理單元為多語句并行執(zhí)行提供了快速有效的原始計算數(shù)據(jù)，解決了帶寬與計算性能不匹配的問題.數(shù)據(jù)管理單元配合內(nèi)存控制單元，能夠提供連續(xù)不間斷的數(shù)據(jù)訪存通路，為多計算引擎提供計算所需的數(shù)據(jù).

實現(xiàn)多查詢語句并發(fā)的另一個關(guān)鍵條件是指令間的調(diào)度和控制，即查詢指令如何映射到多處理單元.為最大化多語句并行度，并簡化控制邏輯，提出同構(gòu)的流式計算引擎陣列設(shè)計.同構(gòu)計算引擎，即所有處理單元架構(gòu)一樣，每個處理單元可以支持包括查詢、刪除、插入和更新在內(nèi)的全部索引操作.同時，由于各處理單元采用流式計算實現(xiàn)，進一步降低其控制邏輯的復雜度.基于上述設(shè)計，多查詢指令的并發(fā)管理變得異常簡單高效，當有新的計算指令時，可以快速分配到任一空閑處理引擎執(zhí)行，而不需要對各處理單元分類別管理.同構(gòu)的處理引擎設(shè)計也會避免計算任務(wù)和處理單元類型不匹配而導致資源浪費.相比于如圖5 所示的異構(gòu)設(shè)計，采用同構(gòu)設(shè)計處理單元存在一定的冗余而使得硬件資源開銷增加，我們也在降低開銷上做了很多精細設(shè)計，詳細見第5 節(jié).

Fig.5 Difference between homogeneous and heterogeneous computing units圖5 同構(gòu)計算單元與異構(gòu)計算單元的區(qū)別

4.5 提升索引維序性能的子樹結(jié)構(gòu)設(shè)計

為緩解索引維序的獨占性而導致的性能損失，提出解耦合的子樹結(jié)構(gòu)設(shè)計，以解決由于索引維序?qū)е碌亩嗾Z句并行阻塞現(xiàn)象.子樹是將1 棵完整的B+樹按照一定的方式拆分為幾棵小的子樹，且規(guī)定每一棵子樹的構(gòu)建嚴格遵循B+樹索引的結(jié)構(gòu)要求.為支持子樹查詢和維序的并行，內(nèi)存管理模塊也需要進行相應(yīng)的修改：查詢和維序操作的起始訪問從內(nèi)存空間的入口地址（即大樹的根節(jié)點）變?yōu)樽訕涞母?jié)點對應(yīng)的內(nèi)存地址.具體地，創(chuàng)建新樹時仍然申請1 個新的內(nèi)存塊；但是在構(gòu)建樹的過程中，按照某種規(guī)則選擇內(nèi)存塊的某些地址作為子樹的根節(jié)點地址，并將樹構(gòu)建的過程平均至每一棵子樹，直到完成1 棵樹的創(chuàng)建.相應(yīng)地，查詢操作的起始地址將變?yōu)樽訕淙肟诘刂罚醋訕涓?jié)點），而不再是原始的大樹入口地址（根節(jié)點）.這樣設(shè)計的優(yōu)勢在于，由于子樹間沒有數(shù)據(jù)依賴，對同一棵大樹但不同子樹的多條插入和更新操作可以并行執(zhí)行，即實現(xiàn)將對1 棵大樹的串行操作轉(zhuǎn)化為對多棵子樹的并行操作.

子樹的劃分粒度是子樹設(shè)計中需要考量的重要設(shè)計參數(shù).劃分子樹時，劃分粒度越細，索引更新可以在更多棵子樹中并行，數(shù)據(jù)并行度增加，從而提升計算并行效率.但劃分越細粒度，子樹根節(jié)點的入口地址維護會越復雜，且劃分越細將丟失越多索引結(jié)構(gòu)信息，對樹的索引結(jié)構(gòu)利用效率降低；反之，子樹劃分粒度越粗，子樹棵樹越少，數(shù)據(jù)依賴越多，計算并行提升有限.但粗粒度的劃分方式能夠更好地利用索引結(jié)構(gòu)信息，且子樹控制邏輯簡單，能夠緩解硬件資源開銷.

5 系統(tǒng)實現(xiàn)

按照第4 節(jié)中提出的優(yōu)化策略，本節(jié)主要介紹基于FPGA 實現(xiàn)的B+樹索引加速系統(tǒng)HyperTree 的具體實現(xiàn)和系統(tǒng)運行流程.HyperTree 統(tǒng)包含3 個主要的子系統(tǒng)，如圖6 所示：存儲管理子系統(tǒng)、索引計算子系統(tǒng)和指令控制子系統(tǒng).其中，存儲管理子系統(tǒng)包含TMMU 和內(nèi)存控制單元.在得到激活控制信號后，TMMU 負責將指令中的邏輯編號轉(zhuǎn)換為內(nèi)存物理地址.內(nèi)存控制單元將TMMU 輸出的物理地址中的內(nèi)存數(shù)據(jù)傳遞到計算引擎，或按照計算引擎給出的結(jié)果寫回相應(yīng)的內(nèi)存空間.指令控制子系統(tǒng)負責解析索引操作指令，提取操作碼和操作數(shù)，并根據(jù)操作碼和操作數(shù)依次激活指令執(zhí)行單元并打開內(nèi)存數(shù)據(jù)通道，負責指令并行控制.索引計算子系統(tǒng)由多個同構(gòu)的計算引擎構(gòu)成，負責并行執(zhí)行索引的查詢、插入、刪除和更新指令.其中，存儲管理子系統(tǒng)和指令控制子系統(tǒng)是實現(xiàn)多語句并行的直接控制邏輯單元，索引計算子系統(tǒng)是執(zhí)行計算并行的核心功能部件.接下來分別對各部分關(guān)鍵模塊的實現(xiàn)進行介紹.

Fig.6 System overall architecture圖6 系統(tǒng)整體結(jié)構(gòu)

5.1 節(jié)點存儲格式設(shè)計

根據(jù)第4 節(jié)中節(jié)點的設(shè)計原則，在微結(jié)構(gòu)實現(xiàn)時以512 B 為單位定義節(jié)點大小.以128 MB 內(nèi)存塊大小為單元設(shè)計樹表，則樹表共包含218行（即節(jié)點），在存儲塊內(nèi)的標號為0～218-1.樹的大小可以通過改變單位節(jié)點大小或樹表容量相應(yīng)調(diào)整.給定固定容量的B+樹，如果1 棵樹滿，可以通過動態(tài)申請存儲塊，創(chuàng)建1 棵新樹以實現(xiàn)數(shù)據(jù)庫表的完整索引結(jié)構(gòu).該過程利用軟件指令顯式維護.B+樹的節(jié)點格式規(guī)則定義如圖7 所示.B+樹包含3 種不同的節(jié)點類型：內(nèi)部節(jié)點、葉子節(jié)點和等值節(jié)點.其中，內(nèi)部節(jié)點只存儲關(guān)鍵字，葉子節(jié)點和等值節(jié)點存儲關(guān)鍵字和衛(wèi)星數(shù)據(jù)（衛(wèi)星數(shù)據(jù)指向數(shù)據(jù)表中的一條數(shù)據(jù)記錄）.兩者的區(qū)別在于，葉子節(jié)點指向不同關(guān)鍵字對應(yīng)的記錄，而等值節(jié)點指向相同關(guān)鍵字對應(yīng)的記錄.等值節(jié)點由葉子節(jié)點維護，葉子節(jié)點內(nèi)的等值索引指針若為0，則原始表位置信息有效，直接指向原始數(shù)據(jù)庫表中的記錄；否則，等值索引指向等值節(jié)點.為簡化索引關(guān)鍵字的尋址過程，設(shè)計8B 對齊的節(jié)點存儲格式.3類節(jié)點的格式組織基本相同，都是由節(jié)點頭部和節(jié)點數(shù)據(jù)2 部分組成.節(jié)點頭部主要標識節(jié)點類型及記錄指針；數(shù)據(jù)部分主要存儲索引關(guān)鍵字和指向子節(jié)點或表邏輯地址的指針.

Fig.7 Data structure definition of tree-table圖7 樹表的數(shù)據(jù)結(jié)構(gòu)定義

規(guī)則的節(jié)點設(shè)計及以節(jié)點為單位的訪存規(guī)則有效地提升了系統(tǒng)的內(nèi)存帶寬和內(nèi)存空間的利用率.以突發(fā)讀寫長度為單位設(shè)計節(jié)點容量，使計算引擎在處理節(jié)點內(nèi)數(shù)據(jù)時，能夠充分利用突發(fā)讀寫的高帶寬，提升內(nèi)存讀寫效率.節(jié)點指針以邏輯地址的形式存儲，所占內(nèi)存空間更小，且標識節(jié)點特征的部分僅占節(jié)點頭部的1/4，提升了節(jié)點對索引關(guān)鍵字及指針的存儲效率，確保最大程度利用內(nèi)存空間.此外，規(guī)則的節(jié)點格式設(shè)計簡化了計算引擎對數(shù)據(jù)解析的過程.在處理單節(jié)點內(nèi)部信息時，進一步提升計算性能.

5.2 存儲管理單元

為充分利用內(nèi)存帶寬，降低樹表地址維護開銷，提出專用樹表存儲管理單元TMMU，其主要實現(xiàn)2部分功能：一是實現(xiàn)邏輯地址到物理地址的快速映射；二是高效地將數(shù)據(jù)傳遞到計算引擎.

快速的地址映射能夠簡化軟件對內(nèi)存地址的管理，并提升節(jié)點存儲空間的存儲效率.在實際應(yīng)用中，軟件不直接管理B+樹的節(jié)點地址，從而維護索引物理地址被轉(zhuǎn)換為硬件開銷.通常計算指令的操作數(shù)所攜帶的信息是B+樹的標識tree_ID；根據(jù)樹表的設(shè)計原則，所得到的節(jié)點指針也只存儲其邏輯地址（以Num表示）.TMMU 的主要任務(wù)之一就是實現(xiàn)B+樹的標識tree_ID及樹內(nèi)節(jié)點邏輯地址與B+樹根節(jié)點入口地址及節(jié)點物理地址的映射，并維護樹表基本信息和節(jié)點的有效性.TMMU 的地址映射由圖8 所示.

Fig.8 Address mapping in TMMU圖8 TMMU 的地址映射

TMMU 中維護地址映射，為充分利用緩存讀寫帶寬，映射表的1 行與緩存單次最大讀寫位寬相同.表中的一行記錄樹的標識編號tree_ID、根節(jié)點入口地址（記為Addr）、樹深度、節(jié)點個數(shù)等信息.根節(jié)點映射表中以有效位1 表示該條記錄有效，否則該位置可以被改寫.當指令輸入tree_ID，TMMU 通過樹表映射表確定樹表的根節(jié)點入口及相應(yīng)信息；再依據(jù)節(jié)點的邏輯地址，根據(jù)式（1）中給出的映射關(guān)系計算其物理地址，其中單位尋址空間的單位為B.節(jié)點邏輯地址到物理地址的映射計算簡單，硬件計算資源開銷很小.

TMMU 可以實現(xiàn)對樹表的動態(tài)維護.新建或刪除B+樹時，TMMU 根據(jù)對內(nèi)存空間動態(tài)申請或釋放的結(jié)果，在樹表映射表中根據(jù)有效位信息增加或刪除相應(yīng)的tree_ID與樹表信息的記錄.指令拆分或合并節(jié)點時，TMMU 負責修改樹表中樹的深度和節(jié)點個數(shù)信息.為簡化樹表管理，規(guī)定增加節(jié)點時邏輯地址相應(yīng)加1，刪除節(jié)點時不修改原有節(jié)點的邏輯地址，下次增加節(jié)點仍然在現(xiàn)有邏輯地址的基礎(chǔ)上遞增.這樣的實現(xiàn)方式雖然造成節(jié)點刪除時存儲空間的浪費（這種空間損失代價很小，每一個節(jié)點僅占樹表結(jié)構(gòu)的1/218），但能夠極大地簡化樹表管理的控制邏輯.

TMMU 的另一個主要功能是充分利用內(nèi)存讀寫帶寬，實現(xiàn)高效的內(nèi)存讀寫.隨著指令控制單元依次解析指令隊列中的指令內(nèi)容，TMMU 接收到節(jié)點邏輯地址后立即計算物理地址，內(nèi)存管理單元打開內(nèi)存通道，將對應(yīng)內(nèi)存空間內(nèi)的數(shù)據(jù)傳遞到指定的計算單元.TMMU 對數(shù)據(jù)的處理是連續(xù)的，即只要接收到指令流的邏輯地址，則執(zhí)行物理地址的計算并打開數(shù)據(jù)通道，對內(nèi)存塊內(nèi)的數(shù)據(jù)進行緩存.該設(shè)計相當于實現(xiàn)了計算引擎的數(shù)據(jù)預取，消除計算時數(shù)據(jù)讀寫所引入的I/O 訪問延遲.TMMU 通過緩存機制實現(xiàn)內(nèi)存的連續(xù)訪問并形成數(shù)據(jù)通道.每個計算引擎獨占1 個數(shù)據(jù)通道，TMMU 以輪詢的方式依次打開并完成數(shù)據(jù)傳輸，能夠充分利用內(nèi)存的高讀寫帶寬.

5.3 流式計算引擎設(shè)計

對于單計算節(jié)點，提出設(shè)計流式計算架構(gòu)以支持高效的索引計算.流式處理引擎不需要復雜的控制電路，計算以數(shù)據(jù)流為驅(qū)動，即只要在輸入端有數(shù)據(jù)則計算會持續(xù)進行，不需要復雜的狀態(tài)控制機制.流式計算引擎能夠最大程度提升單節(jié)點的計算性能.單個計算引擎的內(nèi)部結(jié)構(gòu)如圖9 所示.計算引擎內(nèi)有1 個地址緩存單元和1 個節(jié)點緩存單元，分別用于暫存TMMU 傳遞到計算引擎的節(jié)點地址和節(jié)點內(nèi)容.讀數(shù)據(jù)緩存FIFO 按照8B 對齊的原則讀取數(shù)據(jù)緩存單元內(nèi)的節(jié)點數(shù)據(jù)，以指針和關(guān)鍵字組的順序依次寫入.只要讀數(shù)據(jù)緩存FIFO 不為空，則比較器執(zhí)行待比較關(guān)鍵字與節(jié)點內(nèi)關(guān)鍵字的比較.讀寫控制單元由指令操作碼決定其打開或關(guān)閉.如果操作碼指示了關(guān)鍵字的插入或刪除，讀寫控制單元打開，節(jié)點地址緩存當前節(jié)點的地址，寫數(shù)據(jù)緩存FIFO 依次讀取節(jié)點內(nèi)的數(shù)據(jù)內(nèi)容.當定位到待比較關(guān)鍵字的位置，寫數(shù)據(jù)緩存FIFO 根據(jù)指令控制插入或刪除待比較關(guān)鍵字并更新指針內(nèi)容.節(jié)點內(nèi)關(guān)鍵字全部寫入寫緩存FIFO 后，讀寫控制打開內(nèi)存通道，根據(jù)地址緩存中的地址更新節(jié)點內(nèi)容.由于索引維序的前序依賴是關(guān)鍵字查詢，在同構(gòu)計算引擎設(shè)計中，硬件資源的冗余開銷只有讀寫控制單元和寫數(shù)據(jù)緩存2 部分.相較于異構(gòu)計算引擎的復雜狀態(tài)控制來說，這部分硬件資源冗余幾乎可以忽略.

計算引擎的執(zhí)行過程以流水線方式進行，工作流程按照查詢和維序過程分為2 大類.查詢時，讀寫控制無效，僅有讀數(shù)據(jù)緩存、比較和結(jié)果寫回3 個階段.當比較器得到待查詢關(guān)鍵字期望位置時，輸出關(guān)鍵字所在位置的指針信息.期望位置是指，葉子節(jié)點內(nèi)關(guān)鍵字相等，或內(nèi)部節(jié)點中關(guān)鍵字大于前一個關(guān)鍵字且小于后一個關(guān)鍵字.此時，如果葉子節(jié)點沒有相等關(guān)鍵字，則輸出不存在該數(shù)據(jù).輸出的指針信息為葉子節(jié)點的衛(wèi)星數(shù)據(jù)或等值節(jié)點邏輯地址，以及內(nèi)部節(jié)點的葉子節(jié)點的邏輯地址.插入或刪除時，讀寫控制有效，包括讀數(shù)據(jù)緩存、比較、寫數(shù)據(jù)緩存和結(jié)果寫回4 個階段.指令打開讀寫控制單元，寫數(shù)據(jù)緩存將讀數(shù)據(jù)緩存內(nèi)數(shù)據(jù)和待比較關(guān)鍵字根據(jù)比較結(jié)果的期望順序依次讀入.期望順序是指大于前一個關(guān)鍵字且小于后一個關(guān)鍵字，或存在與原有關(guān)鍵字相等的等值節(jié)點則輸出指向等值節(jié)點的邏輯地址.

為簡化節(jié)點的地址管理，降低節(jié)點動態(tài)維護的開銷，對節(jié)點的合并和拆分進行規(guī)定：當且僅當節(jié)點內(nèi)數(shù)據(jù)為空才執(zhí)行節(jié)點的刪除，當且僅當節(jié)點內(nèi)數(shù)據(jù)量超過512 B 時才執(zhí)行節(jié)點的創(chuàng)建.節(jié)點刪除需要刪除上層父節(jié)點中的指針和索引關(guān)鍵字.節(jié)點的插入對當前層節(jié)點進行修改，寫數(shù)據(jù)緩存將前一半指針和關(guān)鍵字組寫入當前節(jié)點，將后一半指針和關(guān)鍵字組寫入新的節(jié)點地址空間，并在上層父節(jié)點中插入關(guān)鍵字和指針信息.這2 種操作需要同時更新TMMU 中樹表的深度、節(jié)點數(shù)等信息.

5.4 指令控制子系統(tǒng)

指令控制子系統(tǒng)主要包括指令解析模塊、計算控制單元和內(nèi)存控制單元，其結(jié)構(gòu)如圖10 所示.其中，指令解析單元分離指令中的操作數(shù)和操作碼，解析索引計算類型及節(jié)點和樹表邏輯地址.計算控制單元查詢處理引擎的執(zhí)行狀態(tài)，啟動可執(zhí)行的計算.內(nèi)存控制單元將邏輯地址寫入TMMU 完成地址映射，判定編號為tree_ID樹的執(zhí)行情況，并打開可訪問的編號為tree_ID樹的內(nèi)存地址，完成處理引擎對數(shù)據(jù)的緩存.

Fig.10 Instruction control system圖10 指令控制系統(tǒng)

為提升系統(tǒng)性能，設(shè)計多個同構(gòu)計算引擎以實現(xiàn)指令集并行.計算引擎的并行由指令控制單元和內(nèi)存控制單元共同管理，其結(jié)構(gòu)如圖11 所示.計算控制單元為每個處理引擎維護一個寄存器，寄存器中包含處理引擎是否空閑標志位Dest_ID、處理引擎正在執(zhí)行的操作類別及處理引擎在處理的tree_ID信息.計算控制單元獲取指令隊列中的首條指令，查詢處理引擎寄存器信息，找到空閑的處理引擎，并判斷當前指令及所有正在執(zhí)行狀態(tài)的處理引擎中是否存在對該指令tree_ID的更新操作.有則阻塞指令并發(fā)；否則發(fā)送指令操作碼到該空閑的計算引擎，并修改寄存器相關(guān)信息.最大指令并行數(shù)與計算引擎數(shù)目相同.當計算引擎狀態(tài)寄存器Dest_ID空間被賦值，說明計算引擎已經(jīng)完成對本條指令的執(zhí)行，此時可以修改寄存器標識為當前計算引擎為空閑，并清除執(zhí)行信息.

Fig.11 Design of homogenous fully functional multiprocessing engines圖11 同構(gòu)的全功能多處理引擎設(shè)計

5.5 指令設(shè)計

為配合系統(tǒng)的執(zhí)行，設(shè)計支持的索引操作的指令如表1 所示.指令集包含2 類指令：基本指令和附加指令.其中基本指令是直接規(guī)定索引和樹操作的指令，包括樹的操作和關(guān)鍵字操作2 類；附加指令用于部分基本指令的重定義和操作控制，包括范圍查詢和關(guān)鍵字更新2 類附加指令.

Table 1 Design of Instruction Set表1 指令集設(shè)計

5.6 B+樹子樹系統(tǒng)

由于索引維序操作與其他操作之間存在強數(shù)據(jù)依賴，設(shè)計一種子樹結(jié)構(gòu)以解除這種數(shù)據(jù)依賴，其結(jié)構(gòu)如圖12 所示.子樹結(jié)構(gòu)使得對1 棵大樹的一次性訪問可以拆分為多棵子樹的多路訪問.也就是說，操作指令將不再以原始大樹的根節(jié)點作為源操作數(shù)，而是以子樹所在連續(xù)空間的起始地址作為訪存的入口地址，只要讀寫不同子樹空間，則對同棵大樹操作的多條指令可以并行.

Fig.12 Sub-tree structure and TMMU management圖12 子樹結(jié)構(gòu)和TMMU 管理

為降低對子樹入口地址管理的復雜度，并提升子樹劃分方式的靈活性，將1 棵大樹的內(nèi)存地址空間（即樹表）等分為幾段連續(xù)子空間，以每部分子空間的起始地址作為子樹的入口地址.子樹入口地址為

其中i表示在大樹中的第i棵子樹（i從0 開始計數(shù)），子樹空間subtree_space的單位為MB.

對齊的子樹空間設(shè)計降低了內(nèi)存地址管理的復雜性，也降低了地址映射計算資源的開銷.子樹的大小可以由地址空間范圍劃分方法靈活決定，即子樹空間劃分粒度可以根據(jù)實際應(yīng)用需求設(shè)定，這種設(shè)計方式實現(xiàn)了靈活性與高效性的權(quán)衡.從而，在不同數(shù)據(jù)量和并發(fā)查詢請求需求下，有效提升B+樹的并行讀寫效率，避免引入復雜的子樹空間管理開銷.子樹劃分對查詢操作性能和資源的影響在第6 節(jié)中具體評估.

為維護子樹的狀態(tài)，在TMMU 的根節(jié)點映射表中加入與邏輯地址對應(yīng)的子樹的層數(shù)及內(nèi)部節(jié)點數(shù)的記錄.在插入新的索引關(guān)鍵字時，為均衡子樹的訪問頻率，在TMMU 中加入一個專用的輪詢仲裁器管理子樹空間的訪存順序：按照子樹的內(nèi)存空間順序依次檢查子樹空間的訪問狀態(tài)，在可訪問時申請對子樹的訪問，否則對下一棵子樹進行檢查.

顯然，子樹的引入改變了B+樹索引構(gòu)建的方式.為配合子樹結(jié)構(gòu)，提出支持查詢和維序的優(yōu)化設(shè)計，其優(yōu)化進程如圖13 所示.在B+樹索引構(gòu)建及新關(guān)鍵字插入時，計算引擎按照B+樹創(chuàng)建指令的要求從內(nèi)存中申請開辟一段連續(xù)的空間用于存放樹表，即邏輯結(jié)構(gòu)上的1 棵完整B+樹.隨后，將此段空間平均分配為n段連續(xù)子空間，并在TMMU 中分別記錄這幾棵子樹的信息.在當前樹表中，每插入1 個新的關(guān)鍵字，則以輪詢的方式依次分配1 段子空間入口地址，依照關(guān)鍵字插入的順序依次在子樹中插入索引關(guān)鍵字.按照這樣的規(guī)則，子樹仍然保持B+樹的特征，但子樹構(gòu)成的大樹不維持邏輯索引結(jié)構(gòu).引入子樹結(jié)構(gòu)能夠提升數(shù)據(jù)維護時樹的并行讀寫效率.根據(jù)TMMU 的設(shè)計原則，對樹的管理也不會由于引入子樹空間而過于復雜.

Fig.13 Sub-tree structure and query optimization圖13 子樹結(jié)構(gòu)和查詢優(yōu)化

子樹系統(tǒng)改變了索引指令的尋址方式，影響了指令的執(zhí)行過程.關(guān)鍵字插入可以按輪詢的方式選擇子樹.但是，查詢和刪除需要定位關(guān)鍵字所在的葉子節(jié)點，不能以輪詢的方式選擇子樹，而大樹沒有邏輯上的索引結(jié)構(gòu)，需要引入一種快速定位到包含關(guān)鍵字的子樹的機制.為準確定位查詢和刪除操作中關(guān)鍵字所在的子樹，在子樹空間選擇前加入1 級布隆過濾器[13].布隆過濾器是一種快速判斷某元素是否在集合中的功能部件.利用布隆過濾器提前過濾1 次關(guān)鍵字的位置，就可以快速定位關(guān)鍵字所在的子樹空間.將該子樹的入口地址發(fā)送到空閑的計算引擎，子樹內(nèi)執(zhí)行查找和刪除與大樹完全相同.子樹系統(tǒng)使得索引查詢引入了1 級布隆過濾器的計算開銷，計算只需要幾個周期，對性能的影響幾乎可以忽略.

5.7 系統(tǒng)工作流程：多索引查詢指令

基于5.1～5.6 節(jié)所述的系統(tǒng)實現(xiàn)，我們以多條索引查詢指令為例，介紹系統(tǒng)運行的過程，如圖14 所示.當用戶發(fā)出多指令請求時，指令按照順序依次進入指令隊列.①指令處理：指令處理單元將按照隊列順序依次處理隊列中的各條指令.②指令解析：指令處理單元將得到的指令逐條解析，得到操作數(shù)和操作碼.③激活TMMU：操作數(shù)中對B+樹的訪存地址傳遞到TMMU.TMMU 查詢子樹的訪存狀態(tài)，進行邏輯地址與物理地址的映射，得到子樹的入口物理地址.④打開數(shù)據(jù)通道：按照子樹的內(nèi)存地址輪詢結(jié)果，內(nèi)存管理單元打開可用的內(nèi)存數(shù)據(jù)通道，使得節(jié)點內(nèi)容能夠到達相應(yīng)的計算節(jié)點.⑤激活指令控制單元：操作碼和操作數(shù)中的關(guān)鍵字被傳遞到指令執(zhí)行單元，指令執(zhí)行單元管理計算引擎.⑥計算引擎：指令控制單元依次查詢計算引擎狀態(tài)，激活空閑計算單元，修改相關(guān)寄存器內(nèi)容.若沒有空閑計算引擎則等待，直到找到空閑計算引擎.其中①②隨指令流的控制連續(xù)不斷地執(zhí)行；③④和⑤⑥為異步控制.⑦執(zhí)行計算：計算引擎按照操作數(shù)和操作碼的指令，啟動查詢或節(jié)點修改的執(zhí)行流程.⑧結(jié)果寫回：查詢時，僅輸出查詢關(guān)鍵字指向的衛(wèi)星數(shù)據(jù)的地址.更新時，則按照寫數(shù)據(jù)緩存內(nèi)容和地址緩存中的地址修改相應(yīng)節(jié)點內(nèi)容.如果葉子節(jié)點需要刪除，無需寫回數(shù)據(jù)，只修改父節(jié)點及 TMMU 中的相關(guān)信息.如果節(jié)點需要拆分，則將數(shù)據(jù)均等分為2 部分，分別寫入2 個節(jié)點，并修改父節(jié)點和TMMU 相關(guān)信息.

Fig.14 Index query of B+tree accelerating system圖14 B+樹加速系統(tǒng)的索引查詢

6 實驗和評估

6.1 實驗搭建

實驗的硬件平臺利用PCIe 接口搭建CPU 服務(wù)器與FPGA 板卡互聯(lián)的異構(gòu)計算系統(tǒng).CPU 型號為Intel Xeon Gold 5218（@2.30GHz）配備22 MB 的L3 緩存和64 GB 的內(nèi)存（DDR4-2667）.FPGA 板卡選用Xilinx Alveo 的U200，U50，U280 數(shù)據(jù)中心加速卡.CPU與FPGA 的互聯(lián)接口為PCIe3.0 ×16 總線.實驗分別測試3 種不同資源配置（即異構(gòu)系統(tǒng)選擇不同F(xiàn)PGA板卡）下本方案的性能.FPGA 加速板卡具體資源配置情況如表2 所示.

3 個板卡的主要區(qū)別在于其硬件邏輯資源和內(nèi)存帶寬限制不同.U200 邏輯資源充足但內(nèi)存帶寬受限，其上僅配備了DDR4 作為存儲資源，可提供76.8 GBps存儲帶寬；U50 是一種輕量級的板卡，其硬件邏輯資源是三者之中最少的，但它使用了第二代高帶寬內(nèi)存（high bandwidth memory，HBM）資源HBM2，內(nèi)存帶寬能夠達到316 GBps；U280 則是三者之中性能最高的，其硬件邏輯資源最多，且內(nèi)存使用DDR4 和HBM2，既保證了存儲空間大且?guī)捀哌_460 GBps.

為評估數(shù)據(jù)庫索引的查詢和維序性能，實驗的數(shù)據(jù)和程序選擇數(shù)據(jù)庫基準測試程序TPC-C 中提供的標準數(shù)據(jù)庫表生成數(shù)據(jù)和聯(lián)機事務(wù)處理（on-line transaction processing, OLTP）程序，以充分測試數(shù)據(jù)庫表記錄的查詢、刪除、插入和更新的實際性能[14].TPC- C 數(shù)據(jù)集用9 個相關(guān)的數(shù)據(jù)表記錄了某類倉庫在不同地區(qū)的存貨量、存儲的不同商品庫存以及地區(qū)消費者信息和貨物訂單等信息.在這9 個數(shù)據(jù)表中，選擇最大數(shù)據(jù)表order_line 作為本實驗測試用數(shù)據(jù).測試數(shù)據(jù)表的查詢、插入、刪除和更新性能，對應(yīng)TPC-C 基準測試中訂單信息查詢、提交客戶新交易申請、交易結(jié)束刪除訂單信息，以及訂單修改申請.實驗運行所選擇的關(guān)系型數(shù)據(jù)庫為典型的MySQL數(shù)據(jù)庫.在本實驗測試中，測試用的數(shù)據(jù)庫表數(shù)據(jù)仍然存在CPU 主機上，僅在 FPGA 板上內(nèi)存預先存儲需要構(gòu)建索引的部分表信息.此時認為HyperTree 可以屏蔽與CPU 進行數(shù)據(jù)傳輸?shù)拈_銷；HyperTree 可以單獨完成指令要求的索引操作，即從索引構(gòu)建并存儲B+樹索引數(shù)據(jù)，到完成相應(yīng)的事務(wù)處理的全過程.實驗的比較基準選擇CPU 并行執(zhí)行TPC-C 數(shù)據(jù)庫索引查詢和維序的性能.進一步評估實驗結(jié)果，選擇目前具有最優(yōu)效果的基于 GPU 實現(xiàn)的 B+樹索引加速系統(tǒng)結(jié)果[5,7]以及基于FPGA 實現(xiàn)的B+樹加速器結(jié)果[10-11]進行對比和分析.

在6.2 和6.3 節(jié)中，以Alveo U200 板卡作為B+樹索引加速系統(tǒng)HyperTree 的硬件實現(xiàn)原型.此配置方法能夠均衡考慮片上硬件計算資源和帶寬資源的限制，設(shè)計32 個并行的計算節(jié)點和32 路數(shù)據(jù)通道實現(xiàn)對資源的充分利用（具體細節(jié)評估見6.4 節(jié)），配置信息見表3.在這樣的系統(tǒng)配置環(huán)境下，能夠充分利用FPGA 板卡的內(nèi)存帶寬資源，且不會引入冗余的計算引擎，引入不必要的硬件開銷.

Table 3 Hardware Configuration of B+tree Index Accelerator Using Alveo U200 FPGA Board表3 基于Alveo U200 FPGA 板卡的B+樹索引加速器硬件配置

6.2 索引查詢性能

本節(jié)主要評價多查詢語句的并行性能.以6.1 節(jié)中介紹的實驗環(huán)境和實驗數(shù)據(jù)為基礎(chǔ)，實現(xiàn)B+樹索引加速系統(tǒng)HyperTree.實驗評估指標有2 個：一是以每秒執(zhí)行查詢指令數(shù)目條數(shù)QPS（query per second）作為衡量系統(tǒng)性能的指標，其中實驗結(jié)果QPS 實際值的數(shù)量級為百萬條每秒；二是以指令平均響應(yīng)時間衡量每條指令的執(zhí)行時間，用于驗證OLTP 是否滿足應(yīng)用系統(tǒng)的實時需求.

評估數(shù)據(jù)庫表的數(shù)據(jù)量對系統(tǒng)性能的影響.為充分釋放處理引擎的并行度，指定實驗中測試的并發(fā)指令數(shù)目為 32.在實驗中按照樹表格式的設(shè)計規(guī)則，將數(shù)據(jù)庫表大小的不同直接換算為B+樹索引中節(jié)點數(shù)目的不同，從而可以以節(jié)點數(shù)目的差別描述不同容量的B+樹.由于比較基準測試中節(jié)點格式不同，節(jié)點可存儲的關(guān)鍵字數(shù)量存在差別.后序?qū)嶒灋楣綄Ρ?，每組實驗均基于具有相同節(jié)點數(shù)目的 B+樹完成.事實上，基于CPU 和文獻[10]中的方法所生成的B+樹要比HyperTree 基于規(guī)則節(jié)點格式生成的B+樹更小.由此，為公平地評估不同 B+樹索引加速系統(tǒng)的性能隨數(shù)據(jù)量的變化，實驗結(jié)果的對比保持B+樹的節(jié)點數(shù)目的數(shù)量級一致，且在樹結(jié)構(gòu)的限制下盡可能保證數(shù)量相近.實驗評估時，以B+樹索引加速系統(tǒng)HyperTree 生成的 B+樹的容量作為數(shù)據(jù)量數(shù)量級的基準，圖15“數(shù)據(jù)量”指HyperTree 生成的樹.此外，由于樹存儲格式的設(shè)計具有明顯區(qū)別，后續(xù)的實驗結(jié)果對比也僅考慮節(jié)點數(shù)目相同或維持同一數(shù)量級，而不直接以樹的大小作為實驗性能對比的指標.

Fig.15 Normalized throughput of B+tree accelerator圖15 B+樹加速器的歸一化吞吐量

圖15 顯示了系統(tǒng)在B+樹的數(shù)據(jù)量變化下指令查詢的歸一化性能（以CPU 單值查詢?yōu)閱挝?）.當在小數(shù)據(jù)量測試環(huán)境下時系統(tǒng)的吞吐量大約是CPU的11.14 倍；當在大數(shù)據(jù)量的情況時，系統(tǒng)的查詢性能提升大約為CPU 的6.84 倍.小數(shù)據(jù)量時獲得顯著性能提升的原因主要是：緊湊的節(jié)點存儲使得進行B+樹查詢時層間跳數(shù)更少，且節(jié)點規(guī)則格式設(shè)計使系統(tǒng)對內(nèi)存帶寬利用更加高效.大數(shù)據(jù)量時，B+樹索引系統(tǒng)HyperTree 在進行關(guān)鍵字查詢時需要更多層內(nèi)部節(jié)點來構(gòu)建索引，從而增加了內(nèi)部節(jié)點層間的跳數(shù)，使得查詢平均延遲增加.實驗結(jié)果表明，B+樹索引加速系統(tǒng)相比CPU 能夠獲得顯著的性能提升.這一結(jié)果遠超于文獻[10]中利用FPGA 實現(xiàn)的B+樹索引查詢方案所獲得的結(jié)果，相較于CPU 性能僅平均提升1.31～2.24 倍.

在多指令并發(fā)查詢的實驗中，以TPC-C 數(shù)據(jù)集提供的order_line 表為模板，按照規(guī)定的數(shù)據(jù)格式隨機生成數(shù)據(jù)表，每個表包含 6.5～26.2 萬行記錄.這樣，利用其中待查詢的關(guān)鍵字段構(gòu)建 B+樹索引可以保證單棵樹內(nèi)的節(jié)點全部有效，從而節(jié)點的數(shù)量級維持在 105，大約要求樹表有效節(jié)點存儲空間的容量為10～128 MB.實驗設(shè)計單值查詢和范圍查詢2 類查詢指令，單次并發(fā)指令數(shù)目從10 條開始以10 倍量級遞增至100 萬條.圖16 顯示了系統(tǒng)在不同指令并發(fā)狀態(tài)下歸一化后的系統(tǒng)性能（以CPU 單值查詢?yōu)閱挝?）.當并發(fā)指令數(shù)目為10 時，計算引擎沒有被占滿，此時系統(tǒng)的性能明顯低于其他多指令并發(fā)，但仍是CPU 性能的3.21 倍.隨著并發(fā)指令數(shù)的增加，由于查詢關(guān)鍵字在節(jié)點內(nèi)的位置具有不確定性，系統(tǒng)性能具有一定波動性，但與32 條指令并發(fā)的最優(yōu)性能大體一致.與CPU 在范圍查詢時性能顯著下降有所不同，B+樹索引加速系統(tǒng)HyperTree 的32 長度的范圍查詢的性能大約是其單值查詢的75.58%，性能損失不明顯，能夠達到 CPU 性能的 14.53 倍.這是由于B+樹索引加速系統(tǒng)的規(guī)則大節(jié)點設(shè)計以及高效的并發(fā)讀寫機制，在范圍查詢時進行葉子節(jié)點讀寫過程中能夠以較小的節(jié)點跳樹實現(xiàn)大范圍的查詢.實驗結(jié)果表明，B+樹索引加速系統(tǒng)能夠在多指令并發(fā)的情況下維持高效的系統(tǒng)查詢性能.

Fig.16 Normalized throughput of parallel data query instructions圖16 歸一化的并行數(shù)據(jù)查詢指令吞吐量

子樹的引入對索引查詢無顯著影響.一方面，子樹的引入只要求增加1 層布隆過濾器計算，F(xiàn)PGA 實現(xiàn)該計算過程只需要幾個周期；另一方面，即使增加到32 棵子樹，樹表容量的數(shù)量級仍然維持在105.因此，子樹的引入對索引查詢性能的影響很小，幾乎可以忽略不計，所以這一部分實驗不再評估子樹的引入對索引查詢性能的影響.

將該結(jié)果與GPU 優(yōu)化的B+樹進行對比.參考文獻[5,7]中利用GPU 優(yōu)化B+樹存儲結(jié)構(gòu)的多語句并行查詢結(jié)果：GPU 實現(xiàn)的樹的容量為128 MB（只存儲關(guān)鍵字，不存儲衛(wèi)星數(shù)據(jù)）時，相較于CPU 實現(xiàn)的標準B+樹，單值查詢性能提升20.41 倍，范圍查詢性能提升23.91 倍.然而，由于GPU 優(yōu)化的樹結(jié)構(gòu)中只保留存儲關(guān)鍵字的中間節(jié)點，這一方案也只能定位關(guān)鍵字在哪一個葉子節(jié)點，并沒有最終找到數(shù)據(jù)庫中的衛(wèi)星數(shù)據(jù)，因而與本實驗實現(xiàn)的環(huán)境難以直接進行對比.一旦加入對衛(wèi)星數(shù)據(jù)的尋址過程，會極大地損失GPU 的查詢性能.同時，范圍查詢的性能提升要比單值查詢更顯著的原因是，CPU 實現(xiàn)范圍查詢時存在一定性能損失，其單值查詢（比較基準）性能比范圍查詢具有2.36 倍的增益.如果以CPU 單值查詢的性能為基準，GPU 實現(xiàn)的B+樹加速系統(tǒng)的范圍查詢性能提升大約為11.22 倍，僅為單值查詢性能提升結(jié)果的50%左右.而本文所提出的B+樹索引加速系統(tǒng)HyperTree 能夠有效支持范圍查詢，性能損失大約80%.

6.3 索引維序性能

本節(jié)主要評價系統(tǒng)的索引維序性能.在B+樹索引加速系統(tǒng)中，除了設(shè)計多數(shù)據(jù)通道和并行計算引擎以加速索引查詢外，還針對索引維序時由于數(shù)據(jù)沖突所導致的索引維序性能瓶頸提出子樹的設(shè)計思想.以6.1 節(jié)中介紹的實驗環(huán)境和6.2 節(jié)中B+樹索引占滿樹表空間的環(huán)境為基礎(chǔ)，搭建B+樹索引加速系統(tǒng)實驗環(huán)境.通過增加子樹的棵數(shù)，評估子樹系統(tǒng)設(shè)計對索引維序性能帶來的提升.實驗以索引插入指令為例，子樹棵數(shù)從1 棵開始（即1 棵大樹，不實現(xiàn)子樹系統(tǒng)），以2 的冪次增長，直到32 棵為止.實驗結(jié)果以單棵樹的插入性能（QPS）為歸一化的單位1.如圖17所示，實驗結(jié)果表明隨著子樹棵數(shù)的增加，索引插入的并行性能取得顯著提升：當子樹棵數(shù)增加到32 時，系統(tǒng)性能提升約29.14 倍；且由于資源占用而導致的計算阻塞延遲也顯著降低.相比文獻[11]基于FPGA實現(xiàn)的B+樹索引查詢系統(tǒng)對索引更新操作會引入大約70%性能下降這一結(jié)論，HyperTree 能夠有效解決這一問題.另一方面，比較基準文獻[11]所提出的 CPUFPGA 優(yōu)化架構(gòu)并沒有實現(xiàn)顯著的索引維序性能提升，而僅通過優(yōu)化調(diào)度 CPU 和 FPGA 的計算執(zhí)行，使一些不適合利用 FPGA 加速的維序計算由性能更高的CPU 取代，由此并沒有充分利用FPGA 計算性能.

Fig.17 Parallelism of sub-tree圖17 子樹并行性

將該結(jié)果與GPU 優(yōu)化的B+樹進行對比.參考文獻[5,7]中利用GPU 實現(xiàn)的一種優(yōu)化的B+樹存儲結(jié)構(gòu)的關(guān)鍵字插入結(jié)果：實驗執(zhí)行GPU 實現(xiàn)的B+樹容量為128 MB（只存儲關(guān)鍵字，不存儲衛(wèi)星數(shù)據(jù)）時，其更新性能大約僅為CPU 實現(xiàn)的標準B+樹的72%.這也進一步說明B+樹的維序操作是索引性能損失的關(guān)鍵因素.而HyperTree 的子樹解耦合的數(shù)據(jù)存儲方法能夠解決由于索引維序?qū)?shù)據(jù)的獨占性而導致的計算并行困難的問題，從而有效提升索引維序的性能，均衡提升 B+樹查詢和維序性能.

6.4 計算架構(gòu)的可擴展性

本節(jié)評估B+樹索引加速系統(tǒng)的可擴展性.計算架構(gòu)的可擴展性可以衡量一種計算架構(gòu)設(shè)計在增加計算節(jié)點時，硬件資源需求的增加情況以及實際性能的提升倍率.利用不同硬件平臺實現(xiàn)B+樹索引加速系統(tǒng)，可以衡量該計算架構(gòu)設(shè)計是否能夠充分利用板卡資源，以較小的邊際硬件資源成本獲得系統(tǒng)性能提升.在本節(jié)實驗中，選用Xilinx Alveo U200，U50，U280 這3 個不同資源配置的FPGA 板卡來實現(xiàn)B+樹索引加速器系統(tǒng)HyperTree.這3 個板卡中限制系統(tǒng)性能的因素不同：U200 的帶寬資源受限，U50 的硬件邏輯單元受限，U280 則沒有資源受限（在本實驗的實現(xiàn)架構(gòu)設(shè)計情況下）.

評價計算架構(gòu)的可擴展性，可以通過增加系統(tǒng)中的計算引擎數(shù)目，評估系統(tǒng)硬件資源的使用情況及系統(tǒng)帶寬性能.在實驗中，設(shè)計系統(tǒng)的計算引擎數(shù)目從4 開始，以2 的冪次依次增長，直到256 個截止（受硬件邏輯資源限制，U50 僅支持128 個計算引擎）.本測試實驗所實現(xiàn)的子樹棵數(shù)與處理引擎數(shù)目相同，指令并發(fā)數(shù)目與處理引擎數(shù)目也相同.假設(shè)一種理想的實驗環(huán)境，即滿足處理引擎能夠無空閑地執(zhí)行索引計算.所獲得的QPS 值為理想條件下的結(jié)果，即沒有數(shù)據(jù)沖突且處理引擎全部并發(fā).實驗結(jié)果能夠綜合評估處理引擎、數(shù)據(jù)存儲和子樹系統(tǒng)的性能提升，結(jié)果如表4 所示.

Table 4 The Scalability of B+tree Accelerator表4 B+樹加速器的可擴展性

U200 板卡的內(nèi)存帶寬標稱性能為76.8 GBps，為最大化利用內(nèi)存帶寬資源，當計算引擎數(shù)目為32 時，內(nèi)存帶寬資源可以達到41.8 GBps，基本實現(xiàn)了帶寬的最優(yōu)利用效率，相對于CPU 歸一化的QPS 可以達到174.78.計算引擎再翻倍后，受物理內(nèi)存帶寬的限制，系統(tǒng)整體性能不會進一步增長，反而造成計算引擎的冗余，即由于缺少計算所需數(shù)據(jù)而出現(xiàn)計算引擎空閑，造成硬件邏輯資源的浪費.U50 板卡由于使用HBM 資源能夠提供316 GBps 的理論內(nèi)存帶寬.為充分利用這一高內(nèi)存帶寬資源，實驗結(jié)果表明，配置128 個計算引擎能使系統(tǒng)資源的利用性能達到最優(yōu).此時，限制計算性能的因素是U50 片上的其他硬件計算資源的數(shù)目無法支持更多計算引擎.而U280 板卡是三者之中帶寬性能和硬件邏輯資源都最豐富的，其標稱內(nèi)存帶寬可以達到460 GBps.在片上實現(xiàn) 256個計算引擎，系統(tǒng)帶寬性能可以提升至302.3 GBps，相對于CPU 歸一化的QPS 可以達到1 258.12.實驗結(jié)果表明，B+樹索引加速系統(tǒng)具有很好的可移植性，能夠充分利用板卡資源，擴展設(shè)計時只需引入很小的硬件資源開銷即可實現(xiàn)索引查詢和更新性能的線性提升.

7 結(jié) 論

為解決大數(shù)據(jù)環(huán)境下，數(shù)據(jù)庫查詢和更新的性能，本文提出一種支持B+樹索引加速的系統(tǒng)，從訪存和計算2 方面協(xié)同加速數(shù)據(jù)庫索引操作.為提升內(nèi)存讀寫帶寬的利用效率，設(shè)計規(guī)則的樹表存儲結(jié)構(gòu)和高效的節(jié)點存儲格式，規(guī)定讀寫控制以單節(jié)點為單位，使讀寫帶寬可以達到68.8 GBps.為提升系統(tǒng)執(zhí)行性能，設(shè)計同構(gòu)的多計算引擎，支持語句級并行.相比CPU，B+樹索引加速系統(tǒng)能夠?qū)崿F(xiàn)14.53 倍的查詢性能提升.同時，為緩解索引插入和刪除操作的數(shù)據(jù)依賴，設(shè)計一種子樹存儲結(jié)構(gòu)，支持多子樹插入及更新的并行，降低索引刪除的數(shù)據(jù)依賴，進一步提升索引的維序性能.相較于單棵大樹，子樹系統(tǒng)能夠提升索引插入性能29.14 倍.

作者貢獻聲明：吳婧雅負責整理相關(guān)文獻，提出問題解決方法，完成實驗驗證及撰寫論文；盧文巖提出設(shè)計實驗方案并實現(xiàn)優(yōu)化方案；鄢貴海和李曉維提供實驗環(huán)境支持，指導論文撰寫及修改論文.