多路查找树：每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
1、2-3 树
- 2-3 树：每一个结点都具有两个孩子 (2 结点) 或三个孩子 (3 结点) 的多路查找树
- 2 结点：包含一个元素和两个孩子(或没有孩子) ，左小右大。
- 3 结点：包含一小一大两个元素和三个孩子(或没有孩子) ，左小右大。
- 2-3 树中所有的叶子都在同一层次上
2-3 树复杂的地方就在于新结点的插入和已有结点的删除。
插入
- 空树：创建一个 2 结点作为根节点
- 2 结点：将其升级为 3 结点
- 3 结点：先放入 3 结点，再将中间元素上移一层。若已是顶层，则作为新的根节点。
删除
- 3 结点：直接删除
- 2 结点：
- 双亲是 2 结点，其右孩子是 3 结点：左旋
- 双亲是 2 结点，其右孩子是 2 结点：先将右孩子变为 3 结点（双亲的双亲与右孩子结合为 3 结点，双亲的双亲的后继补充到双亲的双亲的位置），再左旋
- 双亲是 3 结点：将双亲一个元素拆分，与一个子元素合并为新的子元素
- 当前树是满二叉树：将层数减少
- 非叶子的分支结点：让前驱或后继补位
2、2-3-4 树
- 2-3-4 树：2-3 树的概念扩展，包括了 4 结点的使用
- 4 结点：包含小中大三个元素和四个孩子 (或没有孩子)，左小右大。
3、B 树
B 树 (B-tree）是一种平衡的多路查找树，2-3 树和 2-3-4 树都是 B 树的特例。
一个 m 阶的 B 树具有如下属性:
- 如果根结点不是叶结点，则其至少有两棵子树。
- 每一个非根的分支结点都有 k-1 个元素和 k 个孩子，其中
$\left \lceil m/2 \right \rfloor \leqslant k \leqslant m$。每一个叶子结点 n 都有 k-1 个元素，其中$\left \lceil m/2 \right \rfloor \leqslant k \leqslant m$。 - 所有叶子结点都位于同一层次。
- 所有分支结点包含下列信息数据(
$n,A_0,K_1,A_1,K_2,A_2,···,K_n,A_n$)，其中:$K_i$为关键字，且$K_i < K_{i+1}$;$A_i$为指向子树根结点的指针，且指针$A_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$A_n$所指子树中所有结点的关键字均大于$K_n$， n($\left \lceil m/2 \right \rfloor -1 \leqslant n \leqslant m-1$) 为关键字的个数(或 n+1 为子树的个数)。
查找
在 B 树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程
插入和删除
B 树的插入和删除，方式是与 2-3 树和 2-3-4 树相类似的，只不过阶数可能会很大而已。
减少内存与外存交换数据次数
对 B 树进行调整，使得 B 树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。
比如说一棵 B 树的阶为 1001 (即 1 个结点包含 1000 个关键字) ，高度为 2 ，它可以储存超过 10 亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。
4、B+树
- B 树缺陷：元素遍历时，必须得在硬盘的页面之间进行多次访问。
- B+树：为解决B 树缺陷，在原有的 B 树结构基础上，加上了新的元素组织方式。
在 B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者(叶子结点)中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
一棵 m 阶的 B+树和 m 阶的 B 树的差异在于:
- 有 n 棵子树的结点中包含有 n 个关键字;
- 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接;
- 所有分支结点可以看成是索引，结点中仅含有其子树中的最大(或最小〉关键字。
查找
B+树的结构特别适合带有范围的查找。
- 随机查找：与 B 树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，也只是用来索引，还是需要到达包含此关键字的终端结点。
- 顺序查找：从最左侧的叶子结点遍历，无需经过分支结点
插入和删除
B+树的插入、删除过程也都与 B 树类似，只不过插入和删除的元素都是在叶子结点上进行而已。