Comparison of B-Tree and Hash Indexes

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云原生数据库 PolarDB 分布式版,标准版 2核8GB
简介: B树和哈希数据结构对索引查询性能至关重要,尤其是在支持选择B树或哈希索引的MEMORY存储引擎上。B树索引适用于=、>、>=、<、<=及BETWEEN运算符,并能用于特定的LIKE比较;而哈希索引则专长于快速等式比较,但不支持范围查询,也无法用于加速ORDER BY操作。合理选择索引类型可显著提升查询效率。

了解B树和哈希数据结构可以帮助预测不同查询在索引中使用,这些数据结构的不同存储引擎上的执行情况,特别是对于允许您选择B树或哈希索引的MEMORY存储引擎。
image.png

B-Tree Index Characteristics

B树索引可用于使用=、>、>=、<、<=或BETWEEN运算符的表达式中的列比较。如果LIKE的参数是一个不以通配符开头的常量字符串,则该索引也可用于LIKE比较。例如,以下SELECT语句使用索引:

image.png

在第一条语句中,只考虑“Patrick”<=key_col<“Patricl”的行。在第二条语句中,只考虑“Pat”<=key_col<“Pau”的行。
以下SELECT语句不使用索引:

image.png

在第一条语句中,LIKE值以通配符开头。在第二条语句中,LIKE值不是常量。
如果你使用。。。LIKE“%string%”和字符串长度超过三个字符,MySQL使用Turbo Boyer-Moore算法初始化字符串的模式,然后使用此模式更快地执行搜索。
如果col_name被索引,则使用col_name IS NULL的搜索将使用索引。

任何不跨越WHERE子句中所有AND级别的索引都不会用于优化查询。换句话说,为了能够使用索引,必须在每个AND组中使用索引的前缀。
以下WHERE子句使用索引:

image.png

这些WHERE子句不使用索引:

image.png

有时MySQL不使用索引,即使有索引可用。发生这种情况的一种情况是,优化器估计使用索引需要MySQL访问表中很大比例的行。(在这种情况下,表扫描可能会快得多,因为它需要更少的查找。)但是,如果这样的查询使用LIMIT只检索部分行,MySQL无论如何都会使用索引,因为它可以更快地找到结果中返回的几行。

Hash Index Characteristics

哈希索引的特性与刚才讨论的有些不同:
它们仅用于使用=或<=>运算符的等式比较(但速度非常快)。它们不用于查找值范围的比较运算符,如<。依赖于这种单值查找的系统被称为“键值存储”;要将MySQL用于此类应用程序,请尽可能使用哈希索引。

优化器不能使用哈希索引来加速ORDER BY操作。(此类索引不能用于按顺序搜索下一个条目。)
MySQL无法确定两个值之间大约有多少行(这由范围优化器用来决定使用哪个索引)。如果将MyISAM或InnoDB表更改为哈希索引的MEMORY表,这可能会影响某些查询。
只能使用整个键来搜索行。(使用B树索引,可以使用键的任何最左侧前缀来查找行。)

相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
11月前
|
搜索推荐 机器人 SEO
Leetcode 62. Unique Paths & 63. Unique Paths II
原谅我重新贴一遍题目描述,不是为了凑字数,而是为了让搜索引擎能索引到这篇文章,其实也是算一种简单的SEO。 简单描述下题目,有个机器人要从左上角的格子走到右下角的格子,机器人只能向下或者向右走,总共有多少种可能的路径?
34 0
|
机器人
LeetCode 63. Unique Paths II
机器人位于m x n网格的左上角(在下图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 现在考虑是否在网格中添加了一些障碍。 有多少条独特的路径?
94 0
LeetCode 63. Unique Paths II
|
机器人
LeetCode 62. Unique Paths
机器人位于m x n网格的左上角(在上图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 有多少可能的独特路径?
75 0
LeetCode 62. Unique Paths
|
机器学习/深度学习
Leetcode-Medium 96.Unique Binary Search Trees
Leetcode-Medium 96.Unique Binary Search Trees
93 0
|
算法 机器人 人工智能
Binary Tree Paths
输出二叉树的寻叶路径Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree:    1  /   \2    3  \   5All root-to-lea...
694 0
[LeetCode] Lowest Common Ancestor of a Binary Search Tree
Well, remember to take advantage of the property of binary search trees, which is, node -> left -> val < node -> val < node -> right -> val.
802 0