04. MySQL数据库索引知识点总结

面试官：当一条查询执行较慢时通常可以如何进行优化
我：加索引！
面试官：那么到底什么是索引，其底层又是如何实现的呢
我：懵逼！

索引的常见模型

索引的出现是为了提高查询效率，就像书的目录一样

常见的实现索引的模型有：哈希表、有序数组和搜索树
哈希表：键 - 值(key - value)。
哈希思路：把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置
哈希冲突的处理办法：链表
哈希表适用场景：只有等值查询的场景
有序数组：按顺序存储。查询用二分法就可以快速查询，时间复杂度是：O(log(N))
有序数组查询效率高，更新效率低
有序数组的适用场景：静态存储引擎。
二叉搜索树：每个节点的左儿子小于父节点，父节点又小于右儿子
二叉搜索树：查询时间复杂度O(log(N))，更新时间复杂度O(log(N))
数据库存储大多不适用二叉树，因为树高过高，会适用N叉树
扩展：为什么树高过高就不好呢？
树高表示N叉树的层数，首先，层数越高占用空间就越大，同时层数越高表示查找到目标数据所要跳层的次数越大，层与层（实际上是父节点与父节点）之间是通过指针连接的，而两个节点的内存地址是连续的概率很低，因此就会触发磁盘随机读效率较低 当索引有100万数据，树高20（2的20次方） 一次查询可能需要跳跃 20 个数据块

哈希表 是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值即Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。（与HashMap类似）
优点：效率高
缺点：因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

你可以设想下，如果你现在要找某字段在[a, b]这个区间的数据，就必须全部扫描一遍了。

所以，哈希表这种结构适用于只有等值查询的场景，不适用于区间查询

有序数组 等值查询和范围查询场景中的性能就都非常优秀

搜索树模型又可以细分为二叉树红黑树B+树

索引的实现由存储引擎来决定，InnoDB索引的实现使用B+树模型
二叉树和红黑树的搜索效率很高，但是应用在数据库中时因为数据量较大，二叉树和红黑树每次只分裂出两个分支，导致分裂层数很大，空间占用率高
而B+树选择增加分支树，把整颗树的高度维持在很小的范围内，同时在内存里缓存前面若干层的节点，可以极大地降低访问磁盘的次数，提高读的效率。
同时要注意的一点是：二叉树类数据结构效率高的前提是数据有序，这也是数据库常存在一个自增主键的原因

扩展：什么是B+树

B-树 即Balance-tree即B树

B+树 B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要在找的数据。因为页目录中的槽是按照主键顺序排列的，所以在每一个页目录中，通过二分查找，定位到数据行所在的页，然后将整个页读入内存

扩展：我们可以人工调整页的大小吗？
所有的innodb索引都是btree索引，索引记录保存在叶子上，默认的索引页大小是16K。当有新的记录插入时，innodb出于对将来的insert和update操作的考虑，会尝试留下1/16的空闲页大小。

如果索引记录是完全按照索引记录的大小顺序插入的，那么索引也将填满整个页大小的15/16，如果插入顺序完全随机，那么索引页基本上填充为1/2至15/16自建。如果填充因子低于1/2,innodb会尝试重建b-tree。

Mysql5.6以后，可以通过innodb_page_size参数设置当前实例下每个索引页的大小，一旦设定，无法再更改回来。推荐的配置一般是16K，8K或者4K。另外假如一个Mysql实例设置了不同于默认值的innodb_page_size A，那么将无法使用其他不同于A值的实例上的文件（比如做一个物理备份和恢复）

B*树 是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针

B树模型小结：

B（B-）树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

说完底层实现我们来说一下表层

索引的种类

普通索引：仅加速查询

唯一索引：加速查询 + 列值唯一（可以有null）

主键索引：加速查询 + 列值唯一（不可以有null）+ 表中只有一个

联合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并

全文索引：对文本的内容进行分词，进行搜索

ps.索引合并，使用多个单列索引组合搜索
覆盖索引，select的数据列只用从索引中就能够取得，不必读取数据行，换句话说查询列要被所建的索引覆盖
联合索引本质：

当创建(a,b,c)联合索引时，相当于创建了(a)单列索引，(a,b)联合索引以及(a,b,c)联合索引。想要索引生效的话,只能使用 a和a,b和a,b,c三种组合；当然，a,c组合也可以，但实际上只用到了a的索引，c并没有用到！只用bc两个条件不会用到索引。
联合索引比对每个列分别建索引更有优势
因为索引建立得越多就越占磁盘空间，在更新数据的时候速度会更慢。另外建立多列索引时，顺序也是需要注意的，应该将严格的索引放在前面，这样筛选的力度会更大，效率更高。
前缀索引
有时候一个字段很长，我们只需要截取前几位或后几位（反转后取前几位）建立索引即可，节约了空间同时也能实现相同的效果
索引下推优化
没太懂，自行百度

索引失效场景
1、如果条件中有or，除非条件中的列全部有索引否则不会使用索引查询
2、like查询是以%开头（但是以%结尾却不会失效）
3、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引。（例如where ID = 3 和 where ID = "3"）
4、如果mysql估计使用全表扫描要比使用索引快,则不使用索引。（因为server层有优化器）
5、索引不会包含有null值的列，只要列中包含有null值都将不会被包含在索引中，复合索引中只要有一列含有null值，那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为null。
6、在列上进行运算将导致索引失效
注意点：
虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行insert、update和delete。因为更新表时，不仅要保存数据，还要保存一下索引文件。所以对数据量不大，查询率不高更新率高的的列添加索引反而得不偿失。
短索引
对串列进行索引，如果可能应该指定一个前缀长度。例如，如果有一个char(255)的列，如果在前10个或20个字符内，多数值是惟一的，那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。
索引回表
我们知道，一般查询数据时都是根据索引找到对应的索引id然后拿着索引id找到对应的数据，这个过程称为回表
覆盖索引
如果执行的语句是select ID from T where k between 3 and 5此时我们要查的数据就是索引，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引k已经“覆盖了”我们的查询需求，我们称为覆盖索引。

问题：针对上面说的索引失效第四条 那么什么情况下使用索引反而没有全表扫描快？
比如你要从一本字典中找到某一个字，使用目录查肯定很快，但是我现在要找到所有拼音a-x开头的字，走全表扫描就是直接翻，走索引需要将每个数据根据目录一层一层的去找反而变慢了。