高性能 MySQL —— 索引类型

1、什么是索引

索引可以理解为数据库的“目录”。存储引擎通过索引找到对应值,再根据该值寻找对应行。

2、索引的类型

(1) B-Tree 索引

如果不指名索引类型,那默认是 B-Tree 索引。如它的名字一样,该索引使用 B-Tree 数据结构来存储数据。

不清楚 B-Tree 的可以看下这篇文章:BTree和B+Tree详解

不同的存储引擎对 B-Tree 的使用也不同:

  • MyISAM:使用前缀压缩技术使索引更小,但相应的会增加搜索成本。通过数据的物理位置引用被索引的行
  • InnoDB::按原数据格式存储。根据主键引用被索引的行

 

B-Tree 的中文意思是平衡多路查找树,每次查找都是从索引的根节点开始(类似与二分查找,不过 B-Tree 可以多路查找)。

每个非叶子结点都定义了一个区间(a,b),并且有三个指向下一个磁盘块地址的指针,分别对应区间的三个范围(小于 a,大于 a 小于 b,大于 b)。叶子结点的指针指向被索引的数据。

假设我们查找75:

  1. 从根节点开始寻找,与关键字(17,35)比较,75 > 35,根据 P3 指针获取最右的磁盘块
  2. 与关键字(65,87)比较,65 < 75 < 87,根据 P2 指针获取中间的磁盘块
  3. 与(75,79)比较,找到75

可以使用B-Tree 索引的查询类型:

  • 全值匹配:和索引中的所有列进行匹配
  • 匹配最左前缀:只是用索引的第一列
  • 匹配列前缀:匹配某一列的开头
  • 匹配范围值:比如查询年龄从0到10的结果(已为年龄字段建立索引)

B-Tree 索引的限制:

  • 查询条件如果不是从索引的最左列开始查找,则无法使用索引
  • 不能跳过索引中的列
  • 如果查询中有某个列是范围查询,则其右边的所有索引都无法使用索引优化查找

在创建 B-Tree 索引时一定要注意索引列的顺序,因为 B-Tree 索引的诸多限制都是与索引列的顺序相关的。

在优化时,可使用相同列、不同顺序的索引来满足不同的查询。

(2) 哈希索引

哈希索引基于哈希表实现,只有精确匹配所有的索引列的查询才有效。

哈希索引通过哈希函数计算某个数据的哈希值(创建时也是使用相同的哈希函数),并用该值寻找对应的记录指针。

因为哈希所以自身只需要存储对应的哈希值,所以索引结构十分紧凑,查找速度也十分快。

哈希索引的限制:

  • 哈希索引只包含哈希值和行指针,不包含具体的字段数据,所以哈希索引必须进行行读取
  • 哈希索引不是按照索引值顺序存储,所以不能使用排序
  • 哈希索引不支持部分索引列匹配查找,因为哈希值的计算需要用到所有列,缺少部分列会导致计算的哈希值不同,所以无法使用该索引
  • 哈希索引只支持等值比较查询
  • 出现哈希冲突时,会使用拉链法(Java 中的 HashMap)解决冲突,不过会降低查询效率

创建自定义哈希索引:

有些存储引擎不支持哈希索引,我们可以手动模拟。

假如我们需要存储大量 URL,查询时有以下语句:

select * from url where url = "https://www.ashtwo.cn"

如果为 URL 建立 B-Tree 索引,那么索引会很大。

可以增加一个用于索引的列 url_crc,使用 CRC32 做哈希函数,现在的查询语句:

select * from url where url = "https://www.ashtwo.cn" and url_crc = CRC32("https://www.ashtwo.cn")

这样做可以大大提高性能,且 where 条件中保留了对应值,即使有哈希冲突,也能通过对应值来判断。

SHA1() 和 MD5() 函数虽然能最大限度消除冲突,但这两个函数产生的哈希值是非常长的字符串,会浪费大量的空间,所以不要使用。

可以自己实现哈希函数,在效率的降低冲突上寻找平衡点。

(3) 空间索引

空间索引无须前缀查询。它会从所有维度来索引数据。查询时,可以有效地使用任意维度来组合查询

(4) 全文索引

全文索引是一种特殊的索引,它更像是搜索引擎,它需要注意很多细节,如停用词、词干和复数、布尔搜索等。

3、总结

索引的优点:

  • 索引大大减少了服务器需要扫描的数据量
  • 索引可以帮助服务器避免排序和临时表
  • 索引可以将随机 I/O 变为顺序 I/O

只有在合理使用索引的情况下,才能发挥出索引的优点。

以上内容筛选自《高性能MySQL》

  • 用支付宝打我
  • 用微信打我

Long may the sunshine

发表评论

电子邮件地址不会被公开。 必填项已用*标注

召唤蕾姆