索码理

V1

2022/07/30阅读:7主题:橙心

【MySQL系列】-B+树索引和HASH索引有什么区别

理解B+树和Hash索引的区别有助于我们预测索引在不同的存储引擎中是怎么执行查询的。

B+ TREE 索引特性

B数是一种在数据库索引中流行的树数据结构。该结构始终保持排序,从而可以快速查找精确匹配。MySQL中使用的是B树的一种变体,B+树,这种类型的索引可用于大多数存储引擎,例如InnoDB和 MyISAM。B+树中的B不是代表二叉(binary),而是代表平衡(balance),因为 B+树是从最早的平衡二叉树演化而来,但是B+树不是一个二叉树。

B+树可以用在=、 >、 >=、 <、 <= 、BETWEEN 等比较运算符中进行比较。也可以用在不是以通配符%开头的LIKE语句中进行比较,因为LIKE语句如果以通配符开头,索引可能会失效。
比如下面的SQL语句就没有使用索引即使key_col建立了索引。

SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';

如果使用LIKE '%string_like%' 进行查询时string_like字符串超过三个字符,MySQL将使用Turbo Boyer-Moore算法对string_like字符串进行初始化以达到快速查询的目的。

Boyer-Moore算法在用于查找子字符串的算法当中,BM(Boyer-Moore)算法被认为最高效的字符串搜索算法,它由Bob Boyer和J Strother Moore设计于1977年。一般情况下,比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能,比如大家所熟知的GNU grep命令使用的就是该算法,这也是GNU grep比BSD grep快的一个重要原因。 --- 百度百科

有时候即使查询能命中索引,MySQL也不会使用索引。当MySQL优化器发现通过索引需要扫描的行占比很大,在这种情况下,表扫描可能会快得多,因为它需要查找的行更少。

Hash 索引特性

Hash 索引是通过hash算法进行索引的建立和查询的,hash算法是把任意长度的输入通过hash算法变换成固定长度的输出,该输出就是hashcode,hash算法本质上来说是压缩算法。当数据量大很可能进行大量hash冲突,影响性能。所以hash所以更适合精确查询。

两者区别

B+树索引支持精确查询、比较查询、范围查询、模糊查询、排序等多种查询方式。
而Hash 索引更适合精确查询,也不能进行 ORDER BY排序操作,比较查询、范围查询、模糊查询更不好处理了。

总结

B+树索引支持的查询方式更多,更适合作为数据库索引的数据结构。但是如果系统需要Hash 索引这种key-value查询的方式也可以选择Hash 索引。

推荐阅读:
【MySQL系列】-索引知多少
MySQL MVCC你了解吗
温故而知新-MySQL隔离级别

如果文章对你有用就点个关注给个赞呗

分类:

后端

标签:

数据库

作者介绍

索码理
V1