数据结构：思想与方法-翁惠玉-第八章.pptVIP

* 直观的概念 非平衡的二叉查找树的最坏情况：树会有线性的深度，因此，将需要10,000,000次磁盘访问。需要463小时 平均情况：一次成功的查找需要1.38logN次磁盘访问，因为log10,000,000接近于24，那么平均查找将需要32次磁盘访问，也就是5秒钟。 典型情况：在随机构造的树中，某些结点的深度将会是平均深度的三倍，于是就需要100次磁盘访问，即16秒。 假设有10,000,000条记录，再假设这些数据内存里是放不下的，我们一秒钟可以执行两千五百万条指令，或进行6次磁盘访问。 * 解决方法 把磁盘访问次数降低到一个很小的常数，比如说3或者4。 方法：增加树的分叉，就能降低树的高度，即采用M叉查找树 M叉查找树的最佳高度为：logMN * B+树 B+树是满足某些平衡条件的M叉树。 M阶的B+树是具有以下性质的B叉树： 数据项被存贮在叶子中。 非叶子结点至多保存M-1个键来引导查找，键i表示了子树i+1中键的最小值。 根或者是叶子，或者是有2到M个儿子。 除根之外所有的非叶结点的儿子数为 到M之间。这保证了B树不会退化成二叉树。 所有的叶子都在同一层上，并且对于某个L要有 到L个数据项 * 一棵5阶的B+树 每个节点是一个磁盘块 L = 5 查找过程： 35 50 64 8 15 23 30 41 46 55 60 70 79 8 9 11 1 3 5 15 16 18 19 21 23 25 26 27 30 31 32 33 34 35 38 40 41 42 43 44 45 46 47 48 50 51 52 53 55 57 59 60 61 62 64 66 68 70 73 77 79 81 82 * L和M的选择 M的选择：如果每个键要占用32字节。因此在一棵M阶B树中，可以有M-1个键，总的数据量就是32M-32个字节加上M个分支。而且因为每个分支其实是另一个磁盘块的块号，假设分支的大小是4个字节。那么分支就要占去4M个字节。则一个非叶子结点总的内存需要量是36M-32字节。要36M-32不超过8,192的M的最大值是228，于是选择 M=228。 假如每条数据记录要256字节，则一块中可以存储32条记录，所以L就取为32。每个叶子有16到32条数据记录。 外存读写单位为块，一个块存放一个结点能使IO效率最高。假设一个块的容量8,192字节 * B+树的插入 叶结点不满：把新节点插入叶子，重新调整该叶子中数据的顺序 叶子已经装满 ：通过分裂该叶子，形成两个半满的叶子来插入一个新的项 。 更新父节点 如果父亲的儿子数量已经满了，我们就继续分裂父亲。最坏情况要分裂根。这就是为什么根节点允许只有两个孩子。 从树根开始查找应该插入的叶结点 * 插入7 35 50 64 8 15 23 30 40 46 55 60 70 79 8 9 11 1 3 5 7 15 16 18 19 21 23 25 26 27 30 31 32 33 34 35 37 38 40 42 43 44 45 46 47 48 50 51 52 53 55 57 59 60 61 62 64 66 68 70 73 77 79 81 82 * 插入41 35 50 64 8 15 23 30 40 43 46 55 60 70 79 8 9 11 1 3 5 7 15 16 18 19 21 23 25 26 27 30 31 32 33 34 35 37 38 40 41 42 46 47 48 50 51 52 53 55 57 59 60 61 62 64 66 68 70 73 77 79 81 82 43 44 45 * 插入22 19 35 50 64 8 15 40 43 46 55 60 70 79 8 9 11 1 3 5 7 15 16 18 23 25 26 27 30 31 32 33 34 35 37 38 40 41 42 46 47 48 50 51 52 53 55 57 59 60 61 62 64 66 68 70 73 77 79 81 82 43 44 45 23 30 19 21 22 * B+树的删除 删除操作首先查找到要删除的项，然后删除它 如果此时它所在的叶子的元素数量正好满足要求的最小值，删除该项就会使它低于最小值 如果邻居不是最少的情况，就借一个过来领养； 如果邻居也处于最少的情况，就把两个结点合并成一个满的结点。很不幸的是，在这种情况下父亲就失去了一个儿子。如果它引起父亲的儿子数少于了最小值，我们就要使用同样的策略了。这个过程一直向上进行过滤到根。如果在寄养的过程中，根只剩下了一个儿子，就把根删除，让它的儿子作为