侯瑞哲的博客

Ruizhe's Blog

0%

平衡二叉搜索树、B树、B+树、B*树理解

发表于 更新于 Valine：

平衡二叉搜索树

概念：

平衡二叉搜索是基于二分法的策略提高数据的查找速度的二叉树的数据结构；

特点：

平衡二叉搜索树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少物管数据的检索，大大提升了数据检索的速度；平衡二叉树的数据结构组转过程有以下规则。

  1. 非叶子节点只能允许最多两个子节点存在；
  2. 每一个非叶子节点的左子树上所有结点都小于当前节点的值，右子树上所有结点都大于当前节点的值；
  3. 树左右两边的层级数相差不会大于1；
  4. 没有值相等重复的结点；
  5. 左右子树也是平衡二查搜索树。

B树

概念：

B树和二叉树稍有不同的是B树属于多叉树又名平衡多路搜索树（查找路径不只两个）。

规则：

  1. 排序方式：所有结点关键字是按递增次序排列，并遵循左小右大原则；
  2. 子节点数：非叶子节点的子节点数>1，且<=M，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路，当M=2是时二叉树，M=3时是三叉）；
  3. 关键字数：枝结点的关键字数量大于等于ceil(M/2)-1 且小于等于M-1个（ceil是向正无穷方向取整的函数，如ceil(1.1) = 2）;
  4. 所有叶子节点都在同一层、叶子节点除了包含了关键字和关键字记录的指针外，也有指向其子节点的指针，只不过其指针地址都为null，对应下图最后一层节点的空格子。

最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）

  • B树的查找流程

    如上图如果要从上图中找到E字母，查找流程如下

    1. 获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往左找到左边的子节点
    2. 拿到关键字D和G，D<E<G所以直接找到D和G中间的节点。
    3. 拿到E和F，因为E=E所以直接返回关键字和指针信息（如果树结构立面没有包含所要查找的节点则返回null)；

  • B树的插入节点流程

    定义一个5阶树（平衡五路搜索树），现在我们要把3，8，31，11，23，29，50，28这些数字构建一个5阶树出来；

    遵循规则：

    1. 节点拆分规则：单签是要组成一个5路搜索树，那么此时m=5，关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
    2. 排序规则：满足节点本身比左子树左右节点大，比右子树所有节点小的排序规则。

    先插入3、8、31、11

    再插入23、29

    再插入50、28

  • B树节点的删除

    规则：

    1. 节点合并规则：当前是要组成一个5路查找树，那么此时m=5，关键字数必须大于等于ceil(5/2)-1（这里就是关键字数<2就要进行节点合并）
    2. 满足节点本身比左子树所有结点大，比右子树所有结点小的排序规则；
    3. 关键字数小于二时先从子节点取，子节点没有符合条件时就向父节点取，取中间值往父节点放；

    特点：

    B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;

B+树

概念：

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

规则：

  1. B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
  2. B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
  3. B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
  4. 非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料，这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的。Mysql 的B+树是用第一种方式实现）;

特点：

  1. B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
  2. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
  3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
  4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B*树

规则：

B*树是B+树的变种，相对于B+树他们的不同之处如下：

（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是ceil(m/2)，b树的初始化个数为（ceil(2/3*m)

（2）B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

特点：

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额外分解次数变得更少；

总结

1、相同思想和策略

从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；

2、不同的方式的磁盘空间利用

不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；