## 浅谈MySQL索引 ### 首先我们要清楚什么是索引？ 索引就是相当于一本书的目录，可以帮助你快速的查找你所需要的内容。好比你想要用新华字典查一个字，你可以利用拼音或者部首进行查找在表中找到所对应的页码然后查看你想要查的这个字的详细内容。也就是说索引可以帮助我们更快的拿到MySQL中所存储的内容。 一般索引可以采用好多种数据结构进行存储，像上面所说的新华字典的相对于的就类似于Hash表的这么一个结构。 ### 哈希索引 哈希表是一种以键值对为存储单元的数据结构，你只要输入key就能得到相应的值Value。哈希的思想很简单就是将元素通过哈希函数确定元素在数组中的位置。但是这样子哈希就不可避免的会出现有不同的key在同一个数组的位置，处理这种哈希冲突(碰撞)的方法一般采用**拉链法**。 所谓的拉链法就是当发生冲突的时候通过链表将发生冲突的结点挂到这条链上。  如上图发生冲突的时候就会把相应的元素挂到对于的链表上。图中key不一定是递增的，所以哈希如果要查找一个区间内的所有元素的话需要将全部的结点扫描一次。**因此哈希只适用于只有等值查询的场景下**。 ### 有序数组 **有序数组在等值查询和范围查询的性能都很优秀**。我们根据一个例子来说明一下。我们要根据学号查找对应的学生姓名，如果用有序数组实现的话，如下图。  这里我们假设学号没有重复，这个数组是按照学号递增的顺序保存的。这时候如果你想要查一个id对应的名字，使用二分法很快就能找出，算法复杂度是O(log(N)) 同时如果想要查找一个[id1, id2]的范围的学生名字，我们可以遍历找到第一个id为id1的学生，然后向右继续遍历知道遇到第一个id大于id2的学生为止。 而**有序数组最大的缺点就是更新代价太大**，如果你想插入一个新的记录你就要将这个记录后面的所有记录都往后移动。 所以**有序数组所以一般只适用于静态存储引擎**，比如某年的人口普查信息等一些不会被修改的信息。 ### 二叉搜索树 二叉搜索树是很经典的数据结构，他的特点是每个结点的左儿子小于父节点，右儿子大于父节点。这样我们要查找某个学号id的话，就可以通过StuA->StuC->StuF->Stu2这个路径得到。这样的算法复杂度是**O(log(N)).**  为了保持查询复杂度为O(log(N)),我们需要保证每次插入新的记录都是有序的所以需要使用O(log(N))进行更新。 搜索二叉树有缺点就是他不是硬盘友好型的，因为索引不只存在内存中，还要写在磁盘上。如果搜索二叉树的高度太高的话，比如**100万个结点**的搜索二叉树，**树高20**。一次查询就要访问20个数据块，在机械硬盘时代，从磁盘随机读一个数据块需要**10ms**左右的寻址时间， 所以单独访问一个行就需要200ms的时间，这个查询真的有够慢的。 讲了半天我们都在讲一些数据结构相关的，但是这些都是数据库处理数据的核心概念之一，在分析问题的时候时常会用到。 下面我们正式走进InnoDB的索引模型 ### InnoDB的索引模型 在InnoDB中我们采用了**B+树**来存储索引，之所以使用B+树是由于他相对于二叉树来说能够有很好的硬盘亲和性，它是一棵多叉树，查询只要读取很少的数据块即可，相对于B树来说他的优势就是他的数据都存在叶子结点，并且将叶子结点连成了一个链表，能够顺序访问这些数据。  从图中不难看出，根据叶子结点的内容，索引的类型分为主键索引和非主键索引，主键索引的叶子结点存的是整行数据，非主键索引存储的是主键的值，在InnoDB中主键索引也称为聚簇索引，而非主键索引称为二级索引。 ------- 根据上面的索引结构说明，我们来讨论一个问题：**基于主键索引和普通索引的查询有什么区别**？ - 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树； - 如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树， 得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询 最后修改：2021 年 11 月 08 日 © 允许规范转载 打赏 赞赏作者 微信 赞 如果觉得我的文章对你有用，请随意赞赏
