一条查询语句是如何执行的
- 当执行 SQL 语句时，应用程序会连接到相应的数据库服务器，然后服务器对 SQL 进行处理。
- 接着数据库服务器会先去查询是否有该 SQL 语句的缓存，key 是查询的语句，value 是查询的结果。如果你的查询能够直接命中，就会直接从缓存中拿出 value 来返回客户端。
- 如果没有命中缓存，则开始第三步。
- 3.1 解析 SQL：生成解析树，验证关键字如 select,where,left join 等）是否正确。
- 3.2 预处理：进一步检查解析树是否合法，如 检查数据表和列是否存在，验证用户权限等。
- 3.3 优化 SQL：决定使用哪个索引，或者在多个表相关联的时候决定表的连接顺序。紧接着，将 SQL 语句转成执行计划。
- 最后，数据库服务器将查询结果返回给客户端。(如果查询可以缓存，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
