B-Tree和哈希索引比较

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS PostgreSQL,集群系列 2核4GB
简介: MySQL B-tree hash 哈希 索引 InnoDB

概述

理解B-Tree和哈希索引数据结构有助于预测不同的查询在不同的存储引擎如何使用这些索引来执行查询,尤其是MEMORY存储引擎可以让你选择B-tree或哈希索引。

  • B-Tree索引特性
  • 哈希索引特性

B-Tree索引特性

B-Tree可以使用的操作符有:=,>,>=,<,<=,BETWEEN。如果LIKE的参数不以通配符开始,B-Tree索引也可以用于LIKE比较。例如,下面的SELECT语句会使用索引:

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

在第一行语句中,只能查询到'Patrick' <= key_col < 'Patricl'符合这个条件的行。
在第一行语句中,只有查询到 'Pat' <= key_col < 'Pau'符合这个条件的行。


下面的SELECT语句不会使用索引:

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

在第一行语句中,LIKE的值以通配符开始。在第二行语句中,LIKE的值不是常量。

如果col_name有索引那么col_name IS NULL会使用索引。


下面的Where子句会使用索引:

... WHERE index_part1=1 AND index_part2=2 AND other_column=3 

/* index = 1 OR index = 2 */ 
... WHERE index=1 OR A=10 AND index=2 

/* optimized like "index_part1='hello'" */ 
... WHERE index_part1='hello' AND index_part3=5 

/* Can use index on index1 but not on index2 or index3 */ 
... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

Any index that does not span all AND levels in the WHERE clause is not used to optimize the query.换句话说,为了使查询能够使用索引,那么索引的前缀必须用到每一个AND分组。
下面的WHERE子句不会使用索引:


 /* index_part1 is not used */ 
 ... WHERE index_part2=1 AND index_part3=2 
 /* Index is not used in both parts of the WHERE clause */ 
 ... WHERE index=1 OR A=10 
 /* No index spans all rows */ 
 ... WHERE index_part1=1 OR index_part2=10

有时候MySQL不会使用索引,即使有一个索引可用。当优化器评估即使使用索引也需要搜索整张表的大部分行,那么优化器就不会使用索引。(在这种情况下,全表扫描会比使用索引更快,因为全表扫描不需要很多的定位)。然而,如果一个查询使用了LIMIT返回一些行,MySQL会尽可能使用索引,因为这样可以更快的查找到记录并返回结果。


哈希索引特性

哈希索引和B-tree有一些不同的特性:

  • 哈希索引只能用于=或<=>操作符(但是很快)。哈希索引无法用于其他比较操作符,比如:返回查询中的<符号。依赖于这种单值查找类型的系统被称为“键-值存储”;  如果使用MySQL是为了键值存储,那么尽可能使用哈希索引。
  • 优化器无法使用哈希索引来加速ORDER BY操作。(哈希索引无法顺序查找下一个实体)
  • MySQL无法使用哈希索引来估计两个值之间有多少行数据(这是范围优化器来确定使用哪个索引)。如果你修改了MyISAM或InnoDB表为哈希索引的MEMORY表,可能会影响一些查询。
  • 哈希索引只能用于全关键字来搜索行(使用B-tree索引可以最左前缀匹配关键字)

原文地址

  1. https://dev.mysql.com/doc/refman/8.0/en/index-btree-hash.html
相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
4月前
|
SQL 关系型数据库 索引
哈希(hash)比树(tree)更快,索引结构为什么要设计成树型?
哈希(hash)比树(tree)更快,索引结构为什么要设计成树型?
|
5月前
|
存储 关系型数据库 MySQL
MySQL数据库——索引(2)-B+Tree、Hash结构,索引分类(聚集索引、二级索引)
MySQL数据库——索引(2)-B+Tree、Hash结构,索引分类(聚集索引、二级索引)
78 1
|
6月前
|
存储 算法 Java
算法系列--哈希表
算法系列--哈希表
37 0
|
存储 算法 数据可视化
MySQL数据库 -- 索引结构 (B+ tree 与 Hash)
索引(index)是帮助MySQL高效获取数据的数据结构 , 在Mysql中有两个最常用的索引 -- B+tree索引 和 Hash索引 B-Tree(B树)是一种多叉路平衡查找树,相对于二叉树,B树每个节点可以有多个分支 哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中
228 0
查找-散列表(哈希表)详解篇
查找-散列表(哈希表)详解篇
|
存储 数据库 索引
解析B+Tree索引在H2中的实现
提到数据库索引的时候,一般都会提到 B+Tree,因为主流数据库都使用它。我们的DawnSql使用的是 H2 中的存储引擎,因此也是使用 B+Tree。这篇文章的目的是帮助读者更快的掌握 B+Tree 在存储引擎中的作用,以及具体的实现。
解析B+Tree索引在H2中的实现
|
存储 算法 Serverless
查找-之散列表/哈希表
前面的查找不可避免的要进行比较,是否能直接通过关键字key得到要查找的元素位置?
118 0
查找-之散列表/哈希表
|
存储 SQL 算法
FAQ系列 | B+树索引和哈希索引的区别
FAQ系列 | B+树索引和哈希索引的区别
224 0
FAQ系列 | B+树索引和哈希索引的区别
|
存储 Serverless 索引
【数据结构】 哈希表查找—哈希函数、哈希冲突
【数据结构】 哈希表查找—哈希函数、哈希冲突
288 0
【数据结构】 哈希表查找—哈希函数、哈希冲突
|
存储 关系型数据库 索引
Hash索引和B+树索引有什么区别或者说优劣势
Hash索引和B+树索引有什么区别或者说优劣势
459 0