学习 MySQL 索引时，经常会同时看到三个名词：

红黑树
B树
B+树

很多人看到这里会产生一种错觉：

红黑树是不是升级成了B树，B树又升级成了B+树？

其实不是。

红黑树、B树和B+树，都是用来提高数据查找效率的树形结构，但它们属于不同的设计路线，适合的场景也不一样。

简单来说：

红黑树：更适合内存中的有序查找
B树：更适合磁盘中的多路查找
B+树：在B树基础上进一步适配数据库索引

本文不研究复杂的旋转、分裂、合并算法，而是从零开始把这三种树的关系讲清楚。

---

一、为什么会出现各种“树”？

假设现在有一组数据：

10、20、30、40、50、60、70

现在要查找数字60。

最简单的方法是从头开始逐个比较：

10，不是
20，不是
30，不是
……
60，找到了

数据量很小时，这种方式没有问题。

但如果有100万条、1000万条数据，逐条查找就会非常慢。

于是，人们开始考虑：

能不能每比较一次，就排除一大部分数据？

树形结构就是为了解决这个问题。

例如：

            40
          /    \
        20      60
       /  \    /  \
     10   30  50   70

查找60时：

1. 先与40比较；

2. 60大于40，排除整个左边；

3. 向右查找；

4. 找到60。

树结构的核心思想就是：

通过分层和分支，不断缩小查找范围。

红黑树、B树和B+树，都是在这个基本思想上发展出来的。

---

二、先认识二叉查找树

理解红黑树之前，需要先知道什么是二叉查找树。

“二叉”的意思是：

每个节点最多有两个子节点。

分别是：

左子节点
右子节点

二叉查找树还满足一个基本规则：

左边的数据 < 当前节点 < 右边的数据

例如：

            40
          /    \
        20      60
       /  \    /  \
     10   30  50   70

因为数据按照大小组织，所以查询时可以不断排除一半范围。

查找50的过程是：

50 > 40，向右
50 < 60，向左
找到50

这比从头到尾逐个查找快得多。

---

三、普通二叉查找树有什么问题？

普通二叉查找树有一个严重问题：

它可能长歪。

例如按照下面的顺序插入数据：

10、20、30、40、50

可能形成这样的结构：

10
  \
   20
     \
      30
        \
         40
           \
            50

这棵树已经不像树了，而更像一条链表。

此时查找50，还是要从10一路找到50：

10 → 20 → 30 → 40 → 50

树原本的快速查找优势就消失了。

因此，需要一种能够自动保持相对平衡的二叉查找树。

红黑树就是其中一种。

---

四、红黑树是什么？

红黑树本质上是：

一种能够自动保持相对平衡的二叉查找树。

它仍然遵守二叉查找树的基本规则：

左边小
右边大
一个节点最多两个子节点

但是红黑树会给节点增加红色或黑色的标记，并通过颜色变化和旋转操作，避免树变得过度倾斜。

例如原本可能长成：

10
  \
   20
     \
      30

经过平衡调整后，可能变成：

       20
      /  \
    10    30

对于刚接触数据库索引的人来说，现在不需要记住红黑树具体有哪些颜色规则。

只需要理解：

红黑树通过一些平衡规则，让二叉查找树不会轻易退化成链表。

---

五、红黑树有什么特点？

红黑树有三个重要特点。

1. 它是二叉树

每个节点最多只有两个分支：

左
右

2. 它可以自动维持相对平衡

插入和删除数据后，红黑树会自动调整结构。

3. 它适合内存中的有序数据

例如Java中的TreeMap和TreeSet，通常就使用红黑树维护有序数据。

因为这些数据一般存储在内存中，访问一个节点的成本比较低。

---

六、红黑树为什么会和MySQL索引扯上关系？

因为学习MySQL索引时，会遇到一个问题：

数据库索引也需要快速查找数据，为什么不直接使用红黑树？

红黑树的查询效率明明已经很高，而且还能保持平衡。

问题在于：

MySQL中的大量数据主要存储在磁盘中，而不是全部存放在内存里。

在内存中，从一个节点访问下一个节点，成本比较低。

但在磁盘环境中，每访问一层，都可能需要读取新的数据页。

这时，树的高度就非常重要。

---

七、红黑树的限制：一个节点只有两个分支

红黑树是二叉树，一个节点最多只能把数据分成两个范围：

小于当前值
大于当前值

例如：

          50
        /    \
     小于50  大于50

每向下一层，只能继续分成两个方向。

当数据量特别大时，即使红黑树保持平衡，树的高度仍然可能比较高。

可以粗略理解为：

数据越多
↓
需要的节点越多
↓
树的层数越多
↓
可能读取的数据页越多

对于数据库而言，真正昂贵的往往不是进行一次数字比较，而是从磁盘读取一个数据页。

所以数据库希望：

树不仅要平衡，还要尽可能矮。

这就引出了B树。

---

八、B树是什么？

B树是一种：

多路平衡查找树。

这里有两个重点：

多路
平衡

“多路”的意思是：

一个节点不再只有两个子节点，而是可以有很多个子节点。

例如：

             [20 | 40 | 60]
           /      |      |      \
        <20    20~40  40~60    >60

这个节点中有三个key：

20、40、60

于是可以把数据分成四个范围：

小于20
20到40
40到60
大于60

这和红黑树有明显区别。

红黑树每层最多分成两个范围。

B树每层可以分成很多范围。

---

九、不要误解：B树不是Binary Tree

这是一个非常容易产生的误区。

很多人看到“B树”，会下意识认为：

B是不是Binary，也就是二叉树？

不是。

B树不是二叉树。

B树是多叉树，一个节点可以拥有很多个子节点。

可以这样记：

二叉树：一个节点最多两个孩子
B树：一个节点可以有很多孩子

B树中的字母B，历史上存在不同解释，但在学习数据库时，没有必要把它理解成Binary。

---

十、B树为什么比红黑树更适合磁盘？

因为B树一个节点可以拥有很多分支。

假设红黑树一层只能分成两个范围：

2个方向

而B树一层可以分成几百个范围：

几百个方向

那么在相同的数据量下，B树就可以更矮。

例如：

红黑树：

根节点
↓
第2层
↓
第3层
↓
第4层
↓
……
↓
目标数据

B树可能是：

根节点
↓
中间节点
↓
目标数据

树越矮，查询过程中需要读取的磁盘页通常就越少。

所以：

红黑树通过“平衡”避免长歪，B树通过“多叉”进一步降低树高。

---

十一、B树中的数据放在哪里？

B树的一个重要特点是：

非叶子节点和叶子节点都可以存储数据。

例如：

              [30 | 60]
            /     |     \
         [10]    [40]    [80]

这里的：

30、60、10、40、80

都可以代表真实数据记录。

因此查询30时，在根节点就可能直接找到，不需要继续向下。

查询40时，则需要进入下一层。

所以B树中的查询可能：

在根节点结束
在中间节点结束
在叶子节点结束

---

十二、B树已经很矮了，为什么还需要B+树？

B树已经解决了红黑树分支少、树容易较高的问题。

但是对于数据库索引而言，B树还有两个地方可以继续优化。

第一个问题：非叶子节点存放了真实数据

一个数据库页的空间有限。

如果非叶子节点既要存索引键，又要存放真实数据，那么一个页能够容纳的索引键就会减少。

索引键越少：

分支越少
↓
树可能越高
↓
磁盘页访问可能越多

数据库更希望非叶子节点专心负责导航。

第二个问题：范围查询不够方便

B树的数据可能分散在不同层级。

例如查询20到70之间的数据，可能需要在不同节点和不同层级之间不断跳转。

数据库中范围查询非常常见：

SELECT *
FROM user
WHERE id BETWEEN 20 AND 70;

因此，需要一种更适合连续范围扫描的结构。

B+树就是针对这些需求进行的改造。

---

十三、B+树是什么？

B+树是B树的一种变体。

它仍然是一种多路平衡查找树，但改变了数据的存储方式。

B+树最核心的规则是：

非叶子节点主要存储索引键和子节点指针，真正的数据记录集中存储在叶子节点。

例如：

               [30 | 60]
             /     |      \
            /      |       \
      [10,20]  [30,40,50]  [60,70,80]

上面的30和60主要用于导航。

它们告诉查询：

小于30，向左
30到60，向中间
大于等于60，向右

真正的数据集中在最下面的叶子节点中。

---

十四、B+树的叶子节点为什么要连接起来？

B+树中的叶子节点会按照索引键顺序组织，并且相邻叶子页之间可以进行顺序访问。

可以简化理解为：

[10,20] → [30,40,50] → [60,70,80]

查询40到70时：

1. 先通过上层索引找到40；

2. 从40开始在叶子层向后读取；

3. 经过50、60；

4. 读取到70后结束。

不需要重新从根节点开始查找每一个数据。

这就是B+树非常适合范围查询的原因。

---

十五、红黑树、B树、B+树放在一起看

可以用一张表把三者区分开。

对比项	红黑树	B树	B+树
树的类型	二叉查找树	多路查找树	多路查找树
每个节点的分支	最多2个	多个	多个
是否自动平衡	是	是	是
数据存放位置	各个节点	各层节点都可以	数据集中在叶子层
树的高度	数据大时相对较高	较低	通常较低
范围查询	可以，但不适合磁盘页连续扫描	可以	更适合
常见场景	内存有序结构	磁盘、文件系统	数据库索引

---

十六、用一个道路的比喻理解

红黑树：每个路口只有左右两条路

左边
右边

虽然道路不会严重倾斜，但数据很多时，需要经过的路口仍然可能比较多。

B树：每个路口有很多条路

第1条路
第2条路
第3条路
第4条路
……

每经过一个路口，就可以排除大量范围，因此需要经过的路口更少。

而且路口本身也可能存放目标数据。

B+树：上面的路口只负责指路

真正的数据全部放在道路最下面的终点区域。

而这些终点之间还按照顺序连接起来。

因此：

• 查单个数据，可以通过路标快速定位；

• 查一段数据，可以找到起点后沿着终点区域继续读取。

---

十七、它们不是简单的升级关系

不能简单地理解成：

红黑树淘汰了
↓
升级为B树
↓
再升级为B+树

更加准确的理解是：

它们是面向不同使用场景设计的查找树。

红黑树适合：

• 数据主要在内存中；

• 需要频繁插入和删除；

• 需要保持数据有序；

• 节点指针访问成本较低。

B树、B+树适合：

• 数据量非常大；

• 数据主要存储在磁盘或固态硬盘中；

• 需要降低树的高度；

• 需要减少页面读取；

• 需要进行范围扫描。

所以不是B+树在所有场景都比红黑树好。

而是：

在数据库索引这个场景中，B+树更加合适。

---

十八、为什么MySQL讨论中总会比较这三种树？

因为MySQL索引需要解决下面几个问题：

快速定位数据
减少磁盘页读取
支持范围查询
支持有序扫描
支持大量数据

于是会依次思考：

普通二叉查找树行不行？

可能长歪，退化成链表。

红黑树行不行？

能够保持平衡，但每个节点最多两个分支，数据量大时树仍然相对较高。

B树行不行？

多叉、平衡、树更矮，已经比较适合磁盘。

B+树为什么更合适？

非叶子节点主要负责导航，可以容纳更多索引键；数据集中在叶子层，也更适合范围扫描。

这就是三者会被放在一起讨论的原因。

---

十九、一个必须纠正的说法

很多文章会简单地说：

红黑树不支持范围查询，B+树支持范围查询。

这个说法并不准确。

红黑树本身也是有序结构，可以通过中序遍历完成范围查询。

真正的区别是：

红黑树的节点跳转更适合内存访问，而B+树的多路结构和叶子层顺序访问更适合数据库按照页读取数据。

因此，不应该说红黑树“不能”做范围查询。

更加准确的说法是：

在大规模磁盘数据库场景中，B+树完成范围查询通常更加高效。

---

二十、面试怎么回答？

如果面试官问：

红黑树、B树和B+树有什么区别？

可以这样回答：

红黑树是一种自平衡二叉查找树，每个节点最多只有两个子节点。它适合内存中的有序查找结构，但由于分支数量少，在数据量很大时树的高度相对较高。

B树是一种多路平衡查找树，一个节点可以存储多个索引键并拥有多个子节点，因此扇出更大、树高更低，更适合磁盘存储场景。B树的非叶子节点和叶子节点都可以存储数据。

B+树是在B树基础上的一种变体，非叶子节点主要负责导航，数据集中存储在叶子节点，并且叶子层按照索引键有序组织，更适合数据库中的范围查询和顺序扫描。

因此，在MySQL InnoDB索引场景中，B+树比红黑树和普通B树更加合适。

---

二十一、这一篇只需要记住三句话

第一句：

红黑树是一种平衡二叉查找树，一个节点最多只有两个子节点。

第二句：

B树是一种多路平衡查找树，一个节点可以拥有很多个子节点，各层都可能存储数据。

第三句：

B+树也是多路平衡查找树，但非叶子节点主要负责导航，数据集中在叶子层，更适合数据库索引。

再压缩成最简单的版本：

红黑树：二叉，适合内存
B树：多叉，各层可以有数据
B+树：多叉，数据集中在叶子层

---

二十二、结尾

红黑树、B树和B+树并不是三个毫无关系的概念。

它们都在解决同一个基础问题：

如何快速查找有序数据？

只是它们面对的环境不同。

红黑树关注的是：

如何让二叉查找树保持平衡

B树关注的是：

如何通过多叉结构降低树高

B+树进一步关注的是：

如何让索引导航、磁盘页读取和范围扫描更加高效

把这条逻辑理清以后，再看MySQL为什么选择B+树，就不会觉得这些数据结构是突然冒出来的。

下一篇可以继续进入：

《MySQL索引原理系列（三）：MySQL主键索引到底是什么？》

这一篇将从树结构正式进入MySQL索引，重点讲清楚：

• 主键是什么；
• 主键和索引是什么关系；
• 什么是主键索引；
• 什么是聚簇索引；
• 为什么InnoDB的数据会和主键索引组织在一起。