引入多路查找树
我们之前谈的树，都是一个结点可以有多个孩子，但是它自身只存储一个元素。二叉树限制更多，结点最多只能有两个孩子。
一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大（结点拥有子树的个数的最大值），要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，显然成了时间效率的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制，因此引入多路查找树的概念。
多路查找树，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
2-3树
2-3树定义
2-3树就是这样一颗多路查找树：其中每个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）。
一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某3结点有孩子的话，左子树包含小于较小元素的结点，右子树包含大于较大元素的结点，中间子树包含介于两元素之间的结点。
如图所示：
2-3树的插入操作
对应2-3树的插入来说，与二叉排序树相同，插入操作一定是发生在叶子结点上。不同地方在于2-3树插入一个元素的过程有可能对该树的其余结点产生连锁反应。
2-3插入分为三种情况：
1、对于空树，插入一个2结点即可，这很容易理解。
2、插入结点到一个2结点的叶子上。由于其本身就只有一个元素，所以只需要将其升级为3结点即可，如图所示：
3、要往3结点插入一个新元素。因为3结点本身已经是2-3树结点最大容量（已经有两个元素），因此就需要将其拆分，且将树种两元素或插入元素三者中选择其一向上移动一层。
第一种情形：如下图，需要在左图中插入元素5，经过遍历可得到元素5比8小、比4大，因此它应该是需要插入在拥有6-7元素的结点3位置。但是6-7结点已经是3结点，不能再加。此时发现双亲结点4是2结点，因此可以考虑让它升级为3结点。
第二种情形：需要向下图中的左图中插入元素11。经过遍历可以知道需要插入在拥有9-10元素的3结点位置。同样道理，9-10结点不能再增加元素，其双亲结点12-14也是一个3结点，不能插入元素。再往上，结点8是2结点，因此可以将9、10拆分，12、14拆分，让根结点8升级为3结点。
第三种情形：如下图，需要在左图中插入元素2。插入位置是1-3的3结点位置。但是1-3、4-6、8-12都是3结点，不能再插入数据了，那就意味着，当前我们的树结构是三层已经不能满足当前结点增加的需要了。需要将1-3、4-6、8-12进行拆分。
2-3树删除实现
2-3树删除也分为三种情况：
1、删除元素位于一个3结点的叶子结点上，这非常简单，只需要在该结点处删除该元素即可，不会影响到整棵树的其他结点结构。
2、所删除的元素位于一个2结点上，即要删除的是只有一个元素的结点。
情形1：此结点的双亲也是2结点，且拥有一个3结点的右孩子。如图所示，删除结点1，只需要左旋，即6称为双亲，4成为6的左孩子，7是6的右孩子。
情形2：此结点的双亲是2结点，它的右孩子也是2结点。此时删除结点1，如果直接左旋会造成没有右孩子，因此需要对整棵树变形，办法是，我们目标是让结点7变成3结点，那就得让比7稍大的元素8下来，随即就得让比元素8稍大的元素9补充结点8的位置，于是成了中间图的样子，再通过左旋的方式，变成右图结果：
情形3：此结点的双亲是一个3结点。此时删除结点10，意味着双亲12-14这个结点不能称为3结点了，于是将此结点拆分，并将12与13合并成为左孩子。
情形4：如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整颗树不能满足2-3树定义，这样就不得不考虑要将2-3的层数减少。
3、所删除的元素位于非叶子的分支结点。通常是将树按中序遍历后得到次元素的前驱或后继元素，考虑让它们来补位即可。
如果我们要删除的分支结点是2结点：
如果我们要删除的分支结点是3结点：
2-3-4树
2-3-4树其实是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小、中、大三个元素和四个孩子（或没有孩子），一个4结点要么没有孩子，要么具有4个孩子。如果某4结点有孩子的话，左子树包含小于最小元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。
如图所示，我们构建一个数组为{7,1,2,5,6,9,8,4,3}的2-3-4树的过程和删除过程：
B树
B树其实就是一棵平衡的m路搜索树（balanced tree of order m），一种适用于外查找的树，它是一种平衡的多叉树，称为B树（细分B-树、B+树、B*树）
B树是一种平衡多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶，因此，2-3树和2-3-4树都是B树的特例。
一个m阶的B树具有如下属性：
在讲2-3-4树时插入9个数后的图转成B树示意如图，左侧灰色方块表示当前结点的元素个数：
在B树上查找过程就是一个顺时针查找结点和在结点中查找关键字的交叉过程。比如我们查找数字7，首先从外存读取得到根结点3、5、8三个元素，发现7不在当中，当在5和8之间，因此通过A2在读取外存6-7结点，查找到所要的元素。
如果大量数据存在外存，会造成内存和外存交换数据次数频繁，导致时间效率上的瓶颈，那么B树结构怎么就可以做到减少次数呢：
我们的外存，比如硬盘，是将所有信息分割成相等大小的页面，每次硬盘读写都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214字节。
在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。我们会对B树调整，使得B树的阶数（或结点的元素）与硬盘存储的页面大小相配。比如一颗B树的阶为1001（即1个结点包含1000个关键字），高度为2，它可以存储10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。这就好比我们普通人数钱都是一张一张地数，而银行职员数钱则是五张、十张，甚至几十张一数，速度当然是比常人快了不少。
通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内存的数据交互准备的。
B-树
B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。这样的检索称为随机检索；
B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
)查找操作
对B+树可以进行两种查找运算：
a.从最小关键字起顺序查找；
b.从根结点开始，进行随机查找。
在查找时，若非终端结点上的元素等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。
B+树和B-树最大的不同点是：
1).B-树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。
2).在B-树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好，而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比B-树多，树高比B-树小，这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中B+树的性能可能还会好些，而且B+树的叶子节点使用指针连接在一起，方便顺序遍历(例如查看一个目录下的所有文件，一个表中的所有记录等)，这也是很多数据库和文件系统使用B+树的缘故。
B+树的特点是能够保持数据稳定有序，其访问、插入与修改拥有较稳定的对数时间复杂度。