树的演进过程

二叉查找树（BST）

特点

  1. 任意节点左子树不为空，则左子树的值均小于根节点的值；
  2. 任意节点右子树不为空，则右子树的值均大于根节点的值；
  3. 任意节点的左右子树也分别是二叉查找树；
  4. 没有键值相等的节点。

局限

解决了排序的基本问题，比普通树查找更快，查找、插入、删除的时间复杂度为O(logN)。但是由于无法保证平衡，可能退化为链表。

平衡二叉树（自平衡二叉查找树，AVL）

特点

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。

不管是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡。

局限

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大（旋转操作效率太低），故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。

红黑树

特点

一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树（由于是若平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索、插入、删除操作多的情况下，我们就用红黑树。

  1. 每个节点非红即黑；
  2. 根节点是黑的；
  3. 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的；
  4. 如果一个节点是红的，那么它的两儿子都是黑的；
  5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
  6. 每条路径都包含相同的黑节点。

局限

通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题。但是在磁盘等场景下，树仍然太高，IO次数太多。

B类树的诞生

MySQL中的数据一般是放在磁盘中的，读取数据的时候肯定会有访问磁盘的操作，磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。

盘片旋转就是市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。

这里就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，基于此进行优化的B类树就诞生了，提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树（相对于二叉树，B树每个内节点有多个分支），与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。

B类树

B树

  1. 定义任意非叶子结点最多只有M个儿子，且M>2；
  2. 根结点的儿子数为[2, M]；
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
  6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]，且K[i] < K[i+1]；
  7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  8. 所有叶子结点位于同一层。

image-20211017213146871

B+树

B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据）非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中。以下是B+树有而B树没有的特点：

  1. 非叶子节点的子树指针与关键字个数相同；
  2. 非叶子节点的子树指针p[i]，指向关键字值属于[k[i],k[i+1]]的子树。（B树是开区间，也就是说B树不允许关键字重复，B+树允许重复）；
  3. 为所有叶子节点增加一个链指针；
  4. 所有关键字都在叶子节点出现（稠密索引）（且链表中的关键字恰好是有序的）；
  5. 非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层；
  6. 更适合于文件系统；

img

为什么InnoDB选用B+树

磁盘读写代价更低

B树的每个结点都存储了key和data，B+树的data存储在叶子节点上。节点不存储data，这样一个节点就可以存储更多的key，使得树更矮，所以IO操作次数更少。

树高度越小，I/O次数越少。 为什么是B+树而不是B树呢，因为它内节点不存储data，这样一个节点就可以存储更多的key。

查询速度更稳定

B+所有关键字数据地址都存在叶子节点上，任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当，查询速度要比B树更稳定。

数据天然具备排序功能，便于区间查找和搜索

B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

全节点遍历更快

B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树在提高了IO性能的同时并没有解决元素遍历的效率低下问题，正是为了解决这个问题，B+树应运而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

Reference