Mysql基础——索引

内容

• 索引基础知识点
• 索引数据结构
• 优化器为什么会选错索引？
• 普通索引和唯一所有如何选择？
• 如何给字符串添加索引？
• 排序查询如何通过索引进行优化？
  • 通过联合索引来优化排序
  • order by工作原理是什么？

一 索引基础

• 常见索引模型：哈希表、有序数组、搜索树
• 哈希表：适合等值查询的场景
• 有序数组：按顺序存储。查询用二分法就可以快速查询，时间复杂度是：O(log(N))，更新效率低
• 有序数组的适用场景：静态存储引擎。
• 主键索引和非主键索引
  主键索引的叶子节点存的是整行的数据(聚簇索引)，非主键索引的叶子节点内容是主键的值(二级索引)主键索引只要搜索ID这个B+Tree即可拿到数据。普通索引先搜索索引拿到主键值，再到主键索引树搜索一次(回表)；
• 页分裂与页合并：当一个数据页满了，按照B+Tree算法，新增加一个数据页，叫做页分裂，会导致性能下降。空间利用率降低大概50%。当相邻的两个数据页利用率很低的时候会做数据页合并，合并的过程是分裂过程的逆过程。
• 从存储和性能上看，自增主键是更好的选择，业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高，而且主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小；
• 回表：根据二级索引找到数据，然后在回到主键索引树搜索的过程，称为回表
• 覆盖索引：某索引已经覆盖了查询需求，称为覆盖索引，例如：select ID from T where k between 3 and 5，二级索引上已经有id值，不需要再次回表；
• 最左前缀原则：B+Tree这种索引结构，可以利用索引的"最左前缀"来定位记录，只要满足最左前缀，就可以利用索引来加速检索。最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符
  1. 第一原则是：如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
• 索引下推：在MySQL5.6之前，只能从根据最左前缀查询到ID开始一个个回表。到主键索引上找出数据行，再对比字段值。MySQL5.6引入的索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

二 索引数据结构

mysql索引数据结构采用B+树，采用聚簇索引的方式来组织表，主键索引就是聚餐索引，树的B+树的叶子节点存储行的真实数据，非主键索引的叶子节点存储的是主键的值。

2.1 聚簇索引

每个InnoDB的表都拥有一个索引，称之为聚簇索引，此索引中存储着行记录，一般来说，聚簇索引是根据主键生成的。为了能够获得高性能的查询、插入和其他数据库操作，理解InnoDB聚簇索引是很有必要的。

聚簇索引按照如下规则创建：

• 当定义了主键后，InnoDB会利用主键来生成其聚簇索引；
• 如果没有主键，InnoDB会选择一个非空的唯一索引来创建聚簇索引；
• 如果这也没有，InnoDB会隐式的创建一个自增的列来作为聚簇索引。

Note: 对于选择唯一索引的顺序是按照定义唯一索引的顺序，而非表中列的顺序, 同时选中的唯一索引字段会充当为主键，或者InnoDB隐式创建的自增列也可以看做主键。
聚簇索引整体是一个b+树，非叶子节点存放的是键值，叶子节点存放的是行数据，称之为数据页，这就决定了表中的数据也是聚簇索引中的一部分，数据页之间是通过一个双向链表来链接的，B+树是一棵平衡查找树，也就是聚簇索引的数据存储是有序的，但是这个是逻辑上的有序，但是在实际在数据的物理存储上是，因为数据页之间是通过双向链表来连接，假如物理存储是顺序的话，那维护聚簇索引的成本非常的高。

2.2 B+定义：

B+树满足如下条件，即可称之为m阶B+树：

• 根结点只有一个，分支数量范围为[2，m]
• 分支结点，每个结点包含分支数范围为[ceil(m/2), m]；
• 分支结点的关键字数量等于其子分支的数量减一，关键字的数量范围为[ceil(m/2)-1, m-1]，关键字顺序递增；

三 优化器为什么会选错索引？

• 选索引依据：优化器会根据扫描行数、是否使用临时表、是否排序等因素进行综合判断选择哪个索引；
• 扫描行数：根据索引的“区分度”来估算扫描行数，一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好。
  1.可以通过：show index from table来查看cardinality
• 优化器选错索引时如何办？
  1.采用 force index 强行选择一个索引；
  2.可以考虑修改语句，引导 MySQL 使用我们期望的索引
  3.在有些场景下，我们可以新建一个更合适的索引，来提供给优化器做选择，或删掉误用的索引。
• 索引统计信息不准确导致的问题，可以用 analyze table 来解决。

四 普通索引和唯一所有如何选择？

如果业务不需要唯一索引来控制数据的唯一性，那么尽量优先考虑普通索引，原因在于唯一索引用不上change buffer机制来改进性能，
2.1 change buffer
在实际过程中，mysql利用change buffer对要更新行的数据页不在内存这种情况做了优化，针对数据页不在内存这种情况，如果更新操作总是需要去随机IO磁盘拿取数据，效果会差一些，所以在buffer pool内存中开辟了一段空间change buffer,当有更新、delete、 insert语句时会把这个操作先写入change buffer, 之后在进行merge操作时，再把change buffer记录的操作应用到原数据页；

• 更新操作时，如果语句中有普通索引，则对普通索引的插入操作会利用change buffer，主键索引则不会，因为数据库对唯一索引的操作总是要把数据页读入内存，进行是否重复的判断，既然已经读入内存了，则不需要change buffer再来优化了；

五 如何给字符串添加索引

• 直接创建完整索引，这样可能比较占用空间；
• 创建前缀索引，节省空间，但会增加查询扫描次数，并且不能使用覆盖索引；
• 倒序存储，再创建前缀索引，用于绕过字符串本身前缀的区分度不够的问题；
  1.用于正序时，前缀重复率的，而字段倒叙后重复率的情景
• 创建 hash 字段索引，查询性能稳定，有额外的存储和计算消耗，跟第三种方式一样，都不支持范围扫描。
  1.额外多建立一个索引字段存储csc32计算得到hash值，通过这个字段来索引数据

六 排序查询如何通过索引进行优化？

6.1 通过联合索引来优化排序

例如有个表：

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;

执行如下语句时：

select name, city, age from people where city='昆明' order by name limit 100;

• 这样的查询，可以考虑添加联合索引（city,name）来加速排序，如果只在city上添加索引，那么name是无序的，mysql server会通过全字段排序或是rowid 排序算法来进行排序，效果都会大打折扣，而建立(city, name)联合索引，相同的city的所有行，就已经是排好序的，避免了排序；
• 如果是高频查询，还可以考虑(city, name, age)的联合索引，避免了回表，再次提升速度；

6.2 order by 是如何工作的呢？

mysql排序执行方式有两种，分别是：全字段排序和rowid排序。
全字段排序：
例如上面的搜索语句，根据city获取数据，然后根据name排序，其基本流程是：

• 初始化 sort_buffer，确定放入 name、city、age 这三个字段；
• 从索引 city 找到第一个满足 city='昆明’条件的主键 id，到主键 id 索引取出整行，取 name、city、age 三个字段的值，存入 sort_buffer 中；
• 从索引 city 取下一个记录的主键 id；
• 重复步骤上面步骤 直到 city 的值不满足查询条件为止，对 sort_buffer 中的数据按照字段 name 做快速排序；
• 按照排序结果取前 100 行返回给客户端。
  sort_buffer有参数sort_buffer_size确定，如果判断sort_buffer_size不够排序使用，会用磁盘的临时文件进行辅助排序，采取归并的方式进行排序；

rowid排序：

• 初始化 sort_buffer，确定放入两个字段，即 name 和 id；
• 从索引 city 找到第一个满足 city='昆明‘条件的主键 id，到主键 id 索引取出整行，取 name、id 这两个字段，存入 sort_buffer 中；
• 从索引 city 取下一个记录的主键 id；
• 重复上面步骤直到不满足 city='昆明’条件为止，对 sort_buffer 中的数据按照字段 name 进行排序；遍历排序结果，取前 1000 行，并按照 id 的值回到原表中取出 city、name 和 age 三个字段返回给客户端。
  并不是所有order by语句就一定要用到排序操作，只有当数据本身是无序时，才会进行排序操作，如果数据是有序组织的，那么就不需要进行排序了，例如上述所说的如果city和name字段建立的联合索引，那么数据是有序组织的，在查询时就不需要排序了，直接确实数据返回个客户端就好。

引用：《丁奇45讲》