前言
提到数据库索引,大家肯定很熟悉,在日常工作中经常会接触到。这几天看了不少相关文章、书籍和课程。决定自己总结一篇文章,虽然我写的这篇文章肯定不如网上各路大神的好文,但是自己总结一遍总归记得更牢固。这应该也是一种好的学习习惯,别人写的字再漂亮都是别人的,自己写的字就算再潦草起码自己也能认识吧 。
索引是一种提高我们查询效率的数据结构。就好像是字典的目录,一本几百页的字典,如果想快速查询到某个字,总不能靠硬翻吧。
索引结构
结论
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 操作即可查找到数据。
总结
哈希表索引操作单数据行的时候很快,但是不支持范围查询,不能利用索引来排序,不支持联合索引最左匹配原则。
B 树的数据可以存储在非叶子节点中,范围查询时可能会有额外的随机磁盘 IO。而且由于真实数据存放在非叶子节点中,B 树的高度肯定要高于同样情况下的 B+ 树。这样也不利于提升效率。
B+ 树把真实数据存储在叶子节点中是为了让树更矮胖,减少 IO 次数,提升效率。
最后
这是我学习 MySQL 索引结构记录下的一些笔记,之后也还会总结一篇索引使用的相关注意事项。我发现阅读完各路大神的文章之后,再自己写一遍印象会深刻许多。虽然是炒旧饭,但也是炒给自己吃。希望大家多多给我鼓励,哈哈哈哈哈。