多路查找树概述

我们之前谈的树，都是一个节点可以有多个孩子，但是它自身只存锗一个元素。二叉树限制更多，节点最多只能有两个孩子。

一个节点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大（节点拥有子树的个数的最大值），要么树的髙度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个节点只存储一个元素的限制，为此引入了多路査找树的概念。

多路査找树（muitl-way search tree），其每一个节点的孩子数可以多于两个，且毎一个节点处可以存放多个元素。

由于它是查找树，所有元素之间存在某种特定的排序关系。在这里，每一个节点可以存储多少个元素，以及它的孩子数的多少是非常关键的。

我们讲解它的5种特殊形式:2-3树、2-3-4树、B树、B+树和B*树。

2-3树

1. 2-3树定义

2-3树是这样的一棵多路査找树：

• 其中的每一个节点都具有两个孩子（我们称它为2节点）或三个孩子（我们称它为3节点）；
• 一个2节点包含一个元素和两个孩子（或没有孩子）。与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2节点点要么没有孩子，要么就有两个，不能只有一个孩子；
• 一个3节点包含一小一大两个元素和三个孩子（或没有孩子）。一个3节点要么没有孩子，要么具有3个孩子。如果某个3节点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素；
• 所有的叶子节点都在同一层次上。

如下图所示，就是一棵有效的2-3树：

事实上，2-3树复杂的地方就在于新节点的插入和已有节点的删除。毕竟，每个节点可能是2节点也可能是3节点，要保证所有叶子都在同一层次，是需要进行一番复杂操作的。

2. 2-3树的查找

由二叉搜索树类推有搜索过程如下：

• 首先从根节点开始，比较根节点中Key与所查找Key的大小。若它与其中一个直接相等，那么查找命中；
• 若它的键小于节点中所有键，则进入左子节点继续查找；
• 若它的值在节点中两个键之间，则进入中子节点继续查找；
• 若它的值大于节点中所有键，则进入右子节点继续查找；
• 若查找路径进入了一个空指针，说明已经找过了叶子节点，则查找未命中；

3. 节点分裂与合并

在讲解2-3树的插入操作之前，先介绍一下节点分裂与合并。

2-3树只能存在2节点和3节点，由于插入的时候会引入4节点，所以我们需要将其分裂。比如单个4节点，只需将中间节点往上提，左边值作为其左子树，右边值作为其右子树即可：

有父节点的4节点，节点分裂后，需与父节点进行合并。我们可以把这种操作看作是向上分裂，即分裂后根节点与父节点合并后。但是与父节点合并后父节点有可能又变成了4节点，则可以继续向上分裂合并。

下图中6与3合并后，满足条件，无需再进行操作：

4. 2-3树的插入实现

2-3树插入可分为三种情况：

1. 对于空树，插入一个2节点即可，这很容易理解
2. 插入节点到一个2节点的叶子上。应该说，由于其本身就只有一个元素，所以只需要将其升级为3节点即可，该种情况下树的高度不变。

3. 往父节点为2节点的3节点中插入一个新元素。在这种情况下进行插入操作时，会首先构造一个4节点。我们首先需要对这个4节点进行分裂，然后合并到父节点。若此时父节点这种种情况下树高依然不变。

4. 往父节点为3节点的3节点中插入一个新元素。同上种情况一样，首先构造一个4节点，然后需要对这个4节点进行分裂，然后合并到父节点。但由于父节点也是3节点，所以合并后也变成了4结点，则需要再次对父节点进行分裂和合并，依次向上分裂合并直到满足条件。应当说，只要插入的路径中有一个2节点，树高依然不变。但还是有可能出现根结点变成4节点的情况，则需要对根节点进行分解。

如果2-3树插入的传播效应导致了根结点的拆分，则树的髙度就会増加。

5. 2-3树的删除实现

如果对前面插入的理解足够到位的话，对删除的理解应当不难，所以此处我们不细说。2-3树的删除也分为三种情况。与插入相反，我们从3结点开始说起：

1. 所删元素位于一个3节点的叶子节点上，直接删除，不会影响树结构。

2. 所删元素位于一个2节点上，直接删除，会破坏树结构。分为四种情况：

• 此节点双亲也是2节点，且拥有一个3节点的右孩子:

• 此节点的双亲是2节点，它右孩子也是2节点

• 此节点的双亲是3节点：

• 当前树是一个满二叉树，降低树高：

3. 所删元素位于非叶子的分支节点。此时按树中序遍历得到此元素的前驱或后续元素，补位。分两种情况：

• 分支节点是2节点：

• 分支节点是3节点：

2-3-4树

1. 2-3-4树定义

理解了2-3树，2-3-4树就很好理解了，它其实就是2-3树的概念扩展，包括了4节点的使用。对于一个4节点，它具有以下性质：

• 一个4节点包含小中大三个元素和四个孩子（或没有孩子），一个4节点要么没有孩子，要么具有4个孩子；
• 如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素；

2. 2-3-4树构建

由于2-3-4树和2-3树是类似的，我们这里就简单介绍一下，如果我们构建一个数组为{7,1,2,5,6,9,8,4,3}的2-3-4过程：

3. 2-3-4树删除

下图是一个2-3-4树的删除节点演变过程，删除顺序是1、6、3、4、5、 2、9。

B树

1. B树的定义

B树(B-tree)是一种平衡的多路査找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶(order)，因此，2-3树是3阶B树，2-3-4树是4阶B树。

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

一棵m阶的B-Tree有如下特性：

• 每个节点最多有m个孩子；
• 除了根节点和叶子节点外，其它每个节点至少有[ceil(m/2)]个孩子；
• 若根节点不是叶子结点，则它至少有 2 个孩子；
• 有 k 个孩子的非叶子结点有 k-1 个关键码，关键码按递增次序排列；
• 所有的叶子结点都在同一层;
• 每个非终端节点包含n个关键字信息(P0,P1,…Pn, k1,…kn)
• 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
• ki(i=1,…n)为关键字，且关键字升序排序
• Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

B树的关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子结点结束，其搜索性能等价于在关键字全集内做一次二分查找。

2. B树的应用

B树中的每个节点根据实际情况可以包含大量的关键字信息和分支 如下图所示为一个3阶的B-Tree：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围大于35。

模拟查找关键字29的过程：

• 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】；
• 比较关键字29在区间（17,35），找到磁盘块1的指针P2。 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】；
• 比较关键字29在区间（26,30），找到磁盘块3的指针P2。 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】；
• 在磁盘块8中的关键字列表中找到关键字29；

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+树

1. B+树定义

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

mysql> show variables like 'innodb_page_size';

从B-Tree图可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

关于B+树，我们需要记住以下几点：

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

2. B+树应用

将B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示:

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有22条数据记录，看不出B+Tree的优势，下面做一个推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为10^3,计算可得深度为3的树可以存储10亿数量级数据。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2-4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

B*树

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

B*树的说明:

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