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