空間數(shù)據(jù)的物理組織

1、空間數(shù)據(jù)的物理組織第1頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五一、文件組織的基本概念1、操作系統(tǒng)的文件管理 文件系統(tǒng)把有關(guān)數(shù)據(jù)組織成為文件并予以命名。2、邏輯記錄與物理記錄 數(shù)據(jù)塊是數(shù)據(jù)物理組織的重要概念，為了簡化軟、硬件的復(fù)雜性，同一系統(tǒng)中的數(shù)據(jù)塊一般均包含相等個數(shù)的字節(jié)。（1）定長記錄固定組塊（2）變長記錄不跨界組塊（3）變長記錄跨界組塊（4）塊列第2頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五3、地址與指針（1）絕對地址（2）相對地址（3）符號地址 指針就是鏈接對象的地址。4、分頁與系統(tǒng)緩沖區(qū) 為了使文件組織獨(dú)立于具體的物理設(shè)備，通常采用分頁技術(shù)，即把內(nèi)、

2、外存空間按同樣大小分成若干頁面。 系統(tǒng)緩沖區(qū)是主存中特別指定的一塊存儲空間，以存放從外存讀入內(nèi)存的數(shù)據(jù)或從內(nèi)存寫進(jìn)外存的數(shù)據(jù)。 緩沖區(qū)管理，就是將緩沖區(qū)分成若干塊，系統(tǒng)用一個程序分配這些緩沖塊，并采用分配算法使緩沖區(qū)的利用為最佳。第3頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五5、文件組織 所謂文件組織，就是按一定的邏輯結(jié)構(gòu)把有關(guān)聯(lián)的數(shù)據(jù)記錄組織成為文件（稱為邏輯文件），并用體現(xiàn)這種邏輯結(jié)構(gòu)的物理存儲形式把文件中的數(shù)據(jù)存放到某種存儲設(shè)備上，使之構(gòu)成物理文件的機(jī)構(gòu)。（1）文件存儲空間利用率 文件包含的數(shù)據(jù)信息量（折合成字節(jié)數(shù)）與文件占用的整個存儲空間（字節(jié)數(shù)）的比值。（2）操作的時

3、間耗費(fèi) 這是文件組織中性能量度的一個重要方面。第4頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五（3）文件的重新組織 系統(tǒng)周期性地把文件中現(xiàn)存的記錄按原來的或新的組織方法和內(nèi)部結(jié)構(gòu)重新組織起來。6、動態(tài)存儲管理 存儲管理不是研究某種數(shù)據(jù)結(jié)構(gòu)，而是研究數(shù)據(jù)結(jié)構(gòu)的空間分配、回收的方法，以滿足某種結(jié)構(gòu)對存儲的不同要求。 解決存儲管理的途徑一般有三條：由用戶解決，由系統(tǒng)解決，由系統(tǒng)和用戶共同解決。第5頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五二、流水文件 它是一種最簡單的文件組織方法，即按照數(shù)據(jù)到達(dá)文件的時間順序依次連續(xù)地存儲數(shù)據(jù)，對數(shù)據(jù)不分析、不規(guī)范，記錄的類型既可相同，

4、也可不同。 在記錄類型不相同時，流水文件的記錄必須由相關(guān)的數(shù)據(jù)項(xiàng)組成。 流水文件中查找記錄、插入記錄，修改操作過程。 流水文件主要用作數(shù)據(jù)庫的日志文件。第6頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五三、順序文件1、如何確定關(guān)鍵字值的順序2、順序文件的存儲組織（1）向量結(jié)構(gòu)（2）鏈結(jié)構(gòu)（3）塊鏈結(jié)構(gòu)3、順序文件的查找（1）順序掃描（2）分塊查找（3）折半查找（4）探查4、順序文件的維護(hù)第7頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五四、索引文件 以英漢詞典為例，詞典本身是一個順序文件，其結(jié)構(gòu)是向量的，主關(guān)鍵字是英文單詞，記錄是英文單詞及其解釋。若將每頁的最后一個單詞

5、與頁號列表，那么查單詞可先查表（稱為索引表），等確定頁面號后，再細(xì)查該頁面。這就是索引文件的基本思想。組織索引表（簡稱索引）是索引文件的關(guān)鍵。第8頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五1、索引順序文件 2、索引無序文件3、B樹 4、B樹5、Hash文件第9頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五索引順序文件 第10頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五索引順序文件的索引機(jī)制第11頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五 傳統(tǒng)的索引方法不能對地理數(shù)據(jù)進(jìn)行有效的索引，尤其是多維性方面。 空間索引是對存儲在介質(zhì)上的數(shù)據(jù)位置信

6、息的描述，是建立邏輯記錄與物理記錄之間的對應(yīng)關(guān)系的橋梁，用來提高系統(tǒng)對數(shù)據(jù)獲取的效率。1、概述 空間數(shù)據(jù)索引是指依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系，按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對象的概要信息，如對象的標(biāo)識、外接矩形及指向空間對象實(shí)體的指針。五、空間數(shù)據(jù)索引第12頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五 空間索引性能的優(yōu)劣直接影響空間數(shù)據(jù)庫和地理信息系統(tǒng)的整體性能，它是空間數(shù)據(jù)庫和地理信息系統(tǒng)的一項(xiàng)關(guān)鍵技術(shù)。 空間索引一般是自頂向下、逐級劃分空間的各種數(shù)據(jù)結(jié)構(gòu)。 對一些非常自然地處理區(qū)域數(shù)據(jù)，應(yīng)用最廣泛的是R樹，已經(jīng)可以在商用的DBMS中看到R樹

7、索引。第13頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五（1）基本概念空間索引：依據(jù)空間對象所在位置及分布特征，按一定 順序編排的一種數(shù)據(jù)結(jié)構(gòu)，且該數(shù)據(jù)結(jié)構(gòu)包含 有對象標(biāo)識和定位這些對象的內(nèi)容的信息?？臻g檢索: 給定查詢條件，利用空間索引從數(shù)據(jù)庫中找出 符合條件的空間數(shù)據(jù)的一種操作。點(diǎn)、線、面 檢索。（2）空間索引的分類 從數(shù)據(jù)庫索引結(jié)構(gòu)的實(shí)現(xiàn)方法 靜態(tài)索引、動態(tài)索引第14頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五空間檢索 空間實(shí)體間的關(guān)系檢索 面與面 線與線 點(diǎn)與點(diǎn) 線與點(diǎn) 面與線 面與點(diǎn)第15頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五 從空間索

8、引技術(shù)上 對象影射技術(shù)、對象復(fù)制和裁剪技術(shù)、重疊子空間方法。 按空間數(shù)據(jù)對象 a 基于點(diǎn)對象的索引方法 b 基于面對象的索引方法 按照數(shù)據(jù)的存儲介質(zhì) a 基于外存的索引 b 基于主存的索引 c 基于數(shù)據(jù)庫的索引第16頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五（3）基于外存的空間索引 BSP樹第17頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五 K-D樹 R樹第18頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五 CELL樹第19頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五（4）基于主存的空間索引 面向主存的空間索引是主存空間數(shù)據(jù)庫的一個重要組

9、成部分。 主存網(wǎng)格空間索引 它是一種相對簡單的主存空間索引。 主存F樹空間索引 自頂向下逐級劃分空間（5）基于數(shù)據(jù)庫的空間索引 索引實(shí)質(zhì)不同 基于數(shù)據(jù)庫的索引，實(shí)質(zhì)上是基于數(shù)據(jù)庫的SQL語言優(yōu)化，通過適當(dāng)?shù)谋斫Y(jié)構(gòu)設(shè)計(jì)，表索引設(shè)計(jì)，以及SQL查詢的設(shè)計(jì)，達(dá)到對空間數(shù)據(jù)的快速檢索。第20頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五 基于數(shù)據(jù)庫的空間索引的特點(diǎn) a 無須對原始數(shù)據(jù)進(jìn)行結(jié)構(gòu)調(diào)整 b 通用性強(qiáng) c 在一定程度降低了索引設(shè)計(jì)的復(fù)雜度 d 在某些方面又增加了索引設(shè)計(jì)的復(fù)雜度索引方法索引實(shí)質(zhì)特點(diǎn)基于文件的索引優(yōu)化I/O用結(jié)構(gòu)適應(yīng)算法基于內(nèi)存的索引優(yōu)化CPU計(jì)算量用結(jié)構(gòu)適應(yīng)算法基于

10、數(shù)據(jù)庫的索引既要優(yōu)化I/O，又要優(yōu)化CPU計(jì)算量，實(shí)質(zhì)上是基于數(shù)據(jù)庫的SQL語言優(yōu)化用算法適應(yīng)結(jié)構(gòu)不同索引方法比較第21頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五2、空間索引與B樹索引 空間索引利用了某種空間聯(lián)系來組織數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)的碼值可以看成是k維空間中的一個點(diǎn)，這里k是在索引中搜索碼的字段的個數(shù)。 在B樹索引中，二維空間域中的點(diǎn)是全排序的。相對而言，空間索引是基于臨近度（在底層的二維空間中）來存儲數(shù)據(jù)項(xiàng)的。第22頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五3、空間填充曲線的索引（1）空間填充曲線（2）Z-排序的四叉樹表示（3） Z-排序的空間查詢4、網(wǎng)格文件 網(wǎng)格空間索引基本思想是將研究區(qū)域用橫豎線條劃分大致相等和不等的網(wǎng)格，記錄每一個網(wǎng)格所包含的空間實(shí)體。 網(wǎng)格文件在給定的數(shù)據(jù)集中以反映數(shù)據(jù)分布的方式將數(shù)據(jù)空間進(jìn)行劃分。它依賴于網(wǎng)格目錄識別出包含所需要的點(diǎn)的數(shù)據(jù)頁。 網(wǎng)格文件不是存儲區(qū)域數(shù)據(jù)的好結(jié)構(gòu)。第23頁，共25頁，2022年，5月20日，12點(diǎn)30分，星期五