SQlite源码分析

R*树优化

R树不足

  1. 当索引数据量增加时,R树的深度及索引空间的重叠都会增大,而查找总是从根节点开始向下搜索,直至找到适合插入的叶节点 。但是它查找所须访问的分枝数、节点数会相应增加,查找性能会急剧下降。它采用的是一种自上而下的搜索方案 , 但是这往往不能获得最为合适的节点.
  2. R树的主要目标是支持高效的查询处理, 而没有考虑对象的更新效率问题。

R树优化

局部优化

在分裂算法中加入周长与重叠面积作为判定指标. 选择子树时,非叶结点采用面积增量标准,而叶结点采用重叠增量标准.

整体优化

对于同一集合,随着插入顺序的不同.会得到不同的R树结构.随着新数据的插入,R树结构的合理性会降低. R*树提出对索引中已有结点进行有选择的重新插入一次,来优化R树的数据结构.