MySQL索引
索引是什么
索引是数据库中用来提高性能的常用工具，索引在 MySQL 中也叫“键（Key）”，是存储引擎用于快速查找记录的一种数据结构，这也是索引的基本功能。
- 索引对于良好的性能很关键，尤其是当表中数据量越来越大时，索引对性能的影响愈发重要
- 在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但数据量逐渐增大时，性能会急剧下降。
- 索引类似一本书的目录，如果要在一本书中找到特定的知识点，先通过目录找到对应的页码
- 在 MySQL 中，存储引擎用类似的方法使用索引，先在索引找到对应值，再根据索引记录找到对应的数据行。
- 索引就是为了提高数据查询的效率，跟一本书的目录一样。
索引的优点
在MySQL中，首先在索引中找到对应的值，然后根据匹配的索引记录找到对应的数据行。索引可以包括
一个或多个列的值，如果索引包含多个列，那么列的顺序也十分重要，因为MySQL只能使用索引的最
左前缀。
- 索引大大减少了服务器需要扫描的数据量
- 可以帮助服务器避免排序和临时表
- 可以将随机IO变成顺序IO。
- 但对于非常小的表，大部分情况下会采用全表扫描。这样更高效
- 对于中到大型的表，索引就非常有效。但对于特大型的表，建立和使用索引的代价也随之增长
哈希索引
哈希索引
- 哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。
- 对于每一行数据, 存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值， 并且不同键值的行计算出的哈希码也不一样。
- 哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
- 只有Memory引擎显式支持哈希索引，这也是Memory引擎的默认索引类型。
- 因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这让哈希索引的速度非常快
哈希索引的限制
- 哈希索引数据不是按照索引值顺序存储的，无法用于排序。
- 哈希索引不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值
的。例如在数据列(a,b). 上建立哈希索引,如果查询的列只有a就无法使用该索引。 - 哈希索引只支持等值比较查询，不支持任何范围查询。
B-Tree索引
概念
- 不同的存储引擎有不同是底层数据结构，在InnoDB中使用B+ Tree索引
- B-Tree通常意味着所有的值都是按顺序存储的，并且每个叶子页到根的距离相同
- B-Tree 索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。
- 根节点的槽中存放了指向子节点的指针,存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。
- 最终存储引擎要么找到对应的值，要么该记录不存在。叶子节点的指针指向的是被索引的数据，而不是其他的节点页。
数据结构
B-Tree索引的限制
- 如果不是按照索引的最左列开始查找,则无法使用索引。
- 不能跳过索引中的列，例如索引为(id,name,sex), 不能只使用id和sex而跳过name。
- 如果查询中有某个列的范围查询，则其右边的所有列都无法使用索引。
B+Tree索引
概念
B+Tree索引的结构与B-Tree索引类似
区别
- B+Tree的非叶子节点不存储数据，所有data存储在叶子节点，导致查询查询时间复杂度为log
- 而B-Tree的查询时间复杂度不固定，与关键字在树中的位置有关，最好为O(1)
- B+Tree的节点两两相连可大大增加区间访问性，可使用范围查询等
- 而B-Tree每个节点关键字和data在一起，无法区间查找
- B+Tree更适合外部存储，由于内节点无data域，每个节点能索引的范围更大更精确
InnoDB为什么选择B+树作为索引结构
Hash索引
- Hash索引底层是哈希表，哈希表是一种以key-value存储数据的结构，所以多个数据在存储关系上是完全没有任何顺序关系的，所以，对于区间查询是无法直接通过索引查询的，就需要全表扫描。所以，哈希索引只适用于等值查询的场景。而B+ 树是一种多路平衡查询树，所以他的节点是天然有序的（左子节点小于父节点、父节点小于右子节点），所以对于范围查询的时候不需要做全表扫描
二叉查找树
- 解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表。
平衡二叉树
- 通过旋转解决了平衡的问题，但是旋转操作效率太低。
红黑树
- 通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多。
B+树
- 在B树的基础上，将非叶节点改造为不存储数据纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。
