SBS：基于固態盤內部并行性的R-樹高效查詢算法

陳玉標 李建中 李英姝,2

1(哈爾濱工業大學計算機科學與技術學院 哈爾濱 150001)

2(佐治亞州立大學計算機科學與技術學院 美國佐治亞州亞特蘭大 30303)(chenyubiao@hit.edu.cn)

閃存固態盤以其耗能低、體積小、高可靠性、讀寫速度快等特點，快速地取代機械硬盤，成為無論是個人電腦，還是數據中心的主流存儲設備.與此同時，技術的進步和越來越多的硬件資源被集成進固態盤，使固態盤擁有豐富的內部并行性[1-4].近些年，學者們針對該特點，開始研究如何發揮固態盤的內部并行性.例如，一些人開始研究如何利用固態盤內部并行性加速數據庫中一些基礎操作和索引，如數據庫表的掃描與聚集[5]、B+樹[6]、R-樹[7]、LSM-樹[8]、文件系統[9]等.

R-樹是Guttman[10]于1984年提出的用于空間數據管理的樹索引結構，它在理論和實踐中都取得廣泛應用[11]，例如在著名數據庫Spatial Hadoop,MySQL,PostgreSQL和GIS軟件平臺ArcGIS中都支持R-樹索引結構.在R-樹的基礎操作中，范圍查詢是最具有代表性的操作.實際上，對于地理數據，例如GML(geography markup language)文件而言，實際操作主要集中在范圍查詢上，因而范圍查詢的執行效率對于R-樹的性能至關重要.

R-樹的特點有：任意子樹最小外接矩形之間允許重疊，因此即使對于精確匹配查詢操作，其查找路徑也不是唯一的，往往結點的多個子樹都需要被查詢.因此，對于范圍查詢，R-樹索引結點的讀操作往往比較密集.這為利用固態盤的并行性優化R-樹索引提供了可能.

因而，本文主要研究如何利用固態盤內部并行性去加速R-樹的范圍查詢.目前，針對R-樹上范圍查詢的優化工作，主要關注在內存環境下多核和多線程并行發揮和外存環境下機械硬盤的IO減少.新型存儲閃存固態盤的出現，為我們提供了新的存儲特性，除了快速隨機讀寫外，另外還包括固態盤的內部并行性.該特點之前并未被考慮，本文就著重從充分發揮固態盤內部并行性的角度去優化R-樹的范圍查詢操作.

本文的主要貢獻包括3個方面：

1) 提出基于棧結構的范圍查詢算法SBS，該算法能充分發揮固態盤的內部并行性；

2) 從理論上證明SBS的內存使用上界；

3) 針對千萬級別的數據，對本文提出R-樹的范圍查詢算法SBS和另外3種算法進行對比實驗，驗證SBS算法的性能.

1 相關工作

地理信息系統在社會生產和生活中起到非常重要的作用，而該類系統的主要操作為范圍查詢，R-樹作為其存儲數據GML文件上的索引結構，其范圍查詢的性能對于整體系統的性能至關重要.因此對于R-樹范圍查詢的優化具有重要意義.接下來，我們概述R-樹范圍查詢優化的研究工作.

第1類工作：通過縮小MBR(minimal bounding rectangle)加速范圍查詢.在R-樹的范圍查詢過程中，MBR對于判定是否可能存在查詢結果起到至關重要的作用.MBR越大，重疊機率越大，查詢過程中加載索引數據就越多，查詢性能越低.因此，想方設法讓MBR面積更小，就能夠提升R-樹的查詢性能.文獻[12]針對軌跡數據，把軌跡數據分段計算出一種更緊湊的MBR以提升查詢效率.上述算法針對的是特定結構數據，而文獻[13]基于bitmap位圖索引構造出一種通用的縮小MBR的方法.它把MBR化成8×8的位圖，如果對應區域有數據就置為1，否則置為0，這樣就能更細粒度地表達一個數據對象或者子樹的外形，從而能夠盡可能地去減少MBR重疊誤判率.這些縮小MBR的思路都是讓MBR形狀更接近真實數據的分布，還有另外一種思路就是讓數據放得更緊湊一些，以此來縮小MBR.文獻[14]基于希爾伯特曲線將近似的數據盡可能放到一起，這在減少MBR的同時，也可以降低機械硬盤的訪道距離以提升整體的查詢效率.

第2類工作：通過并行執行來加速范圍查詢.在外存機械硬盤環境中，文獻[15]針對單CPU多磁盤的存儲模型設計出索引的存儲策略，當有新的索引結點被創建時，根據算法策略判定該結點的不同磁盤存放位置，使R-樹索引上的范圍查詢可以發揮磁盤的并行性.由于大內存環境的出現，在內存環境中，關于R-樹的研究工作也開始出現，隨著技術的進步，服務器中集成了越來越多的處理器和核，于是文獻[16]開始考慮利用多核多線程的并行來加速R-樹索引，其中包括范圍查詢.另外，GPU的計算能力近些年以驚人的速度增長，文獻[17-19]開始考慮使用GPU加速R-樹索引以及R-樹上的范圍查詢.

第3類工作：根據存儲介質特點來加速范圍查詢.傳統外存存儲介質為機械硬盤，它的代價主要和尋道距離有關，因此機械硬盤對于隨機訪問操作非常不友好.而R-樹的范圍查詢恰恰會產生大量的隨機訪問，文獻[20]針對R-樹的葉子結點訪問，通過skip-sequential prefetch技術使得大量葉子結點的隨機訪問變成順序訪問，以此來減少范圍查詢代價.閃存介質作為一種新型存儲介質擁有和磁盤完全不同的特性，首先是讀寫不對稱，其次是擦除次數有限.因而，針對閃存介質的R-樹優化主要集中在這2點上.近些年，關于R-樹的優化主要考慮減少寫操作來提升R-樹的性能，而為了達到這個目的，額外的讀操作是可以被犧牲來換取更少的寫.宏觀上來看，是犧牲R-樹查詢性能來換取更新操作的性能.其中，文獻[21]通過緩存來減少更新；文獻[22]用批量更新代替即時更新；而文獻[23]把每個結點的更新操作信息存儲到更新日志中，當結點被查詢時，才會將更新操作作用到結點.這無一例外是減少了寫的代價，但卻增加了額外讀的代價.

本文主要從存儲介質特點的角度去考慮對R-樹索引的范圍查詢進行優化.傳統機械硬盤主要考慮查詢過程中減少隨機寫或者是減少尋道距離.而針對閃存存儲介質，基于該介質的讀寫不對稱以及擦除次數有限的特點，優化目的更著重于減少寫操作，也就是更偏向于優化更新操作.而閃存固態盤除了擁有閃存介質的特點外，作為一個整體來看，還擁有豐富的內部并行性.本文考慮如何利用固態盤內部并行性來加速R-樹的范圍查詢.

2 背景介紹

2.1 固態盤的內部并行性

如圖1所示，經典的閃存固態盤包含4個部分：主機接口邏輯模塊、內存緩存模塊、固態盤控制器模塊、閃存包模塊.多個閃存包通過共享的數據通道連接至閃存控制器.一個固態盤通常含有2～10個通道來傳輸數據.在通道數據傳輸中，控制指令執行時間相對于數據傳輸時間非常短，可以忽略不計，因此可以認為通道之間工作是獨立的.同樣也可以認為不同包之間的工作也獨立.那么根據上述描述，在閃存固態盤內部，至少存在2個層級上的并行性：通道級別并行和閃存包級別并行.假設通道為m個，每個通道連接n個閃存包，理論上最大并行度為mn.為了利用上述并行性，需要批量地提交大量的IO請求到每個通道與之連接的每個閃存包來使得固態盤的并行性得到充分發揮.文獻[7]實現一個并行批量提交算法ParallelIO，它的輸入為IO請求集合，輸出為加載結果集.文獻[7]從理論和實驗都證明它能夠實現一個比較可觀的加速效果.本文的優化算法均基于該算法實現.

Fig. 1 The architecture of solid state drive

2.2 R-樹表示和范圍查詢定義

本節給出R-樹索引結構的描述和范圍查詢的定義.

R-樹是目前最廣泛使用的空間索引結構，它本質上是B-樹在高緯的拓展，因此它的索引結構和B-樹類似.對于一棵L階、最大項數為M的R-樹，它的索引結構可以描述為：

(Count,Level,Branch1,Branch2,…,BranchM).

1) 中間結點:Branchi=NPi,MBRi；

2) 葉子結點:Branchi=DPi,MBRi.

其中，Count∈[M2,M)表示結點中有效索引項或數據項數目，當L=0時，即當R-樹根結點又是葉子結點時，允許Count

定義1.范圍查詢.對于外存R-樹索引，輸入根結點r，查詢區域為m，要求從根結點r開始查詢返回m范圍內的所有數據索引集合S.這里S滿足S={DPi|MBRi∩m≠?}.

如圖2就是一棵R-樹和范圍查詢的例子，是一棵L=3和M=4的R-樹.圖2(a)為R-樹的空間結構，圖2(b)為R-樹的索引結構.圖2(a)中的虛線框m表示查詢范圍，圖2(b)中每個結點上的通道號是R-樹索引每個結點的存儲單元連接在8通道固態盤上的通道號.查詢結果就是落在虛線框中的黑色圓點的索引集合.這里假設圖2中R-樹索引每個結點單獨占用固態盤1個物理頁，固態盤讀取1頁的時間為T.本文提出的算法都將通過該R-樹例子來具體說明.

Fig. 2 An example of R-tree index range query

2.3 經典范圍查詢算法NS

本節回顧R-樹經典的范圍查詢算法NS(na?ve search).

算法1.NS(r,m).

輸入：r為R-樹根結點，m為搜索的MBR；

輸出：S為m范圍內的數據索引集合.

①S←?；

② if (r是非葉結點) then

③ for all (brancht∈r.branchs) do

④ if (t.MBR∩m≠?) then

⑤child←read(t.NP)；

⑥NS(child,m)；

⑦ end if

⑧ end for

⑨ else

⑩ for all (brancht∈r.branchs) do

如算法1所示，輸入為R-樹根結點r，查詢區域為m；輸出為查找所有搜索矩形m覆蓋的記錄條目；算法返回查詢數據的索引集合.算法1除去開頭初始化和最后返回結果，主要共分成2個部分：

S1. [查找子樹](行②～⑧).如果r是非葉子結點，并且r所對應的矩形與m有重合，那么檢查所有r中存儲的條目，對于所有這些條目，使用NS操作遞歸作用在每一個條目所指向的子樹的根結點上(即結點r的孩子結點).

下面以圖2為例詳細描述算法1的查詢過程，并給出查詢代價分析.查詢過程從根結點A開始，首先枚舉處理它的第1個兒子結點B，判斷B是非葉子結點，那么進入S1子樹查找模式；枚舉處理B的第1個兒子結點E，判斷E是葉子結點，進入S2葉子結點查找模式；判斷E的兒子結點中落在m范圍的有{P2}，將其放入查詢結果集合S中；E處理完后，繼續枚舉B的兒子結點F和G，它們均為葉子結點，將對應的查詢結果{P5,P6}和{P7,P8,P9}放入S中.以B為根結點的子樹被處理完后，繼續以子樹查找模式處理C,D.最終，將S的查詢結果返回.默認根結點A已經加載至內存，整個過程需要依次加載的索引點為{B,E,F,G,C,H,I,J,D,K,L,M}.根據2.2節的假設讀取一個索引結點的時間為T，那么整個查詢過程IO時間為12T.

可以看出，算法1是簡單的深度優先搜索過程，基于算法1的優化將在第3節并行優化算法部分給出.

3 并行優化算法

在本節中，我們將設計用于R-樹的范圍查詢的優化算法，首先給出一個直觀的基準算法NBS(na?ve batch search)，它能夠在不改變原來搜索策略的同時發揮固態盤的內部并行性；然后，我們給出一個優化算法QBS(queue batch search)，它提供了一種新的搜索策略，這種搜索策略會盡可能將IO讀請求聚集然后批量提交，來使固態盤內部并行性充分發揮，但是它存在一個問題，那就是內存開銷會比較大；最終，為克服上述缺點，我們給出一個有內存上界保證的范圍查詢算法SBS，它能在充分發揮固態盤內部并行性的同時，又能限制內存的開銷在一個可接受的范圍內.需要注意的是輸出結果在具體實現中會先將結果放到寫緩存區中，待緩存區滿再寫到外存中去，因此，文中用于衡量內存最大消耗的空間復雜度將不會把輸出結果的規模計入.相關的的符號解釋如表1所示：

Table 1 The Symbols to Describe Algorithms

3.1 基準算法NBS

在算法1中我們發現，當對每個子樹做查找時，對同一父結點的兒子結點之間的查找操作是相互獨立的，可以被并行加載.基于該原則，給出一個基于經典查詢算法NS的并行優化算法.在經典深度優先范圍查詢算法的基礎上，對于每個訪問的中間結點r，找出所有子結點中和搜索范圍m相交的子結點索引集合，通過批量提交算法ParallelIO加載至內存，然后分別遞歸地進行子樹查找.

算法2.NBS(r,m).

輸入：R-樹根結點r、搜索的MBRm；

輸出：S為m范圍內的數據索引集合.

①S←?；

②read_queue←?；*用于批量讀的隊列*

③ if (r是非葉結點) then

④ for all (brancht∈r.branchs) do

⑤ if (t.MBR∩m≠?) then

⑥read_queue.push(t.NP)；

⑦ end if

⑧ end for

⑨children←ParallelIO(read_queue)；

⑩ for all (nodechild∈children) do

算法2輸入依然為R-樹根結點r、查詢區域m；輸出為查找所有搜索矩形m覆蓋的記錄條目S；算法2主要共分成4個部分：

S1. [初始化](行①～②).初始化用于存放查詢結果的集合和用于批量提交的讀隊列均為空.

算法2基于深度優先，在遞歸調用最大深度為O(logN)，因此遞歸中棧的最大空間為O(logN).而在每一層遞歸調用的過程中，需要聚集加載每層中所有和查詢范圍m相交的子結點索引并加載，該部分會產生O(B)空間的開銷，那么最多產生O(BlogN)空間開銷.因此算法2的空間復雜度為O(BlogN).

下面以圖2為例詳細描述算法2的查詢過程，并給出查詢代價分析.查詢過程首先從根結點A開始，批量提交并行讀取{B,C,D}；依次對以B,C,D進行遞歸子樹查找，依次分別批量提交讀取{E,F,G}，{H,I,J}和{K,L,M}.那么整個過程一共經歷4次IO，由于通道之間傳輸完全并行，而每次加載的3個結點數據塊分別連接在不同的通道上，因此每次批量提交讀取結點的加載時間均為T，那么整個加載時間為4T.算法NBS相較于NS，在圖2例子中加速比為3.

3.2 優化算法QBS

NBS算法是在深度優先搜索過程中，對于每個中間結點r，找出所有子結點中和查詢范圍m相交的子結點索引集合，然后批量提交，以充分發揮固態盤內部并行性.如圖2例子所示，這種方式并不能保證將批量提交的性能發揮到最大化，原因是每個被訪問結點的子結點在查詢范圍內m的數量可多可少不能保證.實際上，對于被訪問的r，除了讓m范圍內的子結點加載并行起來，還可以延遲等待其他結點，和其他結點的加載聚集起來一起批量提交.直觀思想就是將所有的待加載結點都找出來聚集，以讓每次批量提交加載的數量盡可能多，那么就能更大地發揮固態盤內部并行性.

基于上述優化思想，實現一個基于隊列的廣度優先的范圍查詢算法QBS，它維護一個已加載至內存結點隊列node_queue和一個用以加載結點索引的隊列request_queue.node_queue初始化為只包含根結點的隊列，每次都將所有node_queue結點的子結點遍歷將和m范圍相交的結點索引添加至request_queue，其目的是盡可能讓批量加載的并行性更充分.request_queue用于存放待加載索引集合，當所有可能產生結果結點的索引被找到后，便開始并行批量提交request_queue中的索引以加載待遍歷的結點.

算法3.QBS(r,m).

輸入：r為R-樹根結點,m為搜索的MBR；

輸出：S為m范圍內的數據索引集合.

①node_queue←{r},request_queue←?；

②S←?；

③ while (node_queue≠?‖request_queue≠?) do

④ while (node_queue≠?) do

⑤top←從node_queue中提取第i個結點；

⑥ for all (brancht∈top.branchs) do

⑦ if (t.MBR∩m≠?) then

⑧ if (top為非葉結點) then

⑨request_queue.push(t.NP)；

⑩ else

算法3輸入依然為R-樹根結點r，查詢區域為m；輸出為查找所有搜索矩形m覆蓋的記錄條目S；該算法主要共分成5個部分：

S1. [初始化](行①～②).算法3維護3個隊列：查詢隊列request_queue、結點隊列node_queue和數據索引隊列S，其中node_queue用于存放已經載入的內存結點,request_queue用于存放待載入內存結點的索引，S存放結果數據索引.該部分初始化查詢隊列和數據隊列為空，初始化查詢隊列為輸入根結點.

算法3采用基于隊列的廣度優先策略，最壞情況下，當每個被訪問node_queue的隊首結點為中間結點時，對于每個當前訪問結點最壞會產生B個待加載結點索引.而只有訪問結點是葉子結點時，處理完成后才是被徹底釋放，不會增加新的待加載結點進request_queue，進而被加載放入node_queue.對于一棵平衡樹，它的樹結點索引規模為O(NB).因此，最壞的情況，所有和m相交的結點都堆積在隊列中等待被處理，因此最壞的空間復雜度為O(NB).

下面以圖2為例詳細描述算法3的查詢過程，并給出查詢代價分析.這里默認NCQ_SIZE=32.按照算法3步驟S1，node_queue初始化只包含根結點A；按照步驟S3：取出node_queue的首結點A，枚舉所有和m相交A的待加載兒子結點{B,C,D}的索引放進request_queue； 按照步驟S4：批量提交{B,C,D}的索引讀取{B,C,D}，然后依次放入node_queue.按照步驟S2，算法并未停止，繼續運行.按照步驟S3，將node_queue中的所有結點{B,C,D}分別處理，獲取待加載兒子結點{E,F,G},{H,I,J}和{K,L,M}的索引放進request_queue；按照步驟S4，批量提交加載{E,F,G,H,I,J,K,L,M}，然后將已加載結點放入node_queue中；回到步驟S2，node_queue不為空，算法繼續；按照算法步驟S3，遍歷{E,F,G,H,I,J,K,L,M}獲取數據索引放入S，此時node_queue和request_queue均為空；回到步驟S2，算法終止；步驟S5，返回查詢結果S.

3.3 優化算法SBS

算法4基于棧來模擬遞歸調用的情形，不同于樸素用棧模擬遞歸調用問題的方法，在每次處理到任意結點時：如果該訪問結點未被加載，由于一次批量提交可以加載NCQ_SIZE個結點.那么，我們往堆棧棧底方向尋找，盡可能聚集滿NCQ_SIZE個子結點再并發提交以提高讀性能.當堆棧中的結點不滿NCQ_SIZE時，尋找先序遍歷順序的后續待加載的結點一起合并提交.如果該訪問結點是已經加載時，直接處理其子樹分支即可.

算法4.SBS(r,m).

輸入：r為R-樹根結點，m為搜索的MBR；

輸出：S為m范圍內的數據索引集合.

①node_stack←{r},S=?；

② while (node_stack≠?) do

③top=node_stack.top()；

④tmp_stack=?；

⑤ if (top未被加載) then

⑥ while (node_stack中未加載的結點數≤NCQ_SIZE) do

⑦ if (node_stack=?) then

⑧ break；

⑨ end if

⑩ 從node_stack中不斷取出結點數據壓入tmp_stack直到第1個已加載結點uncle；

node_stack；

node(t.NP))；

算法4共分為5個部分：

S1. [初始化](行①).算法初始化.初始化返回的數據索引集合S=?，初始化存放已加載內存結點的棧node_stack={r}.

算法4采用一個棧結構，棧每次遍歷一層結點最多壓入B+NCQ_SIZE=O(B)個元組，最多遞歸深度為該樹索引的高度O(logN)，最多壓入元素個數為O(BlogN).因為，這里面棧占據了最大的內存使用空間，當棧內結點彈出，處理后即可釋放.因此，算法4的空間復雜度為O(BlogN).

下面以圖2為例詳細描述算法4的查詢過程，并給出查詢代價分析.按照算法4步驟S1：堆棧node_stack只包含根結點A，由于A默認已經加載，那么直接運行至步驟S4：由于A的兒子結點的MBR均和查詢范圍m相交，因此將D,C,B分別壓進堆棧node_stack；然后按照步驟S2判斷，算法繼續；按照步驟S3：此時top未被加載，那么從node_stack棧頂開始往下尋找未加載的結點索引聚集得到{B,C,D}，并且node_stack不含有可以產生新的未加載索引的已加載結點，于是直接批量提交讀取{B,C,D}.此時棧頂為已加載結點B，那么按照步驟S4：遍歷B的所有兒子結點，查找MBR和m相交的子結點為G,F,E，按此次序依次壓入node_stack；回到步驟S2：因為node_stack不為空，因此算法繼續；由于node_stack棧頂元素為未加載的結點E，那么進入步驟S3：首先從node_stack棧頂開始往下尋找未加載的結點和E聚集批量提交.包括E在內，只尋得{E,F,G}，少于NCQ_SIZE=32，那么需要獲取更多待加載的結點.方法是從node_stack開始尋找已加載結點，如果是未加載結點先壓入tmp_stack，直到找到第1個已加載結點C，將C和m相交的待加載的兒子結點H,I,J依次壓入tmp_stack.此時待加載結點依然不夠，繼續尋找到D，那么將其和m相交的待加載結點K,L,M壓入tmp_stack.最后，將tmp_stack元素均彈出，壓入node_stack.這樣整體遍歷依然滿足先序遍歷的順序，接下來對從node_stack棧頂開始聚集未被加載的結點{E,F,G,H,I,J,K,L,M}批量提交.然后進入步驟S4來處理這些已經加載的葉子結點獲取m范圍內的數據索引加入S；最終進入步驟S5：返回查詢結果S.

圖2例子比較理想，實際固態盤是個黑箱，內存索引結點數據分布并不可知，假設索引數據是均勻地連接在不同的通道上，那么這就是一個球箱子模型，根據文獻[7]的證明可知，算法4依然可以提供一個很好的加速比.如批量提交32個IO請求，對于8通道的固態盤，期望加速比至少為2.93.

4 實驗與結果

本節將對本文提出的優化算法進行實驗測試.優化算法基于在加州大學伯克利分校Gutman[24]提供的開源內存R-樹實現.本節基于真實數據集合生成的數據測試NS,NBS,QBS,SBS的性能.

4.1 實驗設置

1) 真實固態盤測試平臺.實驗的平臺為Dell PowerEdge R730，配置為：2×6核Intel Xeon處理器，主頻1.90 GHz；32 GB內存；系統盤為2 TB 7200rpm機械硬盤；操作系統CentOS7.1，內核版本為3.10.0，libaio庫版本為0.3.109；實驗對象為表2中2塊固態盤.為了消除文件緩存給實驗結果造成的影響，文件打開模式為O_DIRECT.

Table 2 The Testing SSD Parameters

2) 仿真固態盤測試平臺.浪潮天梭TS860，配置為8×16核Intel Xeon處理器，32 GB×96=3 072 GB DDR4內存,1.2TB×8=9.6TB SAS硬盤.操作系統CentOS7.1，內核版本為3.10.實驗對象為用FEMU[25-26]模擬的5款固態盤，配置參數見表3.由于真實盤很難進行控制變量，該仿真盤主要用于測試通道數對于算法性能的影響.

Table 3 The Emulated SSD Parameters

3) 數據集合.測試使用的真實數據集合為美國50州的路網數據，該數據來源于美國國家地理數據庫[27]，共計11 278 412條數據，每個元組包含經緯度坐標和一組字符串屬性值.范圍查詢操作的實驗數據均由其產生.

4) 實驗測試.本測試針對文中4種范圍查詢算法進行性能對比實驗.在4.2節中，對于4種范圍查詢算法，分別從不同固態盤、查詢范圍2個角度進行對比，測試它們對這4種查詢算法的性能影響.為了表達方便，下面將SSDSC2BB480G6R簡稱為Intel-480GB，SSDSC2KW240H6X1簡稱為Intel-240GB.

4.2 查詢實驗

本節測試4種范圍查詢算法的性能，測試內容包含：小范圍查詢范圍變化對于范圍查詢時間和加速效果的影響；大范圍查詢范圍變化對查詢時間和加速效果的影響.這2組實驗分別在表2中2款不同的固態盤上進行實驗，以考察2款不同的固態盤對于范圍查詢時間和加速效果的影響.

先介紹索引構建的過程.首先，根據美國路網數據構建一棵R-樹索引，將共計11 278 412條數據依次插入到初始為空的R-樹索引中，我們就創建了一棵擁有完全數據的R-樹索引，這里把所有路網數據插入生成的R-樹索引稱之為Rfull.本節查詢實驗中，所有的查詢操作均作用于Rfull.

本節考慮查詢范圍變化和不同固態盤對于范圍查詢算法加速性能的影響.因此，本文透過7組不同查詢范圍的測試數據在2款固態盤上實驗來對4種算法進行測試，以檢驗查詢范圍對于它們性能的影響.設P為查詢范圍占整個數據集合MBR的百分比，這里使用P作為衡量范圍查詢操作查詢范圍大小的參數.生成P∈[0.000 1%,100%]共7組范圍查詢操作集，其中每組查詢操作1 000個.在生成查詢操作數據集合的過程中，對于每組查詢操作保證P不變，即確保查詢面積恒定.對于任意一組單個查詢操作生成方法是，在保證查詢區域面積不變的情況下，查詢范圍在各個維度上的長度隨機生成.這里把數據集合分成2組:P∈[0.000 1%,0.1%]和P∈[1%,100%].下面將對于這2組不同范圍的查詢操作集在表2所示2款不同固態盤上對Rfull進行測試實驗.實驗將統計每組查詢操作的平均執行時間.這里考察查詢范圍變化較小情況下對查詢算法效率的影響，這里P∈[0.000 1%,0.1%]，與之對應的是另外一組查詢范圍變化較大情況下對查詢算法效率的影響P∈[1%,100%].

這里先進行小查詢范圍情況下查詢性能對比實驗，比較在查詢范圍較小的情況下本文提出的3種算法NBS，QBS,SBS和經典查詢算法NS的效率比較.圖3是在2款不同固態盤上的小范圍查詢實驗，可以看出QBS比NS要快很多，SBS執行時間略高于QBS.如圖3(a)所示，在查詢范圍很小時，如P=0.000 1%時，NS,QBS,NBS,SBS執行時間幾乎無區別，這是因為非常小的查詢范圍查詢結果為空，異或查詢范圍不會和多個子樹MBR相交即查詢路徑單一，單一路徑上的任意2個結點都是加載依賴的結點，它們之間無法進行并行加載，使得固態盤內部并行無法發揮.因此在圖3(a)中，4種算法的平均執行時間幾乎相等.圖3(b)(c)(d)展示了隨著查詢范圍的變化，NS和NBS,QBS,SBS查詢時間的差距越來越大，同樣地NBS和QBS,SBS的執行時間差距也越來越大.

Fig. 3 Effect of small search range for searching algorithms on SSDs

接下來進行查詢范圍較大查詢性能實驗，比較在查詢范圍較大情況下本文提出的3種算法NBS,QBS,SBS和NS的執行時間比較.圖4分別是在2款不同固態盤上的大范圍查詢對比實驗，可以看出QBS比NS要低，且隨著范圍越來越大，執行時間差距就越大.SBS執行時間略高于QBS.如圖4(c)所示，在查詢范圍最大時，即P=100%時，QBS,NBS,SBS執行時間幾乎無區別，且和NS差距達到最大.這是因為查詢范圍非常大為全索引MBR時，它會和所有子樹和葉子結點的MBR相交，因此QBS,NBS,SBS算法都能很好地充分利用固態盤的內部并行性，因此QBS和SBS的優化就不會產生額外的加速效果.因此在圖4(c)中，3種算法分別的平均執行時間NBS,QBS,SBS幾乎相當，而和經典查詢算法NS執行時間差距最大.圖4(a)(b)展示了隨著查詢范圍的變化，NS和NBS,QBS,SBS查詢時間的差距越來越大，同時NBS和QBS,SBS的執行時間差距卻越來越小.

Fig. 4 Effect of large search range for searching algorithms on SSDs

Fig. 5 Speed up and peak memory usage of proposed searching algorithms on SSDs

圖5顯示了3種優化算法相對于NS的加速比隨著P變化的趨勢.如圖5(a)(b)所示，當P比較小時，隨著P的變大，NBS,QBS,SBS的加速效果越來越好,即加速比逐漸變大；當P比較大時，隨著P的變大，NBS,QBS,SBS加速效果同樣越來越好，而NBS，QBS，SBS之間的加速效果差距也越來越小.QBS雖然是執行效率最高的算法，但是根據算法空間復雜度分析可知，QBS空間復雜度非常高，如圖5(c)所示，QBS隨著P的逐漸增大，內存消耗越來越多，最大達到1.6 GB，而NBS和SBS內存消耗幾乎可以忽略不計.因此，如果內存受限，SBS一定是最優選擇.所以，大家可以根據具體的情況，選擇合適的優化算法來提高查詢效率.

最后在仿真固態盤上測試通道對于算法加速性能的影響，仿真配置如表3所示.我們分別對通道數為2,4,6,8,10這5個仿真固態盤進行實驗測試，用來說明通道數對算法加速性能的影響.如圖6和圖7所示，圖6是在小范圍查詢數據集下通道數對算法加速效果的影響，圖7為大范圍查詢數據集下通道數對算法加速效果的影響.圖6(a)中，隨著通道數的提升，算法加速效果幾乎沒有變化，這是由于查詢范圍小，并發性很低，多通道發揮不出效果；如圖6(b)(c)(d),隨著通道數的增加，相對于NS，QBS，SBS加速比會逐漸上升，但是加速的提升速度減慢，這是因為IO并發性存在，但是依然比較小，因此隨著通道數的提升加速效果會有所增加，但是提升速度會下降.如圖7所示，在大范圍查詢下IO并發性是充足的，因此隨著通道數的增加，加速比斜率變小的速度更緩慢些.結合圖6和圖7整體加速比可以看出，QBS和SBS在較大查詢范圍情況下，通道數的增加對于加速比的提升很明顯，通道越多，加速效果越好.

Fig. 6 Speed up affected by variant channel SSDs under small range search

5 總結和未來工作

地理信息系統在人們生產和生活中起到越來大的作用，作為該系統的核心索引R-樹，主要接受的是范圍查詢操作，那么對R-樹的范圍查詢算法效率改進對于整體系統的性能提升具有重要意義.由于閃存固態盤逐漸成為主流存儲設備，它不同于傳統機械硬盤存儲，擁有很多自己的特點.于是本文從固態盤內部并行性這個特點出發，針對R-樹的范圍查詢操作設計出一系列新的范圍查詢算法包括NBS，QBS，SBS來發揮固態盤內部并行性，以提升R-樹索引范圍查詢效率.通過理論分析和實驗證明：QBS最能發揮固態盤內部并行性，但是需要消耗大量內存；NBS算法實現容易，內存消耗最少，但是在查詢范圍較小情況，加速效果會減弱；為了更能發揮固態盤內部并行性，同時內存消耗又要很低，本文提出基于堆棧的范圍查詢算法SBS.通過理論分析和實驗證明，它可以在消耗很少內存的情況下，高效地發揮固態盤的內部并行性.

在實驗過程中會發現不同的閃存固態盤，在進行算法比較時加速效果會出現差異，這是由于不同固態盤內部并行資源的不同導致.因此在選購固態盤時，如果想充分發揮本文提出算法SBS的性能，應當選取內部并行資源更豐富的固態盤作為存儲盤.