通俗易懂的MySQL底层原理和索引讲解

1 什么是索引？

索引是帮助数据库高效获取数据的排好序的 数据结构 。

为什么使用索引？

先来看一个小例子：假设一个数据表 table1 中有两列数据，分别是col1和col2 ，现在要执行语句 select * from table1 where col1=8。

在不加索引的情况下，sql语句会从第一行开始查找对比，直到找到 col1=8 这条记录，一共查找次数是为 8 次。

那如果是采用索引的方式，把 col1 列存储在一个红黑树 ，从根节点进行查找，只需要 4 次就能查找到 col1=8 这条记录。

2 MySQL使用的索引结构

先说结论：在MySQL中，底层索引的实现采用的是B+树数据结构 。

从上面的例子可以看出，采用一个合适的数据结构建立索引可以有效提升查询效率，至于为什么在MySQL中不采用红黑树，哈希表等数据结构，原因如下：

二叉树： 二叉树的缺点就很明显了，很容易出现树失衡的情况。

红黑树： 一种弱平衡二叉树，可以自己根据节点进行调节平衡。但是它会在数据量大的情况下出现树高度太大的问题。

例如现在有500万条数据，根据二叉树的性质可以大致计算出红黑树的高度在21左右，这就意味着在查找叶子节点的时候，需要进行21次IO查找，这显然是不能满足数据库的性能需要。

哈希表： 哈希表一直由杰出的查找性能而出名，只需要通过一次哈希计算就能够实现精准查找。可是它在数据库中的表现却不那么好，原因是它不支持范围查找和排序。在实际开发中，使用数据库进行范围查找的情况比只查找一条记录的机会多得多，正是哈希表的无顺序存储，导致它在进行范围查找的时候每查找一条数据就得进行一次计算，这也是不能满足数据库需求。(只有memory内存存储引擎支持哈希索引)

什么是B+树？

它其实是 B-树 的一种形式，在原有基础上进行一些优化和升级。

非叶子节点中是不存储数据的，只存储索引（这些都是冗余的索引），目的是尽可能放下多的索引。
叶子节点中包含了所有的索引字段
叶子节点之间在B树的基础上增加了双向的指针连接，这样可以提升区间查询的性能

B+树的每个非叶子节点可以存储多个索引，一般高度可控制在3左右，这样就解决了红黑树结构出现高度不可控的情况，而每个节点中的一个索引，其实也是满足二叉树的左孩子节点小于根节点，右孩子节点大于根节点。

在MySQL中，非叶子节点的大小不是随便取的，默认是16KB大小。这个可以通过 SHOW GLOBAL STATUS LIKE 'Innodb_page_size'; 语句进行查询。

通俗易懂的MySQL底层原理和索引讲解

B+树的索引容量

结论
在采用默认节点大小16KB的情况下，大致计算索引容量能达到千万条级别。

以占用8个字节的 bigint 作为索引的情况举例：

B+树的一个非叶子节点中由多个索引以及索引对应的磁盘地址组成，一个索引占用8字节，磁盘地址默认占用6字节，那么一个非叶子节点就可以存储大约 16KB / 14B=1170 个索引和磁盘地址的组合；

一个叶子节点由于存储有 data数据，这个数据可能是磁盘地址，也可能是索引所在行的其他列的字段；假设占用空间以1KB计算(1KB其实比较大了)，一个节点就可以存储 16KB / 1KB = 16 个索引元素以及data部分；

一个高度为3的B+树，其存储容量就是 １１７０＊１１７０＊１６　＝　２１９０２４００　条，达到千万级别的数据量.

假设现在要从这两千万条记录中查找一行数据,只需要经过两次(根节点一般是常驻内存)磁盘IO即可实现.

3 聚集索引和非聚集索引

聚集索引

叶节点包含了完整的数据记录,索引和数据是在一起的. InnoDB 引擎的主键索引就是聚集索引.

Innodb的非主键索引采用的是非聚集索引,通过非主键索引可以查找到叶子节点中的主键索引,然后再通过主键索引进行查找数据.

通俗易懂的MySQL底层原理和索引讲解

问: 为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
- 在建表时,如果没有指定主键,那么系统会自动从第一列开始找一列不存在重复数据的列作为主键进行维护;
  如果找不到,则会维护一列隐藏列作为主键.所以为了减少数据库负担,我们应该主动建立一个主键.
- 之所以建议使用整型的,是因为方便索引之间的比较;
- 使用自增的数据作为索引,可以避免出现节点的分裂,从而改变树的高度和增加维护树的工作量.

通俗易懂的MySQL底层原理和索引讲解

非聚集索引

叶子节点不包含完成数据,只有数据的磁盘地址,索引和具体数据是分开的. MyISAM 引擎就是非聚集索引.

4 索引分类

主键索引

即主索引,根据主键建立索引,不允许重复,不允许空值;

如果表中没有定义主键,InnoDB会选择一个唯一的非空索引代替;如果没有这样的索引,则会隐式定义一个主键来作为聚集索引.
唯一索引

用来建立索引的列的值必须是 唯一的,允许空值.
普通索引

用表中的普通列构建的索引,没有任何限制.
全文索引

用大文本对象的列构建的索引
组合索引

在MySQL中,索引用多个列组合构建的索引,需要注意最左前缀法则,即在搜索时,只有按组合索引的顺序从最左列开始进行搜索,索引才会有效.