MySQL索引详解

一. 索引简介

1. 索引：帮助MySQL高效查询数据的一种有序的数据结构。

2. 如果没有索引，查询某行数据，只能进行全表扫描。这时，需要频繁地进行磁盘IO，性能很差。

3. 索引一般是一个key-value结构，key是索引值

   对于聚集索引(InnoDB)，value是该行的所有数据

   对于非聚集索引(MyISAM)，value是该行所在的磁盘块的指针

二. 常用的索引数据结构

1. 二叉树(非平衡二叉树)

   弊端：无法保证平衡性。极端情况下，可能退化成链表。

2. 红黑树(平衡二叉树)

   1. 优势：平衡树，不会退化成链表，查询效率有一定提升。
   2. 弊端：当数据量较大时，树的高度不可控，导致磁盘IO次数较多，效率下降。
   3. 优化思路：让一个树的节点存储多个索引元素，有效降低树的高度。

3. B树

1. 特性：

   1. 树的每个节点，存储多个索引元素，同时存储索引对应的数据
   2. 叶节点具有相同的深度，叶节点的指针为空
   3. 所有索引元素不重复
   4. 节点中的数据索引从左到右递增排列

2. 弊端：

   1. 树的所有节点(包括叶子节点和非叶子节点)都同时存储索引和数据，导致每个索引元素所占空间较大。当树的节点空间一定时，每个节点存保存的索引元素数量就较少，最终导致树的高度较高。

   2. 树的每个节点的大小是固定的，一般为一页(Page)16KB。可通过命令查看：

      show global status like ‘Innodb_page_size’;

3. 优化思路：尽可能减少每个索引元素所占的空间大小，使得每个树节点可以存储更多的索引元素，从而减小树的高度。

4. B+树

   1. 特性：
      1. 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
      2. 叶子节点包含所有索引字段
      3. 叶子节点用指针连接，提高区间访问的性能
   2. 优势：
      1. 树高度较矮，针对大多数的表，2~4层即可满足需求。
      2. 区间访问性能较好

5. Hash

   1. 特性：对索引值进行hash，映射成对应数据行所在的磁盘文件指针。
   2. 弊端：
      1. 不支持范围查询
      2. 不支持模糊查询
      3. 不支持排序
   3. 适用场景：大量等值查询时

三. 存储引擎下的索引实现

存储引擎的粒度是表级别的。同一个数据库下的不同表，可以使用不同的存储引擎。

1. MyISAM引擎

1. MyISAM为聚集索引，索引文件和数据文件分离，索引数据保存的是对应行所在的磁盘文件指针

2. MyISAM使用3个文件保存数据：

   1. .frm：保存表的定义、结构等元信息
   2. .MYD：保存表中的所有数据行
   3. .MYI：保存表中的所有索引字段

3. InnoDB引擎

1. InnoDB为聚集索引，索引的叶子节点保存的是该行的所有数据
2. InnoDB使用2个文件保存数据：
   1. .frm：保存表的定义、结构等元信息
   2. .ibd：同时保存InnoDB的数据和索引
3. 对于主键索引，索引保存的是所在行的所有数据；对于非主键索引，索引保存的是主键索引的值

四. 联合索引

1. 联合索引的所有列，构成一个节点，保存在B+树中
2. 联合索引的最左前缀原则

五. 相关问题

1. 为什么InnoDB表必须有主键，且推荐整形的自增主键？

   InnoDB的表数据文件，就是按照B+树组织的一个索引结构文件，因此一定要有一个主键。如果用户没有自定义主键，InnoDB会为选择一列唯一索引作为主键。如果没有唯一索引，InnoDB会为每行数据生成一个唯一的整型自增数值rowId，作为主键。

   使用整型主键，索引查询时，比较效率较高。且整型字段所占空间较小。

   使用自增主键，大部分的插入操作，都是在叶子节点链表上的addLast，不会涉及到节点的分裂和平衡，插入效率很高。

2. 为什么InnoDB的的非主键索引，存储的是主键索引的值，而不是像主键索引一样直接存储数据？

   1. 数据一致性角度：如果数据在多个索引处维护，那么就存在数据一致性问题。插入一条记录时，需要在每个索引树上都插入一遍，就涉及到了分布式事务的问题。
   2. 存储空间角度：如果所有索引树都保存数据，会造成大量的空间浪费。