大家好。数据结构与算法这一讲我们继续第十一章索引的学习。 Hello, everyone. We continue to take up chapter 11th index to study data structure and algorithms.
今天我们主要是学习动态索引其中的B树。 Today we introduce the B-tree of dynamic index.
我们动态索引主要是针对这个主关键码它经常进行插入和删除这样的动态更新的情况。 Dynamic index is for the dynamic updating case that the primary key is inserted and deleted frequently.
我们前面提到的这样的静态多分树它就不是非常好调整，也不好维护。 The adjustment of the static multisection tree we mentioned previously is not well, nor is maintenance.
因此我们就要设计一种新的数据结构来支持这样的操作，这就是我们的B树的来由。 So we have to design a new data structure to support such operations, which is the reason behind the B-tree.
我们来看这个B树其实很像BST树。这就是一个三阶的B树。 The B-tree is like BST tree a lot. This is a 3rd-order B-tree actually.
它的特点就是子结点个数在两到三个之间，它不能有一个的样的子结点的情况。 It is characterized by the number of sub-nodes between two to three, the situation that it has only one sub-node is impossible.
另外所有的叶结点都在同一层。在中序的遍历下，它是一个有序的这样的序列。 Furthermore, all the leaf nodes are in the same layer. In the inorder traversal, it is an ordered sequence.
我们来看一下B树的定义。 Then let’s learn about the definition of the B-tree.
我们为了适应这样的结点的插入删除的动态性，我就使得一个结点它可以也是在一个全满到半满之间的范围浮动。 In order to adapt to this situation that insertion and deletion of the node is dynamic, then I can make a node change in a range of full to half-full.
因此我们会定义结点的这样的一个阶。首先这个阶，它还受制于我们这个磁盘空间的大小。 Therefore, we will define such an order node. This order is subject to the size of disk space.
也就是说我们一个磁盘页框，如果是它只能够容纳比如说512字节或者是1024字节，我们这样的一个结点我就只能够容纳有限的关键码以及指针这样的对。 That is if one disk page frame can only accommodate 512 bytes or 1024 bytes for example, that such a node can only accommodate a limited key and the pointer.
因此我们可以根据这样的一个磁盘页的大小限制计算出我这个B树最大的阶的个数是什么样的。 So we can calculate the number of the B-tree’s maximum order based on such a limited-size disk page.
因此我们首先就是得到一个这个结点它的阶。 First we get an order of the node.
然后我们再规定它全满是不超过m个子结点，然后半满我们允许它是二分之m个子结点。 Then we provide that when it is full, there is no more than m sub-nodes, while when it is half-filled, the number of sub-nodes is a half of m.
对于根我们有一个特别的处理，就是说根节点可以只有两个子结点。 As for the root, it’s special, that is the root can have only two sub-nodes.
这个我们在后面可以看到，就是因为我们在动态调整的时候对于根有一些特殊的情况。 We will draw this conclusion later, because there will be some special cases for root in dynamic adjustment.
还有一个限制就是所有的叶结点我们都要在同一层。这就使得它有一个比较好的一个性能，通过这个限制叶结点在同一层达到了一种平衡使得它的树高整体是一个log m级的。 Another limitation is that all the leaf nodes must be at the same level. This makes it a relatively good performance by limiting the leaf nodes at the same level to achieve a balance, which its overall height of the tree is at the level of log m.
还有一个就是对于有k个子结点的内部结点，它的关键码，它是k减一个。 The key of the internal node which has k sub-nodes is k minus one.
这就类似于BST。BST，它如果是有两个子结点的话，它中间有一个分界的这个关键码。我们看这个树，它正好是这样的一个情况。 This is similar to BST. If there are two sub-nodes of BST, in the middle of it is a demarcated key. We can see that this tree is just such a situation.
我们再来分析一下，B树的性质。首先它的高度是平衡的，所有叶都在同一层。这样使得B树，它是在一个log以m为底N的对数这样的一个量级。 Now let’s analyze the property of the B-tree. First, its height is balanced that all the leaves are at the same layer, which makes a B-tree is at the magnitude that m is the number of the log to the end of N.
然后它的关键码我们也是不允许重复的。对于数据结构里面很多这种索引的情况我们都不让关键码重复。如果你在运用中实在是需要重复，你可以做一些特别的一些处理。 It also does not allow repetitive key. For many cases like this index in data structures will not allow repetitive keys. If you really need to repeat it in application, you can do some special operation.
还有就是B树它把这些相关的这些记录它其实是放在同一个磁盘页框。也就是说B树里面这样一个结点，它们的这个关键码是在同一个磁盘页框存储的。当然还包括指向它的下一级结点的这样的指针。 In fact, a B-tree will put these related records into the same disk page frame. That is the key of such a B-tree node is stored in the same disk page frame. Of course, it also includes the pointer that links to the next level of this node.
这就使得我们一些相关的关键码在相连的区域存放，这使得我们能够很好的利用这样内存的这种缓冲，我可以在访问数据的时候预取一些相应的磁盘块放在内存缓冲区域里面加快我们的这样的检索的速度。 This makes some relevant keys are stored in connected areas, so that we can make good use of the memory buffer, and we can prefetch some corresponding disk blocks and put them in the memory buffer area to speed up the retrieval speed when accessing data.
B树它还有一个特别重要的性质就是它的页框是在全满到半满之间。这就使得它的插入删除的这个性能是能得到一定的保证。 There is a particularly important property of B-tree that its pages frame are between full to half full. This makes its performance of insertion and deletion can get some certain guarantees.
如果我们在一个半满到全满的这么一个范围之内，如果要插入的时候，如果它还没有全满我就有空间可以给它塞进去。删除的时候，因为它也不要求你是给它挤得满满当当的，如果我没有下一处，只要删到这个举局部，整个树也许不需要进行很大的调整。 Because the B-tree is in a range from half-full to full, when we need to insert data, if it is not full, the tree will have space to insert it. When we need to delete data, it won’t need to be filled completely, if there is not the next place, we can delete within this part and the entire tree may not need to be adjusted too much.
我们再后面一些事例的时候大家就可以看出来。 We can verify this conclusion by some example later.
我们一个B树的结点它其实是这么一个结构。这是一个有j加一个子结点的一个B树结点。它就有j个关键码，P0到Pj它是分别指向这个j加一个这样的子结点的一个结构指针。K1到Kj它其实就是这些子结点的分界的关键码。也就是说P1指向的整个这个子树的关键码都会小于K1，然后在小于这个P1指向的这个子树，一直这样。其实就有点像我们在中序下遍历BST它是一个有序的这样的序列。 In fact A B-tree node is such a structure. This is a B-tree node with j plus one sub-nodes, so it has j keys. From P0 to Pj, all of them are structure pointers that pointing to these j plus one sub-nodes. From K1 to Kj ,they are demarcated keys of these sub-nodes. That is the entire subtree’s keys which P1 point are less than K1, and this will always be in the subtree that less than P1 points. That is a bit like a BST in inorder traversal, it is an ordered sequence.
我们再想一想，除了这个P0到Pj，还有一些什么指针？其实还是有的。就回归到我们对于检索和索引的一些约定。 Let us think it over, besides from P0 to Pj, are there some other pointers? It is still there. Then it return to some agreements of search and indexing.
通过这个K找到它的value，这个value有可能并不一定就是存在这个索引结构里的，它是存在某一个原来你放数据的这个主文件，或者是其它的地方。 We can find its value by the K, this value may not be stored in the structure of the index, which is stored in a master file that we store data before, or somewhere else.
因此，我们找到这个key以后，我要通过key 它所对应的一个这样的隐含指针，再找到这个key在这个主文件里面它所拥有的相应的些数据信息，也可以说是属性信息。 So after we found the key, we need to find the information of corresponding data in the main file that the key owns by the corresponding implicit pointer of the key, it can be said the attribute information.
我们来看一下这个图式。这一个就是一个B树的这个索引。我们这些线，其实就对应到前面个p，就是子结点的这个结构指针。然后我们所有的这些A，其实就是对应到我们这个关键码它的文件页里面的个地址的指针。 Then we look at this schema. And this is an index of a B-tree. While these lines correspond to the p, which is the structure pointer of the sub-node. All these A are corresponding to the address pointer of the key’s file pages.
每一个这样的key它都对应到主文件里面具体的一个地址。这个地址我们就可以读出相应的一些数据信息。 Each key corresponds a specific address in the main file, so we can read some corresponding information of data from the address.
B树我们要注意，阶一般是应该是大于等于三， 可以说阶最小的B树就是二三树。 We need to mind that the order of B-tree is no less than three, that is the minimum B-tree is 2-3 trees.
这个二三树其实在内存里面它也是一种非常好的一个索引结构，因为它树高也是平衡的，而且它的实现非常地方便。 The 2-3 trees is also a good index structure in storage, because its height of tree is balanced, and it can be performed very conveniently.
其实B树在内存里面我们也可以用来组织索引结构。它比这个BST就是也是能有更好的性能。 In storage, we can use a B-tree to organize the index structure, and it also performs better than BST.
我们来看一下B树的检索。检索它其实是分成两个步骤。 Now let’s learn retrieval of the B-tree, this retrieval has two steps.
这个步骤就是我们先从这个根来读出这个相应的这个关键码。 The first step is that we read this corresponding key from the root.
因为B树的阶可以很大，它是有j个这样的关键码，然后有j加一个这样的指针的话，我们在这个阶的关键码里面我也许可以用二分，因为它也不是很多，顺序也行，我们找到它的这个关键码是不是在根里面存在，如果存在我就可以停止。 Consider that the order of a B-tree may be very big, there are j keys and j plus one pointers of it. We can use dichotomizing retrieval to search the keys of the order, for the keys are not too much, as well as sequential retrieval. Then we’ll confirm if the key exists in the root, and we can stop searching if is does.
如果不存在，我就需要通过这个它的关键码这个分界的性质去继续到下一层来查找，一直找到相应的关键码为止。 If it doesn’t exist, we need to search it by the boundary property of the key, until we find the corresponding key.
或者是说我们找不到，其实就是这个下一层关键码我们就会指向的这个外部的这个空结点. Or if we can’t find it, the key of next layer will point to the outside empty node.
其实我们在失败的检索情况下都是停在这样的一个叶层这一个位置，然后它再往下索引的时候，已经是没有外部结点了，就是这个查找失败。 In fact, we will stay in such a position, a leaf layer when we failed to retrieve, then there will be no external nodes when the index performs further, that is the search fails.
插入的过程其实是一个失败的检索，也就是说我们要检这个关键码，如果检到了我告诉它B树不允许插入重复的关键码。如果是失败了，我们一定是停在叶层，我就是在这个叶层的相应位置，我就插入关键码。 The process of insertion is actually a failed retrieval, which means we have to retrieve the key, if we find it, then we’ll be told that it is not allowed to insert a repeat key into a B-tree. And if we can’t find it, then it will stay at the leaf level, where we can insert a key in the corresponding position of the leaf layer.
插入的过程我们一定要注意保持B树的性质。 In the process of insertion, we must pay attention to maintaining the property of the B-tree.
这个B树的性质它主要是有两个方面的约束。 The property of the B-tree is mainly constrained in two aspects.
一个就是说它的这个阶的约束，这个阶，对于子结点数其实也对于关键码的个数我们就是要保持它不能够溢出，因为是插入。如果是上一处，怎么办，我一个磁盘块，我是放不下这么多东西的我就必须把它分成两块，在分裂的过程，我需要把它的分阶关键码给他提出来放到上一集有插入在上一集有一个新的分阶关键码，这样话，上一层它也可能会产生上一处，一直这样传下去也许会传到根。 The one is the constraint from the order. We need to maintain the number of sub-nodes, or the number of keys not overflow, which because it is insertion. What should we do if it is last space? One disk block will be divided into two blocks if it can’t contain so much data. In the process of dividing, the sub-order key need to be put on the last set, be inserted into last set and generate a new sub-order key, so that the last layer may produce the last position, which may transmit to the root.
我们来看这个插入的实例。这是一个3阶的B树，我们插入14，这个插入的过程我就是顺着这个根结点然后往下面一直找。我找到这个叶这一层，然后我可以插到这个接点里面，插入以后，这个是正好它没有发生树的一些形状的改变，我们就完成了这个插入。 Now we look at this insertion application. This is a third-order B-tree, we’ll insert 14 into it, the process of inserting is search down below the root. I find this leaf layer, then we can insert the 14 into the junction. After the insertion, the shape of the tree doesn’t change means we complete the insertion.
继续插入55， 我们找到这一个结点。找到这个结点以后我们插入的时候因为这是一个3阶B树，它就已经是上一处，上一处了以后我们就需要把它分成两块，而且它的中间个中位数52就作为这个新的这两块新的关键码插到在上一层。然后，这一次的插入操作就停止了。 Then we continue to insert 55, we find this node. After that we need to divide the tree into two blocks, it’s because this is a third-order B-tree, we have inserted 14 in it, so the node has been the last position, and in the middle of it, the median 52 will be the new key of these two blocks and be inserted into the last layer. At this moment, this inserting operation is to a halt.
继续插入19，我们可以看到跟刚才类似。这个是上一处了以后，它的分阶要往上面传。这上一层，它还是接着上一处，他们又是产生两个新结点，然后它的分界的这个关键码就传到根，然后根也上一处了，所以我们产生这个结点的分裂然后我们形成了一个新的根结点。这个根结点只像刚才分裂的这个老的根结点和它的复制的这个结点。 Then we continue to insert 19, we can know that it’s just like the inserting before. When the 55 became the last position, its sub-order will be transmit to upside. Up this layer, it will follow the last position, so they will produce two new nodes, and its demarcated key will be transmit to the root, then the root will become the last position, therefore the node divisions and produces a new root node. The root node is only like the old divisive root node and the node it duplicates.
从这里可以看出在根结点为什么对它有特别的这个阶的规定也就是说它的这个下阶是M等于2。 From here we can see why there is special provisions for the root node, which is its lower order is M equals to 2.
这就是因为我们在这样的一个插入过程中当我分裂到根的时候，如果你这个M的阶很大，比如说M等于100，我如果还要求满足它的这样一个下阶，就是它的这个直接能够数是2份之M，也就是说50这种情况处它到处去找这么多结点来筹备根？是不好找的。 This is because when I divide to the root in such an insertion process, if the order of the M is very big, equals to 100 for example, then we need to provide a lower order which can meet it, the number is half of M, 50. In such case, how can we find so many nodes to prepare for the root? It’s not easy to find them.
我们为了方便这个运算，我就是允许根结点作为一个特例，它可以只有两个枝结点。 In order to facilitate this operation, we allow the root to be a special case, it can be only two stick nodes.
我们来总结一下，刚才这个连续的插入过程它们会有一些访外的这样的操作，因为我们知道对于这个外层的这样的操作的话，访外是非常的耗时间的，我们所有的这些技术都是为了要减少访外次数。所以我们要理解它到底有些访外次数。 Now let’s summarize what we have learnt. There are some visiting outside operations in the process of continuous inserting before, because we know that visiting outside is time consuming if we operate this outer layer like this, so all of these technologies are aimed at reducing the times of visiting outside. Therefore we have to know what these times of visiting outside.
我们来看刚才连续插入14，55，19 这样的过程，假设我们在访问的过程中这些制版页块它都还放在内存的缓冲区里面，也就是说我下一次要继续访问这个磁盘块的时候我不需要去访外。 Then we review the process of continuous inserting 14, 55, 19. Assuming that the plate leave blocks are stored in the buffer of storage when we visit the disk block, which means we don’t need to visit outside when we visit the disk block next time.
我们在插入14的过程中，我们会是沿着 A，B， F访问这样的读盘的操作，然后接着在插入55的时候是A，D， K， 但是A已经是在缓冲区里面所以这一次它不需要访外，直接从缓冲区拿出来就行了。 When we inserted 14, we did the operation of visiting the disk by the sequence of A, B, F. When we inserted 55, the sequence was A, D, K. But the A has already been in the buffer, so it can be used directly from the buffer instead of visiting outside.
接着是插入19，就是A，C， G，也是只要我访问C和G所以这一个一起是有7次读盘的操作，完成了这样的插入以后它的结果其实本质上都是需要写回外层的。 When we inserted 19, the sequence was A, C, G, so we visited the disk 7 times because we just needed to visit the C and the G. After the insertion, the result is actually wrote back into the outer layer essentially.
当然在一些数据库的技术里面，它可以比如说延缓写出，不是一定马上写出。但是如果我们假设它是马上写出的话或者说我带缓冲情况下的这个写出，也就是说原来这个根结点以及我们最后形成的这个新的根结点也许我们不是说插入完14就全都给他写出，但是我们把必要的都要写出的话这种情况下， 我们写出一些结点就是f把它更改一下就行了， 然后插入55的时候它会要形成两个新的结点就是K和K一撇，对这个D也要进行一个修改的这个操作，插入19的时候，它对这个G有分裂， C也有A也有。就是G， G一撇， C， C一撇， A， A一撇。以及A， A一撇，它们的一个新的根的赋值点就是T，因此我们总共有11次写盘的操作。 Of course, in some database technology, slow down writing for example, it is not necessary to write immediately. But if we assume writing immediately or writing with a buffer, which means the original root node and the new root node that produced at last don’t need to be written very soon after we inserted 14, but they needed to be written. In this case, the nodes which are written is changed from f. When we inserted 55, it would produce two new nodes, K and K′, and the D needed to be amended. When we inserted 19, the G was divided, so was the C and the A. That means it produced G, G′, C, C′, A, A′. There are also A, A′, and a new assignment of root, T, so we did the operation of writing the disk 11 times totally.
B树的删除，也就是一次成功的检索的基础上然后再进行删除。 The deletion of B-tree is based on a successful retrieval and then delete it.
有两种情况，一种就是关键码它如果不是在叶结点的时候，我们还是要跟它在叶结点层里面的后继或者是叶结点层里面的它的前驱来进行交换，然后把这个操作给它降到叶结点开始进行。 There are two cases, the one is if the key is not leaf node, we need to exchange it with its successor or its precursor in the leaf node layer, then lower the operation down to its leaf nodes and begin it.
因此我们下面就统一就是先考虑这个叶结点的某一个值的一个删除。 Therefore we consider the deletion of a certain value of the leaf nodes firstly.
删除了以后，我们主要考虑的就是它会不会造成一个下叶初不满足我们b处这个平衡性能的要求。如果删除以后它不小于这个2份M减1，它就没有产生上一处,我们就直接删除，如果是删除以后关键码的格数已经是产生下一处了，我们就需要进行特殊处理。 Since the value is deleted, we mainly consider if it will result that the beginning of next leaf do not satisfy the requirements of the balance performance at the position b. If it is no less than a half of M minus one after deletion, it did not produce the last position, and we can delete it directly. If the number of keys produces the next position after deletion, then we need special operations.
在删除的情况下，我们是首先考虑像它的这个左右邻居借关键码，注意这个左右邻居一定是亲兄弟，也就是说它们是共同拥有一个直接的父节点。不能去借堂兄弟的些值。 In the case of deletion, we first consider about borrowing key from its left and right neighbor nodes, and we need to notice that its left and right neighbor nodes must be its brothers, namely they share a direct father node, while it can’t borrow the values of its cousins.
如果是亲兄弟某一个它能够给他借结点也就是说亲兄弟它并没有处于哪个邻接的情况下，也就是没有在这个允许的这个最小的关键码码树这个情况，它就可以两个结点以及它们在父节点里面的样的分解的关键码它们一起把这个新的这个中位数传到父结点做一个新的分解，么成两部分的这些关键码值。 If it can borrow a node from one of its brothers, which means its brothers are not in any case of adjacency, so there is not allowed to be the smallest key tree, but it can occupy two nodes and the ordered key in their father node. They transmit the new median to the father nodes as a new order, which produces two parts of the key values.
如果是两个兄弟它都不能够借关键码这种情况它就必须跟其中的一个进行合并。 If it can borrow no node from neither of its brother, it must be merged with one of them.
我们来看一下删除的示例，现在是一个5阶的B树，删除这个关键码92，92我们找到它的一个后继，就是94， 调换以后把92给它挪到叶结点里面我就可以删除了。 Now let’s see an example of deletion. It is a 5th-order B-tree, the key 92 will be deleted, so we find one of its successor, 94, then we can delete 92 after exchanging it and moving 92 into leaf node.
删除了以后，我们发现h这个结点它下一处了就是5阶的B树它最小的关键码树必须是有两个。 Since we delete it, we found the next position of node h is the smallest key tree of 5th-order B-tree, which must be two.
现在下一处以后，它一看这个左邻居还可以借关键码。把这个左邻居以至它自己还有在分结里面的些关键码，我们把它排在一起然后把这个中位数90，给提上去我们就已经完成了这个删除的操作。 After the next position, we found that it can borrow key from its left neighbor node. The deletion operation is completed when itself, the left neighbor node and the keys in ordered are arranged and the median 90 is put up.
继续在树里面我们删除96， 还是这样我们跟它的后继交换以后，然后删除96， 删除了96以后，这个i结点就发生了下一处，但是它想向h借的时候，h也是一个邻接的情况，所以我们就把h和i这两个结点给它合并，而且不要忘了它们在父节点里面的分结的关键码也要拿进来合并，也就是说父节点里面要删掉一个这个关键码。 Now we continue to delete 96 in the tree, it’s also exchanging it with its successor first then delete the 96. Since we delete it, the node i is produced in the next position. But when it needs to borrow a node from the node h, the node h is also in the case of adjacency, so we need to merge the node h and the node I, and merge them with the keys in ordered, which means this key in father nodes should be deleted.
删掉以后， 父节点它也是下一处了，它就要去看一下它的这个兄弟是不是可以借，如果不可以借，这时候我们只能继续合并。 After the deletion, the father nodes would be the next position, so it needed to be checked if it can borrow nodes from its brother nodes, if the answer is no, we can only continue to merge them.
这时候， b，c以至它们这父节点里面的分节一起合并， 合并以后我们整个这个b树它就降低了一层了。 At this moment, b, c and the sub-order node in its father nodes will merge together. After that the layer of the entire B-tree will reduce one layer.
我们看一下这个b树的性能。首先我们就是先估计一下这b树，它的高度会是怎么样的。最高的b树就是假设每一层它这个结点都是在这个就下阶的这样的一个关键码值的一个状况，因此它能够形成最高的b树。 So let’s take a look at the performance of the B-tree. First, we estimate the height of the B-tree. The highest B-tree is a B-tree whose nodes at each layer are in the case that the key values are in next order, so it can be the highest B-tree.
我们首先来看，如果我是有N个关键码，看到这个B树里面也可以看到我们这种画红色的就是表示它是这个外部结点，是我们在这一个叶结点这一层，如果我们检索还要去检索别的值，比如说要检零三六这样的一个值，它就会是落在零零八和零四零这个中间的一个外部结点。 If I have N keys, we can see the nodes painted red are the external nodes in the B-tree, all of them are at the layer of leaf nodes. When we need to retrieve other values, such as 036, the result will be an external node among 008 and 040.
然后它检它也是个空，我们也不能继续下去，所以它就会是返回检索失败。 The result will be empty, so we can not continue to retrieve, so it will return the result that retrieval failed.
对于N个关键码的这样的B树，它总共有N加一个外部的这个空结点。 For such a B-tree with N keys, there are N plus one external empty nodes totally.
我们假设我们的这个层的这样的一个编号就是根是第零层。我们在这个叶层是可以减一层，这个外部是第K层。 We assume the number of the root layer is zero. The number of the leaf layer can minus one, and the number of this external layer is K.
我们来看一下各层的这个结点数。根底下它的函子最少的情况下就是只有两个指结点。第二层，我们就是二乘以二分之m个指结点。 Then we look at the number of nodes in each layer. There are at least two index nodes for the root. At the second layer, there are square a half of m index nodes.
我就是尽量的每一层都是关键码指是尽量的少，让这个数尽量的高。 So the index of the keys in each layer should be as little as possible, while the number of them should be as big as possible.
我们一直到第k层的时候，它会是二乘以二分之m，然后可以减一次方，这样多个指结点。 In the K layer, the number will be square a half of m, and the number of index nodes can minus one square.
我们就能够得到这个N加一它是大于等于这个我们刚计算出来的第k层的这个指结点数。得到这个k它的这么一个值，肯定是小于等于一加log二分之m为底的二分之N加一的对数。 We can get the result that the N plus one is no less than the number of index nodes in the k layer calculated just now. And the value of k must be no more than that a half of m is the number of the log to the end of a half of N plus one.
这个值你可以看到它是log以m为底然后N的一个对数这样的量级的。 We can know that the value is at the magnitude that m is the number of the log to the end of N.
我们假设N是两百万左右的这样的规模，然后对于一定的这样的磁盘空间的限制的话，我假设算出来这个m是一百九十九。 We assume that the size of N is about two million, for the disk space with such certain restrictions we can assume that m is 199.
可以看到，这个k它其实就是四，也就是说顶多四层，我就能够把它给索引起来。 So we can see that k is actually four, that is there are at most four layers which is able to satisfy the requirement of retrieval.
因为这个根，还有根底下的这一层的话就总共加起来你可能也就是两百个结点，这一些结点我可以把它存在内存里面。 Because the number of the nodes of the root and the layer below the root is two hundred in total, some of them can be stored in the memory
因此我真正需要反外的只是就是最底下的这两层。所以B树的索引效率是非常高的。 So what we really need is just these two layers at the bottom. Therefore, the efficiency of the B-tree index is very high.
我们再来看这个B树结点分裂的次数。如果是从一个空的B树开始，逐个逐个的关键码插入，然后当然最开始的这个根结点我们假设它不是经过分裂的，是我先给你的。 Now let’s pay attention to the division times of the B-tree’s nodes. If the division begins from a empty B-tree, and the keys are inserted one by one. We assume the first root node is not produced by division but I give it you.
一部结点数是我假设是p的话，我们大概可以得出N和这个p的一个关系。 If the number of nodes is p, then we can infer the relationship between N and p.
我们如果是每一个都是经过分裂而来的，我们可以得到这个一部关键码p和这个N的一个关系。 If each of the nodes is produced by dividing, then we can infer the relationship between the key p and N.
我们如果是平均到每一个关键码它没插入的时候它可能被分裂的这么一个概率，我们就是p减一除以N。可以看到是跟这个m是相关的。这个概率其实如果我们把刚才m是等于一百九十九，放进来的话其实也就是百分之一左右的这个情况它需要分裂，大部分的情况下它其实是不需要分裂的。 The probability of every key is divided before an insertion is p minus one and divided by N. Then we can know that the probability is related to m. If we substitute the m with the number 199, the probability is about one percent, which is in most cases it is unnecessary to divide the keys.
我们再给出几个思考。 Finally, I’ll question some problems for you to think.
首先就是说，你想一想，如果有二阶的B树会是什么样？ The first is: how about a B-tree with 2nd-order?
第二个问题就是说，我们在B树的删除里面我们都是先去借再合并，也就是说我尽量少发生这种结构上的这个大变化，但是你看它的插入的时候是先给它分裂，然后我根本不考虑说还把我的这个多余的关键码送给邻居的情况。 The second question is that the deletion in B-tree is borrowing nodes first, and then merging them, that is we delete a node with as little structural change as possible. But when we insert a node, the node will be divided first, and it won’t send its extra keys to its neighbors.
就是为什么？因为就是我们B树的定义都是在二分之m到m之间的这样的一个度。我是不是可以有其他的这个划分，比如说我可不可以是三分之m到m这样的一个区域？ Why? Because the degree of B-tree is defined between a half of m to m. Is there any other definition, such as from a third of m to m?
你可以比较一下这两种不同的方法，它有一些什么不同你在算法上在写的时候会有一些什么差异。 So you can compare the two different methods, compare their differences of writing the algorithm.
另外就是这个B树它其实真的是一个比较高效的而且很方便实现的这么一个平衡的索引数。如果是对于这个内存的数域它特别大的时候，然后你又要考虑它的一个平衡的性你用B树的这种变体来写这样的一个索引结构也是可以的。 Besides, the B-tree is a balanced index number which is efficient and performed conveniently. If the number domain of the storage is very large, you have to consider its performance of balance, then you can write the index structure with the variant of B-tree.
而且在这种情况下，你不需要考虑它的这个结的限制，只要你觉得在内存里面是一个合适的结就可以。它不受这个外层的磁盘空间大小的限制。 And in this case, you don’t need to consider the limitation of the knot, as long as you think it is an appropriate knot in the storage. It is not limited by the size of the disk’s space in outer layer.
谢谢大家。 Thanks.