MySQL数据库 -- 索引结构 (B+ tree 与 Hash)

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介: 索引(index)是帮助MySQL高效获取数据的数据结构 , 在Mysql中有两个最常用的索引 -- B+tree索引 和 Hash索引B-Tree(B树)是一种多叉路平衡查找树,相对于二叉树,B树每个节点可以有多个分支哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中

索引概述

索引(index)是帮助MySQL高效获取数据的数据结构

在Mysql中有两个最常用的索引 -- B+tree索引 和 Hash索引

B+tree 索引

B-tree:

B-Tree(B树)是一种多叉路平衡查找树,相对于二叉树,B树每个节点可以有多个分支,即多叉

以一颗最大度数为 5 的 B-tree 为例(树的度数指的是一个节点的子节点个数),那这个B树每个节点最多存储4个key,5个指针,如下:

B-tree

我们可以通过一个数据结构可视化的网站来简单演示一下。 https://www.cs.usfca.edu/~galles/visualization/BTree.html

插入一组数据: 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 然后观察一些数据插入过程中,节点的变化情况

通过该过程,我们发现 B-tree 的特点如下:

  • 5阶的B树,每一个节点最多存储4个key,对应5个指针
  • 一旦节点存储的key数量到达5,就会裂变,中间元素向上分裂
  • 在B树中,非叶子节点和叶子节点都会存放数据

B+ tree

B+Tree是B-Tree的变种,我们以一颗最大度数(max-degree)为4(4阶)的b+tree为例,来看一下其结构示意图:

我们可以看到,两部分:

  • 绿色框框起来的部分,是索引部分,仅仅起到索引数据的作用,不存储数据。
  • 红色框框起来的部分,是数据存储部分,在其叶子节点中要存储具体的数据。

我们可以通过一个数据结构可视化的网站来简单演示一下 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

插入一组数据: 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 然后观察一些数据插入过程中,节点的变化情况

最终我们看到,B+Tree 与 B-Tree相比,主要有以下三点区别:

  • 所有的数据都会出现在叶子节点
  • 叶子节点形成一个单向链表
  • 非叶子节点仅仅起到索引数据作用,具体的数据都是在叶子节点存放的

上述我们所看到的结构是标准的B+Tree的数据结构,接下来,我们再来看看MySQL中优化之后的B+Tree

MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上,增加一个指向相邻叶子节点的链表指针,就形成了带有顺序指针的B+Tree,提高区间访问的性能,利于排序

为什么InnoDB存储引擎选择使用B+tree索引结构?

  • 相对于二叉树,层级更少,搜索效率高
  • 对于B-tree,无论是叶子节点还是非叶子节点,都会保存数据,这样导致一页中存储的键值减少,指针跟着减少,要同样保存大量数据,只能增加树的高度,导致性能降低
  • 相对Hash索引,B+tree支持范围匹配及排序操作

Hash

哈希索引就是采用一定的hash算法,将键值换算成新的hash值,映射到对应的槽位上,然后存储在hash表中

如果两个(或多个)键值,映射到一个相同的槽位上,他们就产生了hash冲突(也称为hash碰撞),可以通过链表来解决

Hash索引有如下特点:

  • Hash索引只能用于对等比较(=,in),不支持范围查询(between,>,< ,...)
  • 无法利用索引完成排序操作
  • 查询效率高,通常(不存在hash冲突的情况)只需要一次检索就可以了,效率通常要高于B+tree索引

在MySQL中,支持hash索引的是Memory存储引擎。 而InnoDB中具有自适应hash功能,hash索引是InnoDB存储引擎根据B+Tree索引在指定条件下自动构建的

相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
1月前
|
SQL 关系型数据库 MySQL
深入解析MySQL的EXPLAIN:指标详解与索引优化
MySQL 中的 `EXPLAIN` 语句用于分析和优化 SQL 查询,帮助你了解查询优化器的执行计划。本文详细介绍了 `EXPLAIN` 输出的各项指标,如 `id`、`select_type`、`table`、`type`、`key` 等,并提供了如何利用这些指标优化索引结构和 SQL 语句的具体方法。通过实战案例,展示了如何通过创建合适索引和调整查询语句来提升查询性能。
242 9
|
28天前
|
SQL 存储 关系型数据库
MySQL秘籍之索引与查询优化实战指南
最左前缀原则。不冗余原则。最大选择性原则。所谓前缀索引,说白了就是对文本的前几个字符建立索引(具体是几个字符在建立索引时去指定),比如以产品名称的前 10 位来建索引,这样建立起来的索引更小,查询效率更快!
94 22
 MySQL秘籍之索引与查询优化实战指南
|
8天前
|
存储 关系型数据库 MySQL
MySQL索引学习笔记
本文深入探讨了MySQL数据库中慢查询分析的关键概念和技术手段。
|
11天前
|
存储 关系型数据库 MySQL
浅入浅出——MySQL索引
本文介绍了数据库索引的概念和各种索引结构,如哈希表、B+树、InnoDB引擎的索引运作原理等。还分享了覆盖索引、联合索引、最左前缀原则等优化技巧,以及如何避免索引误用,提高数据库性能。
|
29天前
|
存储 关系型数据库 MySQL
MySQL中为什么要使用索引合并(Index Merge)?
通过这些内容的详细介绍和实际案例分析,希望能帮助您深入理解索引合并及其在MySQL中的
96 10
|
1月前
|
缓存 关系型数据库 MySQL
MySQL 索引优化以及慢查询优化
通过本文的介绍,希望您能够深入理解MySQL索引优化和慢查询优化的方法,并在实际应用中灵活运用这些技术,提升数据库的整体性能。
87 18
|
1月前
|
存储 Oracle 关系型数据库
索引在手,查询无忧:MySQL索引简介
MySQL 是一款广泛使用的关系型数据库管理系统,在2024年5月的DB-Engines排名中得分1084,仅次于Oracle。本文介绍MySQL索引的工作原理和类型,包括B+Tree、Hash、Full-text索引,以及主键、唯一、普通索引等,帮助开发者优化查询性能。索引类似于图书馆的分类系统,能快速定位数据行,极大提高检索效率。
66 8
|
1月前
|
缓存 关系型数据库 MySQL
MySQL 索引优化以及慢查询优化
通过本文的介绍,希望您能够深入理解MySQL索引优化和慢查询优化的方法,并在实际应用中灵活运用这些技术,提升数据库的整体性能。
91 7
|
1月前
|
缓存 关系型数据库 MySQL
MySQL 索引优化与慢查询优化:原理与实践
通过本文的介绍,希望您能够深入理解MySQL索引优化与慢查询优化的原理和实践方法,并在实际项目中灵活运用这些技术,提升数据库的整体性能。
116 5
|
1月前
|
存储 关系型数据库 MySQL
【MYSQL】 ——索引(B树B+树)、设计栈
索引的特点,使用场景,操作,底层结构,B树B+树,MYSQL设计栈

热门文章

最新文章