資源描述：
《gms數(shù)據(jù)庫(kù)管理系統(tǒng)中時(shí)空索引的分析與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、重慶郵電大學(xué)碩士論文第一章緒論第二，通過(guò)閱讀STOIRM，NT中和空間索引R樹(shù)相關(guān)的源代碼，詳細(xì)分析和R樹(shù)相關(guān)的其它模塊的接口關(guān)系。因?yàn)橐赟ToRM，NT中實(shí)現(xiàn)TPR*．Link樹(shù)必須首先了解索引如何在空間數(shù)據(jù)庫(kù)管理系統(tǒng)中實(shí)現(xiàn)，以便了解要對(duì)索引進(jìn)行哪些相關(guān)操作。第三，TPR*樹(shù)沒(méi)有加入右鏈結(jié)構(gòu)，要考慮引入這種結(jié)構(gòu)后，對(duì)查找、插入、刪除算法的影響。第四，在S1DRM，NT中設(shè)計(jì)并實(shí)現(xiàn)TPR*一Link樹(shù)。使得在現(xiàn)有S1’oRM仆『T系統(tǒng)的基礎(chǔ)上，實(shí)現(xiàn)對(duì)移動(dòng)物體現(xiàn)在和將來(lái)位置的查詢。1．4論文組織結(jié)構(gòu)本文共分七章，各章的內(nèi)容安排如下：
2、第一章主要介紹國(guó)內(nèi)外研究現(xiàn)狀和研究意義。第二章主要介紹時(shí)空索引的基本概念和基礎(chǔ)理論。第三章分析和比較幾種索引移動(dòng)物體現(xiàn)在和將來(lái)位置的典型索引結(jié)構(gòu)，分析的目的是了解當(dāng)前索引的現(xiàn)狀、優(yōu)勢(shì)、缺陷，從中選取最佳方案。第四章詳細(xì)分析了TPR*樹(shù)的索引結(jié)構(gòu)，索引操作。TPR·樹(shù)在索日l(shuí)移動(dòng)物體時(shí)的主要優(yōu)勢(shì)以及存在的問(wèn)題。第五章給出TPR*．Link樹(shù)的索引結(jié)構(gòu)的設(shè)計(jì)，查找、插入算法以及相關(guān)證明。第六章實(shí)現(xiàn)TPR*．Link樹(shù)的基本操作，包括添加的數(shù)據(jù)結(jié)構(gòu)、STORM，NT接口函數(shù)、實(shí)驗(yàn)結(jié)果和性能分析。第七章總結(jié)。重慶郵電大學(xué)碩士論文第二章時(shí)空索
3、引的基礎(chǔ)理論從空間數(shù)據(jù)庫(kù)中獲得時(shí)空數(shù)據(jù)的有效方法，經(jīng)常是通過(guò)使用時(shí)空索引完成的。它可以用來(lái)快速訪問(wèn)一條特定的時(shí)空查詢所請(qǐng)求的數(shù)據(jù)，而無(wú)需遍歷整個(gè)數(shù)據(jù)庫(kù)。2．1時(shí)空索引的概念索引文件是用來(lái)提高數(shù)據(jù)文件查詢效率的輔助文件。時(shí)空索引是從空間數(shù)據(jù)庫(kù)中獲得數(shù)據(jù)的有效方法。時(shí)空索引用一組桶(bucket)(通常對(duì)應(yīng)二級(jí)存儲(chǔ)的頁(yè)面)來(lái)組織對(duì)象。每個(gè)桶有一個(gè)關(guān)聯(lián)的桶區(qū)域，即包含了存儲(chǔ)在桶中全部對(duì)象的一部分空間。桶區(qū)域通常是矩形的。對(duì)于點(diǎn)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，這些矩形數(shù)據(jù)結(jié)構(gòu)是不相交的，它們將空間分成每個(gè)點(diǎn)正好屬于一個(gè)桶。對(duì)于一些矩形數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，桶區(qū)域可能
4、是交疊的。通過(guò)引入時(shí)間維表示每個(gè)對(duì)象的動(dòng)態(tài)屬性。2．2時(shí)空索引主要特點(diǎn)’}／時(shí)空索引要處理的數(shù)據(jù)具有：數(shù)據(jù)量大、多維和隨時(shí)間變化的特點(diǎn)?？臻g數(shù)據(jù)庫(kù)管理系統(tǒng)就是為處理海量空間數(shù)據(jù)而設(shè)計(jì)的。時(shí)空索引也不例外。空間數(shù)據(jù)的一個(gè)低分辨率的美國(guó)衛(wèi)星圖像就會(huì)消耗30兆磁盤(pán)的空間。正是因?yàn)榭臻g數(shù)據(jù)量太大，它甚至都不能用一個(gè)中等規(guī)模的二級(jí)存儲(chǔ)來(lái)裝載，數(shù)據(jù)會(huì)溢出到三級(jí)存儲(chǔ)中。讀取數(shù)據(jù)時(shí)花費(fèi)在訪問(wèn)隨機(jī)存儲(chǔ)器和磁盤(pán)的時(shí)間是不可同日而語(yǔ)的：前者大約是后者的十萬(wàn)分之一。這個(gè)比率還在逐年降低。時(shí)空索引的設(shè)計(jì)必須能迅速找到需要查詢的數(shù)據(jù)，盡量減少內(nèi)存和磁盤(pán)問(wèn)的訪問(wèn)
5、速度?？臻g數(shù)據(jù)一般都是二維或更高維的。傳統(tǒng)索引的實(shí)現(xiàn)主要依賴于索引域排序而存在。空間數(shù)據(jù)如果分類和排序，就會(huì)丟失空間的相鄰性。如圖2．1所示：圖中有一個(gè)按行排序的網(wǎng)格?，F(xiàn)在考慮4的相鄰數(shù)字，在這個(gè)網(wǎng)格里4的相鄰數(shù)據(jù)是3、7和8，但是如果按照排序的順序來(lái)存儲(chǔ)，它的相鄰數(shù)字就成了3和5。因而，排序會(huì)破壞原有的相鄰關(guān)系。值得一提的是，沒(méi)有哪一種全排序可以安全保持空間的相鄰性。由于多維空間不存在自然排序，在關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)中用的最廣泛的索引B樹(shù)，也就無(wú)法直接用于創(chuàng)建空間對(duì)象的索引。為了避免空間對(duì)象在自然排序方面的不足，必須從根本上修改B樹(shù)
6、的思想，以適應(yīng)擴(kuò)展的空間對(duì)象。R樹(shù)的數(shù)據(jù)結(jié)構(gòu)是最早的專用于處理多維擴(kuò)展對(duì)象的索引之一。重慶郵電大學(xué)碩士論文第二章時(shí)空索引的基礎(chǔ)理論l23456789lOll121311IS16圖2．I對(duì)多維數(shù)據(jù)的行排列時(shí)空數(shù)據(jù)是隨著時(shí)間不斷變化的，或者是速度的大小，或者是速度的方向。2．3R樹(shù)的索引結(jié)構(gòu)基于數(shù)據(jù)分區(qū)的時(shí)空索引都是在R樹(shù)基礎(chǔ)上發(fā)展的。索引R樹(shù)(區(qū)域樹(shù))是一種利用B樹(shù)的某些本質(zhì)特征來(lái)處理多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。B樹(shù)的結(jié)點(diǎn)有一個(gè)鍵的集合，這些鍵把線分成片斷，沿著那條線的點(diǎn)僅屬于一個(gè)片斷。如圖2．2所示。B樹(shù)因此很容易地找到點(diǎn)。如果把沿線各處的
7、點(diǎn)表示成B樹(shù)結(jié)點(diǎn)，就能夠確定點(diǎn)所屬的唯一子結(jié)點(diǎn)，在那里可以找到該點(diǎn)?！猒{—}_————_{——H圖2．2B樹(shù)結(jié)點(diǎn)沿線把鍵分成不相連片段另一方面，R樹(shù)表示由二維或更高維區(qū)域組成的數(shù)據(jù)，稱為數(shù)據(jù)區(qū)。一個(gè)R樹(shù)的內(nèi)結(jié)點(diǎn)對(duì)應(yīng)于某個(gè)內(nèi)部區(qū)域，或稱“區(qū)域”，它不是普通的數(shù)據(jù)區(qū)。原則上，區(qū)域可以是任何形狀，雖然實(shí)際中它經(jīng)常為矩形或其他簡(jiǎn)單形狀。R樹(shù)的結(jié)點(diǎn)用子區(qū)域代替鍵，子區(qū)域表示結(jié)點(diǎn)的子區(qū)域的內(nèi)容。如圖2．3顯示了一個(gè)與大矩形相關(guān)聯(lián)的R樹(shù)的結(jié)點(diǎn)。虛線表示的矩形表示與它的子結(jié)點(diǎn)相關(guān)聯(lián)的予區(qū)域。子區(qū)域沒(méi)有覆蓋整個(gè)區(qū)域，只要把位于大區(qū)域內(nèi)的所有數(shù)據(jù)區(qū)都
8、完全包含在某個(gè)區(qū)域中就合乎要求。進(jìn)一步說(shuō)，盡管希望部分重疊更小，子區(qū)域允許有部分重疊。R樹(shù)中的最小外包矩形用來(lái)表示對(duì)象。R樹(shù)有以下幾條特性：1)每個(gè)葉結(jié)點(diǎn)包含m至M條索引記錄(其中m
