R+樹

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

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

R+樹和R樹的區別

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

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

優勢

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

劣勢

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

參考資料

• T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects（頁面存檔備份，存於網際網路檔案館）. In VLDB, 1987.