MySQL 索引原理

MySQL索引深入剖析

官方定义是： 索引（Index）是帮助MySQL高效获取数据的数据结构，简单来说，索引是一种数据结构。以协助快速查询、 更新数据库表中数据。

数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址,如果没有索引的话，我们要从千万行数据里面检索一条数据，只能依次遍历这张表的全部数据, 直到找到这条数据。
但是我们有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种 特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到 数据了。

生活中随处可见索引的例子，如火车站的车次表、图书的目录等。它们的原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。

一：索引类型

1.1逻辑维度

• 主键索引：是一 种特殊的唯一索引它还多了一个限制条件，要求键值不能为空。主键索引用primay key 创建。
• 普通(Normal)：也叫非唯一索引，是最普通的索引，没有任的限制。
• 联合索引：多个字段创建的索引，使用时遵循最左前缀原则。
• 唯一 (Unique)：索引列中的值必须是唯一的，但是允许为空值。
• 空间索引：MySQL5.7之后支持空间索引，在空间索引这方面遵循OpenGIS几何数据模型规则。

1.2数据结构维度

• 哈希索引: 适合等值查询，检索效率高，一次到位。
• B+树索引：所有数据存储在叶子节点，复杂度为O(logn)，适合范围查询。
• 全文(Fulltext):针对比较大的数据，比如我们存放的是消息内容、一篇文章，有 几KB的数据的这种情况，如果要解决like査询在全文匹配的时候效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如char、varchar、text。
• R-Tree索引: 用来对GIS数据类型创建SPATIAL索引

1.3物理存储维度

• 聚集索引：聚集索引就是以主键创建的索引，在叶子节点存储的是表中的数据。
• 非聚集索引：非聚集索引就是以非主键创建的索引，在叶子节点存储的是主键和索引列。

二：索引存储模型推演

2.1、二分查找

二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。 所以第一个,我们可以考虑用有序数组作为索引的数据结构。

2.2、模型推演

1、有序数组，它用于等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题, 可能要挪动大量的数据(改变index),所以只适合存储静态的数据。

2、哈希结构，类似k-v结构，也就是，key和value是一对一关系。它用于「等值查询」还可以，但是范围查询它是无能为力的。

3、为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链 表，它的查找效率还是不够高，所以，有没有可以使用二分査找的链表呢？为了解决这个问题，BST (Binary Search Tree)也就是我们所说的二叉査找树诞生

4、二叉查找树的特点是什么？

• 每个结点最多两个子树，分别称为左子树和右子树
• 左子节点的值小于当前节点的值，当前节点值小于右子节点值
• 顶端的节点称为根节点，没有子节点的节点值称为叶子节点

投影到平面以后，就是一个有序的线性表。二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题，就是它的查找耗时是和这棵树的深度相关的，二叉树在最坏的情况下会退化成一个链表，在最坏的情况下时间复杂度会退化成O(n)，相当于全表扫描。因此，一般二叉树不适合作为索引结构。

5、造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢，这个就是平衡二叉树，叫做Balanced binary search trees,或者AVL树

平衡二叉树特点：它也是一颗二叉查找树，任何节点的两个子树高度最大差为1。所以就不会出现特殊化一个链表的情况

6、AVL树用于存储索引数据

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小，当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次10 *** 作。InnoDB *** 作磁盘的最小的单位是一页(或者叫一个磁盘块)，大小是16K(16384 字节)。那么，一个树的节点必须设计成16K的大小，不然就会出现读不完或者读不够的情况。

如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到16K的容量。

想象一下，我们基于索引査找数据的时候，肯定是希望一次从磁盘加载很多的数据 到内存中进行比较，这样就可以尽快拿到完整的数据。如果一个节点只存1个这样的单 元，就需要读更多的节点，发生更多的I/O *** 作。如果是机械硬盘时代，每次从磁盘读取数据需要10ms左右的寻址时间，交互次数 越多，消耗的时间就越多

所以AVL树就会有下面的问题：

• 平衡二叉树插入或者更新时，需要左旋右旋维持平衡，维护代价大
• 如果数量多的话，树的高度会很高。因为数据是存在磁盘的，以它作为索引结构，每次从磁盘读取一个节点， *** 作IO的次数就多，消耗的时间就越多。

7、怎么解决这个问题？

• 第一个就是让每个节点存储更多的数据。
• 第二个节点上的关键字的数量越多，也就是意味着可以有更多的分叉（我们把它叫做"路数”）
• 第三因为分叉数越多，树的深度就会减少

这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的，这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。

8、多路平衡查找树（Balanced Tree）

这个就是B树，B树在枝节点和叶子节点存储键值、数据地址、节点引用。
特点：

• 分叉数（路数）永远比关键字数多1

比如：我们画的这棵树，每个节 点存储两个关键字，那么就会有三个分叉指向三个子节点（当然肯定不只存3个这么少）

9、那B树又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什 么区别？

B Tree在做检索时，检索效率非常高，但是在做数据插入和删除时，会破坏B Three本身的行知，所以为了保持B Tree的平衡，需要对节点进行分裂、合并、转移等 *** 作，跟AVL树的左旋和右旋是不一样的，而这个 *** 作在节点数量较多的情况下性能影响较大。，所以 解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。

节点的分裂和合并，其实就是InnoDB页的分裂和合并。如果索引键值有序，写满一页接着开辟一个新的页，如果索引键值无序，存储过程造成大量磁盘碎片，带来频繁的page分裂和合并。

B树相对于平衡二叉树，就可以存储更多的数据，高度更低。但是最后会选择B+树呢？因为B+树是B树的升级版

10、B+Tree

• B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。innodb中页的默认大小是16KB，如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。
• B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，链表连着的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。

总结一下，InnoDB中的B+Tree特性带来的优势：

• 它是BTree的变种，BTree能解决的问题，它都能解决
  B Tree解决的两大问题 ：每个节点存储更多关键字；路数更多

• 扫库、扫表能力更强
  如果我们要对表进行全表扫描，只需要遍历叶子节点就可以 了，不需要遍历整棵B+Tree拿到所有的数据

• B+Tree的磁盘读写能力相对于B Tree来说更强
  根节点和枝节点不保存数据区, 所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多

• 排序能力更强
  因为叶子节点上有下一个数据区的指针，数据形成了链表

• 效率更加稳定
  永远是在叶子节点拿到数据，所以I0次数是稳定的

三：为什么不用红黑树?

红黑树也是BST树，但是不是严格平衡的，不需要像AVL树那样严格平衡，通过变色和旋转来保持平衡。

• 节点分为红色或者黑色。
• 根节点必须是黑色的。
• 叶子节点都是黑色的N U LL节点。
• 不允许两个相邻的红色节点。
• 从任意节点出发，至惧每个叶子节点的路径中包含相同数量的黑色节点。
• 从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的2倍。

为什么不用红黑树？

• 1、只有两路
• 2、不够平衡

红黑树一般只放在内存里面用。例如Java的Map,它可以用来实现一致性哈希。

四：B+Tree作为索引的数据结构带来的好处

由于在B+ Tree中，每个节点不存存储数据区，只需要存储键值+指针，使得B+ Tree在每个节点存储的路数更多。

假设索引字段+指针大小一共是16个字节，那么一个Page页（一个节点）能存储1000个这样的单元（键值+指针）。假设一条记录是16bytes，一个叶子节点（一页）可以存储10条记录！

当数的深度是3的时候，就有1000^2个叶子节点，可存储的数据为1000 x1000 x 10 =10000000（千万）

也就是说，在InnoDB中B+树的深度在3层左右，就能满足千万级别的数据存储。

4.1、InnoDB 索引存储：每张InnoDB的表有两个文件（.frm和.ibd）

在InnoDB的某个索引的叶子节点上，它直接存储了我们的数据。 所以，为什么说在InnoDB中索引即数据，数据即索引，就是这个原因。

• 但是这里会有一个问题，一张InnoDB的表可能有很多个多索弓|,数据肯定是只有—份的那数据在哪个索引的叶子节点上呢？

  这里的就是聚集索引（聚簇索引），就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。InnoDB组织数据的方式就是（聚集）索引组织表（clustered index organize table）如果说一张表创建了主键索引，那么这个主键索引就是聚集索引，决定数据行的物理存储顺序。

• 那主键索引之外的索引，会不会也把完整记录在叶子节点放一份呢？

  并不会，因为这会带来额外的存储空间浪费和计算消耗。刚才已经讲了，如果有主键索引，那么主键索引就是聚集索引。其他的索引统一叫做"二级索引”（secondary index）。二级索引存储的是二级索引的键值，例如在name上建立索引，节点上存的是name 的值（很明显，它的键值逻辑顺序跟物理行的顺序不一致）。而二级索引的叶子节点存的是这条记录对应的主键的值。

• 二级索引检索数据的流程是这样的

  当我们用name索引查询一条记录，它会在二级索引的叶子节点找到，然后拿到主键值，然后再到主键索引的叶子节点拿到数据。

• 为什么不存地址而是存键值？因为地址会变化。

  从这个角度来说，因为主键索引比二级索引少扫描了一棵B+Tree （避免了回表）， 它的速度相对会快一些。

• 如果一张表没有主键怎么办？

  那完整的记录放在哪个索引的叶子节点？或者, 这张表根本没有索引呢？数据放在哪里？
  1、 如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索弘
  2、 如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引 作为主键索引。
  3、 如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐 藏的聚集索引，它会随着行记录的写入而主键递增。

五：B+树 索引搜索过程

###表结构
CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `name` varchar(255) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `sex` int(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_age` (`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

insert into user values(100,'1',43,'0');
insert into user values(200,'2',48,'0');
insert into user values(300,'3',36,'1');
insert into user values(400,'4',32,'0');
insert into user values(500,'5',37,'1');
insert into user values(600,'6',49,'0');
insert into user values(700,'7',28,'1');

select * from user where age=32;

• idx_age索引的索引结构图：

id主键索引，聚族索引结构图

• 1搜索idx_age索引树，将磁盘块1加载到内存，由于32<37,搜索左路分支，到磁盘寻址磁盘块2。
• 2将磁盘块2加载到内存中，在内存继续遍历，找到age=32的记录，取得id = 400.
• 3拿到id=400后，回到id主键索引树。
• 4搜索id主键索引树，将磁盘块1加载内存，在内存遍历，找到了400，但是B+树索引非叶子节点是不保存数据的。索引会继续搜索400的右分支，到磁盘寻址磁盘块3.
• 5将磁盘块3加载内存，在内存遍历，找到id=400的记录，拿到R4这一行的数据，好的，大功告成。

什么是回表？拿到主键再回到主键索引查询的过程，就叫做「回表」

六：覆盖索引

覆盖索引：在查询的数据列里面，不需要回表去查，直接从索引列就能取到想要的结果。换句话说，你SQL用到的索引列数据，覆盖了查询结果的列，就算上覆盖索引了。

这就是项目中不要select *, 而是要使用具体的字段 select id,age 的原因

七：索引下推

可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

八：联合索引之最左前缀原则

• 联合索引的最左N个字段。比如组合索引（a,b,c）可以相当于建了（a），（a,b）,(a,b,c)三个索引，大大提高了索引复用能力。
• 最左前缀也可以是字符串索引的最左M个字符。

九：索引创建建议

1、在用于where判断order排序和join的（on）、group by的字段上创建索引
2、索引的个数不要过多——浪费空间，更新变慢。
3、过长的字段，建立前缀索引。
4、区分度低的字段，例如性别，不要建索引——离散度太低，导致扫描行数过多。
5、频繁更新的值，不要作为主键或者索引——B+树的平衡导致 页分裂 ，影响效率
6、随机无序的值，不建议作为索引，例如身份z、UUID、MD5——无序，分裂
7、组合索引把散列性高（区分度高）的值放在前面
8、创建复合索引，而不是修改单列索引

9.1、大表添加索引
可以参考以下方法：
1.先创建一张跟原表A数据结构相同的新表B。
2.在新表B添加需要加上的新索引。
3.把原表A数据导到新表B
4.rename新表B为原表的表名A，原表A换别的表名；

十：索引失效

1、查询条件包含or，可能导致索引失效
2、如果字段类型是字符串，where时一定用引号括起来，否则索引失效
3、like条件中前面带%
4、联合索引，查询时的条件列不是联合索引中的第一个列，索引失效。
5、在索引列上使用mysql的内置函数，列运算（如，+、-、*、/），索引失效。
6、字符串不加引号，出现隐式的类型转化
7、负向查询：索引字段上使用（！= 或者 < >，not in，not like）时，可能会导致索引失效。
8、索引字段上使用is null， is not null，可能导致索引失效。
9、左连接查询或者右连接查询查询关联的字段编码格式不一样，可能导致索引失效。
mysql估计使用全表扫描要比使用索引快,则不使用索引