资料：

• R 树基础：空间数据索引RTree（R树）完全解析及Java实现
• 实用场景 基于HBase与静态多级格网索引的地表覆盖数据高效检索方法

如何理解 R 树

• R 树是平衡树；
• 平衡树要求节点有序；
• R 树的节点是高维数据，比如对于二维来说，存储的是 MBR(最小限定矩形)；
• 高维数据的顺序如何定义？
  • 对一维的线段来说，定义一个坐标系，存在一个原点，线段左端点距原点的距离作为排序的依据；
  • 对二维的MBR来说(可以用左下，右上两个点的坐标表示一个矩形)，怎么定义？
    • 猜想，定义平面直角坐标系，以左下点的坐标(x,y)作为排序的依据：比如(1,2)<(1,3)<(2,1)；

基本概念

MBR

Packed 1-D R-Tree

2-D R-Tree

上图中，总计 12 个实线框，正好对应 R 树中 12 个叶子节点 R8~R19;

实际应用

道路索引

每一条路使用一个最小MBB来进行包裹，使它成为R树的叶子结点（也就是那些数据结点）

将每一条路的最小MBB作为R树的数据单元来进行构建R树(这里采用的是R树的改进版本R*树)