空間數(shù)據(jù)庫索引技術

第5章空間數(shù)據(jù)庫索引技術1空間數(shù)據(jù)索引技術1B樹索引2可擴展的哈希索引3空間填充曲線455.1空間數(shù)據(jù)索引技術空間索引是指根據(jù)空間要素的地理位置、形狀或空間對象之間的某種空間關系，按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)，一般包括空間要素標識，外包絡矩形以及指向空間要素的指針?？臻g索引的理解：可以想象一本書，其中書的內(nèi)容就相當于表里的數(shù)據(jù)，而書前面的目錄就相當于該表的索引?？臻g索引目的是為了在GIS系統(tǒng)中快速定位到所選中的空間要素，從而提高空間操作的速度和效率。5.2B樹索引B樹索引是一個典型的樹結(jié)構(gòu)，始終是平衡的，也就是說從Root節(jié)點到Leaf節(jié)點的任何一個路徑都是等距離的。其包含的組件主要是：葉子節(jié)點（Leafnode）：包含的條目直接指向表里的數(shù)據(jù)行。分支節(jié)點（Branchnode）：包含的條目指向索引里其他的分支節(jié)點或者是葉子節(jié)點。根節(jié)點（Rootnode）：一個B樹索引只有一個根節(jié)點，它實際就是位于樹的最頂端的分支節(jié)點。5.2.1B樹索引的結(jié)構(gòu)5.2.2B樹索引的性質(zhì)1.每個結(jié)點的關鍵字是升序排列2.含有n個關鍵字的結(jié)點,都包含n+1個指針指向其孩子4.父結(jié)點中第i個關鍵字≥第i個孩子的所有關鍵字父結(jié)點中第i個關鍵字≤第i+1個孩子的所有關鍵字3.葉子結(jié)點沒有孩子,所有的葉子都處在同一層5.1≤根結(jié)點的關鍵字的個數(shù)≤2t–1t-1≤非根結(jié)點的關鍵字的個數(shù)≤2t-1最小度用t(t>=2)來表示，最小度數(shù)即內(nèi)結(jié)點中結(jié)點最小孩子數(shù)目例子：查找21

5.2.3B樹的操作1.搜索B樹612磁盤塊568磁盤塊61011磁盤塊71618磁盤塊82123磁盤塊92932磁盤塊103637磁盤塊114043磁盤125660磁盤13磁盤塊11535p1p2p3磁盤塊43944p1p2p3磁盤塊31928p1p2p3磁盤塊239p1p2p32.B樹的插入

GMPXACDEJKNORSTUVYZ初始B樹(t=3)插入BGMPXACDEJKNORSTUVYZ1<=根結(jié)點的關鍵字個數(shù)<=52<=非根結(jié)點的關鍵字個數(shù)<=5范圍B7未超出范圍，直接插入。插入Q

超出范圍分裂，分裂為各含有t-1個關鍵字的結(jié)點,中間關鍵字提升到其雙親結(jié)點中，然后將關鍵字插入。8UV

RSGMPXAB

CDEJKNOYZRSTUVTQ1<=根結(jié)點的關鍵字個數(shù)<=52<=非根結(jié)點的關鍵字個數(shù)<=5范圍9GMPTXAB

CDEJKNOYZRSU

V插入W自頂向下進行插入，分裂沿途中的每個滿結(jié)點xG

M

T

X

PxxxW103.B樹的刪除B樹的刪除關鍵字在終端結(jié)點中，直接刪除關鍵字在內(nèi)結(jié)點x中夠借，借調(diào)◆左孩子夠借，借調(diào)直接前驅(qū)◆左孩子不夠借，右孩子夠借，借調(diào)直接后繼不夠借合并關鍵字不在內(nèi)結(jié)點x中，在子樹中左右兄弟夠借，借調(diào)左右兄弟不夠借，合并自頂向下的方式進行刪除需要借不需要借CGMAB

JKLNOYZQRSUVTXPDEF初始B樹（t=3）刪除FCGMAB

JKLNOYZQRSUVTXPDEF

1<=根結(jié)點的關鍵字個數(shù)<=52<=非根結(jié)點的關鍵字個數(shù)<=511關鍵字在葉結(jié)點中，直接刪除刪除G1<=根結(jié)點的關鍵字個數(shù)<=52<=非根結(jié)點的關鍵字個數(shù)<=5

若左右孩子不夠借,將右孩子合并到左孩子中去，并將所刪關鍵字做為左孩子的中間關鍵字，刪除關鍵字，釋放右孩子。CGLAB

NOYZQRSUVTXPJKDEDEGJK12關鍵字在內(nèi)結(jié)點x中夠借，借調(diào)◆左孩子夠借，借調(diào)直接前驅(qū)◆左孩子不夠借，右孩子夠借，借調(diào)直接后繼不夠借合并x13關鍵字不在內(nèi)結(jié)點x中，在子樹中左右兄弟夠借，借調(diào)左右兄弟不夠借，合并AB

NOYZQRSUVEJKCL

PTX

x刪除By左右夠借,借調(diào)CE代表未畫出的子樹14左右兄弟夠借，借調(diào)左右兄弟不夠借，合并CL

AB

NOYZQRSUVTXPDEJK刪除D左右不夠借，合并CL

PTX

xy關鍵字不在內(nèi)結(jié)點x中，在子樹中5.3可擴展的哈希索引網(wǎng)格文件是一種典型的基于哈希的存取方式，它是由包含很多與數(shù)據(jù)桶相聯(lián)系的單元的網(wǎng)格目錄來實現(xiàn)的。對于二維空間為平行于x或y軸的直線，這一超平面將數(shù)據(jù)空間劃分為兩個子空間。所有的邊界一起將整個數(shù)據(jù)空間劃分成許多k維的矩形子空間，這些矩形子空間稱為網(wǎng)格目錄，由一個k維的數(shù)組表示。目錄項（即網(wǎng)格目錄數(shù)組的元素）和網(wǎng)格單元之間具有一對一的關系。網(wǎng)格目錄的每一網(wǎng)格單元包含一個外存頁的地址，對應著一個數(shù)據(jù)桶，一般一個數(shù)據(jù)桶為硬盤上一個磁盤頁，這一外存頁存儲了包含了網(wǎng)格單元的數(shù)據(jù)目標，稱為數(shù)據(jù)頁。數(shù)據(jù)頁所對應的一個或多個網(wǎng)格單元稱之為存儲區(qū)域,存儲區(qū)域兩兩不相交。每個數(shù)據(jù)桶往往可以包含著幾個相鄰的單元，存儲多個網(wǎng)格單元的目標，只要這幾個網(wǎng)格單元一起形成一矩形的區(qū)域。5.3可擴展的哈希索引網(wǎng)格文件查找先找到涉及網(wǎng)格單元，并提取相應的數(shù)據(jù)頁，然后比較數(shù)據(jù)頁的牧鞭是否滿足查詢要求即可。網(wǎng)格文件插入

先進行一次精確查詢定位該數(shù)據(jù)項插入的網(wǎng)格單元，提取對應的數(shù)據(jù)頁（數(shù)據(jù)桶存放的磁盤頁）。若該磁盤頁有空間，將數(shù)據(jù)插入。若沒有足夠空間，則要根據(jù)與該頁的聯(lián)系的單元的數(shù)目來分裂該數(shù)據(jù)頁。網(wǎng)格文件刪除

在網(wǎng)格文件中刪除一個數(shù)據(jù)，也要進性一次精確查找確定該數(shù)據(jù)所在正確的網(wǎng)格單元，提取對應數(shù)據(jù)頁，從數(shù)據(jù)頁中刪除該目標。D5D4D6網(wǎng)格文件插入目錄示意圖5.4空間填充曲線空間填充曲線是一種重要的近似表示方法，將數(shù)據(jù)空間劃分成大小相同的網(wǎng)格，再根據(jù)一定的方法將這些網(wǎng)格編碼，每個格指定一個唯一的編碼，并在一定程度上保持空間鄰近性，即相鄰的網(wǎng)格的標號也相鄰，一個空間對象由一組網(wǎng)格組成。

這樣可以將多維的空間數(shù)據(jù)降維表示到一維空間當中。理想的空間映射方法是：在多維空間中聚集的空間實體，經(jīng)過填充曲線編碼以后，在一維空間中仍然是聚集的。

（a）行排序（b）Hilbert排序（c）Z排序

圖5-30幾種常用的空間填充編碼方法1)Z-ordering曲線（peano曲線）Z-排序（Z-ordering）技術將數(shù)據(jù)空間循環(huán)分解到更小的子空間（被稱為PeanoCell），每個子空間根據(jù)分解步驟依次得到一組數(shù)字，稱為該子空間的Z-排序值。子空間有不同的大小，Z-排序有不同的長度，顯然，子空間越大，相應的Z-排序值越短。這里，分辨率（resolution）是指最大的分解層次，它決定了Z-排序值的最大長度。

圖5-31Z-排序示例2n×2n個分區(qū)，編號為0~2n×2n-12)H