11-数据结构与算法-北京大学2008-张铭-索引技术

数据结构与算法第11章索引技术本章由张铭主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。主要内容基本概念11.1线性索引11.2静态索引11.3倒排索引11.4动态索引11.4.4动态、静态索引性能的比较11.5位索引技术11.6红黑树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念输入顺序文件主码与辅码索引与索引文件稠密索引与稀疏索引“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。输入顺序文件输入顺序文件(entry-sequencedfile)按照记录进入系统的顺序存储记录一般说来，输入顺序文件的结构相当于一个磁盘中未排序的线性表因此不支持高效率的检索“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。主码主码(primarykey)是数据库中的每条记录的唯一标识例如，公司职员信息的记录的主码可以是职员的身份证号码如果只有主码，不便于各种灵活检索“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。辅码辅码(secondarykey)是数据库中可以出现重复值的码辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来大多数检索都是利用辅码索引来完成的“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。索引索引(indexing)是把一个关键码与它对应的数据记录的位置相关联的过程(关键码，指针)对，即(key,pointer)指针指向主要数据库文件（也称为“主文件”）中的完整记录索引文件(indexfile)是用于记录这种联系的文件组织结构索引技术是组织大型数据库的一种重要技术高效率的检索插入、更新、删除“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。索引文件一个主文件可能有多个相关索引文件每个索引文件往往支持一个关键码字段不需要重新排列重排主文件可以通过该索引文件高效访问记录中该关键码值“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稠密索引vs稀疏索引稠密索引：对每个记录建立一个索引项主文件不按照关键码的顺序排列稀疏索引：对一组记录建立一个索引记录按照关键码的顺序存放可以把记录分成多个组（块）•索引指针指向的这一组记录在磁盘中的起始位置“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。11.1线性索引基本概念线性索引的优点线性索引的问题二级线性索引“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。线性索引文件按照关键码的顺序进行排序文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置92733755数据库记录线形索引文件Go“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。线性索引的优点对变长的数据库记录的访问可以对数据进行高效检索二分检索顺序处理比较操作批处理的操作节省空间(相对其它索引结构)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。线性索引的问题线性索引太大，存储在磁盘中在一次检索过程中可能多次访问磁盘，从而影响检索的效率使用二级线性索引更新线性索引在数据库中插入或者删除记录时“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二级线性索引例如，磁盘块的大小是1024字节，每对(关键码，指针)索引对需要8个字节1024/8=128每磁盘块可以存储128条这样的索引对假设数据文件包含10000条记录稠密一级线性索引中包含10000条记录•10000/128=78.1•那么一级线性索引占用79个磁盘块相应地，二级线性索引文件中有79项索引对这个二级线性索引文件可以在一个磁盘块“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二级线性索引的例子关键码与相应磁盘块中第一条记录的关键码的值相同指针指向相应磁盘块的起始位置120035744107231……2002200220035583574492971072313293…………磁盘块一级索引二级索引“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。例如：检索关键码为2555的记录1.二级线性索引文件读入内存2.二分法找关键码的值小于等于2555的最大关键码所在一级索引磁盘块地址——关键码为2003的记录3.根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘块，并把该块读入内存4.按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置5.最后把所需记录读入，完成检索操作“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。11.2静态索引基本概念多分树ISAM“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念静态索引索引结构在文件创建、初始装入记录时生成一旦生成就固定下来，在系统运行(例如插入和删除记录)过程中索引结构并不改变只有当文件再组织时才允许改变索引结构“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。多分树组织索引一般不用二叉树而采用多分树大大减少访问外存的次数“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树转换成多分树632次访问索引块1次访问外存数据块“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。ISAMISAM是解决需要频繁更新的大型数据库的一个早期尝试在采用基于B+树的VSAM技术之前，IBM公司曾经广泛地采用ISAM技术多分树的应用为磁盘存取而设计结构采用多级索引主索引柱面索引磁道索引“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。11.3倒排索引基本概念11.3.1基于属性的倒排11.3.2对正文文件的倒排“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念基于属性的检索要求检索结构中某个或若干个属性满足一定条件的结点不是按关键码的值检索“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。教师数据库主表EMP#NAMEDepartmentProfessionSpecialtyAddress0155李宇数学教授代数C1050421刘阳外语助教英语E3100208赵亮物理助教力学C2110211张伟物理讲师原子物理D5080132王亮数学助教几何E2200119王卓数学讲师代数B1020330孙丽计算机教授软件A1080455刘珍外语讲师法语A2250310周兵计算机讲师英语B4230341何江计算机助教计算机F406……“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。11.3.1基于属性的倒排对某属性按属性值建立索引表，称倒排表(attr,ptrList)•（属性值，具有该属性值的各记录指针）•记录指针可以是关键码，或该记录的主文件地址颠覆主文件的顺序，因而称为倒排索引属性往往是离散型的对于连续型的索引，往往用B树倒排文件：带有倒排索引的文件“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。教师数据库倒排表DepartmentlistEMP#数学物理计算机外语0155,0132,01190208,02110330,0310,03410421,0455ProfessionlistEMP#教授讲师助教0155,03300211,0119,0455,03100421,0208,0132,0341SpecialtylistEMP#代数几何力学原子物理软件英语法语0155,01190132020802110330,03410421,03100455“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。优缺点优点：能够对于基于属性的检索进行较高效率的处理缺点：花费了保存倒排表的存储代价降低了更新运算的效率“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。11.3.2对正文文件的倒排正文索引(TextIndexing)处理的就是“建立一个数据结构以提供对文本内容的快速检索”。方法词索引(wordindex)全文索引(full-textindex)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。词索引基本思想：把正文看作由符号和词所组成的集合，从正文中抽取出关键词，然后用这些关键词组成一些适合快速检索的数据结构。适用于多种文本类型，特别是那些可以很容易就解析成一组词的集合的文本适用于英文中文等东方文字要经过“切词”处理“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。全文索引基本思想：把正文看作一个长的字符串在数据结构中记录的是子字符串的开始位置查询就可以针对正文中的任何子字符串可以对每一个字符建立索引，从而使查询词不再限于关键词需要更大的空间“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。倒排文件使用最广泛的是词索引词索引使用最广泛一个已经排过序的关键词的列表其中每个关键词指向一个倒排表（postinglist）•指向该关键词出现文档集合•在文档中的位置“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。倒排索引建立示例正文文件：由6个文档组成，每个文档都是长字符串Peaseporridgehot,pleaseporridgecold,文档编号文本内容1Peaseporridgeinthepot,Ninedaysold.Somelikeithot,somelikeitcold,Somelikeitinthepot,Ninedaysold.23456“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。倒排索引12345678910111213编号词语（文档编号，位置）colddayshotinlikenineoldpeaseporridgeitpotsomethe(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)类似处理1中的其他词语同理，处理2中的词语（2,1）依次处理所有文档“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。建立正文倒排文件1.对文档集中的所有文件都进行分割处理，把正文分成多条记录文档切分正文记录取决于程序的需要•定长的块、段落、章节，甚至一组文档“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。建立正文倒排文件（续1）2.给每条记录赋一组关键词以人工或者自动的方式从记录中抽取关键词停用词(Stopword)抽词干(Stemming)切词（segmentati