数据结构第十章索引技术

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