B树、B+树、B*树——简单介绍

B树、B+树、B*树——简单介绍

强烈推介IDEA2020.2破解激活，IntelliJ IDEA 注册码，2020.2 IDEA 激活码

一、为什么是有B树

二叉树存在的问题：二叉树的构建是在内存中执行的，需要将磁盘中的文件通过 IO操作进行读取。如果二叉树的节点少，这样也没有问题，但是如果二叉树的节点很多（比如说一个亿），则存在如下问题： 【1】在构建二叉树时，需要多次进行 IO操作（海量数据存储在数据库或者文件中），节点海量，构建二叉树时，速度有影响。 【2】节点海量，也造成了二叉树的高度很高，会降低操作速度。

二、B树（多叉树）

【1】在二叉树中，一个节点最多可以有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树； 【2】2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。如下图就是一个2-3树；

【3】文件系统及数据库系统的设计者利用磁盘预读（预先读取）原理，将一个节点的大小设置为页<page:数据读取的最小单位>的大小（通常为4k），这样每个节点只需要一次 IO就能载入内存；B树(B+树)广泛应用于文件存储系统及数据库文件系统中。

2-3 树基本介绍：最简单的 B树结构，具有如下特点：   ■  2-3 树的所有叶子节点都在同一层（只要是B树都满足这一点）；   ■  有两个子节点的叫二节点，二节点要么没有子节点，要么有两个子节点；   ■  有三个子节点的叫三节点，三节点要么没有子节点，要么有三个子节点；   ■  2-3 树是由二节点和三节点构成的树；   ■  当按照规则插入一个数到某个节点时，不能满足上述要求时，就需要拆分。先向上拆，如果上层满了，则拆本层。拆后仍需要满足上述条件；   ■  对于三节点的子树的值的大小仍然遵循（BST：二叉排序树）的规则；

2-3 树的插入和删除节点案例：链接

B-Tree树即B（Balanced：平衡）树，有人将B-Tree 翻译成 B-树，容易让人产生误解，会以为 B-树是一种树。实际上，B-Tree就是B树。

三、B树、B+树、B*树

【1】B树介绍：前面介绍的2-3、2-3-4树就是 B树，在 MySql 中经常听说某种索引是基于 B树、B+树的，如下图：

【2】B+树介绍：B+ 树是B树的变体，也是一种多路搜索树，如下图：

【3】B* 树介绍：B* 树是B+树的变体，在B+树的非根和非叶子节点增加了指向兄弟的指针，如下图：