[發(fā)明專利]基于Key/Value型NoSQL數(shù)據庫的矢量數(shù)據先序四叉樹編碼和索引方法

在審

• 申請?zhí)枺?/td>: 201310051629.4
• 申請日: 2013-02-17
• 公開（公告）號: CN103092992A
• 公開（公告）日: 2013-05-08
• 發(fā)明（設計）人: 胡斌;劉熠;胡秋翔;羅青;邵華
• 申請（專利權）人: 南京師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務所 32207
• 代理人: 汪旭東

技術領域

本發(fā)明涉及空間數(shù)據庫領域，特別涉及基于Key/Value型NoSQL數(shù)據庫的矢量數(shù)據先序四叉樹編碼和索引方法。

背景技術

自E.F.Codd博士提出關系模型理論以來，?關系數(shù)據庫得到迅速發(fā)展，并已成為數(shù)據庫的主流，空間數(shù)據庫也從文件型發(fā)展到關系數(shù)據庫型。但隨著互聯(lián)網的高速發(fā)展，出現(xiàn)了很多大規(guī)模和高并發(fā)的空間數(shù)據在線應用，這些應用要求空間數(shù)據庫支持數(shù)據的高并發(fā)性、存儲訪問的高效性和在線擴展性，關系數(shù)據庫在這些應用面前疲態(tài)盡顯，而NoSQL數(shù)據庫具有高可用性、高可靠性和高性能等優(yōu)異特性，無疑為滿足上述應用要求提供了一條很有前景的解決之道。

空間索引是提高空間查詢效率的關鍵技術，常用的空間索引包括網格索引、四叉樹索引和R樹索引等，而四叉樹索引因其簡單高效得到廣泛應用。四叉樹索引采用遞歸查詢方法，從根結點開始進行層次遍歷，對于關系型空間數(shù)據庫，由于空間范圍的連續(xù)性并不意味著數(shù)據物理存儲的連續(xù)性，最終的空間查詢結果往往需要很多次I/O操作，影響了查詢效率。與關系數(shù)據庫不同，Key/Value型NoSQL數(shù)據庫具有順序存儲的特點，因此，如果數(shù)據查詢時能進行順序查詢而不是隨機查詢，就能減少?I/O操作，提高查詢效率。經典的四叉樹索引或者不對數(shù)據對象編碼作任何要求，或者采用層次四叉樹編碼，都不能有效利用Key/Value型NoSQL數(shù)據庫順序存儲的優(yōu)勢。本發(fā)明在MX-CIF四叉樹的基礎上，設計了一種前序四叉樹編碼方案和索引方法，在使用Key/Value型NoSQL數(shù)據庫存儲時，能使矢量數(shù)據物理存儲次序與空間連續(xù)性一致、數(shù)據主鍵次序與物理存儲次序一致，從而在空間查詢時發(fā)揮Key/Value型NoSQL數(shù)據庫順序查詢的優(yōu)勢，提高查詢性能。

發(fā)明內容

如圖1所示，本發(fā)明針對矢量數(shù)據（主要是線狀數(shù)據和面狀數(shù)據）數(shù)據組織和四叉樹索引的特點，結合Key/Value型NoSQL數(shù)據庫主鍵邏輯順序和物理順序一致的特點，提供了一種基于Key/Value型NoSQL數(shù)據庫的矢量數(shù)據先序四叉樹編碼和索引方法，這種方法矢量數(shù)據先序四叉樹編碼和索引方法包括如下步驟：

步驟1：完全四叉樹空間劃分與先序四叉樹結點編碼；

四叉樹根結點對應整個數(shù)據空間，按完全四叉樹的規(guī)則，將整個空間進行完全四叉樹遞歸劃分，直到到達四叉樹的最大高度，得到一棵完全四叉樹，然后對完全四叉樹進行先序遍歷，按先序遍歷次序依次給各結點編號，直到完成整棵四叉樹結點編碼；?

步驟2：矢量數(shù)據前綴編碼和索引構建；

從根結點開始遍歷整棵四叉樹，根據矢量對象的最小外包矩形（MBR）確定能完整包含該MBR的最小結點node，以該結點編碼作為前綴編碼該矢量對象，并以該編碼作為主鍵key把矢量對象存儲到數(shù)據庫，然后更新node索引信息，索引信息包含兩部分，一部分是索引對象（key，MBR）表，要求node中的索引對象表按主鍵key遞增排列，一部分是索引區(qū)間（minKey，maxKey），表示以該結點為根的子樹的索引鍵區(qū)間。最后更新從node到根結點路徑上所有結點的索引區(qū)間；

步驟3：先序四叉樹索引；

從根結點開始先序遍歷；

A如果查詢窗口與結點相離，跳過以該結點為根的整棵子樹；

B如果查詢窗口完全覆蓋結點，則讀取該結點的索引區(qū)間信息（minKey，maxKey），然后根據minKey和maxKey對數(shù)據庫進行范圍查詢；

C如果查詢窗口與結點部分相交，則首先讀取該結點的索引對象表并進行MBR和查詢窗口相交檢測，然后使用通過檢測的索引對象編碼對數(shù)據庫進行查詢，最后先序遍歷四棵子樹，按上述方法處理子樹結點。

本發(fā)明的優(yōu)點為：該方法使數(shù)據物理存儲次序與空間范圍連續(xù)性一致、數(shù)據主鍵次序與物理存儲次序一致，從而在空間查詢時能減少?I/O操作，提高查詢效率。

附圖說明

圖1為本發(fā)明的完全四叉樹空間劃分的示意圖。

圖2為本發(fā)明的四叉樹先序編碼的示意圖。

附圖標記說明：1-根結點編碼；2、23、44、65、3、8、13、18、24、29、34、39、45、50、55、60、66、71、76、81、25、26、27、28、82、83、84、85-子結點編碼。

?

圖3為本發(fā)明的矢量數(shù)據前綴編碼和索引構建的示意圖。

附圖標記說明：1、2、3、4、5、6-矢量對象及其外包矩形MBR。

圖4為本發(fā)明的先序四叉樹索引的示意圖。