第十章文件、外部排序与外部搜索.ppt

第十章 文件、外部排序与外部搜索,主存储器和外存储器 文件组织 多级索引结构 外排序,1,主存储器与外存储器,主存储器又叫内存储器，简称为内存；外存储器简称为外存。外存储器与内存储器相比，优点是：价格较低永久的存储能力缺点：访问外存储器上的数据比访问内存要慢56个数量级要求我们在开发系统时必须考虑如何使外存访问次数达到最少。,2,磁带（tape）,磁带是一种顺序存取设备。磁带主要用于备份、存储不经常使用的数据，以及作为将数据从一个系统转移到另一个系统的脱机介质。,3,磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或者把计算机中的信息写到磁带上去。数据记录在磁带带面上。在带面上并列存放有 9 个磁道的信息，即每一横排有 9 位二进制信息：8 位数据加 1 位奇偶校验位。磁带的存储密度用 BPI（Bit Per Inch）为单位，典型的存储密度有 3 种：6250BPI（=246排/mm）、1600BPI（=64排/mm）、800BPI（32排/mm）。正常走带速度为35m/Sec，因设备而异。,4,数据的传送速度 = 存储密度走带速度。在应用中使用文件进行数据处理的基本单位叫做逻辑记录，简称为记录；在磁带上物理地存储的记录叫做物理记录。在使用磁带或磁盘存放逻辑记录时，常常把若干个逻辑记录打包进行存放，把这个过程叫做“块化”（blocking）。经过块化处理的物理记录叫做块化记录。磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程，在这段时间内走带不,5,稳定，只能走空带，这段空带叫做记录间间隙IRG（Inter Record Gap）或者块间间隙IBG（Inter Block Gap），其长度因设备而异。,6,如果每个逻辑记录是 80个字符，IRG为 0.75英寸，则对存储密度为 1600BPI 的磁带，一个逻辑记录仅占 80/1600 = 0.05英寸。每传输一个逻辑记录磁带走过 0.05英寸，接着磁带要走过一个IRG占0.75英寸。结果大部分时间都花费在走空带上，存储利用率只有1/16。如果将若干逻辑记录存放于一个块，将IRG变成IBG，可以提高存储利用率。例如，将50个有80个字符的逻辑记录放在一个块内，此块的长度将达到5080/1600 = 2.5英寸，存储利用率达到0.77。因此在磁带上采用按块读写。,7,在磁带设备上读写一块信息所用时间tIO = ta + tb其中，ta 是延迟时间，即读写磁头到达待读写块开始位置所需花费的时间，它与当前读写磁头所在位置有关。tb是对一个块进行读写所用时间，它等于数据传输时间加上IBG时间。磁带设备只能用于处理变化少，只进行顺序存取的大量数据。,8,磁盘（disc）,磁盘存储器通常称为直接存取设备，或随机存取设备，它访问外存上文件的任一记录的时间几乎相同。磁盘存储器可以顺序存取，也可以随机存取。目前使用较多的是活动臂硬盘组：若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。,9,10,每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。 每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一个磁道。任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据 。,11,各个记录盘面上半径相同的磁道合在一起称为柱面。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。 一个磁道可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。对磁盘存储器进行一次存取所需时间：当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很快。,12,选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是机械动作，速度较慢。这称为“寻查（seek）”。选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。确定磁道后，还要确定所要读写数据在磁盘上的位置（如在哪一个扇区）。这实际上就是在等待要读写的扇区转到读写磁头下面。这是机械动作。这段时间一般称为旋转延迟（rotational delay）时间。真正进行读写时间。,13,在磁盘组上一次读写的时间主要为： tiotseektlatencytrw其中，tseek是平均寻查时间，是把磁头定位到要求柱面所需时间，这个时间的长短取决于磁头移过的柱面数。tlatency是平均等待时间，是将磁头定位到指定块所需时间。trw是传送一个扇区数据所需的时间。在MS-DOS系统中，多个扇区集结成组，称为簇。簇是文件分配的最小单位，其大小由操作系统决定。在UNIX系统中不使用簇，文件分配的最小单位和读写的最小单位是一个扇区，称为一个块（block）。,14,缓冲区（buffer）,磁盘一次读写操作访问一个扇区，称为访问“一页”（page）或“一块”（block），又称为“一次访外”。为了实施磁盘读写操作，在内存中需要开辟一些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域称为缓冲区。多数操作系统至少设置两个缓冲区，一个为输入缓冲区，一个为输出缓冲区。,15,例如，在从磁盘向内存读入一个扇区的数据时，数据被存放到输入缓冲区，如果下次需要读入同一个扇区的数据，就可以直接从缓冲区中读取数据，不需要重新读盘。缓冲区大小应与操作系统一次读写的块的大小相适应，这样可以通过操作系统一次读写把信息全部存入缓冲区中，或把缓冲区中的信息全部写出到磁盘。如果缓冲区大小与磁盘上的块大小不适配，就会造成存储空间的浪费。缓冲区的构造可以看作一个先进先出的队列。,16,缓冲区的定义及其操作,#include #include const int DefaultSize = 2048;template struct buffer T *data;/缓冲区数组 int current, maxSize;/当前指针, 缓冲区容量buffer (int sz = DefaultSize) : maxSize(sz), current(0) data = new Tsz; assert (data != NULL); buffer() delete data; ,17,void OutputInfo (ostream,18,template void buffer:InputInfo (istream,19,文件组织,什么是文件文件是存储在外存上的数据结构，一般是在逻辑上具有完整意义的一组相关信息项的有序序列。文件分操作系统文件和数据库文件 操作系统中的文件是流式文件：是没有结构的字符流 数据库文件是具有结构的数据集合数据结构中讨论的是数据库文件。操作系统对文件是按物理记录读写的，在数据库中文件按页块存储和读写。,20,文件的基本概念,文件的组成,文件由记录组成；记录由若干数据项组成。记录是文件存取的基本单位，数据项是文件可使用的最小单位。从不同的观点，文件记录分为逻辑记录和物理记录。前者是面向用户的基本存取单位，后者是面向外设的基本存取单位。能够唯一标识一个记录的数据项或数据项集称为主关键码项，其值称为主关键码；不唯一标识一个记录的数据项或数据项集称为次关键码项，其值称为次关键码。,21,文件结构包括文件的逻辑结构、文件的存储结构和文件的操作。文件的逻辑结构是线性结构，各个记录以线性方式排列。文件的存储结构是指文件在外存上的组织方式，它与文件特性有关。 顺序组织直接存取组织（散列组织）索引组织文件的操作是定义在逻辑结构上的，但操作的具体实现要在存储结构上进行。,22,评价一个文件组织的效率执行文件操作所花费的时间文件组织所需要的空间。,23,文件的操作,检索,维护,简单查询范围查询函数查询布尔查询,插入删除修改重构恢复,顺序文件 (Sequential File ),顺序文件中的记录按它们进入文件的先后顺序存放，其逻辑顺序与物理顺序一致。如果文件的记录按主关键码有序，则称其为顺序有序文件，否则称其为顺序无序文件。顺序文件通常存放在顺序存取设备（如磁带）上或直接存取设备（如磁盘）上。当存放在顺序存取设备上时只能按顺序搜索法存取；当存放在直接存取设备上时，可以使用顺序搜索法、折半搜索法等存取。,24,顺序文件的存储方式连续文件：文件的全部记录顺序地存放于外存的一个连续的区域中。优点是存取速度快、存储利用率高、处理简单。缺点是区域大小需事先定义，不能扩充。串联文件：文件记录成块存放于外存中，在块中记录顺序连续存放，但块与块之间可以不连续，通过块链指针顺序链接。优点是文件可以扩充、存储利用率高。缺点是影响了存取和修改的效率。,25,直接存取文件 (Direct Access File),又叫散列文件。利用散列技术组织文件。处理类似散列法，但它是存储在外存上的。文件记录的逻辑顺序与物理顺序不一定相同。通过记录的关键码可直接确定该记录的地址。使用散列函数把关键码集合映射到地址集合时，往往会产生地址冲突，处理冲突有两种处理方式：按桶散列可扩充散列,26,(1) 按桶散列,文件中的记录成组存放，若干个记录组成一个存储单位，称之为桶。假若一个桶能存放m个记录，则m个互为同义词的记录可以存放在同一地址的桶中。当第m+1个同义词出现时，才发生“溢出”。 (a) 溢出链当发生“溢出”时，将第m+1个同义词存放到“溢出桶”。并称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同。当在基桶中检索不成功，就循指针到溢出桶中检索。,27,桶大小为3的溢出桶链表示例,在这种散列文件中删除记录时，因为可能需要重新链接，所以只需做一个逻辑删除标记即可，待系统做周期性重构时再做物理删除。,28,(b) 分布式溢出空间溢出桶按照一定的间隔分布在基桶之间。如果有一个基桶溢出了，系统就将记录存放在下一个溢出桶中。 如果溢出桶自己溢出了，则使用下一个相继的溢出桶，这需要第二次溢出处理。,29,如果系统对基桶按0, 1, 2, 3, 4, 5, 进行编号，在按间隔 G = 5 插入溢出桶后，可按下列公式按字节求出各个桶的实际存储地址：其中，B0是在文件中第0号桶的起始地址，B是每个桶的字节数。在括号中的除数5表示每隔5个基桶安排一个溢出桶。(c) 相继溢出法此方法不设置溢出桶。当记录应存放的桶溢出时，溢出记录存放到下一个相继的桶中。,30,如果该桶已满，就把它放到再下一个桶中，如此处理，直至把记录存放好。相继溢出法的优点是对溢出不需要漫长的寻找。紧邻的桶通常相距不多于一次磁盘旋转。但当邻近的多个桶被挤满时，则为了查找空闲空间就需要检查许多桶。如果桶的容量很小更是如此。,31,H(key) = key % 11,(2) 可扩充散列,这是基于数字搜索树的一种散列方法，细节参见10.5节。,32,散列文件优缺点,散列文件具有随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。散列文件不能顺序存取，只能按关键码随机存取。在经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况。此时需要重新组织文件。,33,索引文件 (Indexed File),索引文件由索引表和数据表（主文件）组成。索引表用于指示逻辑记录与物理记录间的对应关系，它是按关键码有序的表。索引顺序文件：主文件也按关键码有序。此时可对主文件分组，一组记录对应一个索引项。称这种索引表为稀疏索引。索引非顺序文件：主文件中记录未按关键码有序。此时，每一个主文件记录必须对应一个索引项。称这种索引表为稠密索引。,34,静态索引：采用多级索引结构，每一级索引均为有序表。优点是结构简单，缺点是修改很不方便，每次修改都要重组索引。动态索引：采用可动态调整的平衡搜索树结构，如二叉搜索树、B树与B+树等。优点是插入、删除和搜索都很方便。在文件中搜索时，访问外存所花费时间比在内存中搜索所需的时间大得多，因此，外存上搜索一个记录的时间代价主要取决于访问外存的次数，即索引树的高度。,35,36,0 1k 2k 3k 4k 5k 6k 7k,索引表,数据表,索引非顺序文件示例,索引顺序文件示例,当记录在外存中有序存放时，可以把所有n个记录分为b个子表 (块) 存放，一个索引项对应数据表中一组记录 (子表)。,37,对索引顺序文件进行搜索，一般分为两级:先在索引表ID中搜索给定值K, 确定满足 IDi-1.max_key < K IDi.max_key的 i 值, 即待查记录可能在的子表的序号。然后再在第 i 个子表中按给定值搜索要求的记录。索引表是按max_key有序的, 且长度也不大,可以折半搜索，也可以顺序搜索。各子表内各个记录如果也按关键码有序, 可以采用折半搜索或顺序搜索; 如果不是按关键码有序, 只能顺序搜索。,38,索引顺序文件的搜索成功时的平均搜索长度 ASLIndexSeq = ASLIndex + ASLSubList其中, ASLIndex 是在索引表中搜索子表位置的平均搜索长度，ASLSubList 是在子表内搜索记录位置的搜索成功的平均搜索长度。设把长度为n的表分成均等的b个子表，每个子表s个记录，则b = n/s。又设表中每个记录的搜索概率相等，则每个子表的搜索概率为1/b，子表内各记录的搜索概率为 1/s。若对索引表和子表都用顺序搜索，则索引顺序搜索的搜索成功时的平均搜索长度为 ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1,39,索引顺序文件的平均搜索长度与表中的记录个数n有关，与每个子表中的记录个数s有关。在给定n的情况下，s 应选择多大？用数学方法可导出, 当 s = 时, ASLIndexSeq取极小值 +1。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，还要受到页块大小的制约。若采用折半搜索确定记录所在的子表, 则搜索成功时的平均搜索长度为 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2(1+n / s ) + s/2,40,倒排表 (Inverted Index List),对包含有大量数据记录的数据表或文件进行搜索时，最常用的是针对记录的主关键码建立索引。主关键码可以唯一地标识该记录。用主关键码建立的索引叫做主索引。主索引的每个索引项给出记录的关键码和记录在表或文件中的存放地址。但在实际应用中有时需要针对其它属性进行搜索。例如，查询如下的职工信息： (1) 列出所有教师的名单； (2) 已婚的女性职工有哪些人？,这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中去顺序搜索，搜索效率极低。因此，除主关键码外，可以把一些经常搜索的属性设定为次关键码，并针对每一个作为次关键码的属性，建立次索引。在次索引中，列出该属性的所有取值，并对每一个取值建立有序链表，把所有具有相同属性值的记录按存放地址递增的顺序或按主关键码递增的顺序链接在一起。,42,43,0 1k 2k 3k 4k 5k 6k 7k,索引表,数据表,索引非顺序文件示例,次索引的索引项由次关键码、链表长度和链表本身等三部分组成。例如，为了回答上述的查询，我们可以分别建立“性别”、“婚否”和“职务”次索引。,44,性别次索引,次关键码 男 女 计 数 5 3 地址指针,指针 03 08 17 24 47 51 83 95,45,婚否次索引,职务次索引,(1) 列出所有教师的名单；(2) 已婚的女性职工有哪些人？通过顺序访问“职务”次索引中的“教师”链，可以回答上面的查询(1)。通过对“性别”和“婚否”次索引中的“女性”链和“已婚”链进行求“交”运算，就能够找到所有既是女性又是已婚的职工记录，从而回答上面的查询(2)。倒排表是次索引的一种实现。在表中所有次关键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的记录。在次索引中记录记录存放位置的指针可以用主关键码表示: 可通过搜索次索引确定该记录的主关键码, 再通过搜索主索引确定记录的存放地址。,46,在倒排表中各个属性链表的长度大小不一,管理比较困难。为此引入单元式倒排表。在单元式倒排表中, 索引项中不存放记录的存储地址, 而是存放该记录所在硬件区域（即存储区域）的标识。硬件区域可以是磁盘柱面、磁道或一个页块, 以一次 I / O 操作能存取的存储空间作为硬件区域为最好。,47,为使索引空间最小, 在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数, 整个次索引形成一个(二进制数的) 位矩阵。例如, 对于记录学生信息的文件, 次索引可以是如图（下页）所示的结构。二进位的值为 1 的硬件区域包含具有该次关键码的记录。,48,49,单元式倒排表结构,50,针对一个查询：找出所有广东籍学建筑的男学生。可以从“性别”、“籍贯”、“专业”三个次索引分别抽取属性值为“男”、“广东”、“建筑”的位向量，按位求交，求得满足查询要求的记录在哪些硬件区域中，再读入这些硬件区域，从中查找所需的数据记录。由运算结果可知，在硬件区域1，中有所需的记录。然后将硬件区域1，等读入内存，在其中进行检索，就可取出所需记录。,多级索引结构,51,当数据记录数目特别大，索引表本身也很大，在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。此时, 可以建立索引的索引(二级索引)。二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引的索引(三级索引)。这时, 访问外存次数等于读入索引次数再加上1次读取记录。必要时, 还可以有4级索引, 5级索引, 。,多级索引结构常用 m 叉树表示，称为m路搜索树。m路搜索树可能是静态索引结构，即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。m路搜索树还可能是动态索引结构, 即在整个系统运行期间, 树的结构随数据的增删及时调整, 以保持最佳的搜索效率。,52,53,多级索引结构形成 m 路搜索树,ISAM (索引顺序存取方法文件),它是静态索引结构。典型的例子是对磁盘上的数据文件建立盘组、柱面、磁道三级地址的多级索引。ISAM文件用柱面索引对各个柱面进行索引。一个柱面索引项保存该柱面上的最大关键码（最后一个记录）以及柱面开始地址指针。如果柱面太多，可以建立柱面索引的分块索引，即主索引。主索引不太大，一般常驻内存。,54,55,在每个柱面上，所有数据记录存放于基本区，此外保留一部分磁道作为溢出区。所有记录在基本区按关键码升序排列，后一磁道所有记录的关键码均大于前一磁道所有记录的关键码。在一个柱面上所有记录分布在一系列磁道上，通过磁道索引进行搜索。磁道索引一般放在每个柱面上第0号磁道中，每个磁道索引的索引项由两部分组成：,56,基本区索引项存放本磁道在基本区最大关键码（在基本区该磁道最后一个记录）和本磁道在基本区的开始地址，溢出区索引项存放本磁道在溢出区最大关键码和本磁道在溢出区中溢出记录链（有序链表）的第一个结点地址。在某一磁道插入一个新记录时，如果原来该磁道基本区记录已经放满，则根据磁道索引项指示位置插入新记录后，把最后的溢出记录（具有最大关键码）移出磁道基本区，再根据溢出索引项将这个溢出记录放入溢出区，并以有序链表插入算法将溢出记录链入。,57,动态索引结构,现在我们所讨论的 m 路搜索树多为可以动态调整的多路搜索树，它的递归定义为：一棵 m 路搜索树, 它或者是一棵空树, 或者是满足如下性质的树：根最多有 m 棵子树, 并具有如下的结构： ( n, P0, K1, P1, K2, P2, , Kn, Pn ) 其中, Pi 是指向子树的指针, 0in<m; Ki 是关键码, 1in<m。 Ki < Ki+1, 1i < n。,58,动态的 m 路搜索树,在子树 Pi 中所有的关键码都小于 Ki+1, 且大于 Ki，0 < i < n。在子树 Pn 中所有的关键码都大于Kn；在子树 P0 中的所有关键码都小于 K1。子树 Pi 也是 m 路搜索树，0i < n 。,59,一棵3路搜索树的示例,35,20 40,a,b,c,d,e,25 30,10 15,45 50,M路搜索树的C+描述,const int MaxValue = ;/关键码集合中不可能有的最大值template struct MtreeNode /树结点定义 int n;/索引项个数 MtreeNode *parent;/父结点指针 T keym+1; /keym为监视哨，key0未用 int *recptrm+1;/索引项记录起始地址指针MtreeNode *ptrm+1;/子树结点指针，ptrm在插入溢出时使用;,60,template /搜索结果三元组struct Triple MtreeNode *r;/结点地址指针 int i; /结点中关键码序号i int tag;/tag=0,成功; =1,失败;template class Mtree /m叉搜索树定义protected: MtreeNode *root;/根指针 int m;/路数public: Triple Search(const T,61,AVL树是 2 路搜索树。若已知 m 路搜索树的度 m 和它的高度 h, 则树中的最大结点个数为：每个结点中最多有m-1个关键码，在一棵高度为 h 的m路搜索树中关键码最大个数为mh-1。高度h=3的二叉搜索树, 关键码最大数为7；高度h=4的3路搜索树, 关键码最大数为34-1 = 80。,62,m路搜索树的搜索算法,在 m 路搜索树上的搜索过程是一个在结点内搜索和自根结点向下逐个结点搜索的交替的过程。,63,template Triple Mtree:Search (const T /p是扫描指针,q是p的父结点指针 int i = 0；,64,while (p != NULL) /从根开始检测 i = 0; p->key(p->n)+1 = MaxValue; while (p->keyi+1 keyi+1 = x) /搜索成功 result.r = p; result.i = i+1; result.tag = 0; return result; q = p; p = p->ptri;/本结点无x, q记下当前结点, p下降到子树 GetNode(p);/从磁盘上读取结点p result.r = q; result.i = i; result.tag = 1; return result; /搜索失败,返回插入位置;,65,提高搜索树的路数 m, 可以改善树的搜索性能。对于给定的关键码数 n，如果搜索树是平衡的，可以使 m 路搜索树的性能接近最佳。下面将讨论一种称之为B 树的平衡的 m 路搜索树。,66,B 树,一棵 m 阶B 树是一棵平衡(balanced)的 m 路搜索树, 它或者是空树, 或者是满足下列性质的树：根结点至少有 2 个子女。除根结点以外的所有结点 (不包括失败结点)至少有 m/2 个子女。所有的失败结点都位于同一层。在B 树中的“失败”结点是当 x 不在树中时才能到达的结点。这些结点实际不存在，指向它们的指针为NULL。它们不计入树的高度。,67,注意，m阶B树继承了m路搜索树的定义。原来m路搜索树定义中的规定在m阶B树中都保留。事实上，在B 树的每个结点中还包含有一组指针recptrm+1，指向实际记录的存放地址。keyi与recptri (1in<m) 形成一个索引项 (keyi, recptri)，通过keyi可找到某个记录的存储地址recptri。在讨论B树结构的操作时先不涉及recptri，因此在后续讨论中该指针不出现。,68,69,B树类和B树结点类的定义,template class Btree : public Mtree /B树类定义/继承m叉搜索树的所有属性和操作，/Search从Mtree继承， MtreeNode直接使用public: Btree();/构造函数 bool Insert (const T,70,B 树的搜索算法,B树的搜索算法继承了m路搜索树Mtree上的搜索算法。B树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。搜索成功，报告结点地址及在结点中的关键码序号；搜索不成功，报告最后停留的叶结点地址及新关键码在结点中可插入的位置。B 树的搜索时间与B 树的阶数 m 和B 树的高度h直接有关, 必须加以权衡。,71,在B 树上进行搜索, 搜索成功所需的时间取决于关键码所在的层次; 搜索不成功所需的时间取决于树的高度。定义B树的高度h为叶结点（失败结点的双亲）所在的层次，那么，树的高度h与树中的关键码个数 N 之间有什么关系？如果让B树每层结点个数达到最大（m-1），且设关键码总数为N, 则树的高度达到最小：Nmh-1 hlogm(N+1)如果让m阶B树中每层结点个数达到最少，则,72,B 树的高度可能达到最大。设树中关键码个数为N，从B 树的定义知： 1层：1个结点 2层：至少2个结点 3层：至少2 m/2 个结点 4层：至少2 m/2 2 个结点 如此类推， h层：至少有2 m/2 h-2 个结点。所有这些结点都不是失败结点。失败结点在第h+1层，失败结点个数为N+1。,73,这是因为树中关键码有N个，而失败数据一般与已有关键码交错排列。因此，有N+1 = 失败结点数 = 位于第h+1层的结点数 2 m/2 h-1 N2 m/2 h-1-1 h-1log m/2 (N+1)/2) hlog m/2 (N+1)/2)+1示例：若B 树的阶数 m = 199, 关键码总数 N = 1999999，则B 树的高度 h 不超过log100 1000000 +1= 4,74,m值的选择,如果提高B 树的阶数 m, 可以减少树的高度, 从而减少读入结点的次数, 因而可减少读磁盘的次数。事实上，m 受到内存可使用空间的限制。当 m 很大超出内存工作区容量时，结点不能一次读入到内存，增加了读盘次数，也增加了结点内搜索的难度。 m值的选择：应使得在B 树中找到关键码 x 的时间总量达到最小。,75,这个时间由两部分组成：从磁盘中读入结点所用时间在结点中搜索 x 所用时间根据定义, B 树的每个结点的大小都是固定的, 结点内最多有m-1个索引项 (keyi, recptri, Pi), 1i < m。设 keyi 所占字节数为，recptri 和 Pi 所占字节数为，则结点大小近似为 m(+2) 个字节。读入一个结点所用时间为： tseek+ tlatency+ m(+2) ttran = a + bm,76,B 树的插入,B 树是从空树起, 逐个插入关键码而生成的。在B 树中每个非失败结点的关键码个数都在 m/2 -1, m-1 之间。插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超出了上界 m-1，则结点需要“分裂”，否则可以直接插入。实现结点“分裂”的原则是：设结点 p 中已经有 m-1 个关键码，当再插入一个关键码后结点中的状态为,77,( m, P0, K1, P1, K2, P2, , Km, Pm) 其中 Ki < Ki+1, 1 i < m这时必须把结点 p 分裂成两个结点 p 和 q，它们包含的信息分别为： 结点 p： ( m/2 -1, P0, K1, P1, , Km/2 -1, Pm/2 -1) 结点 q： (m-m/2, Pm/2, Km/2+1, Pm/2+1, , Km, Pm)位于中间的关键码 Km/2 与指向新结点 q 的指针形成一个二元组 ( Km/2, q )，插入到这两个结点的双亲结点中去。,78,79,结点“分裂”的示例,80,示例:从空树开始加入关键码建立3阶B树,在插入新关键码时，需要自底向上地分裂结点，最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂。,81,若设B 树的高度为h,则在自顶向下搜索到叶结点的过程中需要进行 h 次读盘。,B 树的删除,在B 树上删除一个关键码时，若结点中所剩关键码个数少于下限，要考虑结点的调整或合并问题，删除过程如下： 首先需要找到这个关键码所在的结点, 从中删去这个关键码。若该结点不是叶结点，且被删关键码为 Ki，1in, 则在删去该关键码之后, 应以该结点 Pi 所指示子树中的最小关键码 x 来代替被删关键码 Ki 所在的位置;然后在 x 所在的叶结点中删除 x。,82,在叶结点上的删除有 4 种情况。被删关键码所在叶结点同时是根结点且删除前该结点中关键码个数n2，则直接删去该关键码并将修改后的结点写回磁盘。被删关键码所在叶结点不是根结点且删除前该结点中关键码个数 nm/2 , 则直接删去该关键码并将修改后的结点写回磁盘, 删除结束。,83,84,85,被删关键码所在叶结点删除前关键码个数 n = m/2 -1, 若这时与该结点相邻的右兄弟 (或左兄弟) 结点的关键码个数 nm/2，则可按以下步骤调整该结点、右兄弟 (或左兄弟) 结点以及其双亲，以达到新的平衡。将双亲结点中刚刚大于 (或小于) 该被删关键码的关键码 Ki (1in) 下移；将右兄弟 (或左兄弟) 结点中的最小 (或最大) 关键码上移到双亲结点的 Ki 位置；将右兄弟 (或左兄弟) 结点中的最左 (或最右) 子树指针平移到被删关键码所在结点,86,中最后 (或最前) 子树指针位置；在右兄弟 (或左兄弟) 结点中，将被移走的关键码和指针位置用剩余的关键码和指针填补、调整。再将结点中的关键码个数减1。,87,88,被删关键码所在叶结点删除前关键码个数 n = m/2 -1，若这时与该结点相邻的右兄弟 (或左兄弟) 结点的关键码个数 n = m/2 -1, 则必须按以下步骤合并这两个结点。,若要合并 p 中的子树指针 Pi 与 Pi+1 所指的结点, 且保留 Pi 所指结点, 则把 p 中的关键码 Ki+1下移到 Pi 所指的结点中。把 p 中子树指针 Pi+1 所指结点中的全部指针和关键码都照搬到 Pi 所指结点的后面。删去 Pi+1 所指的结点。 在结点 p 中用后面剩余的关键码和指针填补关键码 Ki+1 和指针 Pi+1。修改结点 p 和选定保留结点的关键码个数。,89,在合并结点的过程中, 双亲结点中的关键码个数减少了。若双亲结点是根结点且结点关键码个数减到 0, 则将该双亲结点删去, 合并后保留的结点成为新的根结点; 否则将双亲结点与合并后保留的结点都写回磁盘, 删除处理结束。若双亲结点不是根结点且关键码个数减到m/2 -2，又要与它自己的兄弟结点合并, 重复上面的合并步骤。最坏情况下这种结点合并处理要自下向上直到根结点。,90,91,92,93,94,95,B+树,B+ 树是B 树的变种，它与B 树的不同之处在于：所有关键码都存放在叶结点中，上层的非叶结点的关键码是其子树中最小（或最大）关键码的复写。叶结点包含了全部关键码及指向相应数据记录存放地址的指针，且叶结点本身按关键码从小到大顺序链接。每个非叶结点结构有两种方式处理。按下层结点“最大关键码复写”和“最小关键码复写”。,96,按“最大关键码复写”原则组织,一棵m阶B+ 树的结构定义如下：每个结点最多有 m 棵子树；根结点最少有 1 棵子树，除根结点外，其他结点至少有 m/2 棵子树；有 n棵子树的结点有 n 个关键码。所有非叶结点可以看成是叶结点的索引，结点中关键码Ki 与指向子树的指针Pi 构成对子树 (即下一层索引块) 的索引项 ( Ki, Pi )，Ki 是子树中最大的关键码。,97,所有叶结点在同一层，按从小到大的顺序存放全部关键码，各个叶结点顺序链接。叶结点中存放的是对实际数据记录的索引，每个索引项 ( Ki, Pi ) 给出数据记录的关键码及实际存储地址。例如，在一棵4阶B+ 树中，所有非叶结点中的子树棵数2n4，其所有的关键码都出现在叶结点中，且在叶结点中关键码有序地排列。上面各层结点中的关键码都是其子树上最大关键码的副本。,98,通常在B+ 树中有两个头指针：一个指向B+ 树的根结点，一个指向关键码最小的叶结点。因此，可以对B+ 树进行两种搜索运算：循叶结点自己拉起的链表顺序搜索；从根开始进行自顶向下直到叶结点的随机搜索。,99,root,B+ 树的插入,B+ 树的插入仅在叶结点上进行。每插入一个(关键码-指针) 索引项后都要判断结点中的索引项个数是否超出范围m。当插入后叶结点中的关键码个数n > m时，需要将叶结点分裂为两个结点：它们包含的关键码个数分别为 (m+1)/2 和 (m+1)/2。并且它们的双亲结点中应同时包含这两个结点的最大关键码和结点地址。在非叶结点中关键码的插入与叶结点的插入情,100,况类似，但在做根结点分裂时，必须创建新的父结点，作为树的新根。例如，在一棵4阶B+树中的插入过程如下。,101,102,B+树的删除,B+ 树的删除仅在叶结点上进行。当在叶结点上删除一个(关键码-指针)索引项后，结点中的索引项个数仍然不少于 m/2，这属于简单删除，其上层索引可以不改变。如果删除结点的最大关键码，但因在其上层的副本只起了一个引导搜索的“分界关键码”的作用，所以即使树中已经删除了关键码，但上层的副本仍然可以保留。 如果在叶结点中删除后，结点中索引项个数小于 m/2，必须做结点的调整或合并工作。如果右兄弟结点中的子树棵数大于 m/2，从右兄弟结点中移最左的（关键码-指针）索引项到这个被删关键码所在的结点，并修改上层的“分界关键码”的值。,