Octree / R-Tree / R*-Tree 与 BSP-Tree 与其他空间分割

• 强制重插
• 节点重叠降低
• 构建质量

R*-Tree 是 R-tree 的经典改良变体，其核心改进之一是"强制重插"（forced reinsert）：当叶节点溢出时，不从零开始分裂，而是从该节点中选取一部分条目（通常是"距离节点中心最远"的若干条目）重新插入整棵树。这样缓解了节点溢出时的局部拥挤，避免过早分裂，从而降低节点间 MBR 重叠，提升查询性能。工程实现要点：溢出时按条目到节点中心距离排序，取前 30% 重插；重插可触发下级溢出，需限制重插次数（如一遍）防止无限循环。配合 R* 的"最小面积增量/最小重叠"选择策略，R*-Tree 查询性能通常优于 R-tree。

强制重插通过在溢出时"重新分配"而非"立即分裂"，把拥挤的条目分散到更合适的节点，降低重叠。它用"重插次数限制"保证终止，是 R*-Tree 查询性能的关键。

• 插入路径选择
• MBR 扩张
• 分裂策略

R-Tree 插入时，从根向下选择子树：对每个候选子树，计算把新条目加入后该子树 MBR 的面积增量，选择"面积增量最小"的子树（其最小化对父节点 MBR 的影响），若增量相同则选面积更小的。沿路径更新各节点 MBR 以包含新条目。当叶节点溢出时需分裂：用"最小包络化"（quadratic/cubic 分裂）把条目分为两组，使每组 MBR 总和最小、或使两组 MBR 重叠最小。MBR 扩张与分裂策略共同影响树的质量：好的插入减少重叠与 MBR 体积，提升查询剪枝效率。

插入策略"最小面积增量"让新条目尽量少扩张父 MBR，保持树紧凑；分裂策略最小化两组 MBR 的重叠/体积。两者共同决定 R-Tree 的查询性能。

• 删除流程
• CondenseTree
• 下溢处理

R-Tree 删除条目后，若叶节点条目数低于最小填充（下溢），不能直接删除节点（会破坏树结构），需用 CondenseTree 处理：从下溢节点向上，若某节点下溢则将其条目重新插入树的合适位置（reinsert），并删除该节点，其父节点 MBR 相应收缩。重新插入的条目可能在树中重新布局，可能再次触发下溢，需递归处理。删除比插入更难平衡的原因：插入时可按面积增量选择路径主动优化；删除是被动地移除后需修复下溢，且重新插入的条目会破坏原有布局与 MBR 的紧凑性，无法保证回到之前的平衡状态，需要持续的 CondenseTree 修复。

删除通过 CondenseTree 把下溢节点条目重新插入并收缩父 MBR，是"删除后修复"的过程。因为删除是被动触发且重新插入会扰动布局，比插入的"主动优化"更难保持平衡。

• 中位数分割构建
• 最近邻剪枝
• 维数灾难

KD-Tree 构建：每层交替选择维度，取该维度的中位数分割，左右子树分别递归，O(n log n) 构建，保证树平衡。最近邻查询：从根沿分割平面搜索，维护当前最优距离；回溯时用"节点区域到查询点的距离下界"剪枝——若节点所在超矩形到查询点的最小距离已超过当前最优，则整棵子树剪枝。高维退化的原因：维数越高，每个点与查询点的距离越接近均匀，超矩形与查询球的相交概率增大，距离下界剪枝失效，需要访问的节点指数增长，当 d 接近 log n 时退化为 O(n) 线性扫描（维数灾难）。

中位数分割保证平衡，距离下界剪枝是最近邻加速的关键；但高维时"距离接近均匀"使剪枝失效，访问节点数指数增长，故性能退化。维数灾难是 KD-Tree 的根本局限。

• GIST 框架
• MBR 维护
• 空间数据库

PostgreSQL 的 GIST（Generalized Search Tree）是通用索引框架，R-Tree 是其空间索引的实现之一。GIST 允许用户定义"键类型"（如 MBR 包围盒）与"一致性谓词"（如相交、包含）。MBR 维护：插入时沿树更新 MBR 以包含新条目，删除收缩 MBR，分裂时重新计算各节点 MBR。GIST 把 R-Tree 的 MBR 逻辑抽象为"consistency/picksplit"等回调，使空间索引可定制。工程上，GIST 用 R-Tree 的 MBR 组织支持空间查询（范围、最近邻），MBR 维护的质量直接影响查询性能。

GIST 把 R-Tree 的 MBR 维护抽象为可定制的回调（consistency、picksplit），使同一框架支持多种空间数据类型。MBR 的更新、收缩、分裂是空间索引正确性与性能的核心。

• 范围查询剪枝
• 最近邻候选列表
• 节点重叠影响

R-Tree 范围查询：从根遍历，若节点的 MBR 与查询空间不相交则整棵子树剪枝，相交则递归。最近邻查询：用优先队列维护候选分支（按 MBR 到查询点的距离排序），每次取距离最小的分支深入，更新当前最优距离，用最优距离剪枝距离更大的候选。维护候选分支列表 + 剪枝的原因是：R-Tree 的 MBR 允许重叠，一个查询可能触及多个子树，需按"距离下界"排序优先探索最有希望的，并用全局最优剪枝无希望分支。节点重叠越大，查询越可能同时进入多个重叠子树，剪枝效果越差，访问节点越多，性能下降。因此 R-tree 优化的核心是降低重叠。

候选分支列表 + 距离下界排序优先探索，配合全局最优剪枝是 R-Tree 最近邻/范围查询的标准。重叠直接导致剪枝失效，故"降低重叠"是 R-Tree 构建优化的首要目标。

• BSP 平面分割
• AABB 相交
• 查询复杂度

BSP-Tree 用平面递归二分空间，把物体组织到左右子树。碰撞检测中，查询某物体（AABB）与场景中物体的碰撞：沿 BSP 树，用查询 AABB 与分割平面的位置判断进入左/右（或两侧）子树，逐步缩小候选集合，剪枝与查询 AABB 不相交的分支。若 AABB 完全在一侧则只进入该侧，否则探查两侧。平衡 BSP 树使单次查询 O(log n)（平均），但 AABB 跨平面时需访问两侧，最坏 O(n)。Plane 分割提供空间排序，配合 AABB 剪枝实现高效碰撞检测。

BSP 用平面分割提供空间顺序，AABB 查询沿平面判断左右剪枝，平衡树平均 O(log n)。碰撞检测的剪枝依赖"查询体与空间平面的位置关系"。

• 强制重插机制
• 重叠降低
• 查询性能提升

R*-Tree 的强制重插在叶节点溢出时，把"远离节点中心"的若干条目（通常 30%）从该节点取出并重新插入整棵树，而不是立即分裂。效果：这些"离群"条目被重新分配更合适的节点，避免了它们被强行聚在溢出节点导致 MBR 膨胀与重叠；重新插入时按 R* 的"最小面积增量/最小重叠"策略选择子树，使条目分布更均匀。因此节点间 MBR 重叠显著降低，查询时剪枝更有效，访问节点更少，提升查询性能。配合"最小重叠最终选择"策略，R*-Tree 在数据集上通常优于 R-tree。

强制重插的核心是"把溢出节点的离群条目重新分配"，避免 MBR 无谓膨胀与重叠。它把"空间密集拥挤"的问题通过重插分散，换取查询剪枝效率。

• Geohash 编码
• R-Tree MBR
• 范围查询差异

Geohash 把经纬度转为二进制，交替合并经纬度比特，再用 base32 编码成字符串，空间相邻的地理位置前缀相似，把二维映射到一维字符串。范围查询：Geohash 通过"前缀匹配"覆盖区域，但需访问多个相邻前缀（边界处），且精度由格子大小决定，范围查询需枚举多个格子并去重。R-Tree 用 MBR 组织对象，范围查询沿 MBR 相交剪枝，精确高效，适合动态对象与精确空间查询。差异：Geohash 简单、适合分布式/字符串索引（如 Redis），但存在边界误差与精度限制；R-Tree 精确、支持动态但实现复杂。工程上按查询精度与分布需求选择。

Geohash 用一维前缀编码近似空间，范围查询需枚举相邻格子并有边界误差；R-Tree 用 MBR 精确剪枝，边界精确但实现复杂。差异源于"一维编码 vs 二维结构"。

• Z-order 编码
• 位交错
• Geohash 联系

Z-order（Morton code）把二维坐标映射为一维：对每维坐标的二进制位进行"位交错"（bit interleaving），把两维的比特交替合并成一个整数，使空间相邻的点在一维序上接近。Geohash 本质是 Z-order 在经纬度上的应用：把经纬度二进制位交替合并，再 base32 编码成字符串，前缀即粗略位置。Z-order 的局部性：空间相邻的点一维距离近，但"Z"字形跳跃导致某些相邻点跨度大（边界处）。Hilbert 曲线有更好的局部性。工程上，Z-order 编码简单、可用位运算实现，用于空间索引与分布式分片。

Z-order 用位交错把二维坐标压成一维整数，Geohash 是其 base32 字符串形式。映射的局部性来自"相邻坐标比特接近"，但 Z 字形有边界跳跃，是其局限。

• STR packing
• Hilbert packing
• 填充率差异

批量加载（bulk loading）在已知全部数据时构造 R-Tree，比逐点插入更高效紧凑。STR（Sort-Tile-Recursive） packing：先按 x 坐标排序，分成若干垂直条带，再按 y 排序分块，逐层递归构造，使每层 MBR 紧凑。Hilbert packing：按 Hilbert 曲线顺序排序点，连续分块构造节点，利用 Hilbert 局部性。两者都保证高填充率（接近满节点），因为按空间序分块使每个节点尽量装满。逐点插入则因逐条插入、按需分裂，节点填充率低（平均约 70%），且树更不紧凑。批量加载的填充率高、树更平衡、查询更快。

批量加载按空间序（STR/Hilbert）分块，让每个节点尽量装满且空间紧凑，填充率高；逐点插入动态分裂，填充率低。高填充率减少节点数与树高，提升查询。

• 维数灾难
• 距离均匀
• 索引退化

维数灾难指随维数增加，空间索引（KD-Tree、R-Tree 等）查询性能退化到接近线性扫描的核心现象。原因：高维空间中，任意两点间的距离趋于接近（分布集中），最近邻距离与随机点距离差别变小，导致"距离下界剪枝"失效——查询点与几乎所有数据点距离相近，无法通过距离排序排除候选。因此基于"距离剪枝"的索引（基于分区）需要访问大量节点，退化为 O(n) 线性扫描。同时高维空间中数据呈"稀疏"（超球体积集中于表面），分区与剪枝均失效。高阶索引需用近似方法（LSH、近似 ANN）应对。

维数灾难的本质是"高维距离趋于均匀"，使距离剪枝失效、分区无效。索引从"结构剪枝"退化为"线性扫描"，需转向近似最近邻方法。

• 画家算法
• BSP 排序
• 隐藏面消除

Painter's Algorithm（画家算法）按从远到近的顺序绘制多边形，遮挡关系自动正确。BSP-Tree 配合：BSP 用平面二分空间，任意视角下沿 BSP 树"从后到前"遍历即可得到多边形绘画顺序——从视点出发，先访问视点所在侧的子树（较远），再访问另一侧（较近），从而保证画家算法正确。BSP 预计算视点无关的空间排序，视点变化时只需按视点位置遍历，无需重新排序。工程上用于静态场景的隐藏面消除，动态场景需增量更新。BSP 提供"视点无关的深度排序"，是画家算法的最佳数据组织。

BSP 树使"任意视点的深度排序"成为树遍历，从后到前访问子树即画家算法顺序。它把动态排序转化为静态结构 + 视点遍历，适合静态场景。

• 三种空间结构
• 渲染应用
• 取舍

3D 渲染中：BSP-Tree 用任意平面分割，提供视点无关深度排序，适合隐藏面消除与静态场景，但构建复杂、对动态场景不友好；Octree 用立方体均分八分，结构简单、适合动态更新与场景管理，但空间划分不贴合几何，可能不平衡；KD-Tree 用轴对齐平面中位数分割，适合光线追踪的加速遍历（沿光线剪枝），平衡性好。取舍：光线追踪常用 KD-Tree（或 BVH），场景管理用 Octree，隐藏面消除用 BSP。BSP 适合静态、Octree 适合动态、KD-Tree 适合光线遍历，取决于渲染算法的需求。

三种结构的分割方式与适用场景不同：BSP 任意平面（深度排序）、Octree 固定立方体（动态场景）、KD-Tree 轴对齐中位数（光线追踪）。按渲染需求选择。

• 四叉树的点集
• R-Tree 的区域对象
• 适用边界

四叉树/八叉树把空间规则划分为格子（四/八分），适合"点集"索引：点按所在格子组织，查询在格子上剪枝，结构简单、适合均匀分布点集与动态场景。R-Tree 用 MBR 组织"区域对象"（矩形、多边形），MBR 吸收对象形状，适合区域对象索引与空间连接，支持动态插入与精确范围查询。适用边界：若数据是点且分布均匀，四叉树/八叉树简单高效；若数据是区域对象（形状各异）或需精确 MBR 查询，R-Tree 更合适。R-Tree 对区域对象更紧凑，四叉树对点集更直观，但点集也可用 R-Tree（视为退化矩形）。

四叉树按规则格子索引点集，R-Tree 用 MBR 索引区域对象。边界在"点 vs 区域、均匀 vs 各异、动态 vs 静态"——点集均匀用四叉树，区域对象用 R-Tree。

• 二维查询→一维范围
• 局部性比较
• Hilbert 优势

空间填充曲线把二维坐标映射到一维整数，使二维查询（矩形）近似对应一维的若干连续区间。Z-order 中，二维矩形覆盖的格子对应一维上多个区间（因 Z 字形跳跃），需枚举多个区间；Hilbert 曲线通过"翻转/旋转"递归逼近，使相邻格子一维距离更小，矩形覆盖的格子更接近连续区间，区间数更少。局部性：Hilbert 曲线保证任意相邻格子的一维距离有界（至多常数），而 Z-order 的 Z 字形在拐角处有大的跳跃，因此 Hilbert 的局部性更好。工程上，Hilbert 使范围查询映射到更少的一维区间，减少查询开销。

局部性差异源于"相邻格子的连续程度"：Z-order 有 Z 字形跳跃，Hilbert 保证相邻距离有界。更好的局部性使二维查询映射到更少的一维区间，查询更高效。

• Hilbert 填充
• 缓存局部性
• 性能优化

用 Hilbert 曲线排序空间对象后填充 R*-Tree（Hilbert packing），使空间上相邻的对象在存储/节点中也相邻，从而提升缓存局部性：查询时访问的节点在内存中更连续，减少缓存缺失。Hilbert 填充的 R*-Tree 节点内条目空间局部性好，范围查询关注的子树在内存中更紧凑，磁盘/内存访问更顺序。工程上，Hilbert packing 把对象的 Hilbert 值排序，按连续块构造节点，配合高填充率，减少节点数与树高，提升缓存与 IO 效率。相比随机插入，Hilbert 填充的树查询性能与缓存友好性显著提升。

Hilbert 填充用空间序组织节点，使相邻数据在内存/磁盘连续，提升缓存局部性。结合高填充率与低树高，减少访问开销，是 R*-Tree 的经典优化。

• 平面分割
• 视锥剔除
• 光线/碰撞查询

BSP-Tree 用平面递归分割空间，把物体组织到左右子树。光线追踪：沿光线与分割平面的交点，按顺序遍历左右子树，剪枝被遮挡/远离的子树，减少相交测试；碰撞检测：用查询体与平面位置判断进入的子树，剪枝不相交分支。视锥剔除：把视锥（frustum）与分割平面求交，若视锥完全在一侧则只渲染该侧子树，否则两侧都递归，从而剔除不在视锥内的物体。平面分割提供空间排序，使光线/视锥查询沿平面剪枝，只访问相关子树，是静态场景高效渲染与碰撞检测的基础。

BSP 的平面分割使"查询体/光线/视锥与空间平面的位置关系"决定遍历方向，实现剪枝与剔除。它把三维空间搜索转化为平面引导的树遍历。

• PostGIS/Elasticsearch 索引
• R-Tree/Geohash/S2
• 取舍

PostGIS 用 R-Tree（GIST 实现）做精确空间索引，支持范围查询、最近邻、空间连接，适合精确几何；Elasticsearch 用 Geo-point（Geohash 前缀）与 Geo-shape（BKD/R-Tree）做地理索引，支持附近搜索与形状查询。取舍：R-Tree 精确、支持动态与复杂几何，但实现复杂、分布式分片难；Geohash 简单、前缀编码适合分布式/Redis 与近似搜索，但有边界误差与精度限制；S2（Google）用 Hilbert 曲线分层 cell，支持高效的近似覆盖与可扩展的分布式索引，比 Geohash 局部性更好、精度可控，适合大规模地理检索。工程上按精度需求、动态性、分布式需求选择：精确几何用 R-Tree，近似+分布式用 S2/Geohash。

R-Tree 精确 vs Geohash 简单 vs S2 可扩展，构成"精确性/简单性/扩展性"的三角取舍。PostGIS/Elasticsearch 按业务需求组合使用。

• 场景管理
• 空间查询
• 动态更新

四叉树（2D）/八叉树（3D）把场景空间递归均分为格子，每个节点覆盖一个区域，物体按位置归入所在格子。场景管理中用于：视锥剔除（只访问视锥所在的格子）、遮挡剔除、碰撞检测粗筛（只用同格或相邻格物体做精确检测）、空间查询（区域/最近邻）。动态更新：物体移动时更新所在格子，因为结构规则，插入/删除简单。特点：结构简单、适合动态场景与均匀分布；但最坏情况（物体聚集）退化，且格子大小不贴合物体。工程上用于游戏引擎、3D 场景与空间查询，作为"空间重用"的粗筛层。

四叉树/八叉树用规则格子组织场景，支持视锥剔除、碰撞粗筛、空间查询，且动态更新简单。它是场景管理的常用粗筛结构，配合精确检测使用。

• S2 cell 分层
• 范围覆盖
• 与 Geohash 差异

S2 用六边形/三角形把球面分块，按 Hilbert 曲线对 cell 编码，cell 分多层（level 0..30），每层大小不同，高层覆盖大区域、低层精细。范围覆盖查询：把查询区域（圆/矩形）用"覆盖"（cover）分解为若干不同层级的 cell，用这些 cell 的一维（Hilbert）区间表示区域，查询时用 cell 集合做索引。因 Hilbert 局部性好，cell 集合紧凑。与 Geohash 差异：S2 支持任意层级精确覆盖区域（cell 可精确贴合查询形状），精度边界灵活（cell 边界固定但层级可调）；Geohash 按固定格子近似，边界有锯齿状误差，且无法精确覆盖率任意区域（需枚举多个相近前缀）。S2 的 cell 体系更精细、可扩展、局部性更好。

S2 用分层 cell + Hilbert 编码实现"区域 → cell 集合"的精确覆盖，层级可调、边界灵活；Geohash 固定格子近似，边界误差大。S2 在精度、覆盖与分布式扩展上更优。