您好,欢迎访问三七文档
当前位置:首页 > 高等教育 > 理学 > 北大数据结构与算法课件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.2ISAMISAM是解决需要频繁更新的大型数据库的一个早期尝试在采用基于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)北京大学信息学院张铭编写©版权所有,转载或翻
本文标题:北大数据结构与算法课件10A索引技术
链接地址:https://www.777doc.com/doc-10661730 .html