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

時間：2022-10-31 04:30:01 | 來源：信息時代

時間：2022-10-31 04:30:01 來源：信息時代

    空間索引 : 在存儲空間數(shù)據(jù)時依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系,按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu)。其中包含空間對象的概要信息,如對象的標識、外接矩形以及指向空間對象實體的指針。
1. R-樹(R-tree)
R-樹是B-樹在多維空間的擴展,它由Guttman于1984年提出。一棵R-樹包括葉子結(jié)點和索引結(jié)點兩類結(jié)點。對于一棵具有.M個扇出(即M階)的R-樹來說,其結(jié)點結(jié)構(gòu)可描述如下:
葉子結(jié)點: (Count,Level,<OI₁,MBR₁>,<OI₂,MBR₂>,…,<OI_M,MBR_M>);
索引結(jié)點: (Count,Level,<P₁,MBR₁>,<P₂,MBR₂>,…,<P_M,MBR_M>); 其中,<OI_i,MBR_i>稱為數(shù)據(jù)項,OI_i為空間對象的標識,MBR_i為該空間對象在k維空間中的最小包圍矩形。<P_i,MBR_i>稱為索引項,P_i是指向下一層子樹根結(jié)點的指針,MBR_i代表其索引的子樹空間,是包絡(luò)其子樹根結(jié)點中所有數(shù)據(jù)項或索引項的最小包圍矩形。Count代表每個結(jié)點中含有的索引項或數(shù)據(jù)項個數(shù)(即該結(jié)點的“孩子結(jié)點”個數(shù)),并且Count≤M。Level表示該結(jié)點在樹中的層數(shù)。令m為結(jié)點包含索引項或數(shù)據(jù)項的最小數(shù)目,且m滿足2≤m≤M/2。如果結(jié)點所包含的索引項個數(shù)或數(shù)據(jù)項個數(shù)小于m,則會產(chǎn)生下溢(underflow); 反之,如果結(jié)點所包含的索引項個數(shù)或數(shù)據(jù)項個數(shù)大于M,則會發(fā)生上溢(overflow)。
一棵R-樹必須滿足性質(zhì):①若根結(jié)點不是葉子結(jié)點,則至少有兩棵子樹; ②除根結(jié)點以外的所有索引結(jié)點至多有M棵子樹,至少有m棵子樹;③每個葉子結(jié)點均包含m至M個數(shù)據(jù)項;④所有的葉子結(jié)點都出現(xiàn)在同一層上; ⑤所有結(jié)點都需要相同的存儲空間(通常為一個磁盤頁面)。
此外,R-樹還具有特點: ①葉子結(jié)點中的數(shù)據(jù)項所包圍的空間可能重疊; ②索引結(jié)點中的索引項所包圍的空間也可能重疊: ③由于上述重疊性的存在,因此,即使對于精確匹配查找,也會存在多條查找路徑。
圖1描述了對應空間對象分布的一棵R-樹,空間對象的分布則如圖2所示。在圖1中,實線矩形框表示空間對象的MBR,即數(shù)據(jù)矩形;虛線矩形框表示索引結(jié)點中索引項對應的索引空間,即索引矩形或索引MBR。從圖1中可以看出,索引矩形允許重復。

圖1 空間對象分布的R-樹

為找到與查找區(qū)域相交的所有空間對象,查找必須從根結(jié)點進入,然后遞歸遍歷所有索引空間與查找區(qū)域相交的子樹,直至到達葉子結(jié)點。這時,檢測葉子結(jié)點中數(shù)據(jù)項的MBR與查找區(qū)域,如果相交,就提取對應的對象的幾何信息進行計算。R-樹適用的維數(shù)并不高,通常為2～5維,而且子樹的矩形區(qū)域可以有重疊,因此往往存在多條查找路徑,而其中的某些查找路徑往往不包含查找結(jié)果,這無疑增加了不必要的查詢響應時間。

圖2 空間對象的分布

2. R⁺-樹(R⁺-tree)
R⁺-樹是R-樹的一種變體,主要是針對R-樹中兄弟結(jié)點的MBR重疊后,導致空間搜索性能較差的特點提出的。其改進的主要思想是: 如果裁減數(shù)據(jù)矩形,那么可以獲得中間結(jié)點索引矩形的零重疊,因此,對于點查詢,查找路徑可以有一條; 對于區(qū)域查詢,查找性能也可以得到提高。R⁺-樹中,兄弟結(jié)點之間的MBR不允許重疊,這使得空間搜索的性能較好,但由于在插入和刪除時需保證兄弟結(jié)點之間的MBR不能重疊,因此插入和刪除操作的效率較低。
R⁺-樹具有特點:①對于索引結(jié)點中的任意一個索引項〈P_i,MBR_i〉,我們說P_i指向的子樹包含索引矩形R,當且僅當R被MBR_i所覆蓋(cover); P_i指向的子樹包含數(shù)據(jù)矩形D,當且僅當D與MBR_i重疊(overlap)。②對于索引結(jié)點中的任意兩個索引項〈P_i,MBR_i〉和〈P_j,MBR_j〉,MBR_i和MBR_j的重疊(overlap)為零。③葉子結(jié)點中的數(shù)據(jù)矩形允許并可能重疊。④根結(jié)點如果不是葉子結(jié)點,則至少有兩個孩子。⑤所有的葉子結(jié)點都在同一層次上。
顯然,R⁺-樹與R-樹的區(qū)別在于以下三點: ①R⁺-樹中的結(jié)點對數(shù)據(jù)項和索引項的填充個數(shù)沒有嚴格限制(R-樹要求至少有m個)。②R⁺-樹索引結(jié)點的索引矩形不允許重疊(R-樹的索引矩形允許重疊)。③R⁺-樹中空間對象標識可重復存儲在多個葉子結(jié)點中(R-樹空間對象無重復存儲)。
R⁺-樹上的查找操作與R-樹相似。與R-樹相比,對于范圍查找,R⁺-樹的查找路徑應該可以減少,但仍然可能有多條;對于點查找,R⁺-樹通過一條路徑就可以得到查找結(jié)果。