多路查找树
2019-05-11 本文已影响0人
TomyZhang
多路查找树(multi-way search tree)，其每一个结点的孩子数可以多于两个，且每一个结点可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。根据每一个结点可以存储多少个元素以及它的孩子数有多少个，可以将多路查找树划分为：2-3树，2-3-4树，B树（或叫B-树），B+树，B*树。
2-3树
一、概念
一般我们接触最多的是二叉树，也就是一个父结点最多有两个子结点。2-3树的意思是，一个父结点可以有两个子结点，也可以有三个子结点，并且其也满足类似二叉搜索树的定义（父结点的值大于左子树，但小于右子树），所有叶子结点都在同一层。
2结点：父结点存储一个值，最多有左右两个子树。假设父结点为p，子结点为l(左结点)、r(右结点)，且满足：
l < p < r
3结点：父结点存储两个值，最多有左中右三个子树。假设父结点分别为p1,p2，子结点分别为l(左结点)、m(中间结点)、r(右结点)，且满足：
l < p1
p1 < m < p2
r > p2
2-3树
二、相关操作
- 查找
- 插入
- 删除
2-3-4树
一、概念
2-3-4树的每一个结点可能包含一个、两个或三个数据，且任一结点到其每个叶子的所有路径包含的结点数都相同（深度相同）。
2-3-4树
二、相关操作
- 查找
- 插入
- 删除
B树（或叫B-树）
一、概念
一棵m阶B树是一棵平衡的m路搜索树。
特点：
- m即所有结点中孩子结点个数的最大值。
- 每个非根结点所包含的关键字个数j满足：ceil(m/2) - 1 <= j <= m - 1（ceil为向上取整，即大于该数的最小整数）。
- 结点的子结点数会比关键字个数多1。
- 根据以上两条可以得出，每个结点最多有m个分支，非根非叶结点至少有ceil(m/2)个分支。
B树
二、相关操作
- 查找
- 插入
- 删除
B+树
一、概念
一棵m阶B+树是一棵平衡的m路搜索树。
特点：
- 有k个子树的中间结点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子结点。
- 每个非根结点所包含的关键字个数j满足：ceil(m/2) <= j <= m（ceil为向上取整，即大于该数的最小整数）。
- 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接（叶子结点之间增加了横向的指针）。
- 所有的中间结点元素都同时存在于子结点，在子结点元素中是最大（或最小）元素。
B+树的优势：
- 单一结点存储更多的元素，使得查询IO的次数更少。
数据库检索对于磁盘IO扫描是最消耗时间的，因为磁盘扫描涉及很多物理特性，所以B+树设计的初衷就是最大限度的减少对于磁盘的扫描次数。如果一个表或索引没有使用B+树（对于没有聚集索引的表是用堆heap存储），那么查找一个数据，需要在整个表包含的数据库页中全盘扫描。这无疑会大大加重IO负担。而使用B+树进行存储，则仅仅需要将B+树的根结点存入内存中，经过几次查找后就可以找到存放需要数据的被叶子结点包含的页，进而避免了全盘扫描从而提高了性能。 - 所有查询都要查询到叶子结点，查询性能更稳定。
- 所有叶子结点形成有序链表，便于范围查询。
B+树
二、相关操作
- 查找
- 插入
- 删除
B*树
B* 树是B+树的变体，在B+树的非根非叶子节点中再增加指向兄弟节点的指针。B* 树定义了非根结点所包含的关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。
