R树

R树结构

R树是处理多维数据的B+树的改进,是一种高度平衡的数据结构,其所有叶结点处于同一层. R树的搜索码是区间的集合,一个区间是一维.可以把搜索码看成是一个被这些区间包围的方框. 一个数据项的形式为

          <n维方框I,rid>

rid标识一个对象,方框I是包含这个对象的最小方框,数据项存储在叶子结点. 非叶子结点包含的索引项形式为

          <n维方框I,指向子结点的指针>

此时方框I是包含所有与孩子结点相关联的所有方框的最小方框.

R树特点

  1. R-树中各子树的所有空间允许重叠。
  2. 若叶结点不是根结点，则每个叶结点所包含的索引记录个数介于m与M之间.
  3. 若非叶结点不是根结点，则其中包含的子结点个数介于m与M之间.
  4. 根结点至少有两个子结点

SQLite中R树的虚表结构

R树是基于虚表实现的,它的数据存储在3个表中. 3个表分别为:

1.Node表存储结点信息,根结点nodeno为1

   (nodeno int, data BLOB)

2.Parent表存储结点的父结点信息

    (nodeno int, parentnode int)

3.Rowid表存储结点行号

    (rowid  int,nodeno int)

results matching ""

    No results matching ""