多路查找树
每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
四种特殊形式：
- 2-3树、
- 2-3-4树、
- B树
- B+树
2-3树
2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）
一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
并且2-3树中所有的叶子都在同一层次上。
2-3树复杂的地方在于新结点的插入和已有结点的删除。每个结点可能是2结点也可能是3结点，要保证所有叶子结点在同一层次。
2-3-4树
2-3-4树是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子（或没有孩子），一个4结点要么没有孩子，要么具有4个孩子。如果某个4结点右孩子的话，左子树包含小于最小元素的元素；第二个子树包含大于最小元素，小于第二元素的元素；第三字数包含书大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。
B树
B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶，因此2-3树是3阶B树，2-3-4树是4阶B树。
- 关键字集合分布在整棵树中
- 任何一个关键字出现且只出现在一个结点中
- 搜索有可能在非叶子结点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
- 自动层次控制
m阶B-树
- 树中每个结点至多有m个孩子
- 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息
- 每个非终端结点中包含有n个关键字信息，关键字的个数n必须满足： [m/2]-1 <= n <= m-1
image.png
出现的背景
平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构采用多叉树结构
事实实践中，系统存储容量的增长速度 << 应用问题规模的增长速度
| 时间 | 数据库规模 | 存储容量 | 倍数 |
|---|---|---|---|
| 1980 | 10MB | 1MB | 10倍 |
| 2000 | 1TB | 1GB | 1000倍 |
根节点，内部节点和叶节点
- 内部节点是具有子节点的节点。内部节点位于树的底部上方。
- 叶节点是没有子节点的节点。它们是树底部的节点。
- B-Tree的根节点是一个特殊节点。B-Tree只有一个根节点，它位于树的顶部。根据B-Tree中的项目数，根节点可以是内部节点或叶节点。
B+树
B+树是B-树的变体，也是一种多路搜索树
在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引
image.png
B*树
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针
image.png
网友评论