北京大学：《数据结构与算法》课程教学资源（实验班讲义）第十章 索引技术

主要内容 数据结构与算法 基本概念 第十章索引技术 Q101线性索引 任课教员:张铭 Q102静态索引 http:/db.pku.edu.cn/mzhang/ds mzhang@db.pku.edu.cn 103倒排索引 北京大学信息科学与技术学院 令104动态索引 网络与信息系统研究所 ⊙版权所有,转载或翻印必究 105动态、静态索引性能比较 北大驰鑫 张帖写 基本概念 输入顺序文件 输入顺序文件 输入顺序文件( entry- sequenced file) 令主码与辅码 按照记录进入系统的顺序存储记录 令索引与索引文件 般说来,输入顺序文件的结构相当 一个磁盘中未排序的线性表 ◇密索引与稀疏索引 因此不支持高效率的检索 京大息 张帖写 权新有,轨敢向究 北大恤 张帖写 主码 辅码 ■主码( primary key)是数据库中的每 辅码( secondary key)是数据库中可以出 条记录的唯一标识 现重复值的码 ■例如,公司职员信息的记录的主码可 ■辅码索引把一个辅码值与具有这个辅码 以是职员的身份证号码 值的每一条记录的主码值关联起来 如果只有主码,不便于各种灵活检索 大多数检索都是利用辅码索引来完成的 张帖情 权新有:轨即癣究

1 数据结构与算法 第十章 索引技术 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 基本概念 „ 10.1 线性索引 „ 10.2 静态索引 „ 10.3 倒排索引 „ 10.4 动态索引 „ 10.5 动态、静态索引性能比较 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 基本概念 „ 输入顺序文件 „ 主码与辅码 „ 索引与索引文件 „ 稠密索引与稀疏索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 输入顺序文件 „ 输入顺序文件( entry-sequenced file ) 按照记录进入系统的顺序存储记录 „ 一般说来，输入顺序文件的结构相当 于一个磁盘中未排序的线性表 „ 因此不支持高效率的检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 主码 „ 主码( primary key )是数据库中的每 条记录的唯一标识 „ 例如，公司职员信息的记录的主码可 以是职员的身份证号码 „ 如果只有主码，不便于各种灵活检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 辅码 „ 辅码( secondary key )是数据库中可以出 现重复值的码 „ 辅码索引把一个辅码值与具有这个辅码 值的每一条记录的主码值关联起来 „ 大多数检索都是利用辅码索引来完成的

索引 索引文件 褰的位相类 码与它对应的数 个主文件可能有多个相关索引 文件 魏對腐主要数都库文件〔也称为主文件?)中的 每个索引文件往往支持一个关键 赛组爽菇和m)是用于记录这种联系的文 码字段 ■索引技术是组织大型数据库的一种重要技术 不需要重新排列重排主文件 高效率的检索 插入、更新、删除 可以通过该索引文件高效访问记 录中该关键码值 k 大学息 孔陪写 点权新有,郭究 北大驰鑫 张帖写 稠密索引vs稀疏索引 101线性索引 稠密索引:对每个记录建立一个索引项 基本概念 主文件不按照关键码的顺序排列 ■稀疏索引:对一组记录建立一个索引 个线性索引的优点 记录按照关键码的顺序存放 可以把记录分成多个组(块) 个线性索引的问题 紫引指针指向的这一组记录在磁盘中的起始位置 Q二级线性索引 京大息 张帖写 权新有,轨敢向究 孔写 线性索引文件 线性索引的优点 ■按照关键码的顺序进行排序 对变长的数据库记录的访问 文件中的指针指向存储在磁盘上的文件记录起 始位置或者主索引中主码的起始位置 可以对数据进行高效检索 ■二分检索 线性素引文件 顺序处理 比较操作 批处理的操作 数据库记录 ■节省空间(相对其它索引结构) 北京大息学 张铭 新,收即究 张帖写

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 索引 „ 索引( indexing )是把一个关键码与它对应的数 据记录的位置相关联的过程 „ (关键码，指针)对，即(key, pointer) „ 指针指向主要数据库文件（也称为“主文件”）中的 完整记录 „ 索引文件( index file )是用于记录这种联系的文 件组织结构 „ 索引技术是组织大型数据库的一种重要技术 „ 高效率的检索 „ 插入、更新、删除 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 索引文件 „ 一个主文件可能有多个相关索引 文件 „ 每个索引文件往往支持一个关键 码字段 „ 不需要重新排列重排主文件 „ 可以通过该索引文件高效访问记 录中该关键码值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 稠密索引 vs 稀疏索引 „ 稠密索引：对每个记录建立一个索引项 „ 主文件不按照关键码的顺序排列 „ 稀疏索引：对一组记录建立一个索引 „ 记录按照关键码的顺序存放 „ 可以把记录分成多个组（块） „ 索引指针指向的这一组记录在磁盘中的起始位置 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 10.1 线性索引 „ 基本概念 „ 线性索引的优点 „ 线性索引的问题 „ 二级线性索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 线性索引文件 „ 按照关键码的顺序进行排序 „ 文件中的指针指向存储在磁盘上的文件记录起 始位置或者主索引中主码的起始位置 37 55 73 92 92 73 37 55 线性索引文件 数据库记录 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 线性索引的优点 „ 对变长的数据库记录的访问 „ 可以对数据进行高效检索 „ 二分检索 „ 顺序处理 „ 比较操作 „ 批处理的操作 „ 节省空间 (相对其它索引结构)

线性索引的问题 二级线性索引 线性索引太大,存储在磁盘中 例如,磁盘块的大小是1024字节,每对 (关键码,指 需要8个字节 在一次检索过程中可能多次访问 1024/8=128 磁盘,从而影响检索的效率 每磁盘块可以存储128条这样的索引对 使用二级线性索引 假设数据文件包含10000条记录 稠密一级线性索引中包含10000条记录 更新线性索引 10000/128=78.1 那么一级绒性索引占用79个微盘块 在数据库中插入或者删除记录时 相应地,二级线性索引文件中有项索引对 这个二级线性索引文件可以在一个磁盘块 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 例如:检索关健码为2555的记录 关键字2555的记录指针 级线性索引的例子 级索弓 10723 关键码与相应磁盘块中第一条记录的关键码的 200220035583574492971072313293 值相同 ■指针指向相应磁盘块的起始位置 级索引□1mkH 键码为2555的记录 1.二量线性索引文件碳入内存 所在一最囊引磁煮块地址一 级索引 3中的地址指针找到其对应的一版敢性引文件的微盘 微块 4.挽属二分抽对该换遊行检囊,找到所需的记录在敬盘上的位置 LF最后把所雷记读入完成检囊燥作 张铭帖编写 102静态索引 1021基本概念 令基本概念 静态索引 令1021多分树 案时馥在文件创建、初始入记 令10.22sAM 例辅哭删高;種到结 构并不改变 导有蒋文件再组织时才允许改变索 北京大息学 张铭 权质有,印究 张帖写 权新有:命些

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 线性索引的问题 „ 线性索引太大，存储在磁盘中 „ 在一次检索过程中可能多次访问 磁盘，从而影响检索的效率 „ 使用二级线性索引 „ 更新线性索引 „ 在数据库中插入或者删除记录时 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 二级线性索引 „ 例如，磁盘块的大小是1024字节，每对 (关键码，指针)索引对需要8个字节 „ 1024 / 8 = 128 „ 每磁盘块可以存储128条这样的索引对 „ 假设数据文件包含10000条记录 „ 稠密一级线性索引中包含10000条记录 „ 10000/128 = 78.1 „ 那么一级线性索引占用79个磁盘块 „ 相应地，二级线性索引文件中有79项索引对 „ 这个二级线性索引文件可以在一个磁盘块 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 二级线性索引的例子 „ 关键码与相应磁盘块中第一条记录的关键码的 值相同 „ 指针指向相应磁盘块的起始位置 1 2003 5744 10723 1…… 2002 2003 5583 5744 9297 10723 13293 …… …… 磁盘块 一级索引 二级索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 例如：检索关键码为2555的记录 1. 二级线性索引文件读入内存 2. 二分法找关键码的值小于等于2555的最大关键码所在一级索引磁盘块地址—— 关键码为2003的记录 3.根据记录2003中的地址指针找到其对应的一级线性索引文件的磁盘 块，并把该块读入内存 4. 按照二分法对该块进行检索，找到所需要的记录在磁盘上的位置 5. 最后把所需记录读入，完成检索操作 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 10.2 静态索引 „ 基本概念 „ 10.2.1 多分树 „ 10.2.2 ISAM 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 10.2.1 基本概念 静态索引 „ 索引结构在文件创建、初始装入记 录时生成 „ 一旦生成就固定下来，在系统运行 (例如插入和删除记录)过程中索引结 构并不改变 „ 只有当文件再组织时才允许改变索 引结构

数据12.6364的二分索引 1022多分树 6次访问紫引块 查找63 1次访问外存数据块 组织索引一般不用二叉树而采用多 分树 大大减少访问外存的次数 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 叉树转换成多分树 2次访问索引块 1次访问外存数据块 “数据基本区” 多分树的叶结点区域 存放数据记录 索引区 多分树的非叶结点区域 存放各子树结点中的最大(或最小的关 张铭帖编写 叔所有,轨圆即 孔写 10.22 ISAM 溢出、溢出区 新记录要插入的结点已满 ISAM是解决需要频繁更新的大型 把溢出的记录存放到另开辟的溢出区 数据库的一个早期尝试 不改变索引的结构 在采用基于B树的WAM技术之 ■记录送入溢出区的两种方式 前,IBM公司曾经广泛地采用 保持顺序,把最后一个记录送往溢出区 ISAM技术 ■不保持顺序,把新插入的记录送入溢出 北京大息学 张铭 政■印究 张帖写 权新有:命些

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 10.2.2 多分树 „ 组织索引一般不用二叉树而采用多 分树 „ 大大减少访问外存的次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 1 1 33 1 49 1 57 1 123 45 67 8 9………. 二叉树 数据1,2…63,64的二分索引 查找63 61 64 6次访问索引块 63 1次访问外存数据块 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 二叉树转换成多分树 63 2次访问索引块 1次访问外存数据块 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 „ “数据基本区” „ 多分树的叶结点区域 „ 存放数据记录 „ “索引区” „ 多分树的非叶结点区域 „ 存放各子树结点中的最大(或最小)的关 键码 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 „ 溢出、溢出区 „ 新记录要插入的结点已满 „ 把溢出的记录存放到另开辟的溢出区 „ 不改变索引的结构 „ 记录送入溢出区的两种方式 „ 保持顺序，把最后一个记录送往溢出区 „ 不保持顺序，把新插入的记录送入溢出 区 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 10.2.2 ISAM „ ISAM是解决需要频繁更新的大型 数据库的一个早期尝试 „ 在采用基于B+树的VSAM技术之 前，IBM公司曾经广泛地采用 ISAM技术

C 多分树的应用 引 为磁盘存取而设计 结构采用多级索引 主索引 团 h OT oT2oT2 柱面索引 磁道索引 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 103倒排索引 令基本概念 1031基于属性的倒排 个1032对正文文件的倒排 00T2 道索 张铭帖编写 叔所有,轨圆即 孔写 玺公牌件中套如5的 基本概念 都挎式牢龄垩蛋其含义分别为职工号,名 基于属性的检索 0100李字玩具部32400 食品部 ■要求检索结构中某个或若干个属 赵亮服装部3940 性满足一定条件的结点 97张伟 服装部 3000 不是按关键码的值检索 服装部 孙丽 民部47 刘珍电器部262500 3500 北京大息学 张铭 权质有,印究 大 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 „ 多分树的应用 „ 为磁盘存取而设计 „ 结构采用多级索引 „ 主索引 „ 柱面索引 „ 磁道索引 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 400 T1 625 T2 1000 T3 80 C1T0 200 C2T0 400 C3T0 625 C6T0 1000 C9T0 T0 T1 T2 T3 … 40 T1 40T1 80 T2 80 T2 … C1 T0 R10 R20 R30 R40 R50 R60 R70 R80 … T1 T2 T7 … 柱面索引 主索引 基本区 磁道索引 溢出区 C0 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 150 T1 150 T1 200 T2 200 T2 … 890 T1 890 T1 1000 T2 1000 T2 … R90 R110 R120 R150 R160 R175 R190 R200 R830 R840 R880 R890 R920 R930 R980 R1000 T1 T2 T7 … T7 T2 … T1 T0 T0 C2 C9 … … 基本区 磁道索引 溢出区 基本区 磁道索引 溢出区 … 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 10.3 倒排索引 „ 基本概念 „ 10.3.1 基于属性的倒排 „ 10.3.2 对正文文件的倒排 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 基本概念 基于属性的检索 „ 要求检索结构中某个或若干个属 性满足一定条件的结点 „ 不是按关键码的值检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 0673 何江 电器部 40 3500 0552 周兵 玩具部 26 2500 0375 刘珍 电器部 26 2500 0221 孙丽 玩具部 47 5000 0204 王卓 服装部 39 3500 0201 王亮 食品部 55 5000 0197 张伟 服装部 26 3000 0193 赵亮 服装部 39 4000 0172 刘阳 食品部 43 5000 0100 李宇 玩具部 32 4000 EMP# NAME DEPT AGE SAL 例如，在某百货公司的职工文件中，有如下的记录格 式：(EMP#，NAME，DEPT，AGE，SAL) 该记录格式中的数据项其含义分别为职工号，姓名， 所在部门，年龄，工资

1031基于属性的倒 0I97.0204 ■对某属性按属性值建立索引表,称倒排 0375,0552 (attr, ptrList) 020A4 记录指骨可以是类健码,或该记录的主文件地址 颠摄主文件的顺序,因而称为倒排索引 ■属性往往是高散型的 0375.0552 对于连续型的索引,往往用B树 倒排文件:带有倒排索引的文件 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 检索实例 玩具部中年齡在50岁以上或者工资在 ■优点:能够对于基于属性的检索 GE≥50oR ≥500 进行较高效率的处理 分型找 缺点: 对后两个丰 花费了保存倒排表的存储代价 降低了更新运算的效率 张铭帖编写 孔写 1032对正文文件的倒排 词索引 正文索引〔 Text Indexing处理 ■基本思想: 的就是“建立一个数据结构以提 把正文看作由符号和词所组成的集合,从正 后 供对文本内容的快速检索”。 些适合快速检索的数据结构。 方法 适用于多种文本类型,特别是那些可以 很容易就解析成一组词的集合的文本 词索引( word index) 适用于英文 全文索引fu- text index) ■中文等东方文字要经过“切词”处理 北京大息学 张铭 政■印究 张帖写

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 10.3.1 基于属性的倒排 „ 对某属性按属性值建立索引表，称倒排 表 „ (attr, ptrList) „ （属性值，具有该属性值的各记录指针） „ 记录指针可以是关键码，或该记录的主文件地址 „ 颠覆主文件的顺序，因而称为倒排索引 „ 属性往往是离散型的 „ 对于连续型的索引，往往用B树 „ 倒排文件：带有倒排索引的文件 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 0375, 0552 0197 0204, 0673 0100, 0193 0172, 0201, 0221 2500 3000 3500 4000 5000 SAL list EMP# 0197, 0375, 0552 0100 0193, 0204 0673 0172 0221 0201 26 32 39 40 43 47 55 AGE list EMP# 0100, 0221, 0552 0172, 0201 0193, 0197, 0204 0375, 0673 玩具部 食品部 服装部 电器部 DEPT list EMP# 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 检索实例 列出玩具部中年龄在50岁以上或者工资在 5000元以上的职工记录 (DEPT=“Toy”AND(AGE≥50 OR SAL≥5000))。 分别找出满足条件DEPT=“Toy”， AGE≥50，和SAL≥5000的指针集合，然后 对后两个指针集合求并，并且将结果集合与第 一个指针集合求交，最后的结果集合中包含的 指针所指的各记录即为所求。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 „ 优点：能够对于基于属性的检索 进行较高效率的处理 „ 缺点： „ 花费了保存倒排表的存储代价 „ 降低了更新运算的效率 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 10.3.2 对正文文件的倒排 „ 正文索引(Text Indexing)处理 的就是“建立一个数据结构以提 供对文本内容的快速检索”。 „ 方法 „ 词索引(word index) „ 全文索引(full-text index) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 词索引 „ 基本思想： „ 把正文看作由符号和词所组成的集合，从正 文中抽取出关键词，然后用这些关键词组成 一些适合快速检索的数据结构。 „ 适用于多种文本类型，特别是那些可以 很容易就解析成一组词的集合的文本 „ 适用于英文 „ 中文等东方文字要经过“切词”处理

全文索引 基本思想 词索引使用最广泛 把正文看作一个长的字符串 在数据结构中记录的是子字符率的开始位量 一个已经排过序的关键词的列表 查询就可以针对正文中的任何子字符串 其中每个关键词指向一个倒排表 (每限子柔 z符建立索引,从而使查 (posting list) ■需要更大的空间 指向该关键词出现文档集合 在文档中的位置 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 阿淘城 倒排索引 pm4e饰e 位 建立正文倒排文件 5细断网 a{68 6每 (L3)(44) 1.对文档集中的所有文件都进 行分割处理,把正文分成多条记 6ke(42) 录文档 切分正文记录取决于程序的需要 e(12)(15(22) 定长的块、段落、章节,甚至一组 文档 张铭帖编写 叔所有,轨圆即 孔写 丽中科院计算所汉语词法分新系统 2.给每条记录赋一组关键词 操作选项 一输出格式 ■以人工或者自动的方式从记录中 语切分一级注二根根注‘北大杯准C米速8 抽取关键词 停用词( Stopword) ”,车整上作 空 a抽词干( Stemming ■切词( segmentation) 北京大息学 张铭 权质有,印究

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 全文索引 „ 基本思想： „ 把正文看作一个长的字符串 „ 在数据结构中记录的是子字符串的开始位置 „ 查询就可以针对正文中的任何子字符串 „ 可以对每一个字符建立索引，从而使查 询词不再限于关键词 „ 需要更大的空间 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 词索引使用最广泛 „ 一个已经排过序的关键词的列表 „ 其中每个关键词指向一个倒排表 （posting list） „ 指向该关键词出现文档集合 „ 在文档中的位置 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 倒排索引 1 2 3 4 5 6 7 8 9 10 11 12 13 编号 词语 （文档编号，位置） cold days hot in like nine old pease porridge it pot some the (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) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 建立正文倒排文件 „ 1. 对文档集中的所有文件都进 行分割处理，把正文分成多条记 录文档 „ 切分正文记录取决于程序的需要 „ 定长的块、段落、章节，甚至一组 文档 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 „ 2. 给每条记录赋一组关键词 „ 以人工或者自动的方式从记录中 抽取关键词 „ 停用词(Stopword) „ 抽词干(Stemming) „ 切词（segmentation） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42

对关键词的检索 ■3.建立正文倒排表、倒排文件 ■第一步,在倒排文件中检索关键词 得到各个关键词的集合 步,如果找到了关键词,那么获 倒排表,并获取倒排 对于每一个关键词得到其倒排表 然后把所有的倒排表存入文件 记录在每个倒排表在索引文件中开 筹集阻表建霜菱麴字典)进 始的位置以及每个表的大小(也可 以记录每个关键词的出现次数) 散列 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 倒排文件优劣 104动态索引 高效检索,用于文本数据库系统 ①基本概念 ■支持的检索类型有限 Q1041B树 检索词有限 Q10.4.2B树 只能用索引文件中的关键词 10.4.3ⅤsSAM 倒排文件中的索引效率可能不高 044B树的性能分析 需要的空间代价往往很高 张铭帖编写 孔写 基本概念 104.1B树 ■动态索引结构 种平衡的多分树( Balanced tre 索引结构本身也可能发生改变 3阶B树 在系统运行过程中插入或删除记录时 2-3树 ■目的 保持较好的性能 例如较高的检索效率 [2023,[44[50s1 北京大息学 张铭 权质有,印究 张帖写 权新有:命些

8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 „ 3. 建立正文倒排表、倒排文件 „ 得到各个关键词的集合 „ 对于每一个关键词得到其倒排表 „ 然后把所有的倒排表存入文件 „ 记录在每个倒排表在索引文件中开 始的位置以及每个表的大小（也可 以记录每个关键词的出现次数） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 对关键词的检索 „ 第一步，在倒排文件中检索关键词 „ 第二步，如果找到了关键词，那么获取 文件中的对应的倒排表，并获取倒排表 中的记录 „ 通常使用另一个索引结构（字典）进一 步对关键词表进行有效索引 „ Trie „ 散列 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 倒排文件优劣 „ 高效检索，用于文本数据库系统 „ 支持的检索类型有限 „ 检索词有限 „ 只能用索引文件中的关键词 „ 倒排文件中的索引效率可能不高 „ 需要的空间代价往往很高 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 10.4 动态索引 „ 基本概念 „ 10.4.1 B树 „ 10.4.2 B+树 „ 10.4.3 VSAM „ 10.4.4 B树的性能分析 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 基本概念 „ 动态索引结构 „ 索引结构本身也可能发生改变 „ 在系统运行过程中插入或删除记录时 „ 目的 „ 保持较好的性能 „ 例如较高的检索效率 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 10.4.1 B树 „ 一种平衡的多分树 (Balanced Tree) 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 3阶B树 2-3树

m阶B树的结构定义 2.B树的性质 (1)每个结点至多有m个子结点; ■(1)树高平衡,所有叶结点都在同一层 (2)除根结点和叶结点外,其它每个结点至少有 关键码没有重复,父结点中的关键码是 「m/21个子结点 其子结点的分界 ■(4)B树把(值接近)相关记录放在同一个 (3)根结点至少有两个子结点 磁盘页中,从而利用了访问局部性原理; 唯一例外的是根结点就是叶结点时没有子结点 此时时树只包含一个结点 ■(5)B树保证树中至少有一定比例的结点是 (4)所有的叶结点在同一层 (5)有k个子结点的非根结点恰好包含k-1个关键 这样能够改进空间的利用率 码。 减少检紫和更新操作的磁盘读取数目 张陪写 新。■印乡究 上京大学 权新有轴命 B树的结点结构 B树的查找 B树的一个包含个关键码,j1个指针的结点的一般形式 交替的两步过程 母根结点读比率查获结定的类的关 K,P1,K2,P2,…,P}1 找到则检索成功 2.否则,确定要查的关键码值是在某个K1 和K之间,于是取p所指向的结点继续查 是关键码值,K<K2<…k 找 包括K到K之间的关键码的子树的指针 如果指向外部空结点,表示检索失败 张铭帖编写 孔写 B树检索长度 B树插入 ■设B树的高度为h 注意保持性质,特别是等高和阶的 独根树高为1 ■在自顶向下检索到叶结点的过程中 1)找到最底层,插入 可能需要进行h次读盘 2)若溢出,则结点分裂,中间关键 码连同新指针插入父结点 3)若父结点也溢出,则继续分裂 分裂过程可能传达到根结点(则树升高 北京大息学 张铭 权质有,印究 张帖写 权新有:命些

9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 m阶B树的结构定义 „ (1) 每个结点至多有m个子结点； „ (2) 除根结点和叶结点外，其它每个结点至少有 个子结点； „ (3) 根结点至少有两个子结点 „ 唯一例外的是根结点就是叶结点时没有子结点 „ 此时B树只包含一个结点 „ (4) 所有的叶结点在同一层； „ (5) 有k个子结点的非根结点恰好包含k-1个关键 码。 ⎡ ⎤ m / 2 ⎢ ⎥ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 2. B树的性质 „ (1) 树高平衡，所有叶结点都在同一层； „ (2) 关键码没有重复，父结点中的关键码是 其子结点的分界； „ (4) B树把（值接近）相关记录放在同一个 磁盘页中，从而利用了访问局部性原理； „ (5) B树保证树中至少有一定比例的结点是 满的 „ 这样能够改进空间的利用率 „ 减少检索和更新操作的磁盘读取数目 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 B树的结点结构 B树的一个包含j个关键码，j+1个指针的结点的一般形式 为： „ 其中Ki 是关键码值，K1<K2<…<Kj ， „ Pi 是指向包括Ki 到Ki+1之间的关键码的子树的指针。 „ 还有指针吗？ P0， K1， P1， K2， P2， …， Pj-1， Kj， Pj 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 B树的查找 „ 交替的两步过程 „ 1. 把根结点读出来，在根结点所包含的关 键码K1，…，Kj 中查找给定的关键码值 „ 找到则检索成功 „ 2. 否则，确定要查的关键码值是在某个Ki 和Ki+1之间，于是取pi 所指向的结点继续查 找 „ 如果pi 指向外部空结点，表示检索失败 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 B树检索长度 „ 设B树的高度为h „ 独根树高为1 „ 在自顶向下检索到叶结点的过程中 可能需要进行 h 次读盘 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 B树插入 „ 注意保持性质，特别是等高和阶的 限制 „ 1) 找到最底层，插入 „ 2) 若溢出，则结点分裂，中间关键 码连同新指针插入父结点 „ 3) 若父结点也溢出，则继续分裂 „ 分裂过程可能传达到根结点(则树升高一 层)

B树的插入 ■叶结点处在第层的B树,插入的关 ■叶结点处在第层的B树,插入的关 键码总是在第I-1层 键码总是在第I-1层 司国:[2[ 111 插入14 北京大息 张陪写 新。■印乡究 京大恤盒 孔稳写 权新有轴命剑究 念5楼 含值50和52的页 插入55结果 升到父结点 B3」 张铭帖编写 孔写 插入引起3阶B树根结点分裂的例子 插入引起3阶B树根结点分裂的例子 插入19 入19 北京大息学 张铭 权质有,印究 大歌张帖写 权新有:命些 10

10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 B树的插入 „ 叶结点处在第I层的B树，插入的关 键码总是在第I-1层 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 插入14 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 „ 叶结点处在第I层的B树，插入的关 键码总是在第I-1层 插入14 18 33 12 23 30 48 10 14 15 20 21 24 31 45 47 50 52 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 插入55,使得包含值50和52的页 分裂，把值52提升到父结点 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 55 18 33 12 23 30 48 52 10 15 20 21 24 31 45 47 50 插入55结果 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 插入引起3阶B树根结点分裂的例子 插入19 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 插入引起3阶B树根结点分裂的例子 插入19 21 18 33 12 23 30 48 10 15 19 24 31 45 47 50 52 20