多路查找树

二叉树与B树

树

B 树，B+ 树，B* 树

​ 钢达姆机器人

二叉树与B树

二叉树的问题分析

二叉树的操作效率较高，但是也存在问题，请看下面的二叉树

层数：5

节点数量：31

• 计算方式：2 ^ 5^层数^ - 1 = 31

1. ==二叉树需要加载到内存的==，如果二叉树的==节点少==，==没==有==什么问题==，但是如果二叉树的==节点很多== (比如 1 亿)，就==存在==如下==问题==：
2. 问题1：在==构建二叉树时==，需要==多次进行 i/o 操作== (海量数据存在==数据库==或==文件==中)，节点海量，==构建二叉树时，速度有影响==。
3. 问题2：==节点海量==，也会造成二叉树的==高度很大==，会==降低操作速度==。

多叉树

1. 在二叉树中，每个节点有数据项，最多有两个子节点。如果==允许每个节点可以有更多的数据项==和==更多的子节点==，就是==多叉树== (multiway tree)
2. 后面讲解的 2 - 3 树，2 - 3 - 4 树就是多叉树，==多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化==。
3. 举例说明 (下面 2 - 3 树就是一颗多叉树)

多叉树中，如果一个节点中存在了三个分叉则称为 ==3 节点==。如果是两个分叉则称为 ==2 节点==。

B树的基本介绍

B树通过重新组织节点，降低树的高度，并减少 i/o 读写次数来提升效率。

上图说明：

• 一个 ○ 代表一个数项

• 一整个 ○ ○ ○ 的集合代表一个节点

优点理解：

• 降低树的高度：

  可以看到，一个节点中有很多数据项，就能大大减少节点数量，从而降低树的高度

• 减少 I/O 读写次数

  文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页 (页的大小通常为 4K)，这样每个节点只需要一次 i/o 就可以完全载入。

  这样说，你可能没有概念，举个例子：将树的度 M 设置为 1024 ，在 600 亿个元素中最多只需要4次 i/o 操作就可以读取到想要的元素，B树 (B+) 宽泛应用于文件存储系统以及数据库系统中。

  什么是 度？

• 节点的度：

  一个节点下的子树节点个数就是 节点的度。

• 树的度：

  指一颗树中 ，节点的度最大的哪一个值。

树

2 - 3 树基本介绍

2 - 3 树 是最简单的 B树结构，具有如下特点：

1. ==2 - 3 树的所有叶子节点都在同一层== (只要是B树都满足这个条件，就是满树)

2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点

   不能只有一个节点，==说得通俗点就是不能比父节点的节点还少==

3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点

   不能有二个子节点，一个子节点，==说得通俗点就是不能比父节点的节点还少==

4. ==2 - 3 树==是==由二节点==和==三节点构成的树==。

2-3 树构建图解

对数列 {16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成一个 2-3树，那么它构建的规则要满足前面说的特点。下面进行图解后，你就明白，上面的特点是如何限制的。

有几个额外的注意事项：

1. 一个节点中，最多只允许放 2 个数据。
2. 构建的树必须是有序的，也就是按照二叉排序(BST)的要求构建有序的树

下面是图解步骤：

1. 添加 16,24

添加 16 时，没有数据，直接新建一个节点，放进去。

添加24时，发现有一个节点了，并且比 16 大， 此时该节点中只有一个数据，则将24放在 16 的右边。

1. 添加 12

此时会发现，12 比 16 小，本来应该放在 16 的左边。此时发现这个节点 已经有两个数据了，那么就只能放在 左子节点。

如果直接将 12 放到 16 , 24 的左节点，就会破坏 2-3树的条件：2 节点 ，要么没有子节点，要么有两个节点。

那么此时就只能将 16,24 这个节点进行拆分。如上图： 24 变成 16 的右节点，12 变成 16 的左节点。

这时就满足了 2-3树 的特性。

1. 添加 32

这个就简单了，以现在的树结构，可以直接添加到 24 的 右边 ，变成 24,32

1. 添加 14

这个也简单，直接添加到 12 的右边，变成 12,14

1. 添加 26

此时应该添加到 24,32 的中间，由于一个节点只能添加两个数据，那么就需要拆分。

为了满足B树特点，发现上层的 16 只有一个数，那么就补足它。组成 16,26。

因为此时 24,32 这个节点，不满足 BST 的排序了，24是小于 26的。只能 32 满足。

拆完上层，再拆本层：由于 24 介于 16,24 之间，则将它安排在 3 节点中的中间节点， 24,32 把 24 拆分出去了，只剩下 32 ，此时完全满足B树的特点

1. 添加 34

此时就简单了，添加到 32,34 中。

1. 添加 10

此时应该添加到 12,14 的左侧，但是不满足条件：一个节点最多只能装 2 个数据。

放到 12,14 的左节点，也不满足条件：所有叶子节点必须在同一层，也不满足 2-3树 节点的 数量要求。

那么此时就需要拆分，先看它们上层 16,26 是满 的，如何做呢？看下图：

左侧的拆分图，上面我们分析过了，不满足B树要求，那么就需要拆分成右图这样：

1. 将 12,14 中的14 拆分成 右子节点 ，10 挂在 左节点。

2. 此时不满足 B树要求的，则将 16,26 中的 26 拆分成 右子节点。

3. 24 这个节点由于上层被拆分了，不满足在中间节点了。调整它的位置

4. 原来的 32,34 节点调整为 16 的有节点。

5. 添加8

   此时很简单，组成 8,10 即可

   

6. 添加 28

这里有个小问题，此时 28 不是应该加在 26,28 吗？难道说还有一个规则？

• 只有一个数据的节点，下面只允许 最多右 2 个节点，要么没有
• 有 2 个数据的节点，下面只允许 最多 3 个节点，要么没有

1. 添加 38

此时就简单，直接组成 34,38

1. 添加 20

这个也简单，直接组成 20,24

2-3树添加规则总结

满足如下特点：

1. 所有 ==叶子节点== 都在同一层

   只要是 B 树都满足这个条件，就是==满树==。

2. 有两个子节点的节点 叫 ==二节点==

   二节点要么 ==没有子节点== ，要么 ==必须有两个子节点==。

3. 有三个子节点的节点叫 ==三节点==

   三节点要么 ==没有子节点==，要么 ==必须有三个子节点==。

4. 2-3树 是由 ==二节点== 和 ==三节点== 构成的树

5. 构建的树，要满足二叉排序树（BST）的顺序。

6. ==一个节点中，最多只允许放 2 个数据==。

7. ==只有一个数据的节点==，下面只允许 ==最多有 2 个节点，要么没有==

8. ==有 2 个数据的节点==，下面只允许 ==最多有 3 个节点，要么没有==

其它说明

除了23树，还有234树等，概念和23树类似，也是一种B树。如图：

B树，B+ 树，B*树

B树的介绍

B-tree 树即 ==B树==，B即==Balanced==，平衡的意思。有人把B-tree翻译成B-树，容易让人产生==误解==。会以为B-树是一种树，而B树又是另一种树。实际上，==B-tree就是指的B树==。

前面已经介绍了 2-3树 和 2-3-4树，它们就是B树(英语: B-tree 也写成 B-树)，这里我们再做一个说明，我们在学习MySQL时，经常听到说某种类型的索引是基于B树或者B+树的，如图：

B树的说明:

1. B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4
2. B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.
4. 搜索有可能在非叶子结点结束
5. 其搜索性能等价于在关键字全集内做一次二分查找

B+树的介绍

B+树是B树的变体，也是一种多路搜索树。

B+树的说明:

1. B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
2. 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
3. 不可能在非叶子结点命中
4. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
5. 更适合文件索引系统
6. B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然.

B树的介绍

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

B树的说明:

1. B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
2. 从第1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高