深入刨析 mysql 底层索引结构B+树

---

前言

很多人看过mysql索引的介绍：hash表、B-树、B+树、聚簇索引、主键索引、唯一索引、辅助索引、二级索引、联合索引、倒排索引、普通索引。。。等等。好像都知道，但是却分不清，本系列为大家系统分享介绍一下mysql的各种索引知识，将不同知识点串起来。

---

一、什么是索引？

MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构。

二、不同索引结构对比

2.1 二叉树

2.2 平衡二叉树

2.3 B-树

2.4 B+树

总结
1.索引为排好序的一种数据结构，用于提升数据库的查找速度。
2.Hash索引时间复杂度为O(1)，树索引是O(log(n))。Hash 底层是哈希表实现，等值查询，可以快速定位数据。但不支持范围查询，无法用于排序分组，无法模糊查询等操作。
3.B+树作为索引优势：

• 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；
• 非叶子节点存储记录的PK（KEY数据小，相同内存情况下，节点可以多存KEY，增大了节点广度(B+树出度更大，进而树高更矮，磁盘IO次数更少)）用于查询加速，适合内存存储；
• 叶子之间，增加了链表。可以很好的支持范围查询，并且获取所有节点，不再需要中序遍历；
• 更少查询次数：B+树出度更大，树高更低，查询次数更少；
• 很适合磁盘存储，能够充分利用局部性原理，磁盘预读（为了减少IO操作，往往不严格按需读取，而是预读。B+树叶子结点存储相临，读取会快一些）

三、mysql 的索引

3.1 聚簇索引

聚簇索引并不是一种单独的索引类型。而是一种数据存储方式（所用的用户记录都保存在页子节点）也就是所谓的索引即数据，数据即索引。

聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个非空唯一索引代替。如果没有，InnoDB 会使用隐藏的_rowid 列来作为聚簇索引。

如下图所示，一张表 聚簇索引和非聚簇索引的关系:

特点：

• 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
  • 页内 的记录是按照主键的大小顺序排成一个 单向链表 。
  • 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。
  • 存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 。
• B+树的 叶子节点 存储的是完整的用户记录。
  所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

优点：

• 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
• 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以 节省了大量的io操作 。

缺点：

• 插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
• 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新
• 二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据。（也就是常说的回表，但是并不是一定会回表）

限制:

• 对于mysql数据库中只有InnoDB支持聚簇索引，而MyISAM不支持聚簇索引。
• 由于数据物理存储方式只能有一种，而每个mysql的表只能有一个聚簇索引，一般情况下就是该表的主键。
• 如果没有定义主键，InnoDB会选择非空的唯一索引代替，如果没有这样的索引，InnoDB会隐式的定义一个主键来作为聚簇索引。
• 为了充分利用聚簇索引的聚簇的特性，索引InnoDB表的主键列尽量选用有序的id，而不建议使用无需的id，比如uuid，md5，hash，字符串作为主键将无法保证数据的顺序增常。

3.2 非聚簇索引

非聚簇索引：不是根据主键构建的索引叫做非聚集索引或者二级索引或者辅助索引。

二级索引中如果将多个列作为索引，就叫做联合索引
如果索引类型为唯一索引，索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一

可视化数据结构的网址 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html