跳至內容

R+樹

維基百科,自由的百科全書

R+樹(英語:R+ tree)可以用地址來查詢數據。地址用坐標來表示,一般是(x, y)軸坐標,常用於地理坐標。單個地址查詢問題早已被解決,而多地址查詢,或者查詢在坐標系上的附近地址則需要更巧妙的算法。

R+樹本質上來說是樹結構,是R樹的一個變體,也被用來檢索空間信息。

R+樹和R樹的區別

R+樹是R樹k-d樹這兩種空間檢索方式的折中辦法。為了避免子節點重疊,R+樹允許把同一個對象插入到多個葉子節點中。當對象跟多個子節點相交時,將其切割成多份,使每一份只跟一個子節點相交。根據具體情況,可以讓每個分割持有完整或部分數據,或者把對象存儲在其它地方,每個分割持有一個指向存儲位置的標識符。定義覆蓋範圍為樹上所有外接矩形覆蓋的區域,重疊範圍為所有存在至少兩個外界矩形的區域[1]。讓覆蓋範圍儘量小可以減少R樹上節點涵蓋的「無效區」,也就是不存在對象的區域。讓重疊範圍儘量小可以減少搜索路徑。就減少訪問時間而言,最小化重疊範圍比最小化覆蓋範圍更關鍵。為了提高搜索性能,要讓覆蓋範圍和重疊範圍都儘量小。

R+樹和R樹的區別在於:R+樹的節點並不保證至少填充一半,節點互不相交,並且指向同一個對象的標識符可能會存在於多個葉子節點中。

優勢

因為節點互不相交,所以在搜索時最多只會有一個子樹(子節點)覆蓋一個點,因此R+樹的點搜索操作性能極佳。在搜索一個點時,算法只需要沿着一條路徑一直往下訪問就可以了,這要比R樹的訪問量少很多。

劣勢

因為一個對象的外接矩形可能會被分割成多份分別插入不同的節點,所以使用同樣的數據集,R+樹可能比R樹需要更多空間。創建和維護R+樹也比R樹和其它R樹的變體更加複雜。

註釋

  1. ^ Härder, Rahm, Theo, Erhard. Datenbanksysteme. 2., überarb. Aufl. Berlin [etc.]: Gardners Books. 2007: 285, 286. ISBN 3-540-42133-5. 

參考資料