mysql索引

一条查询语句是如何执行的

1. 当执行 SQL 语句时，应用程序会连接到相应的数据库服务器，然后服务器对 SQL 进行处理。
2. 接着数据库服务器会先去查询是否有该 SQL 语句的缓存，key 是查询的语句，value 是查询的结果。如果你的查询能够直接命中，就会直接从缓存中拿出 value 来返回客户端。
3. 如果没有命中缓存，则开始第三步。

• 3.1 解析 SQL：生成解析树，验证关键字如 select,where,left join 等）是否正确。
• 3.2 预处理：进一步检查解析树是否合法，如 检查数据表和列是否存在，验证用户权限等。
• 3.3 优化 SQL：决定使用哪个索引，或者在多个表相关联的时候决定表的连接顺序。紧接着，将 SQL 语句转成执行计划。

4. 最后，数据库服务器将查询结果返回给客户端。(如果查询可以缓存，MySQL 也会将结果放到查询缓存中)

这就是一条查询语句的执行流程，可以看到索引出现在优化 SQL 的流程步骤中，接下来了解索引到底是什么？

索引简介

索引是什么

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

索引的分类

从存储结构上来划分

• Btree 索引（B+tree，B-tree)
• 哈希索引
• full-index 全文索引
• RTree

从应用层次上来划分

• 普通索引：即一个索引只包含单个列，一个表可以有多个单列索引。
• 唯一索引：索引列的值必须唯一，但允许有空值。
• 联合索引：一个索引包含多个列。

从表记录的排列顺序和索引的排列顺序是否一致来划分

• 聚集索引：表记录的排列顺序和索引的排列顺序一致。
• 非聚集索引：表记录的排列顺序和索引的排列顺序不一致。

聚集索引和非聚集索引

聚集索引

以主键创建的索引
聚集索引在叶子节点存储的是表中的数据。

聚集索引表记录的排列顺序和索引的排列顺序一致，所以查询效率快，因为只要找到第一个索引值记录，其余的连续性的记录在物理表中也会连续存放，一起就可以查询到。

缺点：新增比较慢，因为为了保证表中记录的物理顺序和索引顺序一致，在记录插入的时候，会对数据页重新排序。

非聚集索引

以非主键创建的索引（也叫做二级索引）
非聚集索引在叶子节点存储的是主键和索引列。

索引的逻辑顺序与磁盘上行的物理存储顺序不同，非聚集索引在叶子节点存储的是主键和索引列，当我们使用非聚集索引查询数据时，需要拿到叶子上的主键再去表中查到想要查找的数据。这个过程就是我们所说的回表。

索引底层数据结构

索引的底层是怎么实现的呢？为什么索引可以如此高效地进行数据的查找？如何设计数据结构可以满足我们的要求？

哈希索引

可能直接想到的就是用哈希表来实现快速查找，就像我们平时用的 hashmap 一样，value = get(key) O(1)时间复杂度一步到位，确实，哈希索引 是一种方式。

哈希索引就是采用一定的哈希算法，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。本质上就是把键值换算成新的哈希值，根据这个哈希值来定位。

• 哈希索引没办法利用索引完成排序。
• 不能进行多字段查询。
• 在有大量重复键值的情况下，哈希索引的效率也是极低的（出现哈希碰撞问题）。
• 不支持范围查询。

在 MySQL 常用的 InnoDB 引擎中，还是使用 B+树索引比较多。InnoDB 是自适应哈希索引的（hash 索引的创建由 ==InnoDB 存储引擎自动优化创建==，我们干预不了）。

B树

• 关键字分布在整棵树所有节点
• 任何一个关键字 出现且只出现在一个节点中。
• 搜索有可能在 非叶子节点 结束。
• 其搜索性能等价于在关键字全集内做一次二分查找。

B+树

了解了 B 树，再来看一下 B+树，也是 MySQL 索引大部分情况所使用的数据结构。

• 非叶子节点的子树指针与关键字个数相同。
• 非叶子节点的子树指针 P[i]，指向关键字属于 [k[i],K[i+1]) 的子树（注意：区间是前闭后开)。
• 为所有叶子节点增加一个链指针。
• 所有关键字都在叶子节点出现。
• 所有的关键字 都出现在叶子节点的链表中，且链表中的关键字是有序的。
• 搜索只在叶子节点命中。
• 非叶子节点相当于是 叶子节点的索引层，叶子节点是 存储关键字数据的数据层。

相对 B 树，B+树做索引的优势

• B+树的磁盘读写代价更低。B+树的内部没有指向关键字具体信息的指针，所以其内部节点相对 B 树更小，如果把所有关键字存放在同一块盘中，那么盘中所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相应的，IO 读写次数就降低了。
• 树的查询效率更加稳定。B+树所有数据都存在于叶子节点，所有关键字查询的路径长度相同，每次数据的查询效率相当。而 B 树可能在非叶子节点就停止查找了，所以查询效率不够稳定。
• B+树只需要去遍历叶子节点就可以实现整棵树的遍历。

https://blog.csdn.net/wangfeijiu/article/details/113409719
https://zhuanlan.zhihu.com/p/29118331
https://www.runoob.com/mysql/mysql-index.html
https://www.cnblogs.com/zsql/p/13808417.html
https://www.infoq.cn/article/OJKWYykjoyc2YGB0Sj2c
https://blog.csdn.net/dengchenrong/article/details/88425762
https://zhuanlan.zhihu.com/p/73204847