二叉树与多叉树

二叉树存在的问题

二叉树提供了高效的插入删除查找等操作，但是也存在一定的问题：

  • 当数据量较小时，普通二叉树不存在什么问题

  • 当数据量特别大时，会导致二叉树的深度过深，使用搜索算法自上向下搜索时经过的节点就会相当多。这些节点存储在外存储器时，每访问一个节点就相当于进行了一次 I/O，随着树深度的增加，开销会越来越大，进而降低操作速度！

多叉树

如果每个节点可以有更多的数据项和更多的节点，就是多叉树。

多叉树通过重新组织节点，降低树的高度，并且减少 I/O 读写次数来提升效率。

image-20200427205618162

2-3树

2-3树是最简单的b树结构，具有以下特点：

  1. 2-3树的所有叶子节点在同一层
  2. 二节点（有两个子节点的节点）要么没有子节点，要么有两个子节点
  3. 三节点（有三个子节点的节点）要么没有子节点，要么有三个子节点
  4. 2-3树是由二节点和三节点构成的树

B树、B+树、B*树

B树

B树（Balanced Tree），前面介绍的2-3树，还有2-3-4树都是b树

MySQL中的索引就是基于B树或B+树的

image-20200427213158970

  1. B树的阶：节点最多的节点的子节点个数（2-3树的阶是3）

  2. B树的搜索：

    从根节点开始，对节点内的关键字的有序序列进行二分查找，找到则结束，否则进入查询关键字所属范围的子节点

  3. 叶子节点和非叶子节点都可以存放数据（区别于B+树）

  4. 搜索有可能在非叶子节点结束（区别与B+树）

  5. 搜索性能等价于在关键字全集内做一次二分查找

B+树

B+树是B树的变体，也是一种多路搜索树。

image-20200427213704102

  1. B+树的搜索：

    只有到达叶子节点才会找到或结束，性能也等价于在关键字全集做一次二分查找

  2. 所有关键字都存储在叶子节点的链表中，且链表中的关键字也是有序的

  3. 非叶子节点相当于叶子节点的索引，叶子节点相当于存储数据的数据层

  4. 更适合文件索引系统

B*树

B*树是B+树的变体，在B+树的非根和非叶子节点增加指向兄弟的指针

image-20200427215305770

B*定义了非叶子节点关键字个数至少为（2/3）x M，块的最低使用率为 2/3，而B+树块的最低使用率为 1/2