二叉树与B树

二叉树的问题分析：

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

二叉树需要加载到内存。如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)，就存在如下问题:

问题1：在构建二叉树时，需要多次进行i/o操作(海量数据存在数据库或文件中)，所以构建二叉树时，速度有影响

问题2：节点海量，也会造成二叉树的高度很大，会降低操作速度.

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

如图B树通过重新组织节点，降低了树的高度。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只需要一次I/O就可以完全载入。将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素。因此 B树(B+)广泛应用于文件存储系统以及数据库系统中。

多叉树

在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）

之后的2-3树，2-3-4树就是多叉树。多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。

举例说明(下面2-3树就是一颗多叉树)

2-3树基本介绍

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

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

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

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

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

示例：

将数列{16, 24, 12, 32, 14, 26, 10, 8, 34, 28, 38, 20} 构建成2-3树，并保证数据插入的大小顺序。

插入规则:

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

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

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

当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。

对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则

具体操作：

第一步：

因为需要满足插入规则的所有条件，有时某些数据还不能作为子节点出现，所以有时会出现该节点需要存放两个数据的情况，16的左右两条竖杠是为了和其他数据区分开。之后会遇到。

为什么说最多只能存放两个数据？因为只能有二节点和三节点的存在，而三节点最多只能存放两个数据，同时不能判断在以后这个节点会变成二节点还是三节点，所以每个节点都会能够容纳两个数据。

（我对这个方面没有仔细的查阅过，如果感兴趣这时每个节点内部是如何构造的，可以自行查阅。自我理解就是节点存放一个数据，能有两个子节点，这也是以前二叉树的构造。那多一个数据自然就只能有三个子节点。）

第二步：

因为插入规则的2和3，不能存在只有一个子节点的情况，所以24暂时存放在根节点中。

第三步：

在之前讨论过，每个节点只能存放两个数据，所以12的加入，让其变成二节点。（注意需要遵守二叉排序树的规则，即：左子节点比父节点值小，右子节点比父节点值大）

第四步：

首先32的加入不能和16存放在一起，否则会变成三节点，而现在的数据不足以满足三节点的条件，即插入规则3。同时32不能作为24的子节点，不能存在只有一个子节点的情况，所以32暂时和24存放在同一节点中。（这种情况之后不再赘述）

第五步：

因为26比16大，所以26本应该放在16的右子树中，但是16的右子节点中已经存放了两个数据，同时不能将16的右子树变成以26为父节点的二节点，因为需要满足插入规则1，所有叶子节点需要在同一层。所以26既然不能放在16的右子树中，那么就和16放在一起构成三节点，正好满足条件。（同时需要注意二叉排序树的规则，对于三节点同样成立，即：左子节点比父节点左值小，中子节点比父节点左值大、比父节点右值小，右子节点比右父节点值大。）