北大数据结构与算法课件10A索引技术

数据结构与算法第十章索引技术信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2主要内容„基本概念„10.1线性索引„10.2静态索引„10.3倒排索引„10.4动态索引„10.5动态、静态索引性能比较北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3基本概念„输入顺序文件„主码与辅码„索引与索引文件„稠密索引与稀疏索引北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4输入顺序文件„输入顺序文件(entry-sequencedfile)按照记录进入系统的顺序存储记录„一般说来，输入顺序文件的结构相当于一个磁盘中未排序的线性表„因此不支持高效率的检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5主码„主码(primarykey)是数据库中的每条记录的唯一标识„例如，公司职员信息的记录的主码可以是职员的身份证号码„如果只有主码，不便于各种灵活检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6辅码„辅码(secondarykey)是数据库中可以出现重复值的码„辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来„大多数检索都是利用辅码索引来完成的北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7索引„索引(indexing)是把一个关键码与它对应的数据记录的位置相关联的过程„(关键码，指针)对，即(key,pointer)„指针指向主要数据库文件（也称为“主文件”）中的完整记录„索引文件(indexfile)是用于记录这种联系的文件组织结构„索引技术是组织大型数据库的一种重要技术„高效率的检索„插入、更新、删除北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8索引文件„一个主文件可能有多个相关索引文件„每个索引文件往往支持一个关键码字段„不需要重新排列重排主文件„可以通过该索引文件高效访问记录中该关键码值北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9稠密索引vs稀疏索引„稠密索引：对每个记录建立一个索引项„主文件不按照关键码的顺序排列„稀疏索引：对一组记录建立一个索引„记录按照关键码的顺序存放„可以把记录分成多个组（块）„索引指针指向的这一组记录在磁盘中的起始位置北京大学信息学院张铭编写©版权所有，转载或翻印必究Page1010.1线性索引„基本概念„线性索引的优点„线性索引的问题„二级线性索引北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11线性索引文件„按照关键码的顺序进行排序„文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置3755739292733755线性索引文件数据库记录北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12线性索引的优点„对变长的数据库记录的访问„可以对数据进行高效检索„二分检索„顺序处理„比较操作„批处理的操作„节省空间(相对其它索引结构)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13线性索引的问题„线性索引太大，存储在磁盘中„在一次检索过程中可能多次访问磁盘，从而影响检索的效率„使用二级线性索引„更新线性索引„在数据库中插入或者删除记录时北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14二级线性索引„例如，磁盘块的大小是1024字节，每对(关键码，指针)索引对需要8个字节„1024/8=128„每磁盘块可以存储128条这样的索引对„假设数据文件包含10000条记录„稠密一级线性索引中包含10000条记录„10000/128=78.1„那么一级线性索引占用79个磁盘块„相应地，二级线性索引文件中有79项索引对„这个二级线性索引文件可以在一个磁盘块北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15二级线性索引的例子„关键码与相应磁盘块中第一条记录的关键码的值相同„指针指向相应磁盘块的起始位置120035744107231……200220035583574492971072313293…………磁盘块一级索引二级索引北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16例如：检索关键码为2555的记录1.二级线性索引文件读入内存2.二分法找关键码的值小于等于2555的昀大关键码所在一级索引磁盘块地址——关键码为2003的记录3.根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘块，并把该块读入内存4.按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置5.昀后把所需记录读入，完成检索操作北京大学信息学院张铭编写©版权所有，转载或翻印必究Page1710.2静态索引„基本概念„10.2.1多分树„10.2.2ISAM北京大学信息学院张铭编写©版权所有，转载或翻印必究Page1810.2.1基本概念静态索引„索引结构在文件创建、初始装入记录时生成„一旦生成就固定下来，在系统运行(例如插入和删除记录)过程中索引结构并不改变„只有当文件再组织时才允许改变索引结构北京大学信息学院张铭编写©版权所有，转载或翻印必究Page1910.2.2多分树„组织索引一般不用二叉树而采用多分树„大大减少访问外存的次数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2011331491571123456789……….二叉树数据1,2…63,64的二分索引查找6361646次访问索引块631次访问外存数据块北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21二叉树转换成多分树632次访问索引块1次访问外存数据块北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22„“数据基本区”„多分树的叶结点区域„存放数据记录„“索引区”„多分树的非叶结点区域„存放各子树结点中的昀大(或昀小)的关键码北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23„溢出、溢出区„新记录要插入的结点已满„把溢出的记录存放到另开辟的溢出区„不改变索引的结构„记录送入溢出区的两种方式„保持顺序，把昀后一个记录送往溢出区„不保持顺序，把新插入的记录送入溢出区北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2410.2.2ISAM„ISAM是解决需要频繁更新的大型数据库的一个早期尝试„在采用基于B+树的VSAM技术之前，IBM公司曾经广泛地采用ISAM技术北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25„多分树的应用„为磁盘存取而设计„结构采用多级索引„主索引„柱面索引„磁道索引北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26400T1625T21000T380C1T0200C2T0400C3T0625C6T01000C9T0T0T1T2T3…40T140T180T280T2…C1T0R10R20R30R40R50R60R70R80…T1T2T7…柱面索引主索引基本区磁道索引溢出区C0北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27150T1150T1200T2200T2…890T1890T11000T21000T2…R90R110R120R150R160R175R190R200R830R840R880R890R920R930R980R1000T1T2T7…T7T2…T1T0T0C2C9……基本区磁道索引溢出区基本区磁道索引溢出区…北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2810.3倒排索引„基本概念„10.3.1基于属性的倒排„10.3.2对正文文件的倒排北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29基本概念基于属性的检索„要求检索结构中某个或若干个属性满足一定条件的结点„不是按关键码的值检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30350040电器部何江0673250026玩具部周兵0552250026电器部刘珍0375500047玩具部孙丽0221350039服装部王卓0204500055食品部王亮0201300026服装部张伟0197400039服装部赵亮0193500043食品部刘阳0172400032玩具部李宇0100SALAGEDEPTNAMEEMP#例如，在某百货公司的职工文件中，有如下的记录格式：(EMP#，NAME，DEPT，AGE，SAL)该记录格式中的数据项其含义分别为职工号，姓名，所在部门，年龄，工资。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3110.3.1基于属性的倒排„对某属性按属性值建立索引表，称倒排表„(attr,ptrList)„（属性值，具有该属性值的各记录指针）„记录指针可以是关键码，或该记录的主文件地址„颠覆主文件的顺序，因而称为倒排索引„属性往往是离散型的„对于连续型的索引，往往用B树„倒排文件：带有倒排索引的文件北京大学信息学院张铭编写©版权所有，转载或翻印必究Page320375,055201970204,06730100,01930172,0201,022125003000350040005000EMP#SALlist0197,0375,055201000193,0204067301720221020126323940434755EMP#AGElist0100,0221,05520172,02010193,0197,02040375,0673玩具部食品部服装部电器部EMP#DEPTlist北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33检索实例列出玩具部中年龄在50岁以上或者工资在5000元以上的职工记录(DEPT=“Toy”AND(AGE≥50ORSAL≥5000))。分别找出满足条件DEPT=“Toy”，AGE≥50，和SAL≥5000的指针集合，然后对后两个指针集合求并，并且将结果集合与第一个指针集合求交，昀后的结果集合中包含的指针所指的各记录即为所求。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34„优点：能够对于基于属性的检索进行较高效率的处理„缺点：„花费了保存倒排表的存储代价„降低了更新运算的效率北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3510.3.2对正文文件的倒排„正文索引(TextIndexing)处理的就是“建立一个数据结构以提供对文本内容的快速检索”。„方法„词索引(wordindex)„全文索引(full-textindex)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page36词索引„基本思想：„把正文看作由符号和词所组成的集合，从正文中抽取出关键词，然后用这些关键词组成一些适合快速检索的数据结构。„适用于多种文本类型，特别是那些可以很容易就解析成一组词的集合的文本„适用于英文„中文等东方文字要经过“切词”处理北京大学信息学院张铭编写©版权所有，转载或翻印必究Page37全文索引„基本思想：„把正文看作一个长的字符串„在数据结构中记录的是子字符串的开始位置„查询就可以针对正文中的任何子字符串„可以对每一个字符建立索引，从而使查询词不再限于关键词„需要更大的空间北京大学信息学院张铭编写©版权所有，转载或翻印必究Page38词索引使用昀广泛„一个已经排过序的关键词的列表„其中每个关键词指向一个倒排表（postinglist）„指向该关键词出现文档集合„在文档中的位置北京大学信息学院张铭编写©版权所有，转载或翻印必究Page39倒排索引12345678910111213编号词语（文档编号，位置）colddayshotinlikenineoldpeaseporridgeitpotsomethe(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)(3,2)(2,2)(2,3)(2,4)(2,5)(3,1)(4,6)(3,3)(4,1)(4,2)(4,3)(4,4)(4,5)(4,7)(4,8)(5,1)(5,2)(5,3)(5,4)(5,5)(5,6)(6,1)(6,2)(6,3)北京大学信息学院张铭编写©版权所有，转载或翻