空间数据库之空间索引课件.ppt

1、地理信息系统原理空间索引空间索引l问题的提出问题的提出l假想让我们在一个没有进行任何管理的图书馆中索取一份自己假想让我们在一个没有进行任何管理的图书馆中索取一份自己想要的资料，让我们在一个没有字母索引的字典里查找生字，想要的资料，让我们在一个没有字母索引的字典里查找生字，用焦头烂额来形容是再合适不过了。为了避免这种毫无方向漫用焦头烂额来形容是再合适不过了。为了避免这种毫无方向漫无边际的检索我们必须提出一种能加快定位速度的有效方法，无边际的检索我们必须提出一种能加快定位速度的有效方法，于是索引技术应运而生。给一个庞大的数据集找到一个有效的于是索引技术应运而生。给一个庞大的数据集找到一个有效的索引

2、体系是十分重要的，特别对于空间数据这种海量数据而言索引体系是十分重要的，特别对于空间数据这种海量数据而言更是如此。所以有这样的说法更是如此。所以有这样的说法“海量数据如无索引管理将寸步海量数据如无索引管理将寸步难行，必将成为难行，必将成为数据坟墓数据坟墓，丢不敢丢，用不能用，丢不敢丢，用不能用”。因此，。因此，一个信息系统不论是一般的关系型数据库还是空间数据库一个信息系统不论是一般的关系型数据库还是空间数据库,其一其一项根本的任务就是信息的检索查询。能否快速的检索信息是数项根本的任务就是信息的检索查询。能否快速的检索信息是数据库性能高低的一个主要的标志。据库性能高低的一个主要的标志。空间索引空

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

4、指针）。多个索引项就构成了一个索引（表）l索引本身也是一个文件，当索引很大时，也可将其分块，建立索引本身也是一个文件，当索引很大时，也可将其分块，建立高一层的索引。如此继续下去，直到最高级索引不超过一个块高一层的索引。如此继续下去，直到最高级索引不超过一个块时为止，这样就得到了一个多级索引结构时为止，这样就得到了一个多级索引结构l索引通常置于磁盘或内存，内存中一般只存放最高级索引。一索引通常置于磁盘或内存，内存中一般只存放最高级索引。一旦对一个大型数据文件建立了索引而形成了索引文件，则不论旦对一个大型数据文件建立了索引而形成了索引文件，则不论是对随机查找，还是对顺序查找都是方便的是对随机查找，

5、还是对顺序查找都是方便的空间索引空间索引l主要的索引技术主要的索引技术l如何组织索引文件是索引技术中的主要问题如何组织索引文件是索引技术中的主要问题.对名级索引可采对名级索引可采用定长记录固定组块的方式用定长记录固定组块的方式,并可对索引进行再索引并可对索引进行再索引,层层上去层层上去,直到最高级索引不超过系统规定的一个块的大小为止直到最高级索引不超过系统规定的一个块的大小为止.这样这样,整整个索引文件就构成了一棵以索引块和记录块为的索引树个索引文件就构成了一棵以索引块和记录块为的索引树空间索引空间索引l主要的索引技术主要的索引技术l树状数据结构有很多树状数据结构有很多,如二叉树如二叉树,多叉

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

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

8、找.为了寻找一种适合外查找且能动态维持索为了寻找一种适合外查找且能动态维持索引树平衡的结构引树平衡的结构,因而就应运面生了因而就应运面生了B-B-树和树和B+B+树树空间索引空间索引索引文件索引文件 记录本身的主文件外，还利用索引法列出一个键值记录本身的主文件外，还利用索引法列出一个键值K K与其对应记与其对应记录的磁盘地址的索引表，即索引是由关键字和指针组成的索引项录的磁盘地址的索引表，即索引是由关键字和指针组成的索引项构成。构成。空间索引空间索引l索引非顺序文件索引非顺序文件索引表中顺序列出所有可能的键值索引表中顺序列出所有可能的键值（稠密索引），利用二分查，利用二分查找法查找所需键值，得

9、到所需记录地址。找法查找所需键值，得到所需记录地址。该方法存取快，且无需记录顺序排列。建立方法：记录按输入的顺序放入数据区，同时软件在索引区建立方法：记录按输入的顺序放入数据区，同时软件在索引区建立索引表，待全部数据输完后，软件自动将索引表排序。建立索引表，待全部数据输完后，软件自动将索引表排序。空间索引空间索引l索引非顺序文件索引非顺序文件删除删除删除索引项，数据区保留，重新组织文件时消除之。删除索引项，数据区保留，重新组织文件时消除之。删除数据，索引保留，重新组织文件时消除之。删除数据，索引保留，重新组织文件时消除之。增加增加数据放在文件末尾，增加索引项，并排序。数据放在文件末尾，增加索引

10、项，并排序。修改修改查找相应位置，修改记录内容。查找相应位置，修改记录内容。（修改前后内容大小不一致时，涉及到删除增加操作）（修改前后内容大小不一致时，涉及到删除增加操作）空间索引空间索引l多级索引多级索引空间索引空间索引l索引顺序文件索引顺序文件是一种按照逻辑键值排序的索引文件，是用嵌入索引的手段是一种按照逻辑键值排序的索引文件，是用嵌入索引的手段把顺序文件予以扩充，以加速查找，记录的物理顺序与索引把顺序文件予以扩充，以加速查找，记录的物理顺序与索引中键值的顺序是一致的。中键值的顺序是一致的。（采用稀疏索引）建立方法：建立方法：数据按顺序分块存放（块间相临），记录每块数据按顺序分块存放（块间

11、相临），记录每块的最后记录键值及块的首地址形成索引表。的最后记录键值及块的首地址形成索引表。空间索引空间索引l索引顺序文件索引顺序文件空间索引空间索引l索引顺序文件索引顺序文件删除删除物理删除物理删除逻辑删除逻辑删除增加增加避免移动过多文件，将之暂放于溢出避免移动过多文件，将之暂放于溢出取。（重新组织文件时归位）取。（重新组织文件时归位）修改修改查找相应位置，修改记录内容。查找相应位置，修改记录内容。空间索引空间索引l空间索引空间索引其一是由于计算机的体系结构将内存分为内存、外存两种，访其一是由于计算机的体系结构将内存分为内存、外存两种，访问这两种内存一次所花费的时间一般为问这两种内存一次所花

12、费的时间一般为3040ns3040ns，810ms810ms，可，可以看出两者相差十万倍以上以看出两者相差十万倍以上,尽管现在有尽管现在有“内存数据库内存数据库”的说的说法，但绝大多数资料是存储在外存磁盘上的，如果对磁盘上资法，但绝大多数资料是存储在外存磁盘上的，如果对磁盘上资料的位置不加以记录和组织，每查询一个数据项就要扫描整个料的位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这种访问磁盘的代价就会严重影响系统的效率，因数据文件，这种访问磁盘的代价就会严重影响系统的效率，因此系统的设计者必须将资料在磁盘上的位置加以记录和组织，此系统的设计者必须将资料在磁盘上的位置加以记录和组织

13、，通过在内存中的一些计算来取代对磁盘漫无目的的访问，才能通过在内存中的一些计算来取代对磁盘漫无目的的访问，才能提高系统的效率提高系统的效率,尤其是尤其是GISGIS涉及的是各种海量的复杂资料，索涉及的是各种海量的复杂资料，索引对于处理的效率是至关重要的引对于处理的效率是至关重要的空间索引空间索引l空间索引空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指概要信息，如对象

14、的标识、外接矩形及指向空间对象实体的指针。针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率，从而提高空间操作的速度和效率空间索引空间索引l空间索引空间索引构造一个高性能的空间索引系统要解决几个主要问题：构造一个高性能的空间索引系统要解决几个主要问题：1,1,高速查询，高速查询，在大资料量的条件下能进行实时查询；在大资料量的条件下能进行实时查询；2,2,高度扩展性，可以无限扩展高度扩展

15、性，可以无限扩展索引区域；索引区域；3,3,地理元素变化时，能够很快更新空间索引；地理元素变化时，能够很快更新空间索引；4,4,不受坐标不受坐标系或投影变换的直接影响系或投影变换的直接影响空间索引的性能的优劣直接影响空间数据库和地理信息系统的空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术整体性能，它是空间数据库和地理信息系统的一项关键技术空间索引空间索引l空间索引空间索引尽管有许多特定的数据结构和算法用来完成空间索引,但基本原理相似,即采用分割原理,把查询空间划分为若干区域(通常为矩形或多边形),这些区域或单元包含空间资料并可唯一标识

16、。目前,有两种分割方法,一种是规则分割方法,另一种是基于对象的分割方法。规则分割方法是将地理空间按照规则或半规则方式分割,分割单元间接地与地理对象相关联,地理要素的几何部分可能被分割到几个相邻的单元中,这时地理对象的描述保持完整、而空间索引单元只存储对象的位置参考信息。在基于对象的分割方法中,索引空间的分割直接由地理对象来确定,索引单元包括地理对象的最小外接矩形空间索引空间索引l空间索引空间索引目前目前,国际上研究出许多高效的空间索引方法国际上研究出许多高效的空间索引方法,常见的空间索引常见的空间索引方法一般是自顶向下、逐级地划分地理空间方法一般是自顶向下、逐级地划分地理空间,从而形成各种树从

17、而形成各种树状空间索引结构。比较有代表性的规则分割方法包括规则格网状空间索引结构。比较有代表性的规则分割方法包括规则格网索引方法索引方法(,1997,1997年年)、树、树(,1983,1983年年)和树和树(,1987,1987年年)等。基于对象的等。基于对象的分割方法包括树分割方法包括树(,1984,1984年年)、+树树(,1987,1987年年)和树和树(,1991,1991年年;刘刘东东,1996,1996年年;陈述彭陈述彭,19991999年年)等。等。空间索引空间索引l格网索引（格网索引（Grid Index)Grid Index)思路：思路：是将研究区域用横竖线条划分大小相等或

18、不等的格网，是将研究区域用横竖线条划分大小相等或不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。询速度。空间索引空间索引l格网索引（格网索引（Grid Index)Grid Index)步骤：步骤：划分行列（划分行列（M X NM X N）；）；计算网格大小及每个格网的矩形范围；计算网格大小及每个格网的矩形范围；开辟目标空间（记录目标穿过的网格）和格网空间（记录开辟目标空间（记录目标穿过的网格）和格网空间（记录格网内的目标）；格网内的目标）；注册点、线、面、注记等目标，并记录之；注册点、线、面、注记等目标，并记录之；空间索引空间索引l格网索引（格网索引（Grid Index)Grid Index)查询：首先计算出用户查询对象所在的网格查询：首先计算出用户查询对象所在的网格,然后通过该网格然后通过该网格快速查询所选地理对象。快速查询所选地理对象。作业：绘出格网索引建立过程和基作业：绘出格网索引建立过程和基于该所引开窗检索目标过程的程于该所引开窗检索目标过程的程序流程图序流程图