大家好。数据结构与算法 这一讲，我们继续第十一章索引的学习。 Hello everybody! In this lecture, we will continue Chapter 11 about data structures and algorithms.
今天我们介绍 索引里面的B+ 树动态索引。 Today we introduce B + tree dynamic index.
B+树，它是B树的一种变形。 在这个叶结点上，所有的关键码都出现。 The B + tree is a deformation of the B tree. On this leaf node, all of the keys will appear.
而这些非叶结点是底层的它的一些子结点 中，我们把这个子结点框的 最大的关键码进行一下复写。 And the non-leaf nodes in a relay node are at the bottom of their leaf nodes. We rewrite the biggest keys in the frame of the child nodes.
当然我们也可以用最小关键码来复写。 我们来看一下B+树的定义。 Of course, we also can use minimum keys to rewrite. Then we take a look at the definition of the B + tree.
跟B树类似,B+树它的阶 也是根据我们外层的这个磁盘页块的大小， 以及你的这个关键码域和相应的指针域，它所占用的空间的大小，然后计算出来的。 Similar to B tree, the order of B + tree is also calculated based on the size of the outer layer of the page of the disk, the primary key domain and corresponding pointer domain and the size of the space it occupies.
因此我们最大就不能超过 这个设定的m这样的一个阶。 Thus, for maximum, we cannot exceed the order like the m we set.
为了使得我们这个动态树比较好维护， 我们是允许它有一定的这样的就是不满的情况。 In order to make our dynamic tree easier to maintain, we allow it to have certain situations that are not full.
但是为了让它的空间效率也不至于太低，因此我们 是规定在一个全满到半满之间。 所以它的这样的一个阶的下界是2分之m。 But in order to make its space efficiency not too low, we set it to be between half full and completely full, so the lower bound of such an order is m/2.
，我们也是允许根结点可以有 只有两个子结点的特殊情况。 We also allow the special case that the root node have two child nodes.
不同于B树，B+树，它如果是 有k 个子结点，一定是有k个关键码。 Different from B tree, if the B+ tree has k child nodes, then it must have k primary keys.
这样的话，我们就使得这个 关键码是跟我们的这样的一个指向 子结点的指针，它其实是一对一对的。 Then we have to let the primary key match the pointer pointing to the child node.
而，我们在这个 叶层，这个关键码和它的这样的一个指针对， 指向的是这个关键码在 主文件里面的信息的存储地址。 The primary key matches the pointer of the leaf level; it points to the information storing address of the primary key inside the main file.
这样的话，我们B+树它就有非常高的一个存储的效率。 Then, our B+ tree has a very high storing efficiency.
也可以说，它几乎就没有被浪费的空指针。 而我们还可以在叶层 把这些结点，给它串起来。 In another word, it doesn’t have any wasted blank pointer. We can also connect these nodes in the leaf level.
串起来以后，我们就可以支持一个 这样的范围的查找。 我们来看这个3阶B树的一个检索的例子。 After we connect these nodes, we can support such a searching range.
如果是我要检索的这个关键码 是47，因为这个B+树 它是对这个子结点的最大关键码的一个复写， 因此，我们就会找到70是 大于47的最紧的关键码。 我们就沿着70 所指向的这个子结点，继续往下找。 If the primary key I want to search for is 47, then because this B+ tree is a rewrite of the maximum key of the child node, we will find 70 as the key which is greater than and closest to 47. Then we follow the child node that 70 is pointing to and keep looking. ，
接着找，我们找到50是这个最紧的这样的一个关键码。 We keep searching, and we find 50 is the closest primary key.
因此，在沿着它的这个子结点的指针找到了这个叶层。 ，在叶层里面我们找到了47这个关键码。 Thus, we follow the pointer of the child node and fine the leaf level. Then we find the primary key 47 in the leaf level.
但是，我们还要顺着 47 这个关键码，它所指向的自己在 主文件里面的这个地址的指针。 But then, we still have to follow the primary key 47 and the pointer in the address in the main file that it points to.
然后 再到这个主文件的相应位置，把这个47 所对应的首现的这些信息都给它拿出来。 我们来看一下B+树的插入。 Then, we go to the corresponding position in the main file, take out all the information that 47 is corresponded to. Now, let’s look at B+ tree’s insertion.
B+树的插入，跟查找是类似的。 插入就是一个失败的查找的过程。 我们如果是说没有找到这个关键码，我就可以在 落在叶层的结点 插入我们相应的这个新的关键码。 The insertion of the B+ tree is similar to searching. Insertion is a failed process of searching. If we did not find the primary key, we can insert the primary key at the corresponding node in the leaf level.
如果是说插入了以后， 它这个结点没有发生上溢出，我们的插入 就 可以完成。 If we insert it and does not cause overflow on this node, then our insertion is able to complete.
当然，还要注意，在它的这些 祖先路径上头的这些分界关键码 它的一些复写的信息是不是正确。 如果是在这个叶层，我们插入以后发生了上溢出， 这个结点，就需要分裂成两个新的结点。 而且，在父层，要添加一个复写关键码和指向这个新结点的指针。 我们来看一个例子。 Of course, we have to be careful about whether some rewritten information on these dividing primary key’s address is correct. If it causes overflow in the leaf level when we insert the primary key, then the node would split into two new nodes. In the father level, we have to add a primary key for rewriting and a pointer to the new node.
在这个3 阶B+树里面，我们要插入15。 我顺着这个根一直找到结点e。 然后我们插入15以后，它会发生一个上溢出。 我们就分裂成两个新的结点。 然后，在父层我们会要产生一个 新的一个关键码的复写这样的一个分界。 然后，我们也要产生一个新的指针对应着刚才的这个复写的关键码。 In the three-level B+ tree, we want to insert 15, so we follow the root to find the node. When we insert 15, it will have an overflow and the node will split into two new nodes. Then in the father level, we have a new primary key for rewriting and a new pointer to the new primary key.
，在父结点也发生了上溢出，我们继续分裂。 这个分裂，我们就一直传到了根。 ，根结点，它也是被分裂成两个新的结点。 然后，我们需要产生一个新的根结点。 ，它分别指向刚才的个旧根结点和，一个新的 结点。在插入之后，我们发现树高可能会增高一层。 Then, there will be overflow at the father node, we continue to split. This split leads to the root. The root node is also split into two new root nodes. Then we need to create a new root node which point to the old root node and a new node. After insertion, we found that the tree will increase a level.
我们再来看一下删除的情况。 删除，当然它就是对应到一个成功的检索。 一直检到叶结点。 然后，我们在发现这个的这个 关键码以后，我们在相应的这个叶结点 进行删除。如果没有下溢出，我们这个 删除也是可以结束。 Now, let’s look at the situation of deleting. Deleting is corresponding to a successful search. We keep searching to the leaf node. Then after we found the third-generation primary key, we delete at the corresponding leaf node. If there is not overflow, then we can end the deleting process.
当然，也是要注意， 我们是不是需要在这个父结点以及这个祖先路径上 些分界关键码的正确性。 Then, we have to check whether the primary key on the father node and its address is correct.
因为 在我们这个B+树里面，我们定义的是 对子结点的这里面最大关键码的一个复写。因此，在 删除的情况，其实最上层的复本它不进行修改也是可以保证正确性的。 当然我们为了让自己在做题的时思路清晰一些， 你可以也多把它修改成一致的情况。 It’s because, in the B+ tree, our definition is a rewrite of the maximum primary key on the child node. Therefore, in the situation of deleting, the rewrite on the top level is correct without correction. Of course, if we want to be clearer, we can change it to a matching form.
在删除以后，如果是发生下溢出，我们就可能是 跟这个B树一样要进行一些调整。 If there is overflow after deleting, then we need to make adjustment like the B tree.
这个调整也是，我们先看一下， 他们的左右这个兄弟 是不是可以借关键码。 This adjustment, we have to check whether we can borrow primary key from the neighbors.
如果可以借， 我就是先借。 借完以后也是把这个关键码平分， 它可能是需要进行调整的。 If we can borrow, then we borrow. After we borrow, we equally divide the primary key and then rewrite. It might need adjustment as well.
我们来看一下在 这个3阶的B+树里面删除关键码75。 我们找到这个叶里面的75这个关键码。 Let’s see. If we want to delete 75 from this three-level B+ tree, we find the primary key 75 in the leaves.
删除以后，它发生了下溢出。因为它没有 左兄弟，就只能看右兄弟。右兄弟也是个临界的状态。 After we delete it, there is overflow. That’s because it doesn’t have neighbors on the left. Its neighbor on the right is at the 0 state.
所以，我们借不了关键码，只能是跟右兄弟合并。 合并以后，在它的父结点这一个地方，我们要删除一个 分界的关键码和指针对。 So, we can’t borrow the primary key, we can only merge with the neighbor on the right. After merging, we have to delete a primary key and its pointer at the father node.
然后， 在父这一层也发生了一个下溢出。我们就 也需要去看一下能不能够借关键码 进行一个微调，在这一层，我们发现 父的这样的一个亲兄弟这个左兄弟可以借关键码。 Then, there will be overflow on the father level. We check whether we can borrow primary key, make slight adjustment. We discover that the father node can borrow primary node from its neighbors on the left.
我们借过来。 然后，同样的它所对应的这个子结点 也要移过来，就是关键码，它是跟一个 指针指向的这个子结点是有关联的。 We borrow it, as well as moving the corresponding child node. The primary key is related to the child node pointed by a pointer.
我们都移过来以后， 在这个根这一层 对应的样的一个关键码的复写，它是需要修改的。否则就不一致了。 After we moved everything, on the root level, the corresponding rewrite of the primary key needs to be corrected; otherwise it wouldn’t match.
我们还有一些其他的B+树的变种 例如我们看一下这个B+树。 它相同的地方就是在叶结点还是这些关键码的一个全级。 We have some variations of the B+ tree. For example, let’s look at this B+ tree, the similarity is that the leaf node is a full level of the primary key.
不同就是在这个非叶结点它不是像我们刚才的这样的一个复写的形式， 在这个结构里面 我们的分叶节点它其实是类似于我们上一节讲讲的 B树的情况 每一个这个内部结点它如果是拥有 K个关键码，它就有K+1个这样的指向子结点的指针。 The difference is that the non-leaf node is not in the form of a rewrite. In this organization, our divided leaf node is similar to the ones of the B tree in our last lecture. If every inner node had k primary keys, then it has k+1 pointers to the child node.
我们在中序情况下来编列这个非叶层的这些结点 可以得到一个正序的序列。 在这样的一个定义下我们的 叶结点和内部结点，它的阶可以不一致， 你根据这个内部结点它所需要的这些索引的信息 和叶结点需要的索引信息你分别去计算它可以拥有不同的阶。 我 们看一下在这个B+树的 例子中，我们删除关键码33的一个情况。 If we compile the nodes in the divided leaf level under an infix order, we can get a prefixed sequence. Then under such a definition, the order for the leaf node and the inner node doesn’t have to match. Based on the indexed information that the inner node and the leaf node need, we can calculate the different orders that it can have. Let’s look at the B+ tree. In our example, let’s look at the case where we delete a primary key 33.
首先虽然说在这个分叶层 它们的这个关键码并没有复写的情况 也就是说他们在中序编列下是一个顺序的一个序列， 但是我们一直是要 检到叶层。 First, even though the primary key doesn’t have a rewrite in the divided leaf level, or in another word, they have a prefixed sequence under an infix order, we still have to search till the leaf level.
我们删除33以后，这个结点也发生下溢出， 我们看一下右边也不能够借，就把这两个结点合并。 而且在副结点我们删掉个分界的这个关键码和 相应的指针这个时候在父亲层也发生了下溢出， 它就向它的这个左边的亲兄弟去借关键码。 After we delete 33, the node has an overflow. We cannot borrow from the right neighbor, so we merge the two nodes. We deleted the dividing primary key and the corresponding pointer at the sub-node, so we have overflow at the negative level as well, so it will borrow primary key from its left neighbor.
可以借的情况下我们 就把它借了过来。 我们再来看一下， 对于B树和B+树它们的效率。 首先我们来看一下对B+树。 如果是我们有N个记录， 每一个记录里面它只能容纳 m个这样的关键码 加指针的二元对，假设我们关键码和指针的大小是一样的情况。 If we can borrow, we borrow. Then let’s look at the efficiency of the B tree and the B+ tree. Let’s look at the B+ tree first. If we have N records and every record can only contain m binary pairs of primary keys and pointers, we assume that our primary key and pointer are of the same size.
好，对于B+树来说，我们每一个结点 正好是只需要 关键码加指针这样的若干个二元对，我们并没有 其他的这些指针信息。 当然我们对叶结点里面的顺序拉链我们可以先不考虑它，个不是必要的。 我们在内部结点和叶结点都是这样，就是 每一个关键码对应的是关键码 和它的一个子结点的一个地址，样的一个对，二元对。 To the B+ tree, every node only needs a certain binary pairs of primary keys and pointers; we don’t need other information on the pointers. We don’t have to consider the prefix chain in the leaf node; it’s unnecessary. Our inner node and leaf node are the same, every primary key correspond to a primary key and an address of its child node, such a binary pair.
在叶层我们是一个关键码再加上 它的主的一个存储地址的二元对。 假设B+树，它是一个介于 半满到全满之间的一种情况。平均来说就是75%满。 On the leaf level, we have a binary pair of a primary key and its main storing address. Assume that the B+ tree is between a half-full and completely full situation, the average would be 75% full.
这样的话我们这个B+树的高度就是以 0.75m为底N的对数。 我们再来看一下B树， B树的情况它是比较特殊的。 This way, the height of the B+ tree is a log base 0.75m. Let’s look at the B tree. The B tree has a special case.
我们要注意，除了关键码和子结点这样的 一对以外，我们其实还有对每个关键码它都有 隐含指针。 We have to be careful that besides the pair of the primary key and the child node, every primary key has a hidden pointer.
这个隐含指针就是指向的这个关键码所对应的记录 在主文件里面的存储地址。 The hidden pointer is pointing to the address in the main file of the records corresponded to the primary key.
因此我们可以简略的来看，对于一个B树 它每一个结点里面的这个关键码对应的要带两个指针。 So, we can look at this simply. For a B tree, the primary key in every node corresponds to two pointers.
这种情况下 我们前面只能够容纳这样的m对关键码和 指针的这个信息，而你这里又多了一个指针信息，当然我们假设关键码 和指针占有的空间是一样的情况。 Under this case, we used to only contain m pairs of primary key and pointers, but now, we have another piece of pointer information, of course, we are assuming the space the primary key takes and the space the pointer takes is the same.
这种情况，我们这么一个B树它就是 只能是0.67m的阶。 So, our B tree has an order of 0.67m.
假设B树的充盈度也是75%， 这样的情况下 B树结点它的子结点的个数就只能有0.5m个。 Assuming the completeness of B tree is 75%, then the number of child nodes of the B tree’s node can only be 0.5m.
因此 在同样的情况下这个B树的高度就是以 0.5m为底N的对数这样一个高度，它显然比刚才样一个 B+树的0.75m为底的这样的一个 树就会要高很多。 Therefore, the height of the B tree is log N base 0.5m. It obviously is higher than the B+ tree which is base 0.75m.
B+树因为它的存储效率比 B树要高，它的检索效率也更高。 So, the storing efficiency of the B+ tree is higher than the B tree, so its searching efficiency is also higher.
而且我们前面也提到过 在叶结点这一层我们可以拉上这样的一个双向的链。 We mentioned before, we can zip a double-direction chain in the level of the leaf node.
它就更好的支持范围检索。 在数据库里面我们对主码的索引是 更广泛的用到了B+树。 It can better support range retrieval. In databases, we are more likely to use B+ tree for primary key indexing.
主码的这个情况它一般来说 重复的这个关键码不多，或者说我们几乎就不允许它重复， 在这种情况下B+树的索引效率是很高的。 The primary key hardly has any repeated primary key, so the indexing efficiency of the B+ tree is very high.
还有就是我们基于B+树的这个磁盘的虚拟存储管理系统 就完全取代了基于多分树的ISAM系统。 Also, the virtual memory management system of the disk based on the B+ tree completely replaces the ISAM system based on the multi-branch tree.
我们这个VSAM的组织其实是这么一个形式。 在最底层我们可以看到它的整个 数据区域，然后我们先建立一个顺序的索引。 Our VSAM system is in such a form. We can see its entire data region from the lowest level, then we establish a prefix index.
在这个顺序索引之上，我们再建立树形的B+树的索引。 Above the prefix index, we then establish the B+ tree’s index.
这个的存储效率就比ISAM要高很多， 而且它可以很好的动态维护。 最后留给大家几个思考，首先就是我们可以去研究一下是不是能够有 2阶的B+树？ So the storing efficiency is much higher than the one of the ISAM system, also, it can do a very good job on dynamic maintenance. Finally, I have a couple thinking questions: first, we can research whether there can be a second-order B+ tree.
另外就是我们再好好想一想 为什么B+树比B树的存储效率也要高？ Then, we can think about why the storing efficiency of the B+ tree is higher than that of the B tree.
另外就是如果大家感兴趣，可以查阅一下数据库的相关文件， 看一下在数据库里面对主码的索引 B+树起到了什么样的作用。 Finally, it you guys are interested, you can check out related materials on database and see what effect the indexing to the primary key has on the B+ tree.
谢谢大家。 Thank you very much.