04. MySQL数据库索引

面试官：当一条查询执行较慢时通常可以如何进行优化

我：加索引！

面试官：那么到底什么是索引，其底层又是如何实现的呢

我：懵逼！

索引的常见模型

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

常见的实现索引的模型有： 哈希表、有序数组和搜索树

哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值即Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。（与HashMap类似）

优点：效率高

缺点：因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

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

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

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

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

索引的实现由存储引擎来决定，InnoDB索引的实现使用B+树模型

二叉树和红黑树的搜索效率很高，但是应用在数据库中时因为数据量较大，二叉树和红黑树每次只分裂出两个分支，导致分裂层数很大，空间占用率高

而B+树选择增加分支树，把整颗树的高度维持在很小的范围内，同时在内存里缓存前面若干层的节点，可以极大地降低访问磁盘的次数，提高读的效率。

同时要注意的一点是：二叉树类数据结构效率高的前提是数据有序，这也是数据库常存在一个自增主键的原因

扩展：什么是B+树

B-树即Balance-tree即B树

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

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

B树模型小结：

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

索引失效

1、如果条件中有or，即使其中有部分条件带索引也不会使用，除非条件中的列全部有索引。

2、like查询是以%开头（但是以%结尾却不会失效）

3、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引。（例如where ID = 3 和 where ID = "3"）

4、如果 mysql 估计使用全表扫描要比使用索引快,则不使用索引。（因为server层有优化器）