1、索引定义
MySql官方定义是这样的
Indexes are used to find rows with specific column values quickly.
Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.
The larger the table, the more this costs.
If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. This is much faster than reading every row sequentially.
索引用于快速查找具有特定列值的行。如果没有索引,MySQL必须从第一行开始,然后读取整个表以查找相关行。表越大,成本越高。如果表中有相关列的索引,MySQL可以快速确定要在数据文件中间寻找的位置,而无需查看所有数据。这比按顺序读取每一行要快的多。
通俗的理解就相当于一本字典的目录,如果你想快速查找某个字,就可以根据目录查找出对应的页码位置。
2、索引分类
索引从存储引擎的角度来看,共分4类索引,分别为B+Tree索引,哈希索引,全文索引,空间索引。
2.1 索引对比
索引类型 | 优点 | 不足 | 应用场景 |
B+Tree |
|
| InnoDb存储引擎默认索引 |
哈希索引 | 查询速度非常快 |
| Memory存储引擎默认索引; NDB集群引擎; |
全文索引 | 查找关键词,适合长文本场景匹配 |
| 相似度查询,搜索引擎 |
空间索引(R_Tree) | 各类维度组合查询数据,无需前缀匹配 | MySQL对GIS支持不完善 | MyISAM支持,但更好的替代是postgresql的PostGIS |
2.2 索引原理介绍
接下来重点针对我们常用的两类索引,b+tree索引,哈希索引进行原理的浅析
2.2.1 B+Tree 索引
- 非叶子节点只存储键值对信息。
- 所有的值存储在最底层叶子节点,节省空间。
- 顺序存储,便于范围搜索。
如上图说明
b+树索引数据的存储方式
浅蓝色的块我们称之为一个磁盘块,可以看到每个磁盘块包含几个数据项(橙色所示)和指针(红色所示),如磁盘块1包含数据项17和35,包含指针P1、P2、P3,P1表示小于17的磁盘块,P2表示在17和35之间的磁盘块,P3表示大于35的磁盘块。
真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据,只存储指引搜索方向的数据项,如17、35并不真实存在于数据表中。
b+树的查找过程
举例说明:要查找数据项29的过程,
1、首先会把磁盘块1由磁盘加载到内存,此时发生一次IO,在内存中用二分查找确定29在17和35之间,锁定磁盘块1的P2指针,内存时间因为非常短(相比磁盘的IO)可以忽略不计。
2、通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存,发生第二次IO,29在26和30之间,锁定磁盘块3的P2指针。
3、通过指针加载磁盘块7到内存,发生第三次IO,同时内存中做二分查找,找到29,结束查询。
总计三次IO。真实的情况是,3层的b+树可以表示上百万的数据,如果上百万的数据查找只需要三次IO,性能提高将是巨大的,如果没有索引,每个数据项都要发生一次IO,那么总共需要百万次的IO,显然成本非常非常高。
2.2.2 哈希索引
1、基于哈希表实现
2、哈希冲突,链表存储
存储方式
如上图,用户U2和U4根据哈希算法计算出来的值都是N,虽然形成哈希冲突,后续的值以链表的形式存储。
查找过程
键值key通过Hash映射找到桶bucket。在这里桶(bucket)指的是一个能存储一条或多条记录的存储单位。一个桶的结构包含了一个内存指针数组,桶中的每行数据都会指向下一行,形成链表结构,当遇到Hash冲突时,会在桶中进行键值的查找。
假设,这时候你要查U2对应的名字是什么,处理步骤就是:
首先,将U2通过哈希函数算出N;然后,按顺序遍历,找到U2对应的节点,得到对应的值NAME2。
需要注意的是,图中四个用户的值并不是递增的,这样做的好处是增加新的用户时速度会很快,只需要往后追加。但缺点是,因为不是有序的,所以哈希索引做区间查询的速度是很慢的。
你可以设想下,如果你现在要找身份证号在[U_X, U_Y]这个区间的所有用户,就需要全表扫描。
Hash冲突定义
如果桶的空间小于输入的空间,不同的输入可能会映射到同一个桶中,这时就会产生Hash冲突,如果Hash冲突的量很大,就会影响读取的性能。
通常Hash值的字节数比较少,简单的4个字节就够了。在Hash值相同的情况下,就会进一步比较桶(Bucket)中的键值,从而找到最终的数据行。
Hash值的字节数多的话可以是16位、32位等,比如采用MD5函数就可以得到一个16位或者32位的数值,32位的MD5已经足够安全,重复率非常低。
总结
今天介绍了MySQL的常见索引分类,对比了每一类索引的优缺点及适用场景,同时对B+tree索引,Hash索引的原理进行深入浅出的讲解,下一节,将重点介绍MySQL B+tree索引的最佳实践。
个人主页网站:https://travelprogrammer.com/