R+樹可以用地址來查詢數據。地址用坐標來表示，一般是(x, y)軸坐標，常用於地理坐標。單個地址查詢問題早已被解決，而多地址查詢，或者查詢在坐標繫上的附近地址則需要更巧妙的算法。
基本介紹
- 中文名：R+樹
- 外文名：R+ tree
- 作用：用地址來查詢數據
- 表示：地址用坐標來表示
- 學科：數據結構
- 領域：數據結構
簡介,R+樹和R樹的區別,優勢,劣勢,
簡介
R+樹可以用地址來查詢數據。地址用坐標來表示，一般是(x, y)軸坐標，常用於地理坐標。單個地址查詢問題早已被解決，而多地址查詢，或者查詢在坐標繫上的附近地址則需要更巧妙的算法。
R+樹本質上來說是樹結構，是R樹的一個變體，也被用來檢索空間信息。
R+樹和R樹的區別
R+樹是R樹和k-d樹這兩種空間檢索方式的折中辦法。為了避免子節點重疊，R+樹允許把同一個對象插入到多個葉子節點中。當對象跟多個子節點相交時，將其切割成多份，使每一份只跟一個子節點相交。根據具體情況，可以讓每個分割持有完整或部分數據，或者把對象存儲在其它地方，每個分割持有一個指向存儲位置的標識符。定義覆蓋範圍為樹上所有外接矩形覆蓋的區域，重疊範圍為所有存在至少兩個外界矩形的區域。讓覆蓋範圍儘量小可以減少R樹上節點涵蓋的“無效區”，也就是不存在對象的區域。讓重疊範圍儘量小可以減少搜尋路徑。就減少訪問時間而言，最小化重疊範圍比最小化覆蓋範圍更關鍵。為了提高搜尋性能，要讓覆蓋範圍和重疊範圍都儘量小。
R+樹和R樹的區別在於：R+樹的節點並不保證至少填充一半，節點互不相交，並且指向同一個對象的標識符可能會存在於多個葉子節點中。
優勢
因為節點互不相交，所以在搜尋時最多只會有一個子樹（子節點）覆蓋一個點，因此R+樹的點搜尋操作性能極佳。在搜尋一個點時，算法只需要沿著一條路徑一直往下訪問就可以了，這要比R樹的訪問量少很多。
劣勢
因為一個對象的外界矩形可能會被分割成多份分別插入不同的節點，所以使用同樣的數據集，R+樹可能比R樹需要更多空間。創建和維護R+樹也比R樹和其它R樹的變體更加複雜。
