本文共 1346 字，大约阅读时间需要 4 分钟。

多路查找

二叉树的问题分析

1. 二叉树需要加载到内存中去，当结点较少时，检索效率较高，但是当二叉树的结点过多时会出现如下问题

• 在构建二叉树的过程中，需要多次进行i/o操作（海量数据存储在数据库或者是文件中），构建二叉树时的速度严重下降
• 在检索二叉树时，二叉树高度过高，会带来检索上的困难

多路查找树

1. 基本介绍：其中每一个结点的子节点数多于两个，并且每一个节点可以存储多个元素。
2. 常见的四种特殊形式：2-3树，2-3-4树，B树，B+树

2-3树和2-3-4树

1. 基本介绍：2-3树是一种多路查找树，其中每一种节点都具有两个或者是三个字节点

2. 2-3树的特征：

   • 所有的叶子结点都在同一层面上
   • 由2结点和3结点构成

3. 2结点：该节点有两个子节点或者是没有子节点，同时左子树包含的值小于该元素，右子树包含的值大于该元素。

4. 3结点：该节点有三个字节点或者是没有节点，左子树的值小于中间子树的值，右子树的值大于中间字数的值。

2-3树的插入实现

1. 问题引入：将数列{16，24，12，32，14，26，34，10，8，28，38，20}构成对应的2-3树，并且保证数据插入的大小顺序
   图例:
   
2. 插入规则

• 满足2-3树的基本特点
  • 所有叶子结点都在同一层面上
  • 所有的2子节点，要么有两个字结点，要么没有子节点
  • 所有的3子节点，要么由三个子节点，要么没有子节点
  • 当按照规则插入某一数到某一个结点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满了，则拆本层，拆后仍然需要满足上述条件
  • 对于而节点的子树的值大小仍旧要遵循二叉排序树（BST）的规则。

3. 情况分类
   • 对于空树，直接插入一个2结点
   • 当插入结点到一个2节点的叶子上时，将其与当前节点相比较，然后将对应的2节点升级为3结点
   • 往3结点插入一个新的元素时，因为3结点已经是2-3树中最大的容量，故而将其拆分。且将树中的元素或者是插入的元素三者中选择其一，向上移动一层。

B树

1. 基本介绍：B树，值的是Balanced，是平衡的意思，是一种平衡的多路查找树，之前的2-3树和2-3-4树都是特殊的B树。

2. 相关说明：

   • B树的阶：子节点的最多的节点的字节点的个数。如2-3树的阶是3，2-3-4树的阶是4
   • B-树的搜索：从根节点开始，对节点内的关键字序列进行二分查找，如果命中就结束，否则进入查询关键字所属范围的儿子节点：重复操作，直到所对应的儿子节点的指针为空
   • 关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据

B+树

1. 基本介绍：B+树是B树的变体
2. 相关说明：
   • B+树基本与B数相同，区别在于B+树所有的关键字都是在叶子节点，必须命中叶子节点才能找到关键字
   • 所有的关键字都出现在叶子结点的链表中，且链表的关键字必须是有序的。（数据只在叶子节点中称之为稠密索引）
   • 非叶子节点相当于叶子结点的索引（稀疏索引），叶子节点相当于存储关键字的数据层
3. B+树更适合实际应用中操作系统的文件索引和数据库索引

B*树

1. B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟结点的指针
2. 相关说明：
   • B*树定义了非叶子节点关键字的个数至少为（2/3）*M，即块的最低使用率是2/3，而B+树的块的最低使用率为B+树的1/2
   • B*树的分配新节点的概率比B+树耕地，空间使用率更高

转载地址：http://rqgpb.baihongyu.com/