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

前言

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

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

数据结构	查找时间复杂度	缺点	优点
hash表	O(1)	- hash冲突; - 无法范围查	随机查找效率高
二叉树	O(logN)	线性增加数据会退化成O(N)；数据量较大时，树会变高；每个节点只能存储一个数据，IO次数多
平衡二叉树	O(logN)	- 数据量较大时，树会变高；- 每个节点只能存储一个数据，IO次数多	- 线性增加数据不会退化成O(N)；
b-树	O(logN)	- 范围查询时效率低; - 数据分散在非叶子节点，当数据量大时，树的高度也不低	- 叶子节点和非叶子节点都可以存储数据; - m叉分裂，可以降低树的高度
b+树	O(logN)		- 非叶子节点只存key，不存data，大大降低了树的高度;- 叶子节点设计为链表，很好的支持了范围查询

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

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

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

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

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

在这里插入图片描述
如下图所示，一张表聚簇索引和非聚簇索引的关系:

特点：

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

优点：

缺点：

限制:

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