第十章索引技术.ppt
《第十章索引技术.ppt》由会员分享,可在线阅读,更多相关《第十章索引技术.ppt(137页珍藏版)》请在三一办公上搜索。
1、第十章 索引技术,任课教员:张 铭http:/,北京大学信息学院 版权所有,转载或翻印必究 Page 2,主要内容,10.1 线性索引10.2 静态索引10.3 倒排索引10.4 动态索引10.5 动态、静态索引性能比较,北京大学信息学院 版权所有,转载或翻印必究 Page 3,基本概念,输入顺序文件主码与辅码索引与索引文件稠密索引与稀疏索引,北京大学信息学院 版权所有,转载或翻印必究 Page 4,输入顺序文件,输入顺序文件(entry-sequenced file)按照记录进入系统的顺序存储记录输入顺序文件的结构相当于一个磁盘中未排序的线性表因此不支持高效率的检索,北京大学信息学院 版权所
2、有,转载或翻印必究 Page 5,主码,主码(primary key)是数据库中的每条记录的唯一标识例如,公司职员信息的记录的主码可以是职员的身份证号码 如果只有主码,不便于各种灵活检索,北京大学信息学院 版权所有,转载或翻印必究 Page 6,辅码,辅码(secondary key)是数据库中可以出现重复值的码辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来大多数检索都是利用辅码索引来完成的,北京大学信息学院 版权所有,转载或翻印必究 Page 7,索引,索引(indexing)是把一个关键码与它对应的数据记录的位置相关联的过程 索引技术是组织大型数据库的一种重要技术数据库组
3、织存储在外存中的大量记录高效率的检索插入、更新、删除,北京大学信息学院 版权所有,转载或翻印必究 Page 8,索引文件,索引文件(index file)是用于记录这种联系(关键码与它对应的数据记录的位置)的文件组织结构。索引文件的记录(关键码,指针)对将每个关键码和一个指针关联指针指向主要数据库文件(也称为“主文件”)中的完整记录,北京大学信息学院 版权所有,转载或翻印必究 Page 9,索引文件,索引文件并不需要重新排列记录在磁盘中的顺序(不用重排主文件)一个数据库可能有多个相关的索引文件每个索引文件往往支持一个关键码字段可以通过该索引文件高效访问记录中该关键码值,北京大学信息学院 版权所
4、有,转载或翻印必究 Page 10,稠密索引,对每一个记录建立一个索引项,这样建立的索引被称为稠密索引(dense index)数据库文件中的记录不按照关键码的顺序排列时(比如按照加入的顺序排列),北京大学信息学院 版权所有,转载或翻印必究 Page 11,稀疏索引,对一组记录建立一个索引项,这种索引称之为稀疏索引(spare index)当记录在磁盘中是按照关键码的顺序存放可以把记录分成多个组(块)稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置,北京大学信息学院 版权所有,转载或翻印必究 Page 12,10.1 线性索引,基本概念线性索引的优点线性索引的问题二级线性索引,北京大学
5、信息学院 版权所有,转载或翻印必究 Page 13,基本概念,线性索引(linear index)的索引文件一组简单的关键码(key)/指针(pointer)对的序列,北京大学信息学院 版权所有,转载或翻印必究 Page 14,基本概念(续),线性索引文件按照关键码的顺序进行排序文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置,北京大学信息学院 版权所有,转载或翻印必究 Page 15,基本概念(续),线性索引的索引文件存储在内存中,把索引存储在内存中能大大地提高检索速度存储在磁盘中根据线性索引的文件大小和内存的空间限制,北京大学信息学院 版权所有,转载或翻印必究 Pa
6、ge 16,线性索引的优点,对变长的数据库记录的访问可以对数据进行高效检索二分检索 顺序处理比较操作批处理的操作节省空间(相对其它索引结构),北京大学信息学院 版权所有,转载或翻印必究 Page 17,线性索引的问题,线性索引太大,存储在磁盘中在一次检索过程中有可能多次访问磁盘,从而影响检索的效率解决办法:使用二级线性索引更新线性索引在数据库中插入或者删除记录时,北京大学信息学院 版权所有,转载或翻印必究 Page 18,二级线性索引,每一条二级线性索引记录对应于一个一级线性索引文件的磁盘块关键码的值与对应的线性索引文件的磁盘块中第一条记录(从物理位置上看的第一条)的关键码的值相同记录中的指针
7、则指向相应线性索引文件的磁盘块的起始位置,北京大学信息学院 版权所有,转载或翻印必究 Page 19,二级线性索引,例如,磁盘块的大小是1024字节,每个关键码指针记录需要8个字节,则每磁盘块可以存储128条这样的记录假设线性文件索引中包含10000条记录,那么该线性索引占用79个磁盘块,相应的,二级线性索引文件中有79项记录,北京大学信息学院 版权所有,转载或翻印必究 Page 20,二级线性索引的例子,关键码与相应磁盘块中第一条记录的关键码的值相同指针指向相应磁盘块的起始位置,北京大学信息学院 版权所有,转载或翻印必究 Page 21,二级线性索引检索,在检索时,线性索引文件并不被读入内存
8、,被读入内存的是二级线性索引文件 由于二级索引往往存储内存,通常只需要访问两次磁盘即可:一次读入线性索引文件,一次读入数据库记录,北京大学信息学院 版权所有,转载或翻印必究 Page 22,二级线性索引检索的例子,例如,检索关键码为2555的记录首先在内存中的二级线性索引文件中找到关键码的值小于等于2555的最大关键码所在的记录关键码为2003的记录根据记录中的指针找到其对应的线性索引文件的磁盘块,并把该块读入内存按照二分法对该块进行检索,找到所需要的记录在磁盘上的位置最后把所需记录读入,完成检索操作,北京大学信息学院 版权所有,转载或翻印必究 Page 23,10.2 静态索引,10.2.1
9、 多分树10.2.2 ISAM,北京大学信息学院 版权所有,转载或翻印必究 Page 24,基本概念,静态索引索引结构在文件创建、初始装入记录时生成一旦生成就固定下来,在系统运行(例如插入和删除记录)过程中索引结构并不改变只有当文件再组织时才允许改变索引结构,北京大学信息学院 版权所有,转载或翻印必究 Page 25,10.2.1 多分树,组织索引一般不用二叉树而采用多分树 大大减少访问外存的次数,北京大学信息学院 版权所有,转载或翻印必究 Page 26,多分树图例,北京大学信息学院 版权所有,转载或翻印必究 Page 27,上图访问一个叶结点查找二叉树访问六次外存 查找多分树访问两次外存,
10、北京大学信息学院 版权所有,转载或翻印必究 Page 28,结点更大以更少的外存访问次数来完成查找 需要较大的缓冲区读入一个结点也需较多时间 一个结点最好能放在一个磁盘块中,北京大学信息学院 版权所有,转载或翻印必究 Page 29,“数据基本区”多分树的叶结点区域存放数据记录“索引区”多分树的非叶结点区域存放各子树结点中的最大(或最小)的关键码,北京大学信息学院 版权所有,转载或翻印必究 Page 30,溢出、溢出区新记录要插入的结点已满把溢出的记录存放到另开辟的溢出区不改变索引的结构 记录送入溢出区的两种方式 保持顺序,把最后一个记录送往溢出区不保持顺序,把新插入的记录送入溢出区,北京大学
11、信息学院 版权所有,转载或翻印必究 Page 31,10.2.2 ISAM,ISAM是解决需要频繁更新的大型数据库的一个早期尝试在采用基于B+树的VSAM技术之前,IBM公司曾经广泛地采用ISAM技术,北京大学信息学院 版权所有,转载或翻印必究 Page 32,多分树的应用 为磁盘存取而设计 结构采用多级索引主索引柱面索引磁道索引,北京大学信息学院 版权所有,转载或翻印必究 Page 33,北京大学信息学院 版权所有,转载或翻印必究 Page 34,北京大学信息学院 版权所有,转载或翻印必究 Page 35,ISAM的查找,先查主索引,从主索引查出柱面索引的分布主索引常驻内存从柱面索引查出磁道
12、索引的分布柱面索引放在中间位置的柱面 从磁道索引查出所要找的记录的地址,北京大学信息学院 版权所有,转载或翻印必究 Page 36,ISAM的插入,磁道索引中,索引项的两个子项在记录插入之前是相同的,在插入记录后就要改变 例如,插入R165 以后:,北京大学信息学院 版权所有,转载或翻印必究 Page 37,如果有多个溢出记录,则这些溢出记录必须按顺序链接起来,在溢出索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录所在磁道号 例如,再插入R168,R166以后:,北京大学信息学院 版权所有,转载或翻印必究 Page 38,如果有多个溢出记录,则这些溢出记录必须按顺序链接起来,在溢出
13、索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录所在磁道号 例如,再插入R168,R166以后:,北京大学信息学院 版权所有,转载或翻印必究 Page 39,在溢出区中,除了存放记录以外还存放链指针 柱面索引变化:,北京大学信息学院 版权所有,转载或翻印必究 Page 40,ISAM插入的好处,在进一步查找时,容易判断要查找的记录是在基本区还是在溢出区若在基本区,则指针指出了记录所在的磁道号;若在溢出区,则指针指出了溢出记录链中第一个(关键码为最小)记录所在的磁道号及在磁道中的相对记录号,沿着该链可以找到要找的记录。,北京大学信息学院 版权所有,转载或翻印必究 Page 41,10
14、.3 倒排索引,10.3.1 基于属性的倒排10.3.2 对正文文件的倒排,北京大学信息学院 版权所有,转载或翻印必究 Page 42,基本概念,不仅需要按关键码的值查找还需要按照属性的值来查找记录,北京大学信息学院 版权所有,转载或翻印必究 Page 43,基本概念,倒排索引对某属性按属性值建立索引(属性值,具有该属性值的各记录的地址列表)不是由记录关键码来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)这种属性往往是离散型的对于连续型的索引,往往用B树,北京大学信息学院 版权所有,转载或翻印必究 Page 44,基本概念,倒排索引文件带有倒排索引的
15、文件简称倒排文件(inverted file),北京大学信息学院 版权所有,转载或翻印必究 Page 45,10.3.1 基于属性的检索,基于属性的检索要求检索结构中某个或若干个属性满足一定条件的结点,北京大学信息学院 版权所有,转载或翻印必究 Page 46,例如,在某百货公司的职工文件中,有如下的记录格式:(EMP#,NAME,DEPT,AGE,SAL)该记录格式中的数据项其含义分别为职工号,姓名,所在部门,年龄,工资。,北京大学信息学院 版权所有,转载或翻印必究 Page 47,查询实例,对这样的职工文件进行下列类型的查询:(1)简单查询。例如:列出玩具部(即DEPT=“Toy”)的所有
16、职工记录(2)范围查询。例如:列出工资在40元和80元之间(即40SAL80)的所有职工记录(3)逻辑查询。例如:列出玩具部中年龄在50岁以上或者工资在100元以上的职工记录(DEPT=“Toy”AND(AGE50 OR SAL100),北京大学信息学院 版权所有,转载或翻印必究 Page 48,10.3.1 倒排表,倒排表(inverted list)是基于属性的倒排在保留原表的同时,对于感兴趣的(即可以用来作为检索参数的)每个属性的可能取值都建立一个称作倒排表的线性表存放与此属性相对应的所有关键码值,北京大学信息学院 版权所有,转载或翻印必究 Page 49,10.3.1 倒排文件,索引项
17、一个具体的索引值一组指针(例如记录的主码)这些指针分别指向在该属性项上具有该具体值的各个记录一个倒排表一个索引项倒排文件倒排表组成的索引文件,北京大学信息学院 版权所有,转载或翻印必究 Page 50,北京大学信息学院 版权所有,转载或翻印必究 Page 51,10.3.1 基于属性的倒排,列出玩具部(即DEPT=“Toy”)的所有职工记录。从关于属性DEPT的索引中,取出属性值为“Toy”的倒排表,此倒排表中包合的指针所指向的各记录即为所求。,北京大学信息学院 版权所有,转载或翻印必究 Page 52,列出工资在40元和80元之间(即40SAL80)的所有职工记录。从关于属性SAL的索引中,
18、找出属性值在40与80之间的倒排表,每个倒排表中含有一个指针集合。对这些集合进行并的运算,其结果集合中包含的指针所指的各记录即为所求。,北京大学信息学院 版权所有,转载或翻印必究 Page 53,列出玩具部中年龄在50岁以上或者工资在100元以上的职工记录(DEPT=“Toy”AND(AGE50 OR SAL100)。先采用类似(1)、(2)的方法,分别找出满足条件DEPT=“Toy”,AGE50,和SAL100的指针集合,然后对后两个指针集合求并,并且将结果集合与第一个指针集合求交,最后的结果集合中包含的指针所指的各记录即为所求。,北京大学信息学院 版权所有,转载或翻印必究 Page 54,
19、优点:能够对于基于属性的检索进行较高效率的处理 缺点:花费了保存倒排表的存储代价降低了更新运算的效率,北京大学信息学院 版权所有,转载或翻印必究 Page 55,10.3.2 对正文文件的倒排,正文索引(Text Indexing)处理的就是“建立一个数据结构以提供对文本内容的快速检索”。方法词索引(word index)全文索引(full-text index),北京大学信息学院 版权所有,转载或翻印必究 Page 56,词索引,基本思想:把正文看作由符号和词所组成的集合,从正文中抽取出关键词,然后用这些关键词组成一些适合快速检索的数据结构。适用于多种文本类型,特别是那些可以很容易就解析成一
20、组词的集合的文本 适用于英文不适用于中文等东方文字,北京大学信息学院 版权所有,转载或翻印必究 Page 57,全文索引,基本思想:把正文看作一个长的字符串在数据结构中记录的是子字符串的开始位置查询就可以针对正文中的任何子字符串可以对每一个字符建立索引,从而使查询词不再限于关键词 需要更大的空间,北京大学信息学院 版权所有,转载或翻印必究 Page 58,词索引使用最广泛一个已经排过序的关键词的列表其中每个关键词指向一个倒排表(posting list)指向该关键词出现文档集合在文档中的位置,北京大学信息学院 版权所有,转载或翻印必究 Page 59,倒排文件的全文本索引,北京大学信息学院 版
21、权所有,转载或翻印必究 Page 60,简化的正文倒排文件,北京大学信息学院 版权所有,转载或翻印必究 Page 61,建立正文倒排文件,第一步,对文档集中的所有文件都进行分割处理,把正文分成多条记录文档。切分正文记录取决于程序的需要定长的块、段落、章节,甚至一组文档,北京大学信息学院 版权所有,转载或翻印必究 Page 62,第二步,给每条记录赋一组关键词。以人工或者自动的方式从记录中抽取关键词停用词(Stopword)抽词干(Stemming)切词(segmentation),北京大学信息学院 版权所有,转载或翻印必究 Page 63,第三步,建立正文倒排表、倒排文件得到各个关键词的集合对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 索引 技术
链接地址:https://www.31ppt.com/p-5286312.html