空间数据库课件：SDB（第五章）.pptx

1、RSGIS, WHURSGIS, WHU版权：遥感信息工程学院 地理信息系统教研室空间数据库空间数据库RSGIS, WHURSGIS, WHU问题的提出问题的提出假想让我们在一个没有进行任何管理的图书馆中索取一假想让我们在一个没有进行任何管理的图书馆中索取一份自己想要的资料，让我们在一个没有字母索引的字典份自己想要的资料，让我们在一个没有字母索引的字典里查找生字，用里查找生字，用来形容是再合适不过了。为了来形容是再合适不过了。为了避免这种毫无方向漫无边际的检索我们必须提出一种能避免这种毫无方向漫无边际的检索我们必须提出一种能加快定位速度的有效方法，于是索引技术应运而生。给加快定位速度的有效方法

2、，于是索引技术应运而生。给一个庞大的数据集找到一个有效的索引体系是十分重要一个庞大的数据集找到一个有效的索引体系是十分重要的，特别对于空间数据这种海量数据而言更是如此。所的，特别对于空间数据这种海量数据而言更是如此。所以有这样的说法以有这样的说法“。因此，。因此，一个信息系统不论是一般的关系型数据库还是空间数据一个信息系统不论是一般的关系型数据库还是空间数据库库, ,其一项根本的任务就是信息的检索查询。能否快速的其一项根本的任务就是信息的检索查询。能否快速的检索信息是数据库性能高低的一个主要的标志。检索信息是数据库性能高低的一个主要的标志。RSGIS, WHURSGIS, WHU概概 念念RS

3、GIS, WHURSGIS, WHU概概 念念n 索引对大家来说并不陌生的，如日常生活遇到的词典中索引，文索引对大家来说并不陌生的，如日常生活遇到的词典中索引，文献中的词条索引，等等这些生活中的索引（以及书籍目录等）中就献中的词条索引，等等这些生活中的索引（以及书籍目录等）中就包括了计算机索引结构的基本原理包括了计算机索引结构的基本原理n 索引的基本构件是索引项。索引的基本构件是索引项。，通，通过指针就可找到含有此关键词值的记录，即一个索引项为：过指针就可找到含有此关键词值的记录，即一个索引项为：。多个索引项就构成了一个索引（表）。多个索引项就构成了一个索引（表）n 索引本身也是一个文件，索引

4、本身也是一个文件，。如此继续下去，直到最高级索引不超过一个块时为止，。如此继续下去，直到最高级索引不超过一个块时为止，这样就得到了一个多级索引结构这样就得到了一个多级索引结构n 索引通常置于磁盘或内存，内存中一般只存放最高级索引。一旦索引通常置于磁盘或内存，内存中一般只存放最高级索引。一旦对一个大型数据文件建立了索引而形成了索引文件，则不论是对随对一个大型数据文件建立了索引而形成了索引文件，则不论是对随机查找，还是对顺序查找都是方便的机查找，还是对顺序查找都是方便的RSGIS, WHURSGIS, WHU概概 念念RSGIS, WHURSGIS, WHU概概 念念RSGIS, WHURSGIS

5、, WHU主要的索引技术主要的索引技术对对各级索引可采用定长记录固定组块的方式各级索引可采用定长记录固定组块的方式, ,并可并可对索引进行再索引对索引进行再索引, ,层层上去层层上去, ,直到最高级索引不直到最高级索引不超过系统规定的一个块的大小为止超过系统规定的一个块的大小为止. .这样这样, ,整个索整个索引文件就构成了一棵以索引块和记录块为索引的引文件就构成了一棵以索引块和记录块为索引的树。树。RSGIS, WHURSGIS, WHU主要的索引技术主要的索引技术树状数据结构有很多树状数据结构有很多, ,如二叉树如二叉树, ,多叉树等多叉树等, ,它们都可用来构成它们都可用来构成索引文件索

6、引文件. .但是但是, ,这些结构主要有以两方面的问题这些结构主要有以两方面的问题: :，大都只适于内查找，大都只适于内查找, ,即所要查找的资料均放在内存中即所要查找的资料均放在内存中; ;，易引起所谓不平衡的问题，易引起所谓不平衡的问题. .对后者我们以二叉树为例对后者我们以二叉树为例. .当二叉插入记录时当二叉插入记录时, ,每次都从根开每次都从根开始比较关键词的大小始比较关键词的大小, ,比根小的放到根的左子树中比根小的放到根的左子树中, ,比根大的比根大的则放到根的右子树中则放到根的右子树中, ,在子树中重复上述过程在子树中重复上述过程, ,直至找到记录直至找到记录的正确位置的正确位

7、置. .在这种不加控制的情况下在这种不加控制的情况下, ,树中可能会出现长短树中可能会出现长短不一的分枝不一的分枝, ,即有的可能很长即有的可能很长, ,有的可能很短有的可能很短. .这种这种从根到叶的从根到叶的路径不等长的现象就叫做不平衡路径不等长的现象就叫做不平衡. .如果出现不平衡如果出现不平衡, ,则在检索则在检索时平均查找次数可能变大时平均查找次数可能变大, ,使得查找效率大为降低使得查找效率大为降低. .RSGIS, WHURSGIS, WHU主要的索引技术主要的索引技术n 为解决平衡问题为解决平衡问题, ,人们相继提出了人们相继提出了及及, ,但这些树仍局限于内查找但这些树仍局限

8、于内查找. .n 为了寻找一种适合外查找且能动态维持索引树平为了寻找一种适合外查找且能动态维持索引树平衡的结构衡的结构, ,因而就应运面生了因而就应运面生了B-B-树和树和B+B+树树. .RSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHU数据库索引原理数据库索引原理RSGIS, WHURSGIS, WHUSpatial Index StructuresRSGIS, WHURSGIS, WHU数据库索引原理数据库索引原理RSGIS, WHURSGIS, WHU数据库索引原理数据库索引原理RSGIS, WHURSGIS, WHU数据库索引原理数据库索引原理RSGIS

9、, WHURSGIS, WHU索引文件索引文件 主文件外，还利用索引法列出一个主文件外，还利用索引法列出一个键值键值K K与其与其对应记录的磁盘地址的索引表对应记录的磁盘地址的索引表，即索引是由关，即索引是由关键字和指针组成的索引项构成。键字和指针组成的索引项构成。RSGIS, WHURSGIS, WHU索引文件索引文件 RSGIS, WHURSGIS, WHU（修改前后内容大小不一致时，涉及到删除增加操作）索引文件索引文件 RSGIS, WHURSGIS, WHU索引文件索引文件 RSGIS, WHURSGIS, WHU索引文件索引文件 RSGIS, WHURSGIS, WHU索引文件索引文

10、件 RSGIS, WHURSGIS, WHU索引文件索引文件 RSGIS, WHURSGIS, WHUContentsRSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHUIntroductionRSGIS, WHURSGIS, WHUIntroductionRSGIS, WHURSGIS, WHUIntroductionRSGIS, WHURSGIS, WHUIntroductionRSGIS, WHURSGIS, WHUIntroductionRSGIS, WHURSGIS, WHUIntroductionRSGIS, WHURSGIS, WHURSGIS, WH

11、URSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WH

12、URSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHUR R树和树和R+R+树空间索引树空间索引RSGIS, WHURSGIS, WHUR R树和树和R+R+树空间索引树空间索引RSGIS, WHURSGIS, WHUR R树和树和R+R+树空间索引树空间索引RSGIS, WHURSGIS, WHUR R树和树和R+R+树空间索引树空间索引RSGIS, WHURSGIS, WHU3 R3 R树和树和R+R+树空间索引树空间索引RSGIS, WHURSGIS, WHURSGIS, WHURSGIS, WHUThe R+-treeRSGIS, WHURSGIS, WHUThe R+-treeRSGIS, WHURSGIS, WHUExample of Spatial IndexingRSGIS, WHURSGIS, WHUExample of Spatial Indexing