多路查找树（B树）

多路查找树（multi-way search tree）：其中每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。

2-3树：

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

2-3-4树

是2-3树的概念拓展，包括了4结点的使用，一个4结点包括小中大三个元素和四个孩子（或者没有孩子），一个4结点要么没有孩子，要么有4个孩子。如果某个4结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。

B树

是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order），因此2-3树是3阶B树，2-3-4树是4阶B树。
一个m阶的B树具有如下属性：
（1）如果根结点不是叶结点，则其至少有两棵子树。
（2）每一个费根的分支结点都有k-1个元素和k个孩子，其中[m/2]<=k<=m（[]表示向上取整）。每一个叶子结点n都有k-1个元素，其中[m/2]<=k<=m。
（3）所有叶子结点都位于同一层次。
（4）所有分支结点包含下列信息数据（n,A0,K1,A1,K2,A2,……,Kn,An）,其中：Ki（i=1,2,……,n）为关键字，且Ki<Ki+1（i=1,2,……,n-1）;Ai（i=1,2,……,n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1,2,……,n），An所指子树中所有结点的关键字均大于Kn，n([m/2]-1<=n<=m-1)为关键字的个数（或n+1）为关键字的个数（或n+1为子树的个数）。
B树多应用于内外存的数据交互。
下图即为一个B树。

B树

B+树

B树还是有很多缺陷的。对于树结构来说，可以通过中序遍历来顺序查找树中的元素，都可以在内存中进行。
而在B树中，我们往返于每个结点之间必须得在硬盘的页面之间多次访问，如上图，遍历这棵B树，假设每个结点都属于硬盘的不同页面，为了中序遍历左右的元素，执行页面2->页面1->页面3->页面1->页面4->页面1->页面5，而且每次经过结点遍历时，都会对结点中的元素进行一次遍历，非常糟糕，有没有可能让遍历时每个元素只访问一次呢?
为了解决所有元素遍历等基本问题，在原有的B树结构基础上，加上了新的元素组织方式，就是B+树。
B+树是应文件系统所需而出的一种B树的变形树，严格意义上讲，已经不是以前定义的树了，在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当做它们在该分支结点位置的中序后继者（叶子结点）中再次列出，另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
下图为B+树。最后一个黄色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都连接在一起。

B+树
一棵m阶的B+树和m阶的B树的差异在于：
（1）有n棵子树的结点中包含有n个关键字。
（2）所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针、叶子结点本身依关键字的带下自小而大顺序连接
（3）所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字。
这样的数据结构最大的好处就在于，如果要随机查找，就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，他也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端结点。
如果我们需要从最小关键字进行从小到大的顺序查找，可以从最左侧的叶子结点出发，不经过分支结点，而是沿着指向下一叶子的指针就可遍历所有的关键字。