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

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

RSGMPXAB

CDEJKNOYZRSTUVTQ1<=根結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)<=52<=非根結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)<=5范圍9GMPTXAB

CDEJKNOYZRSU

V插入W自頂向下進(jìn)行插入，分裂沿途中的每個(gè)滿結(jié)點(diǎn)xG

M

T

X

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

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

JKLNOYZQRSUVTXPDEF

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

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

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

NOYZQRSUVEJKCL

PTX

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

AB

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

PTX

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

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

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

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

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

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

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