空間數據結構 （SpatiaI Data Structure）是指空間數據適合於計算機存儲、管理、處理的邏輯結構，是空間數據在計算機內的組織和編碼形式，是地理實體的空間排列和相互關係的抽象描述。
空間數據編碼是指空間數據結構的具體實現，是將圖形數據、影像數據、統計數據等資料按一定的數據結構轉換為適合計算機存儲和處理的形式。不同數據源採用不同的數據結構處理，內容相差極大，計算機處理數據的效率很大程度取決於數據結構。
基本介紹
- 中文名：空間數據結構
- 外文名：SpatiaI Data Structure
- 具體實現：空間數據編碼
- 釋義：數據適於計算機存儲等的邏輯結構
- 組成：空間數據單元
- 結構：層次、網路等、關係、數據
定義,空間數據及特徵,空間數據結構,散列方法,四叉樹及其變形樹,k-d樹及其變形樹,R樹,GIS領域套用,層次數據結構,關係數據結構,網路數據結構,超圖數據結構,發展現狀及趨勢,
定義
空間數據結構是指空間數據的編排方式和組織關係。空間數據編碼是指空間數據結構的具體實現，是將圖形數據、影像數據、統計數據等資料按一定的數據結構轉換為適合計算機存儲和處理的形式。不同數據源採用不同的數據結構處理，內容相差極大，計算機處理數據的效率很大程度取決於數據結構。
空間數據結構是帶有結構的空間數據單元的集合。這些數據單元是數據的基本單位, 一個數據單元可以由幾個數據項組成, 數據單元之間存在某種聯繫叫做結構。所以, 研究空間數據結構, 是指研究空間目標間的相關關係, 包括幾何和非幾何的關係。數據結構是數據模型的表述, 數據結構往往通過一系列的圖表和矩陣, 以及計算機碼的數據記錄來說明。
空間數據及特徵
隨著多維數據在計算機套用方面的數量的增長，空間數據管理的研究成了當前的熱點。空間數據(多維數據)包括：點、線段、區域，三維或更高維中的多面體。嚴格來講，空間資料庫包含帶有對象的外在知識、對象的擴展以及對象在空間的位置等多維數據。這些對象是用矢量格式進行描述的。空間數據被視為一種特殊的數據，它們具有要求用非標準資料庫管理方法的幾個特點：
①空間對象結構的複雜性。比如一個簡單的點或一組任意分布的多邊形，都是空間數據對象。有固定長度的關聯資料庫元組不適合存儲這樣的數據格式。
②空間數據的動態性。這種特點要求數據結構能適應頻繁地插入、刪除以及更新對象。
⑧空間資料庫不斷增長。在地理地圖或者VLSI電路的對象數目往往需要數千兆位元組的存儲空間。
④沒有空間代數標準。它們通常根據特定空間資料庫的套用領域來決定空間操作。
⑤空間操作不封閉。如兩個空間對象的交集可能是一組點、線或區域。
⑥空間數據的多維性。該特性使傳統資料庫索引方法(如B樹或線性散列法)不適合索引空間數據。
空間數據結構
下面列舉了一些最突出的傳統空間數據結構視圖：格子檔案及其變形、四又樹及其變形樹、k-d樹及其變形樹、R樹及其變形樹。
散列方法
(1)格子檔案及其變形。它是散列方法的代表，適合於存取點數據。格子檔案是格子方法的變形，但其單元分割線不一定等距。其目標是最多經過兩次磁碟存取獲得記錄並高效地處理範圍查詢。這是通過格子塊組成的格子目錄來完成的。在一個格子塊里的所有記錄都是存儲在相同的存儲桶中。只要格子塊可以合併構成記錄空間的k維矩形，幾個格子塊就可以共享一個存儲桶。
圖1表示了一個容量為四個數據點的數據桶的格子檔案。
格子檔案
格子檔案圖1中表示了在x軸和y軸上帶有比例尺的目錄。為了回響符合精確匹配的查詢，人們首先使用標尺來定位出包含查找點的單元。如果該格子單元不在主存中，需要一次磁碟存取，並裝入有可能包含匹配數據的參考頁的單元
另一個技術術語叫多重頁： 多重頁也是使用稱為“軸向排列”的線性標尺形式的目錄。然而，多重頁存取一個數據及其潛在溢出鏈不是使用格子目錄，而是使用直接從線性標尺計算得出來的地址。多重頁分為動態和靜態兩種。在動態多重頁中，設定在探測器因子上的範圍控制其執行(定義為一個探測器的頁存取平均數)；在靜態多重頁中，設定在裝載因子上的範圍或平均頁占有控制其執行
把格子檔案與多重頁相比較．將會發現格子檔案把多重頁作為格子目錄的索引來使用。因此，多重頁不需要格子目錄而節約了空間，但這需要以存儲桶的溢出為代價 這意味著多重頁能夠獲得平均情形時的性能，卻不能保證兩次磁碟存取得到記錄。另外，在分離和合併存儲桶時，在多重頁中的插入和刪除包括數據頁的整個行和列(在二維情況下)．然而格子檔案可以每次將一頁分成幾部分．並將格子目錄中更多的全局操作局部化。
(2)其他散列方法一EXCELL方法是一棵通過地址計算以陣列的形式提供存取目錄的二叉查找樹，也可以視為從多維點數據的可擴展散列變化而來。格子檔案的超平面劃分帶有任意性，EXCELL方法則將區域勻稱分解，所有的格子單元大小相等。為了在插入操作時保持該特性，每一次新的分解使目錄的大小加倍。為緩解這個問題，後來提出一種分級的方法，引進溢出頁來限制分級深度
二級格子檔案是另一種散列法，其基本思想是用另一個格子檔案來管理格子目錄。這兩級中的第一級稱為根目錄，是第二級目錄的目錄根目錄條目包含了更低一級的目錄頁的指針，該人口依次包含指向數據頁的指針。有了第二級，劃分常常被限制在子目錄區域而沒有對其他區域造成太大影響。孿生格子檔案又是另一種散列法，該方法與通過引入的二級格子檔案的初始格子檔案相比增加了空間的利用率。這兩個格子檔案之間的聯繫不是分級而是在某種程度上有更多的點平衡。在兩個檔案之間的數據是動態分布的 如果在存儲桶的點的數目超過了給定的限度，孿生格子檔案設法重新分布在兩個格子檔案之間的點。點從初始檔案P向第二級檔案S的傳遞可能造成在S中的存儲桶上溢 然而，也可能意味著在P中存儲桶下溢，可能依次導致存儲桶合併從而減少在P中的存儲桶。孿生格子檔案的目標是將兩個格子檔案P和S中的存儲桶總數減到最少。
四叉樹及其變形樹
(1)四又樹。它具有一個根節點，每箇中問節點有四個孩子。四叉樹的每個節點對應一個正方形。四叉樹主要用於對點數據、曲線、表面以及體的表示。四叉樹每一層分解成等同的部分(如規則多邊形)，也可以由輸入決定。分解的方案可以事先確定，或者由輸入數據的特性決定。對有些套用能夠區分它們是以指定區域的邊界(如曲線和表面)為基礎的數據結構或以組織它們的內部(如面積和體積)為基礎的數據結構。
區域的二元陣列及相應的四叉樹
區域的二元陣列及相應的四叉樹(2)四叉樹的變形樹。區域四叉樹是最重要的表示法一個區域四叉樹是基於有邊界的圖像陣列劃分連續的四個相同大小的正方形區域(平行於軸)。如果該陣列完全地由1或0表示，那么就劃分它為一個個正方形區域，直到得到的塊全由1或全由0組成。四叉樹的數據結構也可表示三維或更高維中圖像，八又樹的數據結構是四叉樹在三維空間的推廣。
k-d樹及其變形樹
k-d樹是早期的多維數據結構，也是一棵存儲k維空間點的二叉搜尋樹。在每一個中間節點．k-d樹把k維空間分成兩個k-1維超平面，即k-d樹頂層節點按一維劃分，下一層節點按另一維進行各個維循環往復。當一個節點中的點數少於給定的最大點數時結束劃分。圖表示了二維空間中的一組點以及這些點的k-d樹表示。每條線對應於樹中的一個節點，葉節點的最大點數設為1。在X軸上標註深度為偶數的值(根的深度認為是0)，Y軸上標註深度為奇數的值。
平面上的點的分布及對應的二叉樹三維以上的點數據更適合使用k-d樹。k-d樹劃分超平面是由點的位置決定，而不是以最可能的位置劃分平面，從而導致了該樹是一棵非平衡樹 自適應k-d樹是改進的k-d樹，在劃分時選擇了一個把空間分成兩個擁有相同數量的點的子空間的超平面。超平面仍然與軸平行，但不包含點 樹的內部節點包含維(如X或Y)，各自的坐標是分離的。所有的點都存儲在葉子上 葉子可容納的點數固定，如果超過了這個數，就要進行劃分。直觀上，k-d樹適合靜態結構，如果頻繁進行插入和刪除操作，很難維持其平衡。
R樹
R樹是分級數據結構。R樹及其變形是空間資料庫套用最多的數據結構。R樹是用來存儲多維對象的MBB(最小的邊界框)，而不是最初的空間對象。n維對象的MBB是包含初始對象的最小的n維矩形。R樹與B樹相似，也是平衡樹，它們能確保高效地利用存儲空間。MBB並不等於實際對象，故R村不能完全回響一個查詢清求，除非資料庫中的對象就是MBB。R村常常用來處理與查詢對象的MBB相交的資料庫對象的初步篩選。
每一個R樹節點對應一個磁碟頁和一個n維的矩形。每一個非葉子節點包含了形如(Ref，Rect)的條目，這裡Ref是孩子節點的地址，Rect是孩子節點的所有條目的MBB 葉子包含了同樣格式的條目，這時Ref指向資料庫對象．Rect是對象的MBB。
GIS領域套用
GIS(地理信息系統)是採集、存貯、處理、分析、轉換和輸出空間數據的計算機系統。空間數據模型(Spatial Data Model)和空間數據結構(Spatial Data Structure)是任何地理信息系統設計的核心, 也是推動地理信息系統發展, 使之不斷更新的關鍵。能否在空間數據結構和空間數據模型基礎上建立起高效優良的空間資料庫, 已經成為當前地理信息系統領域的研究熱點。
層次數據結構
層次數據結構（Hierachical Structure)即樹狀結構。主要表達數據元素之間的層次關係, 通常是1 對多的關係, 每層的數據與下一層中的多個數據元素相關。樹狀結構中只有一個根節點稱為主人, 其餘若干節點稱為成員, 而每一個節點又同時作為下一層節點的主人，如經典的四叉樹和八叉樹。
關係數據結構
在關係數據結構(Relational Structure)中, 關係表是一個二維數據, 數據單元之間是線性關係。實體的層次關係是用列來表示的。每一個數據單元只有一個直接前趨和一個直接後繼。關係結構是一個二維結構, 建立的二維表稱為關係表。一個實體由若干關係組成。二維表的集合就構成關係結構。
網路數據結構
網路數據結構(Network Structure)層次結構相比, 它有多個主人, 因此, 是多對多的關係。
網路結構圖如圖3所示。P , S , R 都是實體, 它們之間的關係用網路來聯接。一個子節點可以有多個父節點。例如, 圖3 中, R2 有S1 , S2 , S3 三個父節點。或者說一個成員可以有多個主人。當然, 多個主人也可以有多個人員。
超圖數據結構
超圖數據結構(The Hypergraph Based DataStructure)。上述幾種數據結構存在一些缺陷, 但是超圖數據結構能夠較好地解決諸如關係數據結構無法表達隱含關係, 缺乏完整性;樹狀數據結構不適合反映非等級關係;網狀數據結構不適合反映非層次結構等問題。
超圖的概念是圖的概念的一個擴展。在圖G =(V ,X)中,X 的每一個元素可以看作是V 的一個二元子集。設V ={v1 , v2 , ..., vp}是一個非空有限集, 令X ={x1 , x2 , ..., xq}是V 的q 個子集的一個組, 則稱二元組H =(V , X)為一個超圖。
發展現狀及趨勢
(1)全球數據模型。隨著全球的變化, 以及信息交換量日益擴大, 資料庫的設計提升到了全球的角度, 迫切需要建立全球數據模型。這樣的系統, 往往是:矢量數據模型用經緯度, 利用比例尺衛星影像, 以小比例尺圖形分析為手段。但是因為拓撲關係不可能包括任何立體球面, 因此, 必須建立球體數據模型,最終達成全球資料庫的建立。
二十面體模型 全球數據模型
二十面體模型 全球數據模型(2)時空數據模型。
通常地理信息系統致力於發展二維數據模型, 但是, 隨著遙感技術的發展, 隨著數據量的複雜度增大和海量數據的出現, 時間序列變化很大, 建立時間序列資料庫已經非常困難, 因此很有必要突破二維平面的限制, 建立一種全新的時空數據模型(Space TimeData Model), 或者稱為四維數據模型, 來解決諸如區域的動態監測、戰場信息的動態管理等問題。如何建立時空數據模型和建立怎樣的時空數據模型已經成為當今GIS 領域的研究熱點。
