浅谈多路查找树（B树）

1、序言

曾今我不知道多叉树有上面用，所以对于多叉树并没有过多的关注，或者说，基本没关注。
直到我了解到了多路查找树（B树），我知道，是我浅薄了。

先不说那些高深莫测的内容，我们就通俗的聊聊。

我们现在常说大数据大数据，就算没说过也听过不少了。但是我们的系统的内存就那么大，而外部硬盘却可以达到成千上百个G。

我们之前聊的数据结构，都是基于内存的，因此考虑的是内存中的运算时间复杂度。但是如果我们操作的数据集非常大，大到内存已经无法处理了，这也是很正常的现象，比方说某个程序要从文件系统中取一个文件出来，这个时间复杂度就会发生变化了。

试想一下，要在一个拥有几十万个文件的文件系统中查找一个文件，你所设计的算法需要读取磁盘上千次还是几十次，这是有本质上的差异的，后者可能是几秒，前者可能就要几分钟了，你能忍？找个文件都要等几分钟！！！

2、2-3树

这是一个简单的多路查找树，学新东西嘛，自然从最简单的开始。什么是多路查找树？和二叉树做个比较可能会比较直观：二叉树，你可以叫它二路查找树。明白了吧。

那么2-3树是一颗怎样的树？长这样：
1、其中每一个节点都有两个孩子（称为2节点）或三个孩子（三节点）或者没有。
2、子节点排序参考二叉树
3、一个二节点包含一个元素和两个子节点（或没有子节点），一个三节点包含两个元素和三个子节点（或没有子节点）
4、2-3树中所有的叶子节点都在同一层次上。

2.1、2-3树的插入

这个比较开始复杂了，不过咱就随便聊聊，聊到哪儿算哪儿。

首先，要明白每个新插入的节点都是二节点。

插入情景1：
插入空树，直接插入，完事儿。

插入情景2：
插入到一个二节点的叶子上，这也没什么，就像上面最左叶子节点，在“1"旁边给新节点“3”留个位置就好了。

插入情景3：
插入到一个三节点的叶子上，这就很尴尬了，2-3树的节点极限就是3，比方说上面要插个5进去。
那怎么弄？
先看一下，要插入节点的父节点是个二节点，那就好办了，把那个二节点变成三节点，自然就有地方插入了。怎么变？把“6”提上去啊，图自己画。
如果要插入节点的父节点是个三节点，那就比较尴尬一点。比方说我现在要插个“11”进去。
那怎么弄？
那就一直往上找，找到二节点为止，然后该怎么做上面已经讲了。

还是刚刚最后一种场景，如果往上找，找到根节点都是三节点，那怎么办？
那就意味着当前=层次已经无法满足我们的需要了，从根开始，全拆成二节点吧。

也不要去钻牛角尖了，咱就随便聊聊，要钻牛角尖咱往后去把代码实现写一下。现在知道是这么回事儿就好。

2.2 2-3树的删除

删除其实就是增加的逆过程，如果增加看懂了，删除就很简单。

以下场景针对删除节点为叶子节点：
删除场景1：要删除的节点位于一个三节点上，直接删了。

删除场景2：删除根节点，也是直接删了吧。

删除场景3：删除的节点位于一个二节点上。就像插入节点在三节点上一样的尴尬。不，更尴尬。

删除场景3.1：该节点的父节点为三节点：将父节点拆开下放一个节点。
删除场景3.2：上面场景不存在，但是 该节点的兄弟节点是三节点，将它的兄弟节点拆开，然后做单旋转。

其他的删除场景嘛，日后深入研究的时候再行探讨，过于复杂。

3、B树

B树是一种平衡的多路查找树。
节点最大的孩子的数量的树叫做m阶B数。
所以2-3树就是3阶B树，二叉树就是2阶B树。

B树有如下性质：

1. 如果根节点不是叶节点，那么B树至少有两叉。
2. 所有叶子节点都位于同一层次。
3. 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<k<m. 21每一个叶子结点n都有k-1个元素，其中[m/2]<k< m.

在B树上的查找过程是一个顺指针查找节点和在节点中查找关键字的交叉过程。

关于B树的插入删除，和2-3树一样，只不过阶数可能会大了些。

4、B树的典型应用

我们的外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，-页的长度可能是 211到214个字节。

在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对 B树进行调整， 使得B树的阶数 (或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001 (即1个结点包含1000个关键字)，高度为2,它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。

B树查找的时间复杂度：O(log n).

下次再深挖的时候我一定带上B+树的！！！

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/105620487