背景
工作中經(jīng)常需要跟空間數(shù)據(jù)打交道，因此頻繁使用一個工具類com.vividsolutions.jts.index.strtree.STRtree栅受。STRtree類似于一個集合麻捻，向其插入一些帶空間信息的數(shù)據(jù)后可以很便利地按范圍查詢空間數(shù)據(jù)，如下圖示意浮创。
由于不清楚STRtree的查詢實(shí)現(xiàn)邏輯诊沪，為探明原因及避免后續(xù)踩坑了解了一下养筒，發(fā)現(xiàn)STRtree應(yīng)用了非常精巧且應(yīng)用廣泛的空間索引結(jié)構(gòu)R樹（R-Tree）及優(yōu)秀的批量加載算法STR。下文我們將從R樹開始介紹端姚，進(jìn)一步了解STR算法晕粪，并說明一些STRtree相關(guān)的注意事項。
R樹是什么
R樹是用來做空間數(shù)據(jù)存儲的樹狀數(shù)據(jù)結(jié)構(gòu)渐裸。例如給地理位置巫湘，矩形和多邊形這類多維數(shù)據(jù)建立索引。R樹是由Antonin Guttman于1984年提出的昏鹃。 ...... 可以用它來回答“查找距離我2千米以內(nèi)的博物館”尚氛，“檢索距離我2千米以內(nèi)的所有路段”（然后顯示在導(dǎo)航系統(tǒng)中）或者“查找（直線距離）最近的加油站”這類問題。R樹還可以用來加速使用包括大圓距離在內(nèi)的各種距離度量方式的最鄰近搜索洞渤。
——維基百科
R樹是一種層次數(shù)據(jù)結(jié)構(gòu)阅嘶，它是B樹在k維空間上的自然擴(kuò)展，因此和B樹一樣载迄，R樹是一種高度平衡樹讯柔，在葉結(jié)點(diǎn)中包含指向?qū)嶋H數(shù)據(jù)對象的指針。
定義：
- 除非它是根結(jié)點(diǎn)之外护昧，所有葉子結(jié)點(diǎn)包含有m至M個記錄索引（條目）魂迄。作為根結(jié)點(diǎn)的葉子結(jié)點(diǎn)所具有的記錄個數(shù)可以少于m。通常捏卓，m=M/2极祸。
- 對于所有在葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點(diǎn)的矩形（注意：此處所說的“矩形”是可以擴(kuò)展到高維空間的）怠晴。
- 每一個非葉子結(jié)點(diǎn)擁有m至M個孩子結(jié)點(diǎn)遥金，除非它是根結(jié)點(diǎn)。
- 對于在非葉子結(jié)點(diǎn)上的每一個條目蒜田，i是最小的可以在空間上完全覆蓋這些條目所代表的點(diǎn)的矩形（同性質(zhì)2）稿械。
- 所有葉子結(jié)點(diǎn)都位于同一層，因此R樹為平衡樹冲粤。
簡單來說美莫，R樹種的每個節(jié)點(diǎn)都是一個矩形，而且是節(jié)點(diǎn)數(shù)據(jù)的最小外接矩形（MBR梯捕，Minimun Bounding Rectangle）厢呵，即覆蓋內(nèi)部幾何圖形的最小矩形邊界。
MBR本身通過x傀顾、y坐標(biāo)容易計算襟铭，計算MBR相交也十分簡單高效，適用于應(yīng)用在索引結(jié)構(gòu)中。
其中寒砖，葉子結(jié)點(diǎn)為實(shí)際結(jié)點(diǎn)空間數(shù)據(jù)的MBR赐劣；非葉子結(jié)點(diǎn)則為其所有子節(jié)點(diǎn)形成的MBR，即剛好包裹住所有子節(jié)點(diǎn)哩都。
從定義中可以看出來日麸，其結(jié)構(gòu)與B樹類似：
- 高度平衡孽锥，查詢性能穩(wěn)定
- 子節(jié)點(diǎn)數(shù)量有限制即存在節(jié)點(diǎn)分裂和合并
- 但節(jié)點(diǎn)不存儲數(shù)據(jù)概行，正如作者Guttman論文所說，整個R樹是完全針對計算機(jī)空間數(shù)據(jù)存儲而設(shè)計的索引結(jié)構(gòu)献雅。
簡單的部分到此為止碉考，R樹具體的插入刪除規(guī)則涉及到復(fù)雜的規(guī)則，在節(jié)點(diǎn)分裂和合并之外還涉及父節(jié)點(diǎn)MBR的調(diào)整等挺身，詳情可參考原論文或其他資料侯谁。
R樹能做什么
在不使用R樹時，最基礎(chǔ)的范圍搜索方法是遍歷整個數(shù)據(jù)集章钾，將所有落在范圍內(nèi)的數(shù)據(jù)返回墙贱，在較大數(shù)據(jù)集中這個代價顯然是不可接受的。當(dāng)然通過網(wǎng)格劃分?jǐn)?shù)據(jù)集的方式也可以大大縮小候選數(shù)據(jù)集贱傀，但仍需要遍歷候選網(wǎng)格的全量數(shù)據(jù)惨撇。
而R樹的搜索算法則類似B樹，從根節(jié)點(diǎn)開始府寒，根據(jù)搜索范圍找到命中的節(jié)點(diǎn)魁衙，并不斷向下查找到葉子結(jié)點(diǎn)，縮小范圍株搔，最終返回命中的數(shù)據(jù)剖淀。這非常易于理解：當(dāng)我們要找到某個商場時，思考路徑也是AA市->BB區(qū)->CC路->DD路口依次縮小范圍纤房。
但R樹與B樹最顯著的區(qū)別在于R樹在非一維空間使用MBR描述節(jié)點(diǎn)的上下界，無法像B樹節(jié)點(diǎn)一樣準(zhǔn)確適應(yīng)子節(jié)點(diǎn)的分布炮姨。雖然通過通過MBR提高了計算和求交的效率捌刮，不過這也勢必犧牲了空間利用率（父節(jié)點(diǎn)包含了空白區(qū)域）及查詢效率（兄弟節(jié)點(diǎn)MBR可能會重疊）。
在查詢時舒岸，以下常見的情況會導(dǎo)致需要多路徑搜索：
- 兄弟節(jié)點(diǎn)MBR重疊绅作，搜索范圍命中重疊區(qū)域
- 兄弟節(jié)點(diǎn)MBR不重疊但搜索范圍跨多個節(jié)點(diǎn)，在點(diǎn)查詢時不會出現(xiàn)這種情況
現(xiàn)在我們可以理解蛾派，R樹中的R表示Rectangle棚蓄，也表明其本質(zhì)是一組有層次關(guān)系的“矩形”堕扶，在一維空間是線結(jié)構(gòu)，在沒有重疊的情況下結(jié)構(gòu)很像B樹梭依，推廣到三維則是長方體。
R樹作為一個比較寬泛的結(jié)構(gòu)定義役拴，并未限定具體的構(gòu)造方式，而基于R樹的概念及各種組織方式衍生出了龐大的R樹家族钾埂，不同組織方式的R樹變體性能差距很大河闰。其他比較有特點(diǎn)的一些變體索引結(jié)構(gòu)：
- R+樹 將跨父MBR的節(jié)點(diǎn)分割成多個MBR，冗余存儲在多個父級節(jié)點(diǎn)中褥紫，避免了兄弟節(jié)點(diǎn)MBR重疊姜性，但增加了樹的高度降低了范圍查詢效率，增刪操作也更復(fù)雜
- R*樹 優(yōu)化了插入和分裂策略髓考，并使用節(jié)點(diǎn)強(qiáng)制重插技術(shù)即在觸發(fā)分裂時優(yōu)先將子節(jié)點(diǎn)重新插入部念，整體使得MBR的結(jié)構(gòu)重疊減少，也減少了節(jié)點(diǎn)的分裂氨菇，提升查詢效率
- SS樹 使用最小外接圓替代MBR儡炼，增加了最近鄰查詢的效率，但在高維度表現(xiàn)不佳
STR R-Tree
通常從空樹開始構(gòu)建整個R樹時查蓉，將記錄逐個插入直至生成整個樹的過程中會頻繁觸發(fā)索引結(jié)構(gòu)的動態(tài)維護(hù)乌询，這對于海量空間數(shù)據(jù)的初始化而言耗時巨大，代價過高豌研。由此發(fā)展而來的Packing（批量加載）算法則可以在數(shù)據(jù)已知且相對靜態(tài)的情況下盡可能提高R樹的構(gòu)建速度并優(yōu)化索引結(jié)構(gòu)妹田。
其中Leutenegger等提出了一種STR(Sort-Tile-Recursive，遞歸網(wǎng)格排序) Packing算法鹃共，該算法易于實(shí)現(xiàn)且適用范圍較廣鬼佣，在大多數(shù)場景下表現(xiàn)良好，且易于推廣到高維空間及汉。
STR算法本質(zhì)上只是R樹的一種構(gòu)建算法沮趣，STR R-Tree本質(zhì)上仍是R樹。
STR核心思路
STR可以理解為切蛋糕坷随，首先確定一共應(yīng)該切成N份房铭，然后從左到右根據(jù)蛋糕上草莓個數(shù)豎切成sqrt(N)個中份，再從上到下把每個中份橫切成sqrt(N)個小份温眉，一趟遞歸就完成了缸匪。下一趟則是將小份蛋糕當(dāng)作草莓，繼續(xù)切直到不需要切為止类溢，自下而上遞歸構(gòu)成R樹凌蔬。
- Sort 子節(jié)點(diǎn)在某維度排序露懒，方便劃分網(wǎng)格
- Tile 網(wǎng)格化，即在某維度將數(shù)據(jù)集劃分成多個切片砂心，最終多個維度切片后綜合形成節(jié)點(diǎn)的MBR
- Recursive 遞歸處理懈词，自下而上每趟構(gòu)建R樹的一層
具體細(xì)節(jié)可以查看作者原論文，算法介紹不到一頁辩诞，概念好理解坎弯。
STR的優(yōu)勢
STR本身邏輯并不復(fù)雜，其排序和網(wǎng)格化的邏輯是與維度無關(guān)的外永，還可以拆分至按維度計算崎脉，對算法實(shí)現(xiàn)比較友好，構(gòu)建效率也高伯顶；同時囚灼，其使用遞歸和網(wǎng)格化的思路可以較好地將兄弟MBR大致分離，盡可能減少重疊區(qū)域砾淌，大多數(shù)數(shù)據(jù)分布下查詢效率較高啦撮。
補(bǔ)充
- MySql使用了R-Tree作為空間索引，參見說明文檔
-
com.vividsolutions.jts.index.strtree.STRtree是實(shí)現(xiàn)了STR packing算法的R樹索引- 在packing后（首次調(diào)用query后）不能再增刪節(jié)點(diǎn)
- STRtree通過Envelope即MBR的形式進(jìn)行查詢汪厨，因此在范圍查詢時如果范圍幾何不是矩形則需要對查詢結(jié)果做過濾處理
參考資料
R-Trees - A Dynamic Index Structure for Spatial Searching
STR: A Simple and Efficient Algorithm for R-Tree Packing
空間數(shù)據(jù)索引RTree（R樹）完全解析及Java實(shí)現(xiàn) - 佳佳牛 - 博客園
MySQL :: MySQL 5.7 Reference Manual :: 11.4.9 Creating Spatial Indexes
