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

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
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索引在指定条件下自动构建的

相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
8天前
|
存储 关系型数据库 MySQL
MySQL基础:索引
MySQL中的索引是一种数据结构,能大幅提升数据库查询效率和减少I/O成本,类似于书的目录帮助快速定位内容。其优势包括提高检索效率和降低排序成本,但会占用空间并影响更新表的效率。鉴于查询远多于更新,索引仍被推荐使用。索引分为多种类型,如B+树和哈希索引,其中B+树因其较低的高度和稳定的查询开销成为常用选择。创建和删除索引需谨慎,以免影响性能。
33 4
MySQL基础:索引
|
19天前
|
存储 缓存 负载均衡
【PolarDB-X 技术揭秘】Lizard B+tree:揭秘分布式数据库索引优化的终极奥秘!
【8月更文挑战第25天】PolarDB-X是阿里云的一款分布式数据库产品,其核心组件Lizard B+tree针对分布式环境优化,解决了传统B+tree面临的数据分片与跨节点查询等问题。Lizard B+tree通过一致性哈希实现数据分片,确保分布式一致性;智能分区实现了负载均衡;高效的搜索算法与缓存机制降低了查询延迟;副本机制确保了系统的高可用性。此外,PolarDB-X通过自适应分支因子、缓存优化、异步写入、数据压缩和智能分片等策略进一步提升了Lizard B+tree的性能,使其能够在分布式环境下提供高性能的索引服务。这些优化不仅提高了查询速度,还确保了系统的稳定性和可靠性。
46 5
|
17天前
|
数据库 索引
数据库索引的作用和优点缺点
【8月更文挑战第27天】创建索引能显著提升系统性能,确保数据唯一性,加快检索速度,加速表间连接及优化分组排序过程。然而,过度使用索引会导致创建与维护成本增加、占用更多物理空间并降低数据维护效率。因此,在创建索引时需谨慎评估需求及影响。
27 2
|
18天前
|
数据库 索引
数据库索引的作用和优点缺点
创建索引能显著提升系统性能,确保数据唯一性,加快检索速度,加速表间连接及优化分组排序过程。然而,过度使用索引会导致创建与维护成本增加、占用更多物理空间并降低数据维护效率。因此,在创建索引时需谨慎评估需求及影响。
24 2
|
21天前
|
监控 数据库 索引
如何优化数据库索引?
【8月更文挑战第23天】如何优化数据库索引?
35 4
|
23天前
|
缓存 关系型数据库 MySQL
在Linux中,如何优化MySQL性能,包括索引优化和查询分析?
在Linux中,如何优化MySQL性能,包括索引优化和查询分析?
|
24天前
|
SQL 关系型数据库 MySQL
MySQL索引你用对了吗?
本文从遇到的问题出发,分析了tddl优化器、MySQL索引、分表拆分键的选择相关知识。
|
12天前
|
C# UED 定位技术
WPF控件大全:初学者必读,掌握控件使用技巧,让你的应用程序更上一层楼!
【8月更文挑战第31天】在WPF应用程序开发中,控件是实现用户界面交互的关键元素。WPF提供了丰富的控件库,包括基础控件(如`Button`、`TextBox`)、布局控件(如`StackPanel`、`Grid`)、数据绑定控件(如`ListBox`、`DataGrid`)等。本文将介绍这些控件的基本分类及使用技巧,并通过示例代码展示如何在项目中应用。合理选择控件并利用布局控件和数据绑定功能,可以提升用户体验和程序性能。
28 0
|
12天前
|
SQL 存储 数据库
|
13天前
|
SQL 关系型数据库 MySQL
SQL Server、MySQL、PostgreSQL:主流数据库SQL语法异同比较——深入探讨数据类型、分页查询、表创建与数据插入、函数和索引等关键语法差异,为跨数据库开发提供实用指导
【8月更文挑战第31天】SQL Server、MySQL和PostgreSQL是当今最流行的关系型数据库管理系统,均使用SQL作为查询语言,但在语法和功能实现上存在差异。本文将比较它们在数据类型、分页查询、创建和插入数据以及函数和索引等方面的异同,帮助开发者更好地理解和使用这些数据库。尽管它们共用SQL语言,但每个系统都有独特的语法规则,了解这些差异有助于提升开发效率和项目成功率。
76 0

热门文章

最新文章