Can you summarize the following document?
        
  R樹的核心思想是聚合距離相近的節點並在樹結構的上一層將其表示為這些節點的最小外接矩形,這個最小外接矩形就成為上一層的一個節點。R樹的“R”代表“Rectangle(矩形)”。因為所有節點都在它們的最小外接矩形中,所以跟某個矩形不相交的查詢就一定跟這個矩形中的所有節點都不相交。葉子節點上的每個矩形都代表一個物件,節點都是物件的聚合,並且越往上層聚合的物件就越多。也可以把每一層看做是對資料集的近似,葉子節點層是最細粒度的近似,與資料集相似度100%,越往上層越粗糙。  跟B樹類似,R樹也是平衡樹(所以所有葉子節點都在同一深度)。它把資料按(記憶體)頁儲存,是為磁碟儲存設計的(跟資料庫的做法相同)。每一頁可以儲存不超過一個上限的條目,這個上限一般用formula_1表示。R樹會在除根節點以外的節點上維持資料條目不小於最小條目數。根據經驗,最小條目數在條目上限的30%–40%時效能最佳,而B樹會維持條目上限的50%,B*樹甚至維持條目上限的66%。這麼做的原因是平衡空間資料比平衡B樹上的線性資料更復雜。  跟其他樹結構一樣,R樹的搜尋演算法(例如:交集,子集,最鄰近搜尋)也非常簡單。核心思想是畫出查詢語句相應的邊框,並用它來決定要不要搜尋某個子樹。這樣在搜尋時可以跳過樹上的大部分節點。跟B樹類似,這個特性讓R樹可以把整棵樹放在磁碟裡,在需要的時候再把節點讀進記憶體頁,從而可以應用在大資料集和資料庫上。  R樹的主要難點在於構建一棵既能保持平衡(所有葉子節點在同一層),又能讓樹上的矩形既不包括太多空白區域也不過多相交(這樣在搜尋的時候可以處理儘量少的子樹)的高效的樹。例如,最初的通過插入節點來構建一棵高效的R樹的構想是選擇一棵子樹插入,使得對其外接矩形的擴張最小。填滿一頁後,把資料分成兩份,使它們分別包括儘量小的區域。大部分關於R樹的研究和改進都是關於如何改進建樹的過程。它們可以分為兩類,一類是如何從頭開始構建一棵高效的樹(被稱為批量載入),另一類是如何在一棵已經存在的樹上插入和刪除。  R樹不保證最壞情況下的效能,但是在現實資料上一般表現不錯。理論上來說,批量載入的優先順序R樹是最壞情況下的最優解,但由於複雜度太高,目前還沒有在實際應用中獲得關注。  當資料被構建成R樹時,任意Lp空間中的資料的最近k個鄰居都可以很高效地用空間交集計算 。這對很多基於最近鄰居法的演算法(例如本地異常因子演算法)都很有幫助。 DeLi-Clu提出的Density-Link-Clustering是一種使用R樹來進行空間交集,從而高效地計算OPTICS聚類的聚類分析演算法.

  

  R樹的資料按(記憶體)頁儲存,每一頁儲存多條資料,資料條數不超過一個事先定義的最大值,一般會多於最小值。非葉子節點上的每一條資料由指向子節點的識別符號和該子節點的外接矩形組成。葉子節點則儲存每個物件需要的資料,一般是一個外接矩形和指向資料的識別符號。如果是點資料,葉子節點只需要儲存這些點本身。如果是多邊形資料(一般資料量很大的多邊形需要額外儲存),一般的做法是在葉子節點中儲存多邊形的最小外接矩形和指向這個多邊形的資料的唯一識別符號。

  輸入是一個搜尋矩形(搜尋框)。搜尋演算法和B+樹類似,從根節點開始,每個非葉子節點包含一系列外接矩形和指向對應子節點的指標,而葉子節點則包含空間物件的外接矩形以及這些空間物件(或者指向它們的指標)。對於搜尋路徑上的每個節點,遍歷其中的外接矩形,如果與搜尋框相交就深入對應的子節點繼續搜尋。這樣遞迴地搜尋下去,直到所有相交的矩形都被訪問過為止。如果搜尋到一個葉子節點,則嘗試比較搜尋框與它的外接矩形和資料(如果有的話),如果該葉子節點在搜尋框中,則把它加入搜尋結果。  對於最鄰近搜尋這類優先順序搜尋,可以查詢一個矩形或者一個點。 先把根節點加入優先佇列,然後查詢優先佇列中離查詢的矩形或者點最近的項,直到優先佇列被清空或者已經得到要求的鄰居數。從優先佇列頂端取出每個節點時先將其展開,然後把它的子節點插回優先佇列。如果取出的是子節點就直接加入搜尋結果 。這個方法可以應用於包括(地理資訊的)大圓距離在內的多種距離度量方式。

  插入節點時,演算法從樹的根節點開始遞迴地向下遍歷。檢查當前節點中所有外接矩形,並啟發式地選擇在哪個子節點中插入(例如選擇插入後外接矩形擴張最小的那個子節點),然後進入選擇的那個子節點繼續檢查,直到到達葉子節點。滿的葉子節點應該在插入之前分割,所以插入時到達的葉子節點一定有空位來寫資料。由於把整棵樹遍歷一遍代價太大,在分割葉子節點時應該使用啟發式演算法。把新分割的節點新增進上一層節點,如果這個操作填滿了上一層,就繼續分割,直到到達根節點。如果跟節點也被填滿,就分割根節點並建立一個新的根節點,這樣樹就多了一層。

  插入演算法在樹的每一層都要決定把新的資料插入到哪個子樹中。如果只有一個外接矩形包含新資料,那麼很容易選擇。但如果有多個外接矩形包含新資料,或者所有外界矩形都不包含新資料,那麼選擇演算法會極大地影響R樹的效能。  經典R樹的實現會把資料插入到外接矩形需要增長面積最小的那個子樹。而更進一步的R*樹則使用了一種混合的啟發式演算法。如果需要選擇的子樹是葉子節點,它會選擇造成最小重疊的子樹,如果有多個選擇不分上下,則選擇外接矩形增長最小的子樹,再不分上下則選擇面積最小的子樹。如果需要選擇的子樹不是葉子節點,演算法和R樹類似,但在不分上下時選擇面積較小的子樹。比R樹更少的重疊是R*樹對R樹的主要優勢之一(這也有R*樹上應用的其它啟發式演算法的原因,並不僅僅因為選擇子樹演算法的不同)。

  因為有指數多種方式來把一個節點中所有物件分割到兩個節點,我們需要使用啟發式演算法來尋找最優分割。在經典R樹中,Guttman提出了二次分割和線性分割兩種啟發式演算法。二次分割演算法在節點中查詢放在同一個節點中最糟糕的兩個物件,把它們作為兩個新節點的初始資料。然後把資料集中對其中一個新節點有最強偏向的資料(外接矩形最小面積增長)分給這個節點,直到所有資料都被分配(節點中資料多於最小條目數)。  還有其它的分割策略,例如Greene's Split,R*樹啟發式分割策略(它也試圖儘量減小重疊,但同時也偏向正方形的節點)以及Chuan-Heng Ang和T. C. Tan提出的線性分割演算法 (這種演算法會產生形狀很不規則的矩形,在很多現實資料分佈以及使用搜尋框時效率較低)。R*樹不僅使用了更高階的啟發式分割,而且還通過重新插入一些數值來試圖避免分割節點(這跟B樹平衡溢位節點的策略類似)。這個方法被證明還可以減少重疊,從而進一步提高R樹效能。  最後,X樹(可以被視為R*樹的變體)也決定避免分割節點。當X樹找不到一個好的分割方式(尤其在高維資料的情況下)時會構建一個所謂的“超節點”來放置溢位的資料。

  從一個節點中刪除一條資料可能會導致演算法需要更新它的父節點的外接矩形。但是當一個節點中的資料不足時,它不會和兄弟節點重新平衡。這個節點會被直接刪除,它的子節點(可能是子樹,不一定是葉子節點)會被重新插入。如果在這個過程中根節點只剩下一個子節點,可以把根節點刪除,樹的高度降低。
R樹是用來做空間資料儲存的樹狀資料結構。例如給地理位置,矩形和多邊形這類多維資料建立索引。R樹是由Antonin Guttman於1984年提出的。人們隨後發現它在理論和應用方面都非常實用。 在現實生活中,R樹可以用來儲存地圖上的空間資訊,例如餐館地址,或者地圖上用來構造街道,建築,湖泊邊緣和海岸線的多邊形。然後可以用它來回答“查詢距離我2千米以內的博物館”,“檢索距離我2千米以內的所有路段”(然後顯示在導航系統中)或者“查詢(直線距離)最近的加油站”這類問題。R樹還可以用來加速使用包括大圓距離在內的各種距離度量方式的最鄰近搜尋。