关于mysql:再一次学习-MySQL-索引

前言

提到数据库索引，大家必定很相熟，在日常工作中常常会接触到。这几天看了不少相干文章、书籍和课程。决定本人总结一篇文章，尽管我写的这篇文章必定不如网上各路大神的好文，然而本人总结一遍总归记得更牢固 ????。这应该也是一种好的学习习惯，他人写的字再丑陋都是他人的，本人写的字就算再潦草起码本人也能意识吧 ????。

索引是一种进步咱们查问效率的数据结构。就如同是字典的目录，一本几百页的字典，如果想疾速查问到某个字，总不能靠硬翻吧 ????。

索引构造

论断

MySQL 索引个别是哈希表或 B+ 树，罕用的 InnoDB 引擎默认应用的是 B+ 树来作为索引的数据结构。

为什么不必哈希表？

如果应用 B+ 树作为索引数据结构，那么拜访或批改一条数据的工夫复杂度是 O(log n)，然而应用哈希表作为索引构造干这些活的时候，工夫复杂度 O(1)。如果只是查一条数据或者批改一条数据，用哈希表做索引必定给力呀！然而个别业务零碎不会这么简略。

在业务开发中，常常会遇到范畴查问、排序查问等需要。这个时候哈希表索引就没方法高效的解决这些需要了。它只能通过扫表来实现这些性能，扫表应该是数据库的噩梦吧 ????。

MySQL 应用 B+ 树数据结构非叶子节点只贮存键值，叶子节点会贮存数据或者是主键。并且在叶子节点中键是依照顺序存储的，使得范畴查问、排序查问等变得异样简略。

尽管哈希表索引在操作单列数据的时候非常高效，然而须要范畴查问、排序查问的时候，B+ 树数据结构显然更适合。在咱们业务开发中，不可能只操作一行数据。综合思考，还是 B+ 树更适宜作为索引的数据结构。

哈希表索引不反对范畴查问，不能利用索引来排序，不反对联结索引最左匹配准则，如果反复键值比拟多，还容易造成哈希碰撞导致效率进一步升高 ????。

为什么不必 B 树？

B+ 树的非叶子节点上只贮存键值，而 B 树的非叶子节点上不仅贮存键值还贮存数据。在 MySQL 数据库中数据页的大小是固定的，Innodb 引擎数据页默认大小为 16 KB。B+ 树这种做法是为了让树的阶数更大，让树更矮胖。进行查问的时候，磁盘 IO 次数就会缩小，查问效率也会更快。

B+ 树的所有数据均贮存在叶子节点中，并且是按键值有序排列。然而 B 树的数据扩散在各个节点。进行范畴查问，排序查问的时候，B 树的效率必定不如 B+ 树。

B+ 树查找过程

磁盘块 1 中存储 17 和 35 数据项，还有 P1、P2、P3 指针，P1 示意数据项小于 17 的磁盘块，P2 示意数据项在 17 和 35 之间的数据项，P3 示意数据项大于 35 的数据项。非叶子节点不贮存数据，只贮存指引搜寻方向的数据项。

咱们晓得每次 IO 读取一个数据页的大小，也就是一个磁盘块。假如咱们要查找 29 这个数据项，首先进行第一次 IO 将磁盘块 1 读进内存，发现 17 < 29 < 35，而后选用 P2 指针进行第二次 IO 将磁盘块 3 读进内存，发现 26 < 29 < 30，而后选用 P2 指针将磁盘块 8 读进内存，在内存中做二分查找，找到 29，完结查问。

通过剖析查问过程，咱们能够晓得 IO 次数和 B+ 树的高度成正比。H 为树的高度，M 为每个磁盘块的数据项个数，N 为数据项总数。从上面的公式能够看出如果数据量 N 肯定，M 越大相应的 H 就越小。

M 等于磁盘块的大小除以数据项大小，因为磁盘块大小个别是固定的，所以减小数据项大小能力使得 M 更大从而让树更矮胖。这也是为什么 B+ 树把实在数据放在叶子节点而不是非叶子节点的起因，如果实在数据放在非叶子结点，磁盘块存储的数据项会大幅度缩小，树就会增高相应查问数据时的 IO 次数就会变多。

B+ 树个别能贮存多少数据？

这里咱们先假如 B+ 树高为 2，即存在一个根节点和若干个叶子节点，假如一行记录的数据大小为 1 KB，那么单个叶子节点（页）中的记录数等于 16 KB / 1 KB = 16 条数据。

而后要计算出非叶子节点能寄存多少指针，咱们假如主键 ID 为 bigint 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节，咱们一个页中能寄存多少这样的单元，其实就代表有多少指针，即 16 KB / 14 B = 1170。那么能够算出一棵高度为 2 的 B+ 树，大略就能寄存下 1170 * 16 = 18720 条数据。

依据同样的原理咱们能够算出一个高度为 3 的 B+ 树就能够寄存下 21902400 条数据。所以在 InnoDB 中 B+ 树高度个别为 1 – 3 层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次 IO，所以通过主键索引查问通常只须要 1 – 3 次逻辑 IO 操作即可查找到数据。

总结

1. 哈希表索引操作单数据行的时候很快，然而不反对范畴查问，不能利用索引来排序，不反对联结索引最左匹配准则。
2. B 树的数据能够存储在非叶子节点中，范畴查问时可能会有额定的随机磁盘 IO。而且因为实在数据寄存在非叶子节点中，B 树的高度肯定要高于同样状况下的 B+ 树。这样也不利于晋升效率。
3. B+ 树把实在数据存储在叶子节点中是为了让树更矮胖，缩小 IO 次数，晋升效率。

最初

这是我学习 MySQL 索引构造记录下的一些笔记 ????，之后也还会总结一篇索引应用的相干注意事项。我发现浏览完各路大神的文章之后，再本人写一遍印象会粗浅许多。尽管是炒旧饭，但也是炒给本人吃 ????。心愿大家多多给我激励，哈哈哈哈哈。

参考文章

我认为我对 MySQL 索引很理解，直到我遇到了阿里的面试官。
为什么 MySQL 应用 B+ 树 – 面向信奉编程
一篇文章讲透 MySQL 为什么要用 B + 树实现索引 – 腾讯云
面试题：InnoDB 中一棵 B + 树能存多少行数据？- 腾讯云
MySQL 索引原理及慢查问优化 – 美团技术团队
搞懂 Mysql InnoDB B+ 树索引 – 阿里云开发者社区