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