本文将对二叉搜索树、平衡二叉树(AVL树)、B 树、B+树四种数据结构进行详解。

除此之外，根据 B+ 树的存储方式不同详解聚簇索引和非聚簇索引。

B+ 树是从二叉搜索树、平衡二叉树(AVL树)、B 树这三种数据结构一步一步演化过来的。

二叉搜索树

上图表示，我们将 user 表中的数据构建成一棵二叉搜索树。

图中的圆表示二叉搜索树的节点，节点存储了键(Key)和数据(Data)。键对应的是 user 表的 id ，数据对应的 user 表中的行数据。

二叉搜索树的特点就是任何节点的左节点的键都小于当前节点的键，右子节点的键都大于当前节点的键。顶端的节点叫做根节点，没有子节点的节点叫做叶子节点。

在对二叉搜索树进行查找 id = 12 的用户信息时，查找流程如下：

1. 首先将根节点作为当前节点，把 12 与当前节点的键 10 作比较，发现 12 大于 10，那么就走右节点，将右节点作为当前节点。
2. 继续把 12 与当前节点的键 13 作比较，发现 12 小于 13，那么就走左节点，将左节点作为当前节点。
3. 把 12 与当前节点的键 12 作比较，发现 12 等于 12，正好满足条件，就从当前节点取出 Data 数据，即 id =12, name = bg。

所以对于查找数据，利用二叉搜索树的时间复杂度为 O(logn)，不使用二叉搜索树而对 user 表一行行查，即全表扫描，时间复杂度为 O(n)。

平衡二叉树

利用二叉搜索树的特性可以快速查找到数据。但是如果二叉搜索树是下图的构造：

由 user 表转成 二叉搜索树时，由于表的行数据按 id 有序排列，导致对应的二叉搜索树退化为了一个链表。这个时候我们查找 id = 17 的用户信息，我们需要全部遍历一次，时间复杂度为 O(n)，就相当于全表扫描了。导致这个原因其实是二叉搜索树变得不再平衡了，树的高度太高了，查询效率不稳定。

为了解决这个问题，需要在二叉搜索树基础上保证树的平衡，所以就用到了平衡二叉树。平衡二叉树又叫 AVL 树，在满足二叉搜索树基础上，要求每个节点的左子树和右子树之间的高度差不超过1。

B 树

因为内存的易失性。一般情况下，对于 user 表中的数据和索引都存储在磁盘中。与内存相比，从磁盘读取数据的速度会非常慢，所以，我们应该尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。如果我们能把尽可能多的数据放进磁盘块中，那一次磁盘读取就会读取更多数据，那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构，那么我们每查找一次数据就需要从磁盘中读取一个节点，也就是一个磁盘块。可是平衡二叉树中每个节点只存储一个键和数据。这就导致，每个磁盘块都只存储一个键和数据，那么存储上亿数据时就会有上亿个节点，树的高度会非常高，查询效率会非常低。

为了解决平衡二叉树的这个问题，B 树可以做到一个节点存储多个键和数据。

B 树是在平衡二叉树的基础上做了修改，继承了二叉搜索树和平衡二叉树的优点，然后每个节点都能存储多个键和数据。下图中给出了 B 树的结构：

图中每个节点称为”页“，页就是磁盘块。

从 B 树的构图中可以看出，B 树相对于平衡二叉树，最大的不同有两个：

1. 每个节点存储了更多的键（Key）和数据（Data）
2. 每个节点有更多的子节点

基于这两个特点，整棵树高度会变得很矮，B 树查找数据读取磁盘的次数也会很少，数据的查找效率也会比平衡二叉树高很多。

比如我们要查找 id = 28 的用户信息，在上图 B 树构图中的查找流程为：

1. 先找根节点，也就是页 1，判断 28 在键值 17 和 35 之间，那么根据页 1 中的指针 p2，我们找到页 3
2. 将 28 与 页 3 的键相比较， 28 在 26 和 30 之间，那么根据页 3 的指针 p2 ，我们找到页 8
3. 将 28 与 页 8 的键相比较， 发现正好有匹配的键 28，键 28 对应的用户信息为（28，bv）

B+树

B+树是对 B 树的进一步优化。B+树的结构图为：

从上图中可以看到 B+ 树与 B 树的区别：

1. B+ 树非叶子节点上不存储数据，只存储键和指针，而 B 树的节点上不仅存储键和指针，还存储行数据。在树这种结构中，一个节点就是一个页，也是一个磁盘块，大小是固定的，如果不存数据，就可以存储更多的键，树会又矮又胖，这样我们再查找数据进行磁盘 IO 的次数也会减少，查询效率会更快。
2. B+ 树的所有数据都存储在叶子节点上，在每个叶子节点中的数据都是通过单向链表有序连接。同级节点之间通过双向链表链接，那么范围查询的 SQL 语句在 B+ 树这种数据结构中会变得很简单，效率也会很高。

B+ 树的每个页（节点/磁盘块）之间是通过双向链表连接的，叶子节点内的数据是通过单向链表连接的。所以通过页之间的双向链表以及叶子节点内部数据的单向链表可以找到表中的所有数据。

聚簇索引 与 非聚簇索引

在 MySQL 中，B+ 树索引按照存储方式的不同分为聚簇索引和非聚簇索引。

聚簇索引

在 MySQL 数据库表中，都会有一个主键 id。以主键 id 为 B+ 树索引的键而构建的 B+ 树称为聚簇索引。

非聚簇索引

以主键 id 之外的字段作为键构建的 B+ 树索引，称为非聚簇索引。

非聚簇索引与聚簇索引的区别就在于：非聚簇索引的叶子节点存储的不是表中的行数据，存储的是该行数据所对应的主键 id 。想要查找真正的行数据，还要再根据主键 id 去查聚簇索引，这个过程也称为回表。

利用聚簇索引和非聚簇索引查找数据

在上图的 B+ 树构图中，可以看出这就是聚簇索引（叶子节点存储的数据是行数据）

现在我们假设要进行范围查询，id >= 18 并且 id < 40的用户数据。对应的 SQL 语句为

select * from user where id >= 18 and id < 40

作为主键的 id 字段，查找流程如下：

1. B+ 树的根节点一般都是常驻内存的，也就是说页 1 已经在内存中了，此时不需要到磁盘中读取磁盘块，直接从内存中读取即可。
2. 对于当前节点，要查找 id >= 18 and id < 40 的范围值，我们首先在当前节点中找到 id = 18 的键，在页 1 中发现键 18 对应的指针为 p2，定位给到页 3 。
3. 从磁盘中把页 3 读取到内存中，然后再查找 id = 18 的键，找到指针 p1，定位给到页 8 。
4. 从磁盘中把页 8 读取到内存中，这时候发现页 8 的数据都是通过单向链表连接的，其中键都是按照顺序排放的，通过二分法定位给到键 18 。
5. 此时已经到了数据页了，也已经找到了符合条件的数据，但是作为范围查找，我们就需要继续对这条数据依次遍历查找符合条件的所有数据。在页 8 中一直找到键为 22 的数据，然后页 8 就没有数据了，此时我们拿着页 8 的 p 指针读取页 9 的数据。
6. 从磁盘中把页 9 读取到内存中，和页 8 一样进行数据的查找，直到将页 12 加载到内存中，发现页 12 的键 41 大于 40，不满足条件，查询到此结束。
7. 最终找到的所有数据，总共有 12 条记录：（18，kl）（19，kl）（22，bn）（24，tt）（25，vg）（29，jk）（31，jk）（33，st）（34，ty）（35，yu）（37，rt）（39，bn）。

利用非聚簇索引查找数据

在上图中是非聚簇索引的构图，其中叶子节点存储的不再是行数据，而是非主键字段对应行数据的主键 id，我们假设非主键字段是 score，这里就不再重复走一遍范围查询，直走一遍等值查询。

对应的SQL语句查询为：

select * from user where score = 34

查找流程和聚簇索引一样，不同的是最后找到的数据是（34，14），说明对应的主键 id 为14，我们需要再回到聚簇索引中查找 id = 14 的行数据，这样的操作也叫做回表。最终我们查到了想要的行数据（14，jk）