资源描述
第十章第十章 索引技术索引技术 任课教员：张任课教员：张 铭铭北京大学北京大学主要内容主要内容n10.1 线性索引线性索引n10.2 静态索引静态索引n10.3 倒排索引倒排索引n10.4 动态索引动态索引n10.5 动态、静态索引性能比较动态、静态索引性能比较北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 2基本概念基本概念n输入顺序文件输入顺序文件n主码与辅码主码与辅码n索引与索引文件索引与索引文件n稠密索引与稀疏索引稠密索引与稀疏索引北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 3输入顺序文件输入顺序文件n输入顺序文件输入顺序文件(entry-sequenced file)按照按照记录进入系统的顺序存储记录记录进入系统的顺序存储记录n输入顺序文件的结构相当于一个磁盘中未排输入顺序文件的结构相当于一个磁盘中未排序的线性表序的线性表n因此不支持高效率的检索因此不支持高效率的检索北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 4主码主码n主码主码(primary key)是数据库中的每是数据库中的每条记录的唯一标识条记录的唯一标识n例如，公司职员信息的记录的主码可例如，公司职员信息的记录的主码可以是职员的身份证号码以是职员的身份证号码 n如果只有主码，不便于各种灵活检索如果只有主码，不便于各种灵活检索北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 5辅码辅码n辅码辅码(secondary key)是数据库中可以出是数据库中可以出现重复值的码现重复值的码n辅码索引把一个辅码值与具有这个辅码辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来值的每一条记录的主码值关联起来n大多数检索都是利用辅码索引来完成的大多数检索都是利用辅码索引来完成的北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 6索引索引n索引索引(indexing)是把一个关键码与它对应是把一个关键码与它对应的数据记录的位置相关联的过程的数据记录的位置相关联的过程 n索引技术是组织大型数据库的一种重要索引技术是组织大型数据库的一种重要技术技术n数据库组织存储在外存中的大量记录数据库组织存储在外存中的大量记录n高效率的检索高效率的检索n插入、更新、删除插入、更新、删除北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 7索引文件索引文件n索引文件索引文件(index file)是是用于记录这用于记录这种联系（关键码与它对应的数据记种联系（关键码与它对应的数据记录的位置）的文件组织结构。录的位置）的文件组织结构。n索引文件的记录索引文件的记录n（关键码，指针）对（关键码，指针）对n将每个关键码和一个指针关联将每个关键码和一个指针关联n指针指向主要数据库文件（也称为指针指向主要数据库文件（也称为“主文件主文件”）中的完整记录）中的完整记录北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 8索引文件索引文件n索引文件并不需要重新排列记录在索引文件并不需要重新排列记录在磁盘中的顺序（不用重排主文件）磁盘中的顺序（不用重排主文件）n一个数据库可能有多个相关的索引文一个数据库可能有多个相关的索引文件件n每个索引文件往往支持一个关键码字每个索引文件往往支持一个关键码字段段n可以通过该索引文件高效访问记录中可以通过该索引文件高效访问记录中该关键码值该关键码值北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 9稠密索引稠密索引n对每一个记录建立一个索引项，对每一个记录建立一个索引项，这样建立的索引被称为稠密索引这样建立的索引被称为稠密索引(dense index)n数据库文件中的记录不按照关键数据库文件中的记录不按照关键码的顺序排列时（比如按照加入码的顺序排列时（比如按照加入的顺序排列）的顺序排列）北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 10稀疏索引稀疏索引n对一组记录建立一个索引项，这种对一组记录建立一个索引项，这种索引称之为稀疏索引索引称之为稀疏索引(spare index)n当记录在磁盘中是按照关键码的顺序当记录在磁盘中是按照关键码的顺序存放存放n可以把记录分成多个组（块）可以把记录分成多个组（块）n稀疏索引索引项的指针指向的是这稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置一组记录在磁盘中的起始位置 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 1110.1 线性索引线性索引n基本概念基本概念n线性索引的优点线性索引的优点n线性索引的问题线性索引的问题n二级线性索引二级线性索引北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 12基本概念基本概念n线性索引线性索引(linear index)的索引文的索引文件件n一组简单的关键码一组简单的关键码(key)/指针指针(pointer)对的序列对的序列北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 13基本概念（续）基本概念（续）n线性索引文件按照关键码的顺序进行排序线性索引文件按照关键码的顺序进行排序n文件中的指针指向存储在磁盘上的文件记录起文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置始位置或者主索引中主码的起始位置北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 14基本概念（续）基本概念（续）n线性索引的索引文件线性索引的索引文件n存储在内存中，把索引存储在内存储在内存中，把索引存储在内存中能大大地提高检索速度存中能大大地提高检索速度n存储在磁盘中存储在磁盘中n根据线性索引的文件大小和内存根据线性索引的文件大小和内存的空间限制的空间限制北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 15线性索引的优点线性索引的优点n对变长的数据库记录的访问对变长的数据库记录的访问n可以对数据进行高效检索可以对数据进行高效检索n二分检索二分检索 n顺序处理顺序处理n比较操作比较操作n批处理的操作批处理的操作n节省空间节省空间(相对其它索引结构相对其它索引结构)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 16线性索引的问题线性索引的问题n线性索引太大，存储在磁盘中线性索引太大，存储在磁盘中n在一次检索过程中有可能多次访在一次检索过程中有可能多次访问磁盘，从而影响检索的效率问磁盘，从而影响检索的效率n解决办法：使用二级线性索引解决办法：使用二级线性索引n更新线性索引更新线性索引n在数据库中插入或者删除记录时在数据库中插入或者删除记录时北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 17二级线性索引二级线性索引n每一条二级线性索引记录对应于一每一条二级线性索引记录对应于一个一级线性索引文件的磁盘块个一级线性索引文件的磁盘块n关键码的值与对应的线性索引文件的关键码的值与对应的线性索引文件的磁盘块中第一条记录磁盘块中第一条记录(从物理位置上看从物理位置上看的第一条的第一条)的关键码的值相同的关键码的值相同n记录中的指针则指向相应线性索引文记录中的指针则指向相应线性索引文件的磁盘块的起始位置件的磁盘块的起始位置北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 18二级线性索引二级线性索引n例如，磁盘块的大小是例如，磁盘块的大小是1024字节，每个字节，每个关键码指针记录需要关键码指针记录需要8个字节，则每磁个字节，则每磁盘块可以存储盘块可以存储128条这样的记录条这样的记录n假设线性文件索引中包含假设线性文件索引中包含10000条记录，条记录，那么该线性索引占用那么该线性索引占用79个磁盘块，相应个磁盘块，相应的，二级线性索引文件中有的，二级线性索引文件中有79项记录项记录北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 19二级线性索引的例子二级线性索引的例子n关键码与相应磁盘块中第一条记录的关键码的关键码与相应磁盘块中第一条记录的关键码的值相同值相同n指针指向相应磁盘块的起始位置指针指向相应磁盘块的起始位置 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 20二级线性索引检索二级线性索引检索n在检索时，线性索引文件并不被读在检索时，线性索引文件并不被读入内存，被读入内存的是二级线性入内存，被读入内存的是二级线性索引文件索引文件 n由于二级索引往往存储内存，通常由于二级索引往往存储内存，通常只需要访问两次磁盘即可：一次读只需要访问两次磁盘即可：一次读入线性索引文件，一次读入数据库入线性索引文件，一次读入数据库记录记录北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 21二级线性索引检索的例子二级线性索引检索的例子例如，检索关键码为例如，检索关键码为2555的记录的记录n首先在内存中的二级线性索引文件中找到关键首先在内存中的二级线性索引文件中找到关键码的值小于等于码的值小于等于2555的最大关键码所在的记录的最大关键码所在的记录关键码为关键码为2003的记录的记录n根据记录中的指针找到其对应的线性索引文件根据记录中的指针找到其对应的线性索引文件的磁盘块，并把该块读入内存的磁盘块，并把该块读入内存n按照二分法对该块进行检索，找到所需要的记按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置录在磁盘上的位置n最后把所需记录读入，完成检索操作最后把所需记录读入，完成检索操作北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 2210.2 静态索引静态索引n10.2.1 多分树多分树n10.2.2 ISAM北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 23基本概念基本概念静态索引静态索引n索引结构在文件创建、初始装入记索引结构在文件创建、初始装入记录时生成录时生成n一旦生成就固定下来，在系统运行一旦生成就固定下来，在系统运行(例如插入和删除记录例如插入和删除记录)过程中索引结过程中索引结构并不改变构并不改变n只有当文件再组织时才允许改变索只有当文件再组织时才允许改变索引结构引结构 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 2410.2.1 多分树多分树n组织索引一般不用二叉树而采用多组织索引一般不用二叉树而采用多分树分树 n大大减少访问外存的次数大大减少访问外存的次数 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 25多分树图例多分树图例北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 26上图访问一个叶结点上图访问一个叶结点n查找二叉树查找二叉树访问访问六次六次外存外存 n查找多分树查找多分树访问访问两次两次外存外存 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 27n结点更大结点更大n以更少的外存访问次数来完成查找以更少的外存访问次数来完成查找 n需要较大的缓冲区需要较大的缓冲区n读入一个结点也需较多时间读入一个结点也需较多时间 n一个结点最好能放在一个磁盘块中一个结点最好能放在一个磁盘块中北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 28n“数据基本区数据基本区”n多分树的叶结点区域多分树的叶结点区域n存放数据记录存放数据记录n“索引区索引区”n多分树的非叶结点区域多分树的非叶结点区域n存放各子树结点中的最大存放各子树结点中的最大(或最小或最小)的关的关键码键码北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 29n溢出、溢出区溢出、溢出区n新记录要插入的结点已满新记录要插入的结点已满n把溢出的记录存放到另开辟的溢出区把溢出的记录存放到另开辟的溢出区n不改变索引的结构不改变索引的结构 n记录送入溢出区的两种方式记录送入溢出区的两种方式 n保持顺序，把最后一个记录送往溢出保持顺序，把最后一个记录送往溢出区区n不保持顺序，把新插入的记录送入溢不保持顺序，把新插入的记录送入溢出区出区 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 3010.2.2 ISAMnISAMISAM是解决需要频繁更新的大型是解决需要频繁更新的大型数据库的一个早期尝试数据库的一个早期尝试n在采用基于在采用基于B B+树的树的VSAMVSAM技术之前，技术之前，IBMIBM公司曾经广泛地采用公司曾经广泛地采用ISAMISAM技技术术 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 31n多分树的应用多分树的应用 n为磁盘存取而设计为磁盘存取而设计 n结构采用多级索引结构采用多级索引n主索引主索引n柱面索引柱面索引n磁道索引磁道索引 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 32北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 33北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 34ISAM的查找的查找n先查主索引，从主索引查出柱面索先查主索引，从主索引查出柱面索引的分布引的分布n主索引常驻内存主索引常驻内存n从柱面索引查出磁道索引的分布从柱面索引查出磁道索引的分布n柱面索引放在中间位置的柱面柱面索引放在中间位置的柱面 n从磁道索引查出所要找的记录的地从磁道索引查出所要找的记录的地址址 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 35ISAM的插入的插入n磁道索引中，索引项的两个子项在磁道索引中，索引项的两个子项在记录插入之前是相同的，在插入记记录插入之前是相同的，在插入记录后就要改变录后就要改变 n例如，插入例如，插入R165 以后：以后：北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 36n如果有多个溢出记录，则这些溢出如果有多个溢出记录，则这些溢出记录必须按顺序链接起来，在溢出记录必须按顺序链接起来，在溢出索引项中是这些溢出记录的最大关索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录键码和具有最小关键码的溢出记录所在磁道号所在磁道号 n例如，再插入例如，再插入R168，R166以后：以后：北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 37n如果有多个溢出记录，则这些溢出如果有多个溢出记录，则这些溢出记录必须按顺序链接起来，在溢出记录必须按顺序链接起来，在溢出索引项中是这些溢出记录的最大关索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录键码和具有最小关键码的溢出记录所在磁道号所在磁道号 n例如，再插入例如，再插入R168，R166以后：以后：北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 38n在溢出区中，除了存放记录以外还在溢出区中，除了存放记录以外还存放链指针存放链指针 n柱面索引变化：柱面索引变化：北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 39ISAM插入的好处插入的好处n在进一步查找时，容易判断要查找在进一步查找时，容易判断要查找的记录是在基本区还是在溢出区的记录是在基本区还是在溢出区n若在基本区，则指针指出了记录所在若在基本区，则指针指出了记录所在的磁道号；的磁道号；n若在溢出区，则指针指出了溢出记录若在溢出区，则指针指出了溢出记录链中第一个链中第一个(关键码为最小关键码为最小)记录所在记录所在的磁道号及在磁道中的相对记录号，的磁道号及在磁道中的相对记录号，沿着该链可以找到要找的记录。沿着该链可以找到要找的记录。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 4010.3 倒排索引倒排索引n10.3.1 基于属性的倒排基于属性的倒排n10.3.2 对正文文件的倒排对正文文件的倒排北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 41基本概念基本概念n不仅需要按关键码的值查找不仅需要按关键码的值查找n还需要按照属性的值来查找记录还需要按照属性的值来查找记录 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 42基本概念基本概念n倒排索引倒排索引对某属性按属性值建对某属性按属性值建立索引立索引n（属性值，具有该属性值的各记录的地址列（属性值，具有该属性值的各记录的地址列表）表）n不是由记录关键码来确定属性值，而是由属不是由记录关键码来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引性值来确定记录的位置，因而称为倒排索引(inverted index)n这种属性往往是离散型的这种属性往往是离散型的n对于连续型的索引，往往用对于连续型的索引，往往用B树树北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 43基本概念基本概念n倒排索引文件倒排索引文件n带有倒排索引的文件带有倒排索引的文件n简称倒排文件简称倒排文件(inverted file)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 4410.3.1 基于属性的检索基于属性的检索基于属性的检索基于属性的检索n要求检索结构中某个或若干个属要求检索结构中某个或若干个属性满足一定条件的结点性满足一定条件的结点北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 45例如，在某百货公司的职工文件中，有如下的记录格式：例如，在某百货公司的职工文件中，有如下的记录格式：(EMP#，NAME，DEPT，AGE，SAL)该记录格式中的数据项其含义分别为职工号，姓名，该记录格式中的数据项其含义分别为职工号，姓名，所在部门，年龄，工资。所在部门，年龄，工资。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 46查询实例查询实例对这样的职工文件进行下列类型的查询：对这样的职工文件进行下列类型的查询：（1）简单查询。例如：列出玩具部）简单查询。例如：列出玩具部(即即DEPT=“Toy”)的所有职工记录的所有职工记录（2）范围查询。例如：列出工资在）范围查询。例如：列出工资在40元和元和80元元之间之间(即即40SAL80)的所有职工记录的所有职工记录（3）逻辑查询。例如：列出玩具部中年龄在）逻辑查询。例如：列出玩具部中年龄在50岁以上或者工资在岁以上或者工资在100元以上的职工记录元以上的职工记录(DEPT=“Toy”AND(AGE50 OR SAL100)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 4710.3.1 倒排表倒排表n倒排表倒排表(inverted list)是基于属性是基于属性的倒排的倒排n在保留原表的同时，对于感兴趣的在保留原表的同时，对于感兴趣的（即可以用来作为检索参数的）每个（即可以用来作为检索参数的）每个属性的可能取值都建立一个称作倒排属性的可能取值都建立一个称作倒排表的线性表表的线性表n存放与此属性相对应的所有关键码值存放与此属性相对应的所有关键码值北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 4810.3.1 倒排文件倒排文件n索引项索引项n一个具体的索引值一个具体的索引值n一组指针（例如记录的主码）一组指针（例如记录的主码）n这些指针分别指向在该属性项上具有该具体值的这些指针分别指向在该属性项上具有该具体值的各个记录各个记录n一个倒排表一个倒排表n一个索引项一个索引项n倒排文件倒排文件n倒排表组成的索引文件倒排表组成的索引文件北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 49北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 5010.3.1 基于属性的倒排基于属性的倒排 列出玩具部列出玩具部(即即DEPT=“Toy”)的所的所有职工记录。有职工记录。从关于属性从关于属性DEPT的索引中，取出属的索引中，取出属性值为性值为“Toy”的倒排表，此倒排表的倒排表，此倒排表中包合的指针所指向的各记录即为中包合的指针所指向的各记录即为所求。所求。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 51列出工资在列出工资在40元和元和80元之间元之间(即即40SAL80)的所有职工记录。的所有职工记录。从关于属性从关于属性SAL的索引中，找出属性值的索引中，找出属性值在在40与与80之间的倒排表，每个倒排表中之间的倒排表，每个倒排表中含有一个指针集合。含有一个指针集合。对这些集合进行并的运算，其结果集合对这些集合进行并的运算，其结果集合中包含的指针所指的各记录即为所求。中包含的指针所指的各记录即为所求。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 52列出玩具部中年龄在列出玩具部中年龄在50岁以上或者工资在岁以上或者工资在100元以上的职工记录元以上的职工记录(DEPT=“Toy”AND(AGE50 OR SAL100)。先采用类似（先采用类似（1）、（）、（2）的方法，分别找出满）的方法，分别找出满足条件足条件DEPT=“Toy”，AGE50，和，和SAL100的指针集合，然后对后两个指针集的指针集合，然后对后两个指针集合求并，并且将结果集合与第一个指针集合求合求并，并且将结果集合与第一个指针集合求交，最后的结果集合中包含的指针所指的各记交，最后的结果集合中包含的指针所指的各记录即为所求。录即为所求。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 53n优点：能够对于基于属性的检索优点：能够对于基于属性的检索进行较高效率的处理进行较高效率的处理 n缺点：缺点：n花费了保存倒排表的存储代价花费了保存倒排表的存储代价n降低了更新运算的效率降低了更新运算的效率 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 5410.3.2 对正文文件的倒排对正文文件的倒排n正文索引正文索引(Text Indexing)处理处理的就是的就是“建立一个数据结构以提建立一个数据结构以提供对文本内容的快速检索供对文本内容的快速检索”。n方法方法n词索引词索引(word index)n全文索引全文索引(full-text index)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 55词索引词索引n基本思想：基本思想：n把正文看作由符号和词所组成的集合，从正把正文看作由符号和词所组成的集合，从正文中抽取出关键词，然后用这些关键词组成文中抽取出关键词，然后用这些关键词组成一些适合快速检索的数据结构。一些适合快速检索的数据结构。n适用于多种文本类型，特别是那些可以适用于多种文本类型，特别是那些可以很容易就解析成一组词的集合的文本很容易就解析成一组词的集合的文本 n适用于英文适用于英文n不适用于中文等东方文字不适用于中文等东方文字 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 56全文索引全文索引n基本思想：基本思想：n把正文看作一个长的字符串把正文看作一个长的字符串n在数据结构中记录的是子字符串的开始位置在数据结构中记录的是子字符串的开始位置n查询就可以针对正文中的任何子字符串查询就可以针对正文中的任何子字符串n可以对每一个字符建立索引，从而使查可以对每一个字符建立索引，从而使查询词不再限于关键词询词不再限于关键词 n需要更大的空间需要更大的空间 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 57词索引使用最广泛词索引使用最广泛n一个已经排过序的关键词的列表一个已经排过序的关键词的列表n其中每个关键词指向一个倒排表其中每个关键词指向一个倒排表（posting list）n指向该关键词出现文档集合指向该关键词出现文档集合n在文档中的位置在文档中的位置 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 58倒排文件的全文本索引倒排文件的全文本索引 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 59简化的正文倒排文件简化的正文倒排文件 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 60建立正文倒排文件建立正文倒排文件n第一步，对文档集中的所有文件第一步，对文档集中的所有文件都进行分割处理，把正文分成多都进行分割处理，把正文分成多条记录文档。条记录文档。n切分正文记录取决于程序的需要切分正文记录取决于程序的需要n定长的块、段落、章节，甚至一组定长的块、段落、章节，甚至一组文档文档 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 61n第二步，给每条记录赋一组关键第二步，给每条记录赋一组关键词。词。n以人工或者自动的方式从记录中以人工或者自动的方式从记录中抽取关键词抽取关键词n停用词停用词(Stopword)n抽词干抽词干(Stemming)n切词（切词（segmentation）北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 62n第三步，建立正文倒排表、倒排文第三步，建立正文倒排表、倒排文件件n得到各个关键词的集合得到各个关键词的集合n对于每一个关键词得到其倒排表对于每一个关键词得到其倒排表n然后把所有的倒排表存入文件然后把所有的倒排表存入文件n记录在每个倒排表在索引文件中开始的位记录在每个倒排表在索引文件中开始的位置以及每个表的大小（也可以记录每个关置以及每个表的大小（也可以记录每个关键词的出现次数）键词的出现次数）北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 63对关键词的检索对关键词的检索 n第一步，在倒排文件中检索关键词。第一步，在倒排文件中检索关键词。n第二步，如果找到了关键词，那么获取第二步，如果找到了关键词，那么获取文件中的对应的倒排表，并获取倒排表文件中的对应的倒排表，并获取倒排表中的记录。中的记录。n通常使用另一个索引结构（字典）进一步对通常使用另一个索引结构（字典）进一步对关键词表进行有序索引关键词表进行有序索引nTrien散列散列北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 64倒排文件优劣倒排文件优劣n高效检索，用于文本数据库系统高效检索，用于文本数据库系统n支持的检索类型有限支持的检索类型有限 n检索词有限检索词有限n只能用索引文件中的关键词只能用索引文件中的关键词n倒排文件中的索引效率可能不高倒排文件中的索引效率可能不高 n需要的空间代价往往很高需要的空间代价往往很高 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 6510.4 动态索引动态索引n10.4.1 B树树n10.4.2 B+树树n10.4.3 VSAMn10.4.4 B树的性能分析树的性能分析北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 66基本概念基本概念n动态索引结构动态索引结构n索引结构本身也可能发生改变索引结构本身也可能发生改变n在系统运行过程中插入或删除记录时在系统运行过程中插入或删除记录时n目的目的n保持较好的性能保持较好的性能n例如较高的检索效率例如较高的检索效率北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 6710.4.1 B树树nB树树(Balanced Tree)n一种平衡的多分树一种平衡的多分树 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 68B树的结构定义树的结构定义定定义：一个一个m阶的的B树满足下列条件：足下列条件：n(1)每个每个结点至多有点至多有m个子个子结点；点；n(2)除根除根结点和叶点和叶结点外，其它每个点外，其它每个结点至少有点至少有 个子个子结点；点；n(3)根根结点至少有两个子点至少有两个子结点点n唯一例外的是根唯一例外的是根结点就是叶点就是叶结点点时没有子没有子结点点n此此时B树只包含一个只包含一个结点点n(4)所有的叶所有的叶结点在同一点在同一层；n(5)有有k个子结点的非根结点恰好包含个子结点的非根结点恰好包含k-1个关键码。个关键码。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 69北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 70B树的结点结构树的结点结构B树的的一一个个包包含含j个个关关键码，j+1个个指指针的的结点点的的一般形式一般形式为：n其中其中Ki是关键码值，是关键码值，K1K2Kj，nPi是指向包括是指向包括Ki到到Ki+1之间的关键码的子树的之间的关键码的子树的指针。指针。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 71B树结点抽象数据类型树结点抽象数据类型templateclassBNodeintn;/子结点的个数子结点的个数/指向父结点的指针指向父结点的指针BNode*parent;/存储关键码的数组，最多有存储关键码的数组，最多有MAXREC个关键码个关键码KeykeyMAXREC;/指向子节点的指针，最多有指向子节点的指针，最多有MAXREC+1个指针个指针BNode*ptrMAXREC+1;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 72template/用于在用于在B树中检索关键码的数据结构树中检索关键码的数据结构structTriple/指向关键码所在结点的指针指向关键码所在结点的指针BNode*r;/记录关键码在结点中的位置记录关键码在结点中的位置inti;/标识是否检索到了关键码标识是否检索到了关键码chartag;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 73B树抽象数据类型树抽象数据类型(续续)templateclassBTreeBNode*root;intm;/B树的阶树的阶BTree();/构造函数构造函数/检索关键码为检索关键码为x的结点，的结点，/检索信息记录在结构检索信息记录在结构 Triple中中Triple&Search(constKey&x);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 74/插入关键码插入关键码xintInsert(constKey&x);/删除关键码删除关键码xintRemove(constKey&x);private:/在结点在结点A中插入关键码中插入关键码x和指针和指针pint insertkey(BNode*A,int pos,Key k,BNode*p);/转移结点转移结点A中的部分关键码到结点中的部分关键码到结点B中中intmove(BNode*A,BNode*B,intb,inte);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 75/调整结点的右兄弟和父节点调整结点的右兄弟和父节点void LeftAdjust(BNode*p,BNode*q,constintd,constintj);/调整结点的左兄弟和父节点调整结点的左兄弟和父节点voidRightAdjust(BNode*p,BNode*q,constintd,constintj);/压缩结点压缩结点voidcompress(BNode*p,constintj);/合并节点合并节点voidmerge(BNode*p,BNode*q,BNode*p1,intj);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 76B树的查找树的查找n把根结点读出来，在根结点所包含的关键码把根结点读出来，在根结点所包含的关键码K1，Kj中查找给定的关键码值中查找给定的关键码值(当结点包含的当结点包含的关键码不多时，就用顺序检索；当结点包含的关键码不多时，就用顺序检索；当结点包含的关键码数目较多时，可以用二分检索关键码数目较多时，可以用二分检索)，n找到则检索成功；找到则检索成功；n否则，确定要查的关键码值是在某个否则，确定要查的关键码值是在某个Ki和和Ki+1之间，于是取之间，于是取pi所指向的结点继续查找。所指向的结点继续查找。n如果如果pi指向外部结点，表示检索失败。指向外部结点，表示检索失败。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 77B树的插入树的插入n叶结点处在第叶结点处在第I层的层的B树，插入的关树，插入的关键码总是在第键码总是在第I-1层层插入插入14北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 78n外部结点处在第外部结点处在第I层的层的B树，插入的树，插入的关键码总是在第关键码总是在第I-1层层插入插入14北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 79n插入可能导致插入可能导致B树朝着根的方向树朝着根的方向生长生长 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 80插入插入55,使得包含值使得包含值50和和52的页的页分裂，把值分裂，把值52提升到父结点提升到父结点 阶阶m=3北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 81插入插入55结果结果北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 82插入引起插入引起3阶阶B树根结点分裂的例子树根结点分裂的例子插入插入19北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 83插入引起插入引起3阶阶B树根结点分裂的例子树根结点分裂的例子插入插入19北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 84插入插入19北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 85插入插入19北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 86B树的删除树的删除n删除的关键码不在叶结点层删除的关键码不在叶结点层n先把此关键码与它在先把此关键码与它在B树里的后继树里的后继对换位置，然后再删除该关键码对换位置，然后再删除该关键码 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 87B树的删除树的删除(续续)n删除的关键码在叶结点层删除的关键码在叶结点层n删除后关键码个数不小于删除后关键码个数不小于n直接删除直接删除n关键码个数小于关键码个数小于n如果兄弟结点关键码个数不等于如果兄弟结点关键码个数不等于n从兄弟结点移若干个关键码到该结点中来从兄弟结点移若干个关键码到该结点中来(父结点父结点中的一个关键码要做相应变化中的一个关键码要做相应变化)n如果兄弟结点关键码个数等于如果兄弟结点关键码个数等于n合并合并北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 88阶阶m=4删除删除045北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 89关键码个数不足关键码个数不足从兄弟结点移动从兄弟结点移动135北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 90注意：兄注意：兄弟结点中弟结点中的的135被被移动到父移动到父结点中，结点中，被移动到被移动到结点中的结点中的是父结点是父结点中的中的112北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 91删除删除112北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 92关键码个数不足关键码个数不足兄弟结点关键兄弟结点关键码个数也不足码个数也不足兄弟结点关兄弟结点关键码个数也键码个数也不足不足北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 93合并合并北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 94北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 9510.4.2 B+树树n是是B树的一种变形树的一种变形n在叶结点上存储信息的树在叶结点上存储信息的树n所有的关键码均出现在叶结点上所有的关键码均出现在叶结点上 n各层结点中的关键码均是下一层各层结点中的关键码均是下一层相应结点中最大关键码（或最小相应结点中最大关键码（或最小关键码）的复写关键码）的复写 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 96B+树的结构定义树的结构定义m m阶阶B B+树的结构定义如下：树的结构定义如下：n(1)(1)每个结点至多有每个结点至多有m m个子结点；个子结点；n(2)(2)每个结点每个结点(除根外除根外)至少有至少有 个子结点；个子结点；n(3)(3)根结点至少有两个子结点；根结点至少有两个子结点；n(4)(4)有有k k个个子子结结点点的的结结点点必必有有k k个个关关键键码。码。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 972阶阶B+树的例子树的例子北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 98B+树的抽象数据类型树的抽象数据类型template class PAIR/用于用于存储关键码和指向磁盘块的指针的数据结构存储关键码和指向磁盘块的指针的数据结构public:void*ptr;/对于叶结对于叶结点是指向磁盘块的指针点是指向磁盘块的指针/而对非叶节点是指向子结点的指针而对非叶节点是指向子结点的指针Key key;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 99template class BPNode/定义定义B+树结树结点点public:/存储关键码的数组存储关键码的数组PAIR recsMAXRECS;int n;/子结点的个数子结点的个数/指向结点左兄弟的指针指向结点左兄弟的指针BPNode*leftptr;/指向结点左兄弟的指针指向结点左兄弟的指针BPNode*rightptr;/表示结点是否是叶结点表示结点是否是叶结点bool isLeaf;BPNode();/构造函数构造函数bool isFull();/结点是否已满结点是否已满;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 100/BPTree classtemplate class BPTree/定义定义B树树public:BPNode*root;/根结点根结点BPTree();/构造函数构造函数BPTree();/析构函数析构函数/检索关键码检索关键码Kbool Search(Key K,Elem*&e)/插入关键码插入关键码Kbool insert(Key K,Elem*&e)/删除关键码删除关键码Kbool remove(Key K,Elem*&e)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 101B+树的查找树的查找n查找应该到叶结点层查找应该到叶结点层n在上层已找到待查的关键码，并不停止在上层已找到待查的关键码，并不停止n而是继续沿指针向下一直查到叶结点层的这而是继续沿指针向下一直查到叶结点层的这个关键码个关键码nB+树的叶结点一般链接起来，形成一个树的叶结点一般链接起来，形成一个双链表双链表 n适合顺序检索（范围检索）适合顺序检索（范围检索）n实际应用更广实际应用更广北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 102B+树的插入树的插入n插入插入分裂分裂n过程和过程和B树类似树类似n注意保证上一层结点中有这两个注意保证上一层结点中有这两个结点的最大关键码（最小关键码）结点的最大关键码（最小关键码）北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 103阶阶m=3m=3插入插入1515北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 104插入插入1515后后北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 105插入插入1616结点满，需要分裂结点满，需要分裂北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 106插入插入1717北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 107插入插入1919北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 108结点满，需要分裂结点满，需要分裂北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 109结点满，需要分裂结点满，需要分裂北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 110树增加一层树增加一层北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 111B+树的删除树的删除n当关键码不满时，与左右兄弟进行当关键码不满时，与左右兄弟进行调整、合并的处理和调整、合并的处理和B B树类似树类似n关键码在叶结点层删除后，其在上关键码在叶结点层删除后，其在上层的复本层的复本可以保留，可以保留，做为一个做为一个“分分界关键码界关键码”存在存在n也可以替换为新的最大关键码（或也可以替换为新的最大关键码（或最小关键码）最小关键码）北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 11223被删除被删除但上层结点但上层结点中的副本保中的副本保留留阶阶m=3 删除删除23北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 11310.4.3 VSAMnVSAM(Virtual Storage Access Method)虚拟存储存取方法虚拟存储存取方法nB+树的应用树的应用n一种索引顺序文件的组织方式一种索引顺序文件的组织方式n与存储设备无关与存储设备无关，存储单位是，存储单位是“逻辑逻辑”的的北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 114北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 115VSAM的组成的组成n索引集索引集n顺序集（顺序集索引）顺序集（顺序集索引）n和索引集共同形成了和索引集共同形成了B+树结构的文件树结构的文件索引索引n数据集数据集n存放文件记录存放文件记录n记录可以是变长的记录可以是变长的北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 116控制区间控制区间n控制区间控制区间(Control Interval)n在数据集中在数据集中nI/O中数据传输的基本单位中数据传输的基本单位 n内部结构如下图内部结构如下图北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 117顺序集的组成顺序集的组成n控制区间的索引项控制区间的索引项n在顺序集中在顺序集中n内容为该控制区间中的最高关键码和内容为该控制区间中的最高关键码和指向该控制区间的指针指向该控制区间的指针 n若干若干“相邻相邻”的索引项构成顺序集一的索引项构成顺序集一个结点个结点叶结点叶结点n控制域控制域(control area)n顺序集的一个结点连同它们对应的全顺序集的一个结点连同它们对应的全部数据集结点部数据集结点 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 118文件初建时的控制与结构文件初建时的控制与结构北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 119控制域的结构和存放方式控制域的结构和存放方式n顺序集结点可以在一个磁道上重复地存顺序集结点可以在一个磁道上重复地存放，以便减少读索引的等待时间放，以便减少读索引的等待时间 n修改时也要改多个复本修改时也要改多个复本北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 120索引集的组成索引集的组成n顺序集结点的索引项顺序集结点的索引项n在索引集中在索引集中n内容为该顺序集结点所在控制域内容为该顺序集结点所在控制域中的最高关键码和指向该顺序集中的最高关键码和指向该顺序集结点的指针结点的指针n相当于非叶结点相当于非叶结点 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 121VSAM的插入的插入n调用调用B+树的查找算法，找到该记录树的查找算法，找到该记录关键码应插入的顺序集结点关键码应插入的顺序集结点 n找到该记录要插入的控制区间及其找到该记录要插入的控制区间及其相应的位置相应的位置n有自由空间有自由空间n无自由空间无自由空间n控制区间所在控制域有空闲控制区间所在控制域有空闲n控制区间所在控制域无空闲控制区间所在控制域无空闲北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 122插入的例子：初始形式插入的例子：初始形式北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究 Page 123插入插入ARK，BED和和BEG后的形式后的形式 n该控制区间中的自由空间足以容该控制区间中
展开阅读全文