红黑树、AVL树、B树 和 B+树

发表于 分类于 阅读次数：

我们知道，索引的作用是做数据的快速检索，而快速检索的实现本质是数据结构。通过不同数据结构的选择，实现各种数据的快速检索。
下面介绍几种MySQL索引底层数据结构选型：

红黑树

特征：

  1. 他是一棵BST树
  2. 节点是红色或黑色
  3. 根是黑色
  4. 所有叶子都是黑色
  5. 每个红色节点必须有两个黑色的子节点
  6. 从任一节点到每个叶子节点的所有简单路径都包含相同数目的黑色节点

示例：
@w=600

红黑树插入情况总结：

  1. 当前节点是根节点：把根节点改为黑色
  2. 当前节点的父节点是黑节点：保持不变
  3. 当前节点的父节点是红节点，并且当前节点的叔叔节点是红节点：把交节点和叔叔节点改为黑色把祖父节点改为红色，把祖父节点作为当前节点，向上判断
  4. 当前节点的父节点是红节点，并且当前节点的叔叔节点不是红节点：四种情况
  • 祖父节点一＞父节点一＞当前节点，是一直向右：做左旋操作，再把父节点改为黑色，之前的祖父节点改为红色
  • 祖父节点一＞父节点一＞当前节点，是一直向左：做右旋操作，再把父节点改为黑色，之前的祖父节点改为红色
  • 祖父节点一＞父节点一＞当前节点，是先向左再向右：先对当前节点做左旋操作，再对当前节点做右旋操作，然后把当前节点改为黑色，之前的祖父节点改为红色
  • 祖父节点一＞父节点一＞当前节点，是先向右再向左：先对当前节点做右旋操作，再对当前节点做左旋操作，然后把当前节点改为黑色，之前的祖父节点改为红色

总结：

  • 红黑树是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态（时间复杂度为 $O(log n)$），也就保证了查找效率不会明显减低。
  • 但是红黑树也存在一些问题，红黑树并没有完全解决二叉查找树，虽然这个“右倾”趋势远没有二叉查找树退化为线性链表那么夸张，但是数据库中的基本主键自增操作，主键一般都是数百万数千万的，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗，我们数据库不可能忍受这种无意义的等待的。

AVL树

AVL树是另一种更为严格的自平衡二叉树。因为 AVL 树是个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能会更多。
特征：

  1. 它是一棵BST树
  2. 它每个节点的左右子树高度之差不超过1

@w=600

从树的形态看来，AVL 树不存在红黑树的“右倾”问题。也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。

总结：

  1. 不错的查找性能$O(log n)$，不存在极端的低效查找的情况。
  2. 可以实现范围查找、数据排序。

看起来 AVL 树作为数据查找的数据结构确实很不错，但是 AVL 树并不适合做 Mysql 数据库的索引数据结构，因为考虑一下这个问题：

  • 数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=0007 这个数据我们就要进行磁盘 IO 四次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

  • 磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

B树

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

B树的组成：

  1. 关键字（可以理解为数据）
  2. 指向孩子节点的指针

B 树的节点如下图所示，每个节点可以有不只一个数据，同时拥有数据数加一个子树，同时每个节点左子树的数据比当前节点都小、右子树的数据都比当前节点的数据大：

一棵B树必须满足以下条件：

  1. 若根结点不是终端结点，则至少有2棵子树
  2. 除根节点以外的所有非叶结点至少有 ceil(M/2) 棵子树，至多有 M 个子树（关键字数为子树减1, M 阶 B 树表示该树每个节点最多有 M 个子树）
  3. 所有的叶子结点都位于同一层

B树优点：

  1. 优秀检索速度，时间复杂度：B 树的查找性能等于 $O(hlogn)$，其中 h 为树高，n 为每个节点关键词的个数；
  2. B 树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度；
  3. 可以支持范围查找。

使用场景：
文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：

  • Windows：HPFS 文件系统
  • Mac：HFS，HFS+ 文件系统
  • Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
  • 数据库：ORACLE，MYSQL，SQLSERVER 等中

B+树

B树的升级版B+树：它比B树的查询性能更高。

一棵 B+ 树需要满足以下条件：

  1. 节点的子树数和关键字数相同（B 树是关键字数比子树数少一）
  2. 节点的关键字表示的是子树中的最大数，在子树中同样含有这个数据
  3. 叶子节点包含了全部数据，同时符合左小右大的顺序

简单概括下 B+ 树的三个特点：

  1. 关键字数和子树相同
  2. 非叶子节点仅用作索引，它的关键字和子节点有重复元素
  3. 叶子节点用指针连在一起

B 树和 B+树 的不同点：

  1. B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。
  2. B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

分析：
通过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。
其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。
因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

总结B+ 树的三个优点：

  1. 层级更低，IO 次数更少
  2. 每次都需要查询到叶子节点，查询性能稳定
  3. 叶子节点形成有序链表，范围查询方便