这是数据库索引相关内容的第二篇复制代码

B树

目录：

1. 什么是B树
2. B树的最小度数
3. B树的高度
4. 什么情况下使用B树
5. B树的插入
6. B树的删除

关于1~4已经在上一节介绍过了

这里重点介绍B树的插入

5. B树的插入

B树要保持它的平衡及最小度数（t-1=<n<=2t-1, t<=child<=2t）特性，则需要在插入以后也是一个满足此特性的B树。

那么如果是你，如何保证在插入关键字后，新的B树也能满足其特性呢？

一般的思路是：

1. 根据B树的排序特性，找到插入的节点
2. 如果插入的节点是不满的（n<2t-1）,直接插入
3. 如果插入的节点是满的（n=2t-1），则不能直接插入，因为插入以后，就不符合B树的特征了，我们要一直维护B树的特征， n<=2t-1,所以需要将节点进行拆分；
4. 节点拆分后，如果只是单纯的拆分，一个child的裂变成两个，显然这么简单的裂变是不行的，因为child+1了，但是父节点的关键字个数n没变，所以不符合child = n+1，子节点多裂变了一个，但是父节点没变；
5. 所以节点拆分后，需要将中间的数据，提到父节点中；
6. 但是如果父节点是满的，子节点提到父节点中又不满足B树的特性了，父节点也要裂变，提一个到父父节点中；
7. 如果父父节点是满的，则又周而复始....

所以这将是个从上到下查找，又从下到上裂变的过程。

虽然这也可以实现，但是有没有优化的方法？

1. 观察一下这个过程，本身定位到插入节点时，已经有一次至上到下的过程了；
2. 如果在至上而下的过程中，每发现满的节点，就进行拆分呢，是不是就可以做到一次向下查找，就能满足后续的插入裂变。

是的，这就是B树的插入过程！

1. 至上而下查找
2. 每发现满节点，就进行裂变
3. 找到插入位置，插入，如果需要裂变，就裂变，因为父节点不可能是满的，再刚刚遍历到父节点的时候，已经提前腾出空间了！

就是这么简单！

让我们来看个例子：

有如下字母：F, S, Q, K, C, L, H, T, V

1. 假设现在有个空树
2. 假设t = 2, 即最小度数为2；
3. 请画出B树的插入过程（只画出关键过程）

解答：

1. t = 2,意味着我们节点的关键字个数在1~3之间，一单关键字个数超过3，则要裂变
2. 在依次插入F,S,Q时，很简单，因为根节点<=3

3. 当插入K时，自上而下的过程中，发现父节点是满的，必然要先拆分父节点

4. 此时父节点已经被成功拆分成不满的节点，并且子节点个数和排序也符合B树要求
5. 插入K，比如是从Q向左查找，插入到F之后。

6. 接着要插入C，直接插入的到F之前就行，因为在至顶向下的过程中，没有发现满节点

7. 好了，下面到L了，当至顶向下的过程中，L是在Q左侧查找，发现了CFK节点是满的，必然进行拆分； 将中间节点F提上来，父节点个数+1，子节点个数+1, 仍然符合B树特征

8. 拆分之后，插入L
   后续的插入，就不用多讲了，重复以上过程。

好了，写的真累，删除下次再写吧

其他相关章节复制代码

数据库索引相关文章之一：