《空间数据库索引技术》由会员分享，可在线阅读，更多相关《空间数据库索引技术（69页珍藏版）》请在金锄头文库上搜索。
1、空间数据库索引技术 一、DBMS索引技术1.索引顺序存取方法2.多层索引树（1）B-树（2）B-树1.索引顺序存取方法索引顺序存取方法存储结构：存储结构：存储结构：存储结构：分为三个区，分为三个区，分为三个区，分为三个区，索引页索引页索引页索引页、数据页数据页数据页数据页和和和和溢出页溢出页溢出页溢出页。 记录是按照关键字值排序。记录是按照关键字值排序。记录是按照关键字值排序。记录是按照关键字值排序。数据页数据页数据页数据页存储数据，数据页可以分块，每块包含多个记录，存储数据，数据页可以分块，每块包含多个记录，存储数据，数据页可以分块，每块包含多个记录，存储数据，数据页可以分块，每块包含多个记
2、录，一个块包含一个索引项，不是每个记录都有索引项。一个块包含一个索引项，不是每个记录都有索引项。一个块包含一个索引项，不是每个记录都有索引项。一个块包含一个索引项，不是每个记录都有索引项。溢出页溢出页溢出页溢出页解决插入问题。因为记录是按照顺序排放，所以解决插入问题。因为记录是按照顺序排放，所以解决插入问题。因为记录是按照顺序排放，所以解决插入问题。因为记录是按照顺序排放，所以如果插入新的数据，就必须调整所有记录。为了解决这个问如果插入新的数据，就必须调整所有记录。为了解决这个问如果插入新的数据，就必须调整所有记录。为了解决这个问如果插入新的数据，就必须调整所有记录。为了解决这个问题，设置溢出
3、页存放插入的数据。题，设置溢出页存放插入的数据。题，设置溢出页存放插入的数据。题，设置溢出页存放插入的数据。 索引页索引页索引页索引页指向数据页和溢出页，每个索引项包含两个部分：指向数据页和溢出页，每个索引项包含两个部分：指向数据页和溢出页，每个索引项包含两个部分：指向数据页和溢出页，每个索引项包含两个部分：基本索引项和指针。数据页每一块设置一个索引项，溢出页基本索引项和指针。数据页每一块设置一个索引项，溢出页基本索引项和指针。数据页每一块设置一个索引项，溢出页基本索引项和指针。数据页每一块设置一个索引项，溢出页中的记录用指针串联起来，同一数据块中的记录链为一个链中的记录用指针串联起来，同一数
4、据块中的记录链为一个链中的记录用指针串联起来，同一数据块中的记录链为一个链中的记录用指针串联起来，同一数据块中的记录链为一个链表。表。表。表。缺点：缺点： 静态结构。在建立索引树之前已经知道静态结构。在建立索引树之前已经知道了有多少数据块。了有多少数据块。 如果大量插入操作作用于同一个数据如果大量插入操作作用于同一个数据块（叶子），则产生很长的溢出页链，降块（叶子），则产生很长的溢出页链，降低效率。低效率。 即树变的不平衡了。即树变的不平衡了。树树 动态结构动态结构，能够随插入和删除而调整的树。，能够随插入和删除而调整的树。 多层索引结构多层索引结构包含包含2m个数据域和个数据域和2m+1个指
5、个指针域。针域。定义：定义：一棵一棵2m+1阶的阶的B树，或为空，或为满足：树，或为空，或为满足：（1）树中每个节点最多有）树中每个节点最多有2m+1棵子树，且棵子树，且除根节点外，所有非叶子节点的子树数量除根节点外，所有非叶子节点的子树数量至少有至少有m+1，而根节点至少有两棵子树。，而根节点至少有两棵子树。（2）所有叶子节点均在最后一层上。）所有叶子节点均在最后一层上。（3）除叶子节点外每个结点结构如下：）除叶子节点外每个结点结构如下：LINKi为指针，指向各子树根节点，为指针，指向各子树根节点，KEYi为为关键字，存放关键字及数据有关信息。关键字，存放关键字及数据有关信息。 要求，要求，
6、KEY有序，而且所对应子树之间也有序，而且所对应子树之间也是有序的。是有序的。（4）所有叶子节点指针为空，叶子节点的元）所有叶子节点指针为空，叶子节点的元素数量大于素数量大于m。（1）检索）检索 从根节点开始，进行关键字的比较。从根节点开始，进行关键字的比较。（2）插入）插入 如果在找到的插入位置叶子节点的元素如果在找到的插入位置叶子节点的元素个数不足个数不足2m个，直接插入。个，直接插入。 如果在插入的位置叶子节点已经有如果在插入的位置叶子节点已经有2m个，个，则进行分裂。则进行分裂。分裂过程分裂过程： 将数据按顺序插入，然后将该叶子结点对将数据按顺序插入，然后将该叶子结点对分，其中前半部分
7、仍然存放原来结点中，分，其中前半部分仍然存放原来结点中，后面的放在一个新申请的结点中，并将中后面的放在一个新申请的结点中，并将中间一个元素放在父结点中。间一个元素放在父结点中。 如果父结点中的元素也已经满了，则父如果父结点中的元素也已经满了，则父结点必须进行分裂。结点必须进行分裂。插入插入27，分裂后，分裂后，22加入到父结点中。加入到父结点中。（3）删除）删除x 检索到后，如果在叶子节点上，则进行删检索到后，如果在叶子节点上，则进行删除，如果不在叶子节点上，则要用一个比除，如果不在叶子节点上，则要用一个比x大的元素大的元素y代替代替x。 y即即x右边指针所指路径最左边叶子节点右边指针所指路径
8、最左边叶子节点的第一个元素。然后在叶子节点中删除的第一个元素。然后在叶子节点中删除y。删除删除y后，如果叶子节点元素数量小于后，如果叶子节点元素数量小于m，则与它相邻的左（右）结点借一个元素；，则与它相邻的左（右）结点借一个元素；如果兄弟结点元素数量正好为如果兄弟结点元素数量正好为m，则进行叶，则进行叶子节点的合并。子节点的合并。合并完成后，父结点少了一个子树，则合并完成后，父结点少了一个子树，则也可能存在合并的问题。也可能存在合并的问题。+树树 B树随机检索效率很高，但是遍历所有树随机检索效率很高，但是遍历所有元素却不方便。元素却不方便。 这是因为，这是因为，B树的非叶子节点同样存储树的非叶
9、子节点同样存储数据。数据。 B+树是树是B树的变形，在非叶子节点中存树的变形，在非叶子节点中存放的不是数据。放的不是数据。定义：定义：定义：定义：一个一个一个一个2m+12m+1阶的阶的阶的阶的B B树满足，树满足，树满足，树满足，（1 1）每个结点至多有）每个结点至多有）每个结点至多有）每个结点至多有2m+12m+1棵子树棵子树棵子树棵子树（2 2）除根节点外，其他每个分支至少有）除根节点外，其他每个分支至少有）除根节点外，其他每个分支至少有）除根节点外，其他每个分支至少有m+1m+1棵子树。棵子树。棵子树。棵子树。（3 3）非叶子节点的根节点至少有两个子树。）非叶子节点的根节点至少有两个子
10、树。）非叶子节点的根节点至少有两个子树。）非叶子节点的根节点至少有两个子树。（4 4）有）有）有）有n n棵子树的非叶节点有棵子树的非叶节点有棵子树的非叶节点有棵子树的非叶节点有n-1n-1个关键码。个关键码。个关键码。个关键码。（5 5）叶节点都在同一个层上，存放了数据文件中记录）叶节点都在同一个层上，存放了数据文件中记录）叶节点都在同一个层上，存放了数据文件中记录）叶节点都在同一个层上，存放了数据文件中记录关键码以及指针。叶节点按照关键码值排序链接。关键码以及指针。叶节点按照关键码值排序链接。关键码以及指针。叶节点按照关键码值排序链接。关键码以及指针。叶节点按照关键码值排序链接。（6 6）
11、所有分支结点可看成是索引的索引。仅存放各子）所有分支结点可看成是索引的索引。仅存放各子）所有分支结点可看成是索引的索引。仅存放各子）所有分支结点可看成是索引的索引。仅存放各子节点的最大（最小）关键码的分界值及指针。节点的最大（最小）关键码的分界值及指针。节点的最大（最小）关键码的分界值及指针。节点的最大（最小）关键码的分界值及指针。B+树包含两部分：树包含两部分：首先是首先是B树索引。树索引。然后链接各叶子节点的顺序链。然后链接各叶子节点的顺序链。 即包含两个指针。即包含两个指针。在插入和删除的方式上，与在插入和删除的方式上，与B树不同。树不同。B+树在插入时，与树在插入时，与B树类似，不同在
12、于树类似，不同在于分裂时，不仅要把元素上升到父节点中，分裂时，不仅要把元素上升到父节点中，并且在叶子节点中也要保留。并且在叶子节点中也要保留。插入插入插入插入8 8叶结点保留原来元素，但是中间节点分裂时不保留。叶结点保留原来元素，但是中间节点分裂时不保留。叶结点保留原来元素，但是中间节点分裂时不保留。叶结点保留原来元素，但是中间节点分裂时不保留。 B+树删除时比较简单。只需要删除叶子树删除时比较简单。只需要删除叶子节点上的数值，而中间节点不需要改变。节点上的数值，而中间节点不需要改变。 但是，这中间存在但是，这中间存在合并合并的过程。的过程。上为删除上为删除上为删除上为删除1919，2020后
13、，下为进一步删除后，下为进一步删除后，下为进一步删除后，下为进一步删除2424后。后。后。后。二、空间数据库索引二、空间数据库索引传统的数据库索引技术包括了传统的数据库索引技术包括了B树、树、B+树、二叉树、哈希索引等，都是针对一维树、二叉树、哈希索引等，都是针对一维属性数据的主关键字索引而设计的。属性数据的主关键字索引而设计的。空间数据库索引基于这些技术分别取得空间数据库索引基于这些技术分别取得了发展。了发展。基于哈希表的检索基于哈希表的检索空间索引大致分为四大类：空间索引大致分为四大类：1.基于二叉树的索引技术基于二叉树的索引技术2.基于基于B树的索引技术树的索引技术3.基于哈希的格网技术
14、基于哈希的格网技术4.空间目标排序法空间目标排序法1.1.基于二叉树的索引技术基于二叉树的索引技术基于二叉树的索引技术基于二叉树的索引技术 主要有主要有主要有主要有KdKd树、树、树、树、KDBKDB树等。树等。树等。树等。其中，典型的其中，典型的其中，典型的其中，典型的KdKd树是一种二分索引树结构，树是一种二分索引树结构，树是一种二分索引树结构，树是一种二分索引树结构，主要用于索引多维数据点，但对于复杂的空间目主要用于索引多维数据点，但对于复杂的空间目主要用于索引多维数据点，但对于复杂的空间目主要用于索引多维数据点，但对于复杂的空间目标，如折线、多边形等必须采用近似方法和空间标，如折线、多
15、边形等必须采用近似方法和空间标，如折线、多边形等必须采用近似方法和空间标，如折线、多边形等必须采用近似方法和空间映射技术。映射技术。映射技术。映射技术。为了能索引复杂的空间目标，为了能索引复杂的空间目标，为了能索引复杂的空间目标，为了能索引复杂的空间目标，MkdMkd树被提出；树被提出；树被提出；树被提出；为了将为了将为了将为了将KdKd树存储到外存，将树存储到外存，将树存储到外存，将树存储到外存，将KdKd树与树与树与树与B B树结合，得树结合，得树结合，得树结合，得到到到到KDBKDB树。树。树。树。所有的方法对于非点状空间目标的索引效率都所有的方法对于非点状空间目标的索引效率都所有的方法
16、对于非点状空间目标的索引效率都所有的方法对于非点状空间目标的索引效率都很低。很低。很低。很低。2.基于基于B树的索引技术树的索引技术目前很多空间数据索引技术，都是目前很多空间数据索引技术，都是B树树发展来的。例如发展来的。例如R树、树、 R+树、树、R*树等。树等。利用最小外包矩形表示空间目标。利用最小外包矩形表示空间目标。3.基于哈希的格网技术基于哈希的格网技术基本思路是将索引空间划分为相等或不基本思路是将索引空间划分为相等或不相等的一些小方格网，与每个格网相关连相等的一些小方格网，与每个格网相关连的空间目标则存在同一磁盘页，而格网的的空间目标则存在同一磁盘页，而格网的访问地址则可以直接通过
17、求数组下标或某访问地址则可以直接通过求数组下标或某种算法得到。种算法得到。4.空间目标排序法空间目标排序法将多维空间映射为一维空间，包括了将多维空间映射为一维空间，包括了Z序、序、Hilbert排序等。排序等。（一）（一）（一）（一）KdKd树树树树1.1.定义定义定义定义KdKd树的每个节点表示树的每个节点表示树的每个节点表示树的每个节点表示K K维空间的一个点，并且树的每一维空间的一个点，并且树的每一维空间的一个点，并且树的每一维空间的一个点，并且树的每一层都根据这层的分辨器（层都根据这层的分辨器（层都根据这层的分辨器（层都根据这层的分辨器（DiscriminatorDiscriminat
18、or）作出分枝决策。）作出分枝决策。）作出分枝决策。）作出分枝决策。KdKd树的第树的第树的第树的第i i层的分辨器定义为：层的分辨器定义为：层的分辨器定义为：层的分辨器定义为：i MOD ki MOD k（根节点为（根节点为（根节点为（根节点为0 0层，层，层，层，下面依次加下面依次加下面依次加下面依次加1 1）。）。）。）。特征如下：特征如下：特征如下：特征如下：（1 1）左子树的所有节点的）左子树的所有节点的）左子树的所有节点的）左子树的所有节点的d d维数值，均小于根节点的维数值，均小于根节点的维数值，均小于根节点的维数值，均小于根节点的d d维数值。维数值。维数值。维数值。（2 2）
19、右子树的所有节点的）右子树的所有节点的）右子树的所有节点的）右子树的所有节点的d d维数值，均大于根节点的维数值，均大于根节点的维数值，均大于根节点的维数值，均大于根节点的d d维数值。维数值。维数值。维数值。（3 3）左右子树也分别为）左右子树也分别为）左右子树也分别为）左右子树也分别为kdkd树。树。树。树。 d d为根节点的分辨器。为根节点的分辨器。为根节点的分辨器。为根节点的分辨器。四、二叉树检索 A点分辨器的值为点分辨器的值为0（x轴），左子树的轴），左子树的所有结点的所有结点的x值都比值都比A的的x值小；右子树反之。值小；右子树反之。分辨器的值是指对应空间中的哪一维。分辨器的值是指
20、对应空间中的哪一维。因此，因此，k层之后就是新的循环。层之后就是新的循环。 首先是从第一维分成两个部分；然后是首先是从第一维分成两个部分；然后是第二维分成两个部分；再次是第三维分成第二维分成两个部分；再次是第三维分成两个部分，直至第两个部分，直至第k维。然后重新按照第一维。然后重新按照第一维维Kd树查询：需要按照分辨器的值进行比较。树查询：需要按照分辨器的值进行比较。Kd树插入：与二叉树同。树插入：与二叉树同。Kd树删除：与二叉树类似，但是，对于结点树删除：与二叉树类似，但是，对于结点的的d维数值，存在相同情况，这就需要处理。维数值，存在相同情况，这就需要处理。图中图中 H和和I的横坐标相同。
21、的横坐标相同。（二）（二）K-D-B树树KD树与树与B树结合，解决分页策略。树结合，解决分页策略。（三）（三）HB树树 hB hB树是一种有效的多维动态索引结构树是一种有效的多维动态索引结构树是一种有效的多维动态索引结构树是一种有效的多维动态索引结构, ,其结点其结点其结点其结点间搜索和增长过程模拟间搜索和增长过程模拟间搜索和增长过程模拟间搜索和增长过程模拟B B树的处理方法树的处理方法树的处理方法树的处理方法, ,结点内采结点内采结点内采结点内采用用用用k k维树组织和进行高效搜索。维树组织和进行高效搜索。维树组织和进行高效搜索。维树组织和进行高效搜索。结点分裂要求结点分裂要求结点分裂要求结
22、点分裂要求k k维树分裂维树分裂维树分裂维树分裂, ,于是抽取一个大小介于于是抽取一个大小介于于是抽取一个大小介于于是抽取一个大小介于1/31/32/32/3间并尽间并尽间并尽间并尽可能平衡的可能平衡的可能平衡的可能平衡的k k维子树维子树维子树维子树, ,并以此子树表示一个新结点。并以此子树表示一个新结点。并以此子树表示一个新结点。并以此子树表示一个新结点。因此因此因此因此hBhB树结点空间是有孔树结点空间是有孔树结点空间是有孔树结点空间是有孔(holey)(holey)的的的的k k方体方体方体方体, ,即即即即每个结点空间是被抽取若干个小每个结点空间是被抽取若干个小每个结点空间是被抽取若
23、干个小每个结点空间是被抽取若干个小k k方体的方体的方体的方体的k k方体方体方体方体. . (b) (b)中结点中结点中结点中结点WW的的的的k k维树是从结点维树是从结点维树是从结点维树是从结点Z Z的的的的k k维树抽取的，如维树抽取的，如维树抽取的，如维树抽取的，如Z Z的的的的k k维树中的维树中的维树中的维树中的extext标识，它相当于标识，它相当于标识，它相当于标识，它相当于(a)(a)中粗线框内的矩中粗线框内的矩中粗线框内的矩中粗线框内的矩形从整个大矩形中抽取形从整个大矩形中抽取形从整个大矩形中抽取形从整个大矩形中抽取. .结点结点结点结点P P是该是该是该是该hBhB树的根
24、树的根树的根树的根, ,其其其其k k维树维树维树维树表示下层表示下层表示下层表示下层hBhB结点结点结点结点W,ZW,Z的导向路径的导向路径的导向路径的导向路径, ,意为满足意为满足意为满足意为满足x xx1x1且且且且y yy1y1的记录应存于结点的记录应存于结点的记录应存于结点的记录应存于结点W,W,其它记录则存于结点其它记录则存于结点其它记录则存于结点其它记录则存于结点Z Z。符符符符合二叉树原理，左边小于右边合二叉树原理，左边小于右边合二叉树原理，左边小于右边合二叉树原理，左边小于右边（a）二维空间的一个划分（b）对应的hB树结构y4 hB hB树能很好地支持树能很好地支持树能很好地
25、支持树能很好地支持精确匹配搜索精确匹配搜索精确匹配搜索精确匹配搜索和和和和范围搜索范围搜索范围搜索范围搜索。进行精确匹配搜索进行精确匹配搜索进行精确匹配搜索进行精确匹配搜索, ,要经过自要经过自要经过自要经过自hBhB树根到一叶子的树根到一叶子的树根到一叶子的树根到一叶子的单一路径，访问的结点数是单一路径，访问的结点数是单一路径，访问的结点数是单一路径，访问的结点数是hBhB树的高度。在树的高度。在树的高度。在树的高度。在hBhB树树树树结点内通过比较结点内通过比较结点内通过比较结点内通过比较k k维树结点值与搜索的相应属性值，维树结点值与搜索的相应属性值，维树结点值与搜索的相应属性值，维树结
26、点值与搜索的相应属性值，最终确定唯一的下层最终确定唯一的下层最终确定唯一的下层最终确定唯一的下层hBhB树结点。范围搜索可能涉树结点。范围搜索可能涉树结点。范围搜索可能涉树结点。范围搜索可能涉及及及及hBhB树每层的多个结点。范围的标界是在若干个树每层的多个结点。范围的标界是在若干个树每层的多个结点。范围的标界是在若干个树每层的多个结点。范围的标界是在若干个属性上取值的上下界。结点内搜索时将属性上取值的上下界。结点内搜索时将属性上取值的上下界。结点内搜索时将属性上取值的上下界。结点内搜索时将k k维树结点维树结点维树结点维树结点的比较值与搜索范围的相应属性上下界进行比较，的比较值与搜索范围的相
27、应属性上下界进行比较，的比较值与搜索范围的相应属性上下界进行比较，的比较值与搜索范围的相应属性上下界进行比较，以决定转向以决定转向以决定转向以决定转向k k维树结点的左子树、右子树或两者。维树结点的左子树、右子树或两者。维树结点的左子树、右子树或两者。维树结点的左子树、右子树或两者。 尽管尽管hB树对于大多数情况能取得较好树对于大多数情况能取得较好效果效果,但它有两个问题但它有两个问题:(1) 空间利用率不理空间利用率不理想想;(2) 可能出现多父结点可能出现多父结点,使使hB树不再是树不再是严格的树结构。严格的树结构。五五. 四叉树检索四叉树检索点四叉树点四叉树区域四叉树区域四叉树l l M
28、X MX四叉树四叉树四叉树四叉树l l PR PR四叉树四叉树四叉树四叉树CIF四叉树四叉树1.点四叉树点四叉树 以空间点为划分点，将索引空间分为两以空间点为划分点，将索引空间分为两两不相交的的两不相交的的2k个子空间，依次与它的个子空间，依次与它的2k个个孩子结点相对应，对于位于某一子空间的孩子结点相对应，对于位于某一子空间的点，则分配给对应的子树。点，则分配给对应的子树。点四叉树的构造过程点四叉树的构造过程点四叉树的构造过程点四叉树的构造过程：（1 1）输入空间点）输入空间点）输入空间点）输入空间点A A，以，以，以，以A A为根节点并进行划分空间。为根节点并进行划分空间。为根节点并进行划
29、分空间。为根节点并进行划分空间。（2 2）输入空间点）输入空间点）输入空间点）输入空间点B B，B B落入落入落入落入A A的的的的NWNW象限，并且象限，并且象限，并且象限，并且A A的的的的NWNW象限象限象限象限为空，则为空，则为空，则为空，则B B直接放入直接放入直接放入直接放入A A的的的的NWNW象限孩子结点。同理，象限孩子结点。同理，象限孩子结点。同理，象限孩子结点。同理，C C是是是是A A的的的的SWSW孩子结点。孩子结点。孩子结点。孩子结点。（3 3）输入）输入）输入）输入D D，由于，由于，由于，由于D D落入落入落入落入A A的的的的NWNW象限，但是象限，但是象限，但
30、是象限，但是NWNW不为空，所不为空，所不为空，所不为空，所以继续往下查找，得到以继续往下查找，得到以继续往下查找，得到以继续往下查找，得到B B的的的的NENE象限为空，因此，象限为空，因此，象限为空，因此，象限为空，因此，D D作为作为作为作为B B的的的的NENE孩子结点。孩子结点。孩子结点。孩子结点。（4 4）同理，空间点）同理，空间点）同理，空间点）同理，空间点E E、F F，分别为，分别为，分别为，分别为A A的的的的SESE、NENE孩子节点。孩子节点。孩子节点。孩子节点。缺点缺点缺点缺点： （1 1）尽管点四叉树构造简单，但是删除一个节点时，）尽管点四叉树构造简单，但是删除一个
31、节点时，）尽管点四叉树构造简单，但是删除一个节点时，）尽管点四叉树构造简单，但是删除一个节点时，该节点对应的所有子树节点必须重新插入四叉树该节点对应的所有子树节点必须重新插入四叉树该节点对应的所有子树节点必须重新插入四叉树该节点对应的所有子树节点必须重新插入四叉树中，效率很差。中，效率很差。中，效率很差。中，效率很差。（2 2）对于精确匹配的点查找，效率很高，但是对于）对于精确匹配的点查找，效率很高，但是对于）对于精确匹配的点查找，效率很高，但是对于）对于精确匹配的点查找，效率很高，但是对于区域查找，查找路径有多条，效率较差。区域查找，查找路径有多条，效率较差。区域查找，查找路径有多条，效率较
32、差。区域查找，查找路径有多条，效率较差。（3 3）树的动态性差，树的结构完全由点的插入顺序）树的动态性差，树的结构完全由点的插入顺序）树的动态性差，树的结构完全由点的插入顺序）树的动态性差，树的结构完全由点的插入顺序决定。树的平衡难以保证。决定。树的平衡难以保证。决定。树的平衡难以保证。决定。树的平衡难以保证。区域四叉树区域四叉树区域四叉树区域四叉树(Region-Based Quadtree)(Region-Based Quadtree)是以区域目是以区域目是以区域目是以区域目标为循环分解对象的四叉树标为循环分解对象的四叉树标为循环分解对象的四叉树标为循环分解对象的四叉树, ,分解过程既可以
33、按照区域分解过程既可以按照区域分解过程既可以按照区域分解过程既可以按照区域边界边界边界边界, ,也可以按照区域内部对二维空间进行划分。也可以按照区域内部对二维空间进行划分。也可以按照区域内部对二维空间进行划分。也可以按照区域内部对二维空间进行划分。如果区域四叉树中的结点覆盖的区域中所有数组元如果区域四叉树中的结点覆盖的区域中所有数组元如果区域四叉树中的结点覆盖的区域中所有数组元如果区域四叉树中的结点覆盖的区域中所有数组元素的值都相同，则该结点是叶子结点。否则，该结点素的值都相同，则该结点是叶子结点。否则，该结点素的值都相同，则该结点是叶子结点。否则，该结点素的值都相同，则该结点是叶子结点。否则
34、，该结点是内部结点，被进一步划分为四个等大小的子结点。是内部结点，被进一步划分为四个等大小的子结点。是内部结点，被进一步划分为四个等大小的子结点。是内部结点，被进一步划分为四个等大小的子结点。主要有主要有主要有主要有MXMX四叉树与四叉树与四叉树与四叉树与PRPR四叉树。四叉树。四叉树。四叉树。避免了点四叉树的动态性差、结构完全由点的插入避免了点四叉树的动态性差、结构完全由点的插入避免了点四叉树的动态性差、结构完全由点的插入避免了点四叉树的动态性差、结构完全由点的插入顺序决定的功能缺点。顺序决定的功能缺点。顺序决定的功能缺点。顺序决定的功能缺点。2.区域四叉树区域四叉树MX四叉树四叉树MX四叉
35、树将每个空间点看成是区域四叉四叉树将每个空间点看成是区域四叉树中的一个黑象素，或当成一个方阵树中的一个黑象素，或当成一个方阵（Square Matrix）中的非零元素，因此称）中的非零元素，因此称为为MX四叉树。四叉树。利用叶子节点为黑节点或空闲点表示数利用叶子节点为黑节点或空闲点表示数据空间某一位置空间点的存在与否。据空间某一位置空间点的存在与否。树的构造过程树的构造过程即是对整个数据空间重复即是对整个数据空间重复地进行地进行2k次等分，次等分，直到每一空间点都位于某直到每一空间点都位于某一象限的最左下角的过程一象限的最左下角的过程。MX四叉树特点：四叉树特点： 空间中每一个点都属于某一象限
36、且位于空间中每一个点都属于某一象限且位于该象限的最左下角，每一象限只与一个空该象限的最左下角，每一象限只与一个空间点相关联。间点相关联。尽管尽管D同时是两个大小不等的象限的最同时是两个大小不等的象限的最左下角，但其应属于最下一级象限（即最左下角，但其应属于最下一级象限（即最后一次空间划分所产生的子象限）。这就后一次空间划分所产生的子象限）。这就决定了所有空间点均位于叶子节点。决定了所有空间点均位于叶子节点。缺点：缺点：插入（或删除）一个点可能导致树的深插入（或删除）一个点可能导致树的深度增加（或减少）一层或多层，所有的叶度增加（或减少）一层或多层，所有的叶子节点都必须重新定位。子节点都必须重新
37、定位。树的深度往往很大，这会影响查找效率。树的深度往往很大，这会影响查找效率。 PR（Point Region）四叉树叶子节点）四叉树叶子节点或者为空，或者包含或者为空，或者包含唯一唯一数据点。数据点。PR四叉树四叉树PR四叉树与四叉树与MX四叉树的构造过程类似，四叉树的构造过程类似，不同的是，当分解到一个象限只包含一个不同的是，当分解到一个象限只包含一个点时，不需要继续分解使该点位于某一子点时，不需要继续分解使该点位于某一子象限的最左下角。象限的最左下角。另外，插入或删除一个点也不会影响到另外，插入或删除一个点也不会影响到其他的分支，操作比较简单。其他的分支，操作比较简单。PR四叉树与四叉树
38、与MX四叉树的区别：四叉树的区别：（1）数据点位于象限内，不要求位于左下角。）数据点位于象限内，不要求位于左下角。（2）叶子节点可能不在树的同一层次。）叶子节点可能不在树的同一层次。（3）PR四叉树的叶子结点数及树的深度都四叉树的叶子结点数及树的深度都小于小于MX四叉树，因此四叉树，因此PR四叉树效率高。四叉树效率高。CIF四叉树四叉树CIFCIF四叉树是为了表示四叉树是为了表示四叉树是为了表示四叉树是为了表示VLSIVLSI（Very Large Very Large Scale Integration)Scale Integration)应用中的小矩形而提出的。它应用中的小矩形而提出的。它
39、应用中的小矩形而提出的。它应用中的小矩形而提出的。它可以用于索引空间矩形及其他形体。可以用于索引空间矩形及其他形体。可以用于索引空间矩形及其他形体。可以用于索引空间矩形及其他形体。表示方式与区域四叉树类似，数据空间被递归表示方式与区域四叉树类似，数据空间被递归表示方式与区域四叉树类似，数据空间被递归表示方式与区域四叉树类似，数据空间被递归的细分，直至产生的的细分，直至产生的的细分，直至产生的的细分，直至产生的子象限不再包含任何矩形子象限不再包含任何矩形子象限不再包含任何矩形子象限不再包含任何矩形。在分解过程中，所有在分解过程中，所有在分解过程中，所有在分解过程中，所有与任一划分线相交的矩形与任
40、一划分线相交的矩形与任一划分线相交的矩形与任一划分线相交的矩形与该划分线对应的象限相关联。与该划分线对应的象限相关联。与该划分线对应的象限相关联。与该划分线对应的象限相关联。0数据桶的容量设为数据桶的容量设为3。相交查询相交查询相交查询相交查询：从根节点开始，首先检查与之关联的所有矩形是：从根节点开始，首先检查与之关联的所有矩形是：从根节点开始，首先检查与之关联的所有矩形是：从根节点开始，首先检查与之关联的所有矩形是否为查找结果；接下来检查象限空间与查询区域相交的孩否为查找结果；接下来检查象限空间与查询区域相交的孩否为查找结果；接下来检查象限空间与查询区域相交的孩否为查找结果；接下来检查象限空
41、间与查询区域相交的孩子结点子结点子结点子结点.直到叶子节点。直到叶子节点。直到叶子节点。直到叶子节点。插入矩形插入矩形插入矩形插入矩形：首先检查根节点，如果与根节点的划分线相交，：首先检查根节点，如果与根节点的划分线相交，：首先检查根节点，如果与根节点的划分线相交，：首先检查根节点，如果与根节点的划分线相交，则插入到根节点对应的桶链表中；否则检查包含该矩形的则插入到根节点对应的桶链表中；否则检查包含该矩形的则插入到根节点对应的桶链表中；否则检查包含该矩形的则插入到根节点对应的桶链表中；否则检查包含该矩形的子象限的孩子结点子象限的孩子结点子象限的孩子结点子象限的孩子结点；如果检查到某一没有孩子的
42、象限，；如果检查到某一没有孩子的象限，；如果检查到某一没有孩子的象限，；如果检查到某一没有孩子的象限，而且该矩形依旧没有插入到对应的位置，那么该象限必须而且该矩形依旧没有插入到对应的位置，那么该象限必须而且该矩形依旧没有插入到对应的位置，那么该象限必须而且该矩形依旧没有插入到对应的位置，那么该象限必须再次细分直到为该矩形找到对应的子象限。再次细分直到为该矩形找到对应的子象限。再次细分直到为该矩形找到对应的子象限。再次细分直到为该矩形找到对应的子象限。删除矩形删除矩形删除矩形删除矩形：找到矩形所在结点，从数据桶中删除。：找到矩形所在结点，从数据桶中删除。：找到矩形所在结点，从数据桶中删除。：找到
43、矩形所在结点，从数据桶中删除。 如果删完后桶为空，且该节点没有孩子结点，则可以删除如果删完后桶为空，且该节点没有孩子结点，则可以删除如果删完后桶为空，且该节点没有孩子结点，则可以删除如果删完后桶为空，且该节点没有孩子结点，则可以删除该节点。该节点。该节点。该节点。CIF四叉树可以用于索引矩形以及任何四叉树可以用于索引矩形以及任何其他形体的空间目标而不需要经过目标近其他形体的空间目标而不需要经过目标近似与空间目标映射，因此对于区与查询，似与空间目标映射，因此对于区与查询，效率相对效率相对MX、PR四叉树要高些。四叉树要高些。但是区域查询往往需要访问多个节点对但是区域查询往往需要访问多个节点对应的
44、存储桶，尤其当索引量增大，大区域应的存储桶，尤其当索引量增大，大区域节点所包含较多数据矩形时，外存节点所包含较多数据矩形时，外存I/O开销开销很大。很大。 四叉树索引优点四叉树索引优点四叉树索引优点四叉树索引优点： 结构清晰，容易建立。它同时具有聚集空间目标结构清晰，容易建立。它同时具有聚集空间目标结构清晰，容易建立。它同时具有聚集空间目标结构清晰，容易建立。它同时具有聚集空间目标的能力（在栅格数据存储中发挥突出作用），提的能力（在栅格数据存储中发挥突出作用），提的能力（在栅格数据存储中发挥突出作用），提的能力（在栅格数据存储中发挥突出作用），提高了检索效率，得到广泛应用。高了检索效率，得到广
45、泛应用。高了检索效率，得到广泛应用。高了检索效率，得到广泛应用。有很多改进的方法被提出有很多改进的方法被提出有很多改进的方法被提出有很多改进的方法被提出： （1 1）一体化索引，进行了索引空间的三级划分，）一体化索引，进行了索引空间的三级划分，）一体化索引，进行了索引空间的三级划分，）一体化索引，进行了索引空间的三级划分，包括索引块、基本格网、细分格网，并采用行次包括索引块、基本格网、细分格网，并采用行次包括索引块、基本格网、细分格网，并采用行次包括索引块、基本格网、细分格网，并采用行次序法对各级区域进行了编码。序法对各级区域进行了编码。序法对各级区域进行了编码。序法对各级区域进行了编码。 （
46、2 2）CELLQTREECELLQTREE， 叶子节点索引点对象，叶子节点索引点对象，叶子节点索引点对象，叶子节点索引点对象， 中间节点索引线和面对象，较好的解决了大区中间节点索引线和面对象，较好的解决了大区中间节点索引线和面对象，较好的解决了大区中间节点索引线和面对象，较好的解决了大区域对象的标示符在子空间结点中的多次重复存储域对象的标示符在子空间结点中的多次重复存储域对象的标示符在子空间结点中的多次重复存储域对象的标示符在子空间结点中的多次重复存储问题。问题。问题。问题。 四叉树索引的缺点四叉树索引的缺点： 当索引数据量较大时，如果四叉树层次过当索引数据量较大时，如果四叉树层次过小，将导
47、致查找性能下降；如果四叉树层小，将导致查找性能下降；如果四叉树层次过大，将导致重复存储的增加，从而增次过大，将导致重复存储的增加，从而增加空间开销，这同时又会影响查找性能。加空间开销，这同时又会影响查找性能。六、基于六、基于B-树的空间索引树的空间索引（一）（一）（一）（一）R-R-树树树树R-R-树是树是树是树是B-B-树在多维空间的扩展，由树在多维空间的扩展，由树在多维空间的扩展，由树在多维空间的扩展，由GuttmanGuttman提出。其特点是能索引一定范围内的对象。其叶提出。其特点是能索引一定范围内的对象。其叶提出。其特点是能索引一定范围内的对象。其叶提出。其特点是能索引一定范围内的对
48、象。其叶子节点包含多个形式为子节点包含多个形式为子节点包含多个形式为子节点包含多个形式为(OI(OI，MBR)MBR)的实体的实体的实体的实体,OI,OI为空为空为空为空间目标标志间目标标志间目标标志间目标标志,MBR,MBR为该目标在为该目标在为该目标在为该目标在k k维空间中的最小包围维空间中的最小包围维空间中的最小包围维空间中的最小包围矩形。非叶子节点包含多个形式为矩形。非叶子节点包含多个形式为矩形。非叶子节点包含多个形式为矩形。非叶子节点包含多个形式为(CP(CP，MBR)MBR)的的的的实体。实体。实体。实体。CPCP为指向子树根节点的指针，为指向子树根节点的指针，为指向子树根节点的
49、指针，为指向子树根节点的指针，MBRMBR为包围为包围为包围为包围其子节点中所有其子节点中所有其子节点中所有其子节点中所有MBRMBR的最小包围矩形。的最小包围矩形。的最小包围矩形。的最小包围矩形。R R树的定义：树的定义：树的定义：树的定义：设设设设MM为节点中包含子节点的最大个数，为节点中包含子节点的最大个数，为节点中包含子节点的最大个数，为节点中包含子节点的最大个数，mm（2mM/2)2mM/2)为节点为节点为节点为节点包含索引项（数据项）的最小数目。包含索引项（数据项）的最小数目。包含索引项（数据项）的最小数目。包含索引项（数据项）的最小数目。（1 1）根节点不是叶子节点，则至少有两棵
50、子树。）根节点不是叶子节点，则至少有两棵子树。）根节点不是叶子节点，则至少有两棵子树。）根节点不是叶子节点，则至少有两棵子树。（2 2）除根之外的所有中间节点至多有）除根之外的所有中间节点至多有）除根之外的所有中间节点至多有）除根之外的所有中间节点至多有MM棵子树，至少有棵子树，至少有棵子树，至少有棵子树，至少有mm棵棵棵棵子树。子树。子树。子树。（3 3）每个叶子节点均包含）每个叶子节点均包含）每个叶子节点均包含）每个叶子节点均包含mm至至至至MM个数据项个数据项个数据项个数据项（4 4）所有的叶子节点都出现在同一层次上）所有的叶子节点都出现在同一层次上）所有的叶子节点都出现在同一层次上）所
51、有的叶子节点都出现在同一层次上（5 5）所有节点需要同样的存储空间。）所有节点需要同样的存储空间。）所有节点需要同样的存储空间。）所有节点需要同样的存储空间。特性：特性：特性：特性：数据矩形可能重叠；目录矩形允许重叠；查找路径多数据矩形可能重叠；目录矩形允许重叠；查找路径多数据矩形可能重叠；目录矩形允许重叠；查找路径多数据矩形可能重叠；目录矩形允许重叠；查找路径多条。条。条。条。R R树的特点决定了，为了高效，需要：树的特点决定了，为了高效，需要：树的特点决定了，为了高效，需要：树的特点决定了，为了高效，需要：（1 1）目录矩形）目录矩形）目录矩形）目录矩形“ “面积面积面积面积” ”尽可能小
52、，尽可能小，尽可能小，尽可能小，“ “死空间死空间死空间死空间” ”尽可能尽可能尽可能尽可能小（即目录矩形内的空白区域）。小（即目录矩形内的空白区域）。小（即目录矩形内的空白区域）。小（即目录矩形内的空白区域）。（2 2）目录矩形间重叠尽可能小，可以减少查找路径。）目录矩形间重叠尽可能小，可以减少查找路径。）目录矩形间重叠尽可能小，可以减少查找路径。）目录矩形间重叠尽可能小，可以减少查找路径。（3 3）目录矩形）目录矩形）目录矩形）目录矩形“ “周长周长周长周长” ”尽可能小。这可以尽量让目录尽可能小。这可以尽量让目录尽可能小。这可以尽量让目录尽可能小。这可以尽量让目录矩形为矩形为矩形为矩形为
53、“ “方方方方” ”形，从而改善树的结构，减少目录矩形形，从而改善树的结构，减少目录矩形形，从而改善树的结构，减少目录矩形形，从而改善树的结构，减少目录矩形面积。面积。面积。面积。（4 4）空间利用率尽可能高。）空间利用率尽可能高。）空间利用率尽可能高。）空间利用率尽可能高。 但实际上这四条互相影响，很难提高。但实际上这四条互相影响，很难提高。但实际上这四条互相影响，很难提高。但实际上这四条互相影响，很难提高。查找查找查找查找：（查找与红框：（查找与红框：（查找与红框：（查找与红框P P相交区域）相交区域）相交区域）相交区域） （1 1）从根节点开始，比较个目录矩形是否与）从根节点开始，比较个
54、目录矩形是否与）从根节点开始，比较个目录矩形是否与）从根节点开始，比较个目录矩形是否与P P相相相相交，因此交，因此交，因此交，因此R R1 1、R R2 2都与都与都与都与P P相交。需要比较相交。需要比较相交。需要比较相交。需要比较R R1 1、R R2 2所所所所包含的子树。包含的子树。包含的子树。包含的子树。（2 2）R R1 1中的目录矩形，只有中的目录矩形，只有中的目录矩形，只有中的目录矩形，只有R R5 5与与与与P P相交。进一步比相交。进一步比相交。进一步比相交。进一步比较较较较R R5 5所对应的目标矩形，得到所对应的目标矩形，得到所对应的目标矩形，得到所对应的目标矩形，得
55、到r r7 7、p p7 7。p p7 7确定相确定相确定相确定相交，交，交，交，r r7 7需要根据其空间坐标进一步判断。需要根据其空间坐标进一步判断。需要根据其空间坐标进一步判断。需要根据其空间坐标进一步判断。（3 3）同理得出）同理得出）同理得出）同理得出r r8 8要进一步判断。要进一步判断。要进一步判断。要进一步判断。插入插入：（只是按照：（只是按照“最小覆盖面积最小覆盖面积”的原则）的原则）从根节点开始，寻找下一个节点，遵循：从根节点开始，寻找下一个节点，遵循：（1）包围新增目标后，目录矩形的）包围新增目标后，目录矩形的“面积面积”增量最小增量最小（2）如果增量相同，目录矩形面积最
56、小。）如果增量相同，目录矩形面积最小。分裂：分裂： 原则上，分裂之后的覆盖面积尽可能小。原则上，分裂之后的覆盖面积尽可能小。这样在检索时可以减少检索的次数。这样在检索时可以减少检索的次数。错误的分裂正确的分裂分裂的最直接方法是遍历，即对所有可能的组合进行分裂的最直接方法是遍历，即对所有可能的组合进行分裂的最直接方法是遍历，即对所有可能的组合进行分裂的最直接方法是遍历，即对所有可能的组合进行计算，选择最优，但是代价太大，计算次数为计算，选择最优，但是代价太大，计算次数为计算，选择最优，但是代价太大，计算次数为计算，选择最优，但是代价太大，计算次数为2 2M-1M-1次。通次。通次。通次。通常常常
57、常MM取值取值取值取值5050，则计算次数为，则计算次数为，则计算次数为，则计算次数为2 24848，这是不可能的。，这是不可能的。，这是不可能的。，这是不可能的。 变通的方法：变通的方法：变通的方法：变通的方法： 平方级分裂算法平方级分裂算法平方级分裂算法平方级分裂算法：要求首先得到两个最浪费的对象，即这两个点构成的要求首先得到两个最浪费的对象，即这两个点构成的要求首先得到两个最浪费的对象，即这两个点构成的要求首先得到两个最浪费的对象，即这两个点构成的矩形，其面积减去这两个对象本身的面积后，差值最大。矩形，其面积减去这两个对象本身的面积后，差值最大。矩形，其面积减去这两个对象本身的面积后，差
58、值最大。矩形，其面积减去这两个对象本身的面积后，差值最大。然后选择一个新对象，计算这个对象增加到两个矩形然后选择一个新对象，计算这个对象增加到两个矩形然后选择一个新对象，计算这个对象增加到两个矩形然后选择一个新对象，计算这个对象增加到两个矩形之后的面积增量之后的面积增量之后的面积增量之后的面积增量d1,d2d1,d2，要求，要求，要求，要求|d1-d2|d1-d2|最大。最大。最大。最大。 把这个对象添加到面积增加小的矩形中去。把这个对象添加到面积增加小的矩形中去。把这个对象添加到面积增加小的矩形中去。把这个对象添加到面积增加小的矩形中去。 不能保证找到最优解不能保证找到最优解不能保证找到最优
59、解不能保证找到最优解。计算代价与计算代价与计算代价与计算代价与MM平方相关，与空间维数线性相关。平方相关，与空间维数线性相关。平方相关，与空间维数线性相关。平方相关，与空间维数线性相关。删除删除删除删除：从从从从R R树中删除一个目标，首先需要找到存放该树中删除一个目标，首先需要找到存放该树中删除一个目标，首先需要找到存放该树中删除一个目标，首先需要找到存放该目标的叶节点，再删除该目标对应数据项，并向目标的叶节点，再删除该目标对应数据项，并向目标的叶节点，再删除该目标对应数据项，并向目标的叶节点，再删除该目标对应数据项，并向上依次调整父节点对应索引项的目录矩形直至根上依次调整父节点对应索引项的
60、目录矩形直至根上依次调整父节点对应索引项的目录矩形直至根上依次调整父节点对应索引项的目录矩形直至根节点。节点。节点。节点。如果删除该目标对应数据项后叶节点下溢，则如果删除该目标对应数据项后叶节点下溢，则如果删除该目标对应数据项后叶节点下溢，则如果删除该目标对应数据项后叶节点下溢，则重新插入该叶节点中剩余的所有数据项于树的叶重新插入该叶节点中剩余的所有数据项于树的叶重新插入该叶节点中剩余的所有数据项于树的叶重新插入该叶节点中剩余的所有数据项于树的叶节点层，然后释放此叶节点的存储空间，最后删节点层，然后释放此叶节点的存储空间，最后删节点层，然后释放此叶节点的存储空间，最后删节点层，然后释放此叶节点
61、的存储空间，最后删除其父节点中与该叶节点对应的索引项。除其父节点中与该叶节点对应的索引项。除其父节点中与该叶节点对应的索引项。除其父节点中与该叶节点对应的索引项。例例例例，删除，删除，删除，删除r r1 1，路径为：根节点，路径为：根节点，路径为：根节点，路径为：根节点-R-R1 1-R-R3 3，找到，找到，找到，找到r1r1的叶节点并删除之，然后调整的叶节点并删除之，然后调整的叶节点并删除之，然后调整的叶节点并删除之，然后调整R R3 3目录矩形使之目录矩形使之目录矩形使之目录矩形使之完全包围完全包围完全包围完全包围p p1 1、p p4 4，调整，调整，调整，调整R R1 1的目录矩形，使之完全的目录矩形，使之完全的目录矩形，使之完全的目录矩形，使之完全包围包围包围包围R R3 3、R R4 4、R R5 5。
