chap09--索引与散列.ppt

单击此处编辑母版标题样式,第一级,第二级,第三级,第四级,第五级,*,数 据 结 构,(,C,语言版),董玉涛,第9章,索引与散列,本章目标,9.1,磁盘和文件,9.2,静态索引及其查找,9.3,动态索引及其查找,9.4 散列表,3,9.1,磁盘和文件,9.1.1 主存和辅存,一般说来，计算机存储设备分为主存储器(,primary memory),和辅存储器(,secondary memory),主存储器通常指,RAM，,高速缓存(,cache),和显存(,video memory)，,又叫,内存,辅存储器指硬盘、软盘和磁带这样的设备，相对地，也叫,外存,。其中磁盘是,直接访问存储设备,(,direct access storage devices,DASD)，,磁带是,顺序访问存储设备,(,sequential access storage devices，SASD),访问内存和磁盘的速度相差极大(差距在10万到100万倍之间)。由于访问磁盘中的数据太慢，因而需要创建有效的应用程序处理存储在磁盘中的信息。设计基于磁盘的应用程序时遵循下面的这条规则极其重要,使访问磁盘的次数最少！,P293,5,9.1.2 磁盘驱动器1-1,磁盘通常称为直接访问存储设备(,DASD),这表明可以对存储在磁盘中的数据进行随机访问,这与磁带之类的顺序访问存储设备不同：需要从磁带的开始处检索数据，直到到达需要的位置,一块硬盘由一个或多个圆形,盘片(,platters),组成，这些盘片从上到下排列，中间有一定的间隙，所有盘片都围着一个,主轴(,spindle),旋转。盘片像唱片一样，以恒定的速度连续转动。盘片有两个面，每个面都有一个,读/写磁头(,read/write head),，,或者称为,I/O,磁头。数据就是通过这些磁头读出或写入的，这有些像留声机的活动臂从唱片中得到声音一样。与留声机的针头不同，磁盘的读/写磁头实际上不接触盘面，这样会防止划伤磁盘。这个距离非常小，比一粒灰尘的高度还要小500万倍,P295,6,9.1.2 磁盘驱动器1-2,硬盘一般有多个盘片和多个读/写磁头，每个磁头都固定到一个回转臂上。当磁头在盘片上方的某个位置时，磁头就可以直接访问相应盘片上的数据。盘面上有许多同心圆，这些圆圈叫,磁道(,tracks),，,数据就保存在磁道上。一个面上有一个磁头，它可以从该面上的一道移动到另一道,由于不同面上的磁头固定在同一个回转臂上，因此它们是同时移动的，并处于同一垂直,柱面(,cylinders),上。,各个盘面上半径相同的磁道组成一个垂直的圆柱面,柱面的个数就是盘面上磁道的个数,一个柱面就是磁头在某一位置上时可以读写的所有数据量，它是位在该柱面上的所有磁道的数据量的总和,P295,图11.3,7,9.1.2 磁盘驱动器1-3,每个磁道可以细分为多个,扇区(,sectors,),。,相邻两个扇区之间有扇区间间隙(,inter-sector gaps,)，,扇区间间隙不存储数据。所有磁道均包含相同数量的扇区。每个扇区中均包含相同的数据量(,bit,数或字节数)。这样，,外层磁道的存储密度比内层磁道的要小,扇区,位数据,扇区间间隙,磁道,这样，一个数据就可以用,柱面号,、,盘面号,和,扇区号,来加以定位,8,9.1.2 磁盘驱动器1-4,软盘(,floppy disks),和光盘(,CD),与硬盘的这种物理布局不同：它们由一个单一的,螺旋磁道,组成。磁道内的,bit,数据分布均匀，因此内层磁道和外层磁道的数据密度相同,从硬盘读写一个字节数据通常分为3个独立的步骤,I/O,磁头在磁道(或者说柱面)间移动，移到正确的磁道上。这个过程叫寻道(,seek)。,寻道所花的时间叫,寻道时间(,seek time),，,一般为几十,ms,磁头等待该磁道上包含数据的扇区转到磁头下方。这个时间叫做,旋转延迟时间(,rotation latency),。,一般为几,ms,数据的传输时间,。一旦数据旋转到,I/O,磁头下方，读写数据所花的时间。这个时间就是读写时，盘片旋转的时间。一般为,ns,级,T,r/w,=T,seek,+T,latency,+T,transition,9,9.1.2 磁盘驱动器1-5,因此，读写一次磁盘所花的时间主要取决于,寻道时间,，即磁头在磁道间移动的时间,注意：实际上，磁盘的设计并不是每次读写一个,byte,，,而是一次读写一个扇区的数据。因此，一个扇区是磁盘一次读写的最小数据量，而非,byte,一般来说，最好把一个文件的所有数据集中存放在一个柱面的相邻扇区中。这样，读写文件时，能够加快文件的读写速度。最差情况就是文件被零散地放在不同柱面上，这样，对文件的读写需要跨柱面(或跨磁道)，增加了额外的寻道时间，造成时间的浪费,不同的操作系统把一个或几个相邻扇区集结成组，称作一个,簇(,cluster),或,块(,block),。,对操作系统而言，,簇是文件分配和读写的最小单位,。因此，一个文件可能是由一个或几个簇组成，对文件的一次读或写的数据量是一个簇的大小,10,9.1.2 磁盘驱动器1-6,例如，,windows98,操作系统规定一个簇是32,kB(,若硬盘的扇区为512,B，,则一簇相当于64个扇区),假设有一个文件，大小为33,kB，,这样，操作系统就为它分配2个簇，其中一个占满了，而另一个只占用一个1,kB，,其余的31,kB,只能被浪费掉了，我们把这种浪费掉且不能分配给其他文件使用的磁盘空间叫,内碎片(,internal fragments),我们读该文件，一次读32,kB，,即一簇的数据量到内存，读到内存的簇或块通常叫,页面或页(,pages),。,它的大小等于一个簇或块的大小,至于,Unix,操作系统，规定文件分配和读写的基本单位是一个扇区，在,Unix,术语中称为一个块(,block),簇或块是操作系统一次读或写的基本单位，它可能由一个扇区或几个扇区组成，这取决于操作系统对硬盘格式化(,format),时的配置,11,9.1.3 磁盘访问的时间代价2-1,访问磁盘扇区的主要代价是寻道时间,当随机访问一个磁盘的扇区时，,当前磁道和目标磁道之间的平均距离是磁盘中磁道总数的1/3,跨越,n,个磁道的,寻道时间,T,seek,=tn+s,，,其中，,t,是跨越一个磁道的时间，,s,是启动磁盘驱动器的时间,拥有10.2,GB,的,Quantum,磁盘就是一个典型的例子。生产厂家的规格说明标识，,cylinders/platters/sectors=19885/16/63，t=2.5ns，s=3ms。,因此，这个磁盘的平均寻道时间可以这样计算0.0025(19885,3),+3=19.6,ms,多年来磁盘的一般旋转速度是5400转/分钟，即11.1,ms/,圈。近一时期磁盘的旋转速度是7200转/分钟，即8.3,ms/,圈。当随机读取一个扇区时，磁盘平均需要转半圈使得目标扇区到达,I/O,磁头之下，或者对一个5400转/分钟的磁盘来说，需要5.5,ms,12,9.1.3 磁盘访问的时间代价2-2,一旦,I/O,磁头到达目标扇区，扇区中的数据就可以以扇区旋转的速度在磁头下传送。如果要读取整个磁道，那么就旋转一圈(11.1,ms)。,使得磁头经过整个磁道。如果需要读取磁道的一部分，例如磁道中有63个扇区，而只读出1个扇区，这就需要大约0.2,ms,例：假定一个,Quantum,磁盘容量为10.2,GB，,分布在16个盘片上，每个盘片上有19885个磁道，每个磁道中包含63个扇区，这样可以算出每个扇区内有512个字节。,I/O,磁头的启动时间是3,ms，,磁头跨越一个磁道的时间是2.5,ns。,假定操作系统规定的簇的大小是8,kB(16,个扇区)，则一次读写的时间代价是,T,r/w,=T,seek,+T,latency,+T,transition,=0.0025(19885,3),+3+11.1,2+11.14=19.6+5.5+2.3=27.4 ms,13,9.2,静态索引及其查找,索引结构,我们已经学习了磁盘存储数据的方式，知道数据或纪录是被存储在簇或块中，一个簇或块存储了一条或多条纪录,操作系统一次读取一整块到内存，形成页。此外操作系统或数据库管理系统一般也规定一条纪录不能跨块存储，即任何一条纪录不能被分割在两个不同的块上,当数据库中的纪录个数,n,很大时，如果用无序线性表形式的集合结构存储，采用顺序查找，则查找效率极低：为查找一个符合条件的纪录平均需要查找几乎一半的纪录；如果采用有序表形式的查找结构，用折半查找，时间开销为,log,2,n，,对很大的,n，,代价也很大。这时可采用索引方法来实现记录的存储和查找,索引结构是一种集合结构，通常用于外存中的大型文件系统和数据库管理系统的检索,。它分为静态和动态两种，其差别类似于上一章中的静态集合和动态集合,15,9.2.1 线性索引3-1,线性索引是最简单的一种静态索引结构,在索引结构中，首先要建立一个索引表(,index table)。,索引表可以是线性结构的，也可以是树型结构的。线性结构的索引表叫做线性索引。如下图左边的索引表就是一个线性索引,16,9.2.1 线性索引3-2,其特点是,每一行代表一个索引项。索引项是由关键字,key,和包含该关键字的纪录在磁盘中的地址组成的。当然我们这里的地址只是一个示意地址。根据上一节的内容我们知道磁盘地址应该由纪录所在的“,柱面号：盘面号：块号,”组成,索引项按关键字递增有序,所有的索引项组成一个线性结构。形成了一个顺序表，可以采用折半查找,索引表是静态的，只供查找，一旦建立就不能再改变了。所以线性索引是一种静态索引结构,它又分为稠密索引(索引无序结构)和稀疏索引(索引有序结构),17,为什么要用索引？,设上图中每一条纪录大小为1,kB，,又设查找程序的工作内存为64,kB。,因此，在某一时刻内存最多可容纳64条纪录。又假设表中共有14,400条纪录，我们打算查找第14,400条纪录，在不采用索引的情况下一共需要读取14,400/64=225次外存。由于一次读取磁盘至少在20,ms,的数量级，这样225次就是4.5秒左右,再来看采用索引的情形,设索引项关键字域为,short,型(2,B)，,地址域为柱面号+盘面号+块号=2+1+1=4,B，,这样一个索引项为6,B，14,400,个索引项约为84,kB。,因此最多只需从外存读两次索引表，便能找到第14,400条纪录对应的索引项，然后再利用索引项中的地址读取一次外存，将该纪录所在的页块读入内存。所以，只需读取23次外存便能找到纪录。时间大约为30,ms。,差了150倍之多,18,稠密索引(索引无序结构),从上图可以看出，职工数据表中有多少条纪录，索引表中就对应有多少个索引项。这样使每一个索引项唯一对应数据表中的一条纪录,这种一个索引项对应数据表中一条纪录的线性索引结构叫做,稠密索引,(索引项数等于纪录数。当纪录数很大时，索引表中的索引项也很多),当纪录在磁盘中按加入的先后顺序而不是按关键字顺序存放时必然采用稠密索引，因此这种索引结构也叫做,索引无序结构,19,稠密索引的性能分析,(1)首先，将索引表从外存读入内存工作缓冲区,(2)然后，由于索引表中的索引项是按关键字有序排列的，因此可以对缓冲区中的索引表做折半查找，找到给定的关键字,(3)接着，再利用地址域将纪录所在的页块读入内存,(4)最后，由于纪录在页中是按关键字无序排列的，因此对页中的所有纪录只能做顺序查找(利用上一章中讲到的顺序查找)，直至找到我们要找的纪录,因此，利用稠密索引查找磁盘上的一条纪录的过程为：读磁盘(第1步)+内存折半查找(第2步)+读磁盘(第3步)+内存顺序查找(第4步)。其中，在内存中的查找操作的耗时比起读磁盘的时间要小得多(两者相差3 4个数量级)，可忽略不计。因此时间主要消耗在2次读磁盘(一次读索引，一次读纪录)上了。若索引表太大以至于不能一次读入内存工作缓冲区，则读磁盘的次数还可能更多,20,稀疏索引(索引有序结构)4-1,见上图，设一个数据表中的纪录分布在外存的4个页块中。块内的纪录可以按关键字有序，也可以无序(比如这个例子)排列。但块与块之间是按关键字有序的，即一个块中的所有关键字均大于另一个块，例如块4块3块2块1。我们将这种有序叫做,按块有序,P225,地 址,块 1,块 2,块 3,块 4,21,稀疏索引(索引有序结构)4-2,这时，我们可以建立一张索引表，表中的每个索引项对应一个页块，关键字域存放这个页块中最大的关键字，叫,max_key，,地址域存放该页块在磁盘中的地址(形式为柱面号：盘片号：块号),这样，数据表占几个页块，索引表中就有几个索引项，所以索引项的数目远远小于实际的纪录数，这种线性索引结构叫做,稀疏索引,。又由于纪录按块有序，所以这种索引也叫,索引有序结构(或索引顺序结构),22,稀疏索引的性能分析5-1,(1)首先，将索引表从外存读入内存工作缓冲区,(2)然后，由于索引表中的索引项是按关键字有序排列的，因此可以对缓冲区中的索引表用顺序查找或折半查找，找到给定的,key,对应的索引项(,i-1.max_key key i.max_ key，,此时的,i,为对应的索引项),(3)接着，再利用地址域将纪录所在的页块读入内存,(4)最后，若纪录在页中按关键字无序排列，则对所有纪录做顺序查找；否则做折半查找。直至找到要找的纪录,因此，利用稠密索引查找磁盘上的一条纪录的过程为：读磁盘(第1步)+内存折半查找(第2步)+读磁盘(第3步)+内存顺序查找或折半查找(第4步)。其中，在内存中的查找操作的耗时比起读磁盘的时间要小得多(两者相差3 4个数量级)，可忽略不计。因此时间主要耗在2次读磁盘(一次读索引，一次读纪录)上了。若索引表太大以至于不能一次读入内存工作缓冲区，则读磁盘的次数还可能更多,23,下面我们仅讨论在内存中查找所消耗的时间代价,从前面的性能分析可知：内存中的查找包括(2)和(4)两步，即在索引表中顺序查找或折半查找和在页块中顺序查找。因此，总的,ASL,=,L,b,+,L,w,，,其,L,b,为索引表的平均搜索长度，,L,w,为在页块中查找指定纪录的平均搜索长度,稀疏索引的性能分析5-2,若对索引表折半查找,ASL,=,L,b,+,L,w,=+,log,2,(+1)+,P226,若对索引表顺序查找,ASL,=,L,b,+,L,w,=+=+1，,b,为数据文件在磁盘中占用的块数，也就是索引表中索引项的个数。,s,为每个页块中所能容纳的纪录数。因此，,b,=，,ASL,=,L,b,+,L,w,=(+,s,)+1。,当,s=,时，,ASL,取最小值 +1，即时间复杂度为,O(n ),24,9.2.2 多级树型索引6-1,当纪录数特别大(如,VLDB)，,索引表本身也很大，在内存工作缓冲区中放不下，需要分批多次读外存才能把索引表查找一遍,在这种情况下，可以建立索引的索引，称为二级索引，如果二级索引在内存工作缓冲区中也放不下，还可以建立三级索引，这种多级索引结构形成一种多叉树(见下页)。应该说，多级树型索引是线性索引的一种改进形式,整个树型结构分为,索引部分,和,数据部分,每一个分支结点叫作一个索引块，占用磁盘中的一个簇或块。索引块中的每个索引项给出了下一级索引块中的最大关键字和块地址。因此分支结点又叫做索引的索引,索引树的叶结点(一级索引块)中各索引项给出每个数据块中纪录的最大关键字和页块地址。所有纪录按块有序，数据块内的纪录可按关键字有序，也可无序,25,9.2.2 多级树型索引6-2,620,1100,4150,50 77 90 134 151 157 160,160,330,620,810,900,1100,3800,4000,4150,215 233 260 279 330,500 539 583 590 601 605 610 614 620,650 675 700 750 781 790 800 810,831 845 897 900,1000 1025 1056 1072 1090 1100,3630 3652 3720 3800,3830 3859 3872 3880 3914 3943 3975 4000,4040 4085 4150,二级索引(主索引),索引部分,数据部分,max_key,max_key,一级索引,26,9.2.2 多级树型索引6-3,这样，若要查找某条纪录，我们只需读取3次磁盘：第一次读入二级索引(主索引)、第二次读入一级索引、第三次读入数据页。时间主要消耗在读取磁盘上。每当读入索引块或数据块后，便在内存工作缓冲区中对其进行查找，这时可按顺序查找，但一般采用折半查找。所以说，,在多级树型索引结构中，查找关键字是一个顺指针查找下级结点(读磁盘)和在结点的关键字中进行查找(内存查找)交替进行的过程,ISAM(indexed sequential access method,索引顺序访问方法)文件就是采用多级树型索引结构的典型范例，它是由,IBM,为开发大型,DBMS,提出的。我们所熟知的,Access,数据库就是一种,ISAM,索引文件,多级树型索引可以是静态索引结构，即结构在初始创建、数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化。它还可以是动态的，即在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的查找效率,27,9.3,动态索引及其查找,9.3.1,B,树,我们学过,AVL,树，知道它适合于组织在内存中较小的纪录集。对于存放在外存的较大的,文件系统,和,数据库管理系统(,DBMS),，,用,AVL,树来组织就不太合适了。因为这样一来，找到某个特定关键字需对外存进行,log,2,n,次访问，当,n,很大时，这是很费时的。因此在操作系统的文件系统和大型数据库管理系统中大量采用“,B,树,”或“,B+,树,”等索引结构来存储数据和记录,29,B,树是一种高度平衡的动态,m,阶查找树,其定义为,树中所有结点至多有,m,棵子树(,至多全满，,m-1,个关键字,),根结点至少有2棵子树(,至少有1个关键字,),其他非叶结点至少有,m/2,棵子树,(,至少半满，,m/2-1,个关键字,)，叶结点至少有,m/2-1,个关键字,所有结点具有如下结构,n,P,0,(K,1,A,1,P,1,),(K,2,A,2,P,2,),(K,n,A,n,P,n,),。,其中，,K,i,是关键字，且必须,K,i,K,i+1,(1i n)；P,i,(0inm),是指向子结点的指针(实际上是子结点在磁盘中的地址)；,A,i,是指向包含关键字,K,i,的纪录的指针(实际上是纪录在磁盘中的地址),在子结点,P,i,中所有的关键字都大于,K,i,而小于,K,i+1,。,在子结点,P,0,中的所有关键字都小于,K,1,，,而子结点,P,n,中所有的关键字都大于,K,n,所有叶结点都在同一层上(,=0,高度平衡),B,树的定义7-1,P238,30,B,树的定义7-2,5-阶,B,树示意图,60,10,20,40,70,80,81,89,95,73,77,62,66,45,50,55,58,25,30,12,16,18,6,8,1,3,2,2,由定义可知，,B,树的每个结点其实就是一个索引表，称为索引结点。索引项的关键字域按升序排列，,A,i,指针域指向包含该关键字的纪录在外存中的地址。每个索引结点对应于磁盘中的一个簇或块，因此也叫,索引块,。对索引结点的访问等价于从磁盘读取相应的索引块,31,包含,N,个关键字的,m,阶,B,树的高度,hlog,()+1,B,树的性质8-1,AVL,树近似于二叉,B,树，,B,树是,AVL,树的推广，且高度平衡,已知,m,阶,B,树的度为,m，,它的高度为,h，,则,B,树的最大结点数为：(,m,h,-1)/(m-1)。,由于每个结点最多可容纳,m-1,个关键字，因此最多关键字数为,m,h,-1，,也就是说，以这棵,B,树作为纪录集的索引结构，最多可索引到,m,h,-1,条纪录,P241,32,B,树的性质8-2,证明：第一层至少有1个关键字。由于除根之外的每个结点至少有,q=,-1,个关键字，因此第二层至少有2,q,个关键字；第三层至少有2,q(q+1),个；第四层至少有2,q(q+1),2,个，第,h,层至少有2,q(q+1),h-2,。,因此，,N,1+2q(1+(q+1)+(q+1),2,+(q+1),h-2,)，,即,N2(q+1),h-1,-1=2 ,h-1,-1，,因此，,h,log,()+1。,这便是具有,N,个关键字的,B,树的最大高度,。,这意味着对于很大的阶,m，,即使,B,树存储的关键字很大，高度也非常小。如当,m=200，N=2,000,000,时，,h4，,这就是说，最坏情况下，在,B,树中查找一个关键字只需读4次磁盘。若根常驻内存，则可降低到3次。,33,B,树的性质8-3,若提高,B,树的阶数,m，,可以减少树的高度，从而减少读磁盘的次数。但,m,不能无限增加，它受到程序开辟的内存工作区大小的限制。同时，,m,的增加也会增加块内查找的时间。因此应合理地选择,m,的值，使总的时间开销最小,34,B,树的查找9-1,设,B,树的阶为,m，,则,B,树的存储结构为,P239-240,typedef,struct,BTNode,int,n;,/,结点中关键字的个数,BTNode*parent;,/,指向父结点的指针,KeyType keym;,/,关键字数组，0号单元不用,struct,BTNode*pm;,/,指向子结点的指针数组,Record*recptrm;,/,纪录指针数组，0号单元不用,BTNode,*BTree;,typedef,struct,BTNode*p;,/,指向找到的结点,int,i;,/,结点中的关键字序号,int,tag;,/tag=1,表示查找成功；,tag=0,表示查找失败,Result;,/,若查找成功，则,tag=1，,指针,p,所指结点的,/第,i,个关键字等于,key；,否则，,tag=0，key,插,/入,p,所指结点的第,i,和第,i+1,个关键字之间,35,B,树的查找9-2,B,树结点示意图,key0,n,parent,p0,recptr0,key1,p1,recptr1,key2,p2,recptr2,keym-1,pm-1,recptrm-1,B,树的查找操作为,36,B,树的查找9-3,Result search(BTree T,KeyType k),Result r;,int,i;,ReadNode(T);,/,从磁盘读取,T,指向的索引块,Btree p=T,q=NULL;,while,(p!=NULL),i=0;p,keypn+1=INFINITY;,while,(pkeyi+1k,q=p;p=ppi;,ReadNode,(p);,/,读取下一层结点,/,while,r=(q,i,0);,return,r;,/,未找到,k，k,应插入到,q,keyi,之后,37,B,树查找分析,从该算法可见，,B,树的查找过程蕴含着交替进行的两种基本操作,(1),在,B,树中沿指针找索引结点(索引块),(2)在索引结点中找关键字,由于,B,树存储在磁盘上，则操作(1)是读磁盘的过程，操作(2)是在内存中进行的，即先将磁盘中的索引块读入内存，然后再利用顺序查找或折半查找在内存中查询等于,key,的关键字,显然，读取磁盘比在内存中进行查找耗费的时间多得多，因此，,读取磁盘的次数，即关键字,key,所属索引结点在,B,树中的层数(或高度)是决定,B,树查找效率的首要因素,在,B,树上进行查找，查找成功所需的时间取决于关键字所在层数；查找不成功所需的时间取决于,B,树的高度,P240,38,B,树的插入10-1,B,树是从空树起，逐个插入关键字而动态生成的。当从根走到叶结点没有找到,key，,就在当前叶结点中的适当位置插入,key。,因此，,插入总是从某个叶结点开始的,。但在插入,key,时，如果结点中关键字的个数超过上界,m-1，,则结点要发生“分裂”；否则就直接插入,结点“分裂”的原则是,设结点,p,已经有,m-1,个关键字，当再插入一个关键字后结点中的状态为,m,P,0,(K,1,P,1,),(K,2,P,2,),(K,m-1,P,m-1,),(K,m,P,m,),这时必须把结点,p,分成,p,和,q，,它们包含的信息分别为结点,p:,-1,P,0,(K,1,P,1,),(K,2,P,2,),(K,-1,P,-1,),结点,q:m-,P,(K,+1,P,+1,),(K,m,P,m,),P244,位于中间的关键字,K,与指向新结点,q,的指针形成(,K,q)，,插入到这两个结点的父结点中,39,B,树的插入10-2,我们看一个3阶,B,树(又叫,2-3树,)的插入过程,插入53,53,插入75,53,75,插入139,53,75,53,75,139,53,75,139,插入49，145,49,75,139,53,145,36,插入36,49,75,139,53,145,36,49,139,75,145,53,101,插入101,36,49,139,75,145,53,145,49,75,101,36,139,53,139,145,49,75,101,36,53,40,B,树中的所有非根结点至少有,m/2,个子结点,(至少半满)，即至少含有,m/2-1,个关键字。若从一个结点删除某个关键字后，该结点低于半满，则要发生结点的“合并”。否则直接删除,结点“合并”的原则是,1、若从,叶结点,删除一个,key,1.1、,在删除,key,后，叶结点中关键字数,m/2-1(,至少半满)，只需将,key,后面的关键字左移填补空位,1.2、,在删除,key,后，叶结点中关键字数,m/2-1,的左兄弟或右兄弟，则将父结点中的分隔键移到这个叶结点中，然后从这个兄弟中移一个关键字到父结点中,B,树的删除11-1,41,1.2.2、如果该叶结点的左右兄弟的关键字数都=,m/2-1，,则将这个叶结点和它的一个兄弟合并：该叶结点的关键字、它的兄弟的关键字以及父结点的分隔键全部放到该叶结点中，然后删除它的这个兄弟结点。由于父结点中的分隔键被移走后出现一个空位，有可能导致父结点下溢，这时可把父结点看作叶结点，重复1直到可以执行1.2.1或者到达树的根结点结束,2、若从一个,非叶结点,删除一个,key,将要删除的关键字用它的直接后继,(,也可以用直接前驱)替换，这只能从一个叶结点中找到。然后将这个后继值从叶结点中删除，这就回到了第1种情况,B,树的删除11-2,42,B,树的删除11-3,我们看一个5阶,B,树的删除过程,(,a),初始,B,树,16,3,8,22,25,1,2,5,6,7,13,14,15,18,20,23,24,27,37,(,b),删除6后的,B,树,16,3,8,22,25,1,2,5,7,13,14,15,18,20,23,24,27,37,删除6，情况1.1,43,B,树的删除11-4,(,c),删除7后的,B,树,16,3,13,22,25,1,2,5,8,14,15,18,20,23,24,27,37,再删除8，情况1.2.2，结点合并,再删除7，情况1.2.1,(,d),删除8后的,B,树(未完),16,3,22,25,1,2,5,13,14,15,18,20,23,24,27,37,44,B,树的删除11-5,再删除16，情况2+1.1，用前驱替换,继续，情况1.2.2,结点合并,3,16,22,25,1,2,5,13,14,15,18,20,23,24,27,37,(,e),删除8后的,B,树,3,15,22,25,1,2,5,13,14,18,20,23,24,27,37,(,f-1),删除16后的,B,树,3,18,25,1,2,5,13,14,15,20,22,23,24,27,37,(,f-2),删除16后的,B,树,或用直接后继替换情况2+1.2.2,45,B,树的分析与发展12-1,根据,B,树的定义，每个索引块必须保证至少半满，因此整个索引树可能会有50%的空间被浪费。实验表明，,B,树的平均利用率是69%(31%的磁盘空间被浪费了),因此，,Knuth,等人在,B,树的基础上又提出了,B*,树,在,B*,树中，除根以外的所有结点都至少2/3满而不是半满。更精确地说，对,m,阶,B*,树索引结点中的关键字数,n，,n m-1。,当结点分裂时，两个结点分裂成三个，而不是一分为二，即当两个互为兄弟的结点都满时，分裂成三个结点，原来两个结点中的所有关键字在三个结点中平均分配，使每个结点至少2/3满。实验表明，,B*,树的平均利用率是81%，比,B,树要好。而且通过延迟结点的分裂降低了结点分裂发生的频率，提高了操作效率,类似地，索引结点至少3/4满的,B,树叫,B*,树。至少 满的,B,树叫,B,n,树,46,B,树的分析与发展12-2,我们把,m,阶,B,树索引结点中现有关键字个数,n,与能存放的最大关键字个数,m-1,之比叫填充因子(,fill-factor)。,即填充因子=,n/(m-1),一些数据库管理系统(如,Oracle，SQL Server，DB2,等)允许用户在创建,索引,时，指定一个50%100%之间的填充因子。这个值决定了索引树中每个索引结点的最小填充比例,在,OLTP(OnLine Transaction Processing),环境中，经常执行插入和删除操作，这个值可以给的小一些，这样可以减少结点分裂发生的频率，降低树的高度，提高查找效率,在,OLAP(OnLine Analysis Processing),环境中，例如数据挖掘中，较少执行插入和删除操作，这个值可以给的大一些，以提高磁盘空间的利用率,47,9.3.2,B+,树*,B+,树可以看成,B,树的变型，在实现大型文件系统和数据库管理系统的索引结构方面比,B,树使用的更广泛,在,B+,树中包含了,B,树。除叶结点所在的最底下一层以外实际上是一棵正规的,B,树，只不过这棵,B,树的每个结点中并不像一般的,B,树那样包含指向关键字所属纪录的指针(即在,BTNode,中没有,Record*recptrm,域)。实际上，这个指针数组被放到了叶结点中,P246,48,树中每个非叶结点至多有,m,棵子树(,至多全满,),根结点至少有2棵子树,其他非叶结点至少有,m/2,棵子树(,至少半满,),所有非叶结点只是快速访问数据的索引，可以看成索引部分，具有如下结构,n,P,0,(K,1,P,1,),(K,2,P,2,),(K,n,P,n,)，,其中，,K,i,是关键字，且必须,K,i,K,i+1,(1in)；P,i,(0in m),是指向子结点的指针(实际上是子结点在磁盘中的地址)。结点格式同,B,树,在子结点,P,i,中所有的关键字都大于等于,K,i,而小于,K,i+1,。,在子结点,P,0,中的所有关键字都小于,K,1,，,而子结点,P,n,中所有的关键字都大于等于,K,n,B+,树的定义13-1*,P246,To Be Contibued,49,B+,树的定义13-2*,所有叶结点都在同一层上,。按关键字从小到大排列。与,B+,树的其他结点可以有着不同的结构,struct,LeafNode,KeyType keym1;,/m1,可以不同于,m,Record*recptrm1;,/,指向包含相应关键字的纪录,LeafNode*next;,/,指向右兄弟结点,;,叶结点中关键字的个数介于,和,m1,之间，即半满和全满之间,50,B+,树的定义13-3*,B+,树示意图,索引集,23,18,33,48,48,50,52,33,45,47,23,30,31,18,19,20,21,10,12,15,22,由定义可知，,B+,树的每个非叶结点是一个索引结点，这部分树称作一个,索引集,。索引结点中的关键字按升序排列，每个索引结点对应于磁盘中的一个簇或块，因此也叫,索引块,。对索引结点的访问等价于从磁盘读取相应的索引块。,叶结点中存放的是对纪录的索引。若纪录无序，则为稠密索引；若纪录按块有序，则为稀疏索引,51,B+,树的查找14-1*,通常在,B+,树中有两个头指针,一个指向,B+,树的根结点,另一个指向关键字最小的结点,因此，可以对,B+,树进行两种查找操作,一种是循叶结点构成的线性链表顺序查找，通常适用于范围查找,另一种是从根结点开始，进行自顶向下，直至叶结点的随机查找，通常适用于精确查找,52,B+,树的查找14-2*,在,B+,树上进行随机查找的过程基本上与,B,树类似。只是在查找时，若索引集中结点的关键字等于给定值,key，,查找并不停止，而是继续沿指针向下，一直查到叶结点上的这个关键字。因此，在,B+,树中，不论查找成功与否，每次查找都走了一条从根到叶的路径。路径长度即为读磁盘的次数,P246,在,B+,树上进行查找，查找成功或不成功所需的时间都取决于,B+,树的高度,53,B+,树的插入15-1*,B+,树的插入仅在叶结点上进行,向一个还有空间的叶结点上插入关键字需要将它按顺序放在这个叶结点中。索引集没有变化,但是，如果将一个关键字插入到一个已满的叶结点中，这个叶结点就会分裂成两个叶结点，关键字平均地分配给这两个叶结点，它们包含的关键字的个数分别为 和 。然后，将新叶结点的第一个关键字拷贝到父结点中,此后，问题归于在,B,树中插入一个关键字的操作了(如果父结点未满，需要重整父结点的关键字；如果父结点已满，就以类似于,B,树的方式执行分裂操作),54,B+,树的插入15-2*,B+,树插入示例,10,12,23,33,48,查找50,10,12,23,33,48,50,33,10,12,15,18,20,21,23,31,18,33,48,33,45,47,48,50,52,查找更多关键字,查找30,23,18,33,48,48,50,52,33,45,47,23,30,31,18,20,21,10,12,15,55,B+,树的删除16-1*,B+,树的删除同样仅在叶结点上进行,当从叶结点上删除一个关键字后，结点中的关键字数仍然,(至少半满)，这属于简单情况，其上面的,B,树不变,以,51页的,B+,树,为例,删除关键字18,23,18,33,48,48,50,52,33,45,47,23,30,31,19,20,21,22,10,12,15,18未变,56,B+,树的删除16-2*,当在叶结点上删除一个关键字后，结点中的关键字数,(低于半满)，必须做调整或合并操作,再删除关键字12，,并做调整,23,19,33,48,48,50,52,33,45,47,23,30,31,19,20,21,22,10,15,18,57,B+,树的删除16-3*,再删除关键字33，合并,23,19,33,45,47,48,50,23,30,31,19,20,21,22,10,15,18,52,58,9.3.3 2-3-4树和红黑树17-1*,4阶,B,树又叫做2-3-4树,它的特点是阶数不大，且高度平衡，所以存储同样多的关键字时，2-3-4树的高度比平衡二叉树(如,AVL,树)更低，,ASL,更小，是代替平衡二叉树，用于对存储在,内存,中的数据进行索引的有力工具(,注意：2-3-4树一般不用做外存纪录的索引,),但是，由于2-3-4树是一种,B,树，在最坏情况下，每个索引结点中有2/3的空间被浪费掉了。因为内存空间比外存空间更宝贵，我们当然希望避免内存空间的浪费。所以，把2-3-4树转化成二叉树的形式，使每个结点只保存一个关键字，就可以避免空间的浪费。那么，如何将2-3-4树转化为一棵二叉树呢？下面我们看一个例子,59,9.3.3 2-3-4树和红黑树17-2*,A,B,P,Q,R,A,B,P,Q,R,或,A,B,P,Q,R,结点内用,红边,结点间用,黑边,60,9.3.3 2-3-4树和红黑树17-3*,10,3,