深入刨析 mysql 底层索引结构B+树

2024-04-19 16:12

本文主要是介绍深入刨析 mysql 底层索引结构B+树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、什么是索引?
  • 二、不同索引结构对比
    • 2.1 二叉树
    • 2.2 平衡二叉树
    • 2.3 B-树
    • 2.4 B+树
  • 三、mysql 的索引
    • 3.1 聚簇索引
    • 3.2 非聚簇索引


前言

很多人看过mysql索引的介绍:hash表、B-树、B+树、聚簇索引、主键索引、唯一索引、辅助索引、二级索引、联合索引、倒排索引、普通索引。。。等等。好像都知道,但是确分不清,本系列为大家系统分享介绍一下mysql的各种索引知识,将不同知识点串起来。


一、什么是索引?

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。

二、不同索引结构对比

数据结构查找时间复杂度缺点优点
hash表O(1)- hash冲突; - 无法范围查随机查找效率高
二叉树O(logN)线性增加数据会退化成O(N);数据量较大时,树会变高;每个节点只能存储一个数据,IO次数多
平衡二叉树O(logN)- 数据量较大时,树会变高;- 每个节点只能存储一个数据,IO次数多- 线性增加数据不会退化成O(N);
b-树O(logN)- 范围查询时效率低; - 数据分散在非叶子节点,当数据量大时,树的高度也不低- 叶子节点和非叶子节点都可以存储数据; - m叉分裂,可以降低树的高度
b+树O(logN)- 非叶子节点只存key,不存data,大大降低了树的高度;- 叶子节点设计为链表,很好的支持了范围查询

2.1 二叉树

在这里插入图片描述

2.2 平衡二叉树

在这里插入图片描述

2.3 B-树

在这里插入图片描述

2.4 B+树

在这里插入图片描述
总结
1.索引为排好序的一种数据结构,用于提升数据库的查找速度。
2.Hash索引时间复杂度为O(1),树索引是O(log(n))。Hash 底层是哈希表实现,等值查询,可以快速定位数据。但不支持范围查询,无法用于排序分组,无法模糊查询等操作。
3.B+树作为索引优势:

  • 叶子节点存储实际记录行,记录行相对比较紧密的存储,适合大数据量磁盘存储;
  • 非叶子节点存储记录的PK(KEY数据小,相同内存情况下,节点可以多存KEY,增大了节点广度(B+树出度更大,进而树高更矮,磁盘IO次数更少))用于查询加速,适合内存存储;
  • 叶子之间,增加了链表。可以很好的支持范围查询,并且获取所有节点,不再需要中序遍历;
  • 更少查询次数:B+树出度更大,树高更低,查询次数更少;
  • 很适合磁盘存储,能够充分利用局部性原理,磁盘预读(为了减少IO操作,往往不严格按需读取,而是预读。B+树叶子结点存储相临,读取会快一些

三、mysql 的索引

3.1 聚簇索引

聚簇索引并不是一种单独的索引类型。而是一种数据存储方式(所用的用户记录都保存在页子节点)也就是所谓的索引即数据,数据即索引。

聚簇索引默认是主键,如果表中没有定义主键,InnoDB 会选择一个非空唯一索引代替。如果没有,InnoDB 会使用隐藏的_rowid 列来作为聚簇索引。

在这里插入图片描述
如下图所示,一张表 聚簇索引和非聚簇索引的关系:
在这里插入图片描述
特点:

  • 使用记录主键值的大小进行记录和页的排序,这包括三个方面的含义:
    • 页内 的记录是按照主键的大小顺序排成一个 单向链表 。
    • 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。
    • 存放 目录项记录的页 分为不同的层次,在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 。
  • B+树的 叶子节点 存储的是完整的用户记录。
    所谓完整的用户记录,就是指这个记录中存储了所有列的值(包括隐藏列)。

优点:

  • 数据访问更快 ,因为聚簇索引将索引和数据保存在同一个B+树中,因此从聚簇索引中获取数据比非聚簇索引更快
  • 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
  • 按照聚簇索引排列顺序,查询显示一定范围数据的时候,由于数据都是紧密相连,数据库不用从多个数据块中提取数据,所以 节省了大量的io操作 。

缺点:

  • 插入速度严重依赖于插入顺序 ,按照主键的顺序插入是最快的方式,否则将会出现页分裂,严重影响性能。因此,对于InnoDB表,我们一般都会定义一个自增的ID列为主键
  • 更新主键的代价很高 ,因为将会导致被更新的行移动。因此,对于InnoDB表,我们一般定义主键为不可更新
  • 二级索引访问需要两次索引查找 ,第一次找到主键值,第二次根据主键值找到行数据。(也就是常说的回表,但是并不是一定会回表)

限制:

  • 对于mysql数据库中只有InnoDB支持聚簇索引,而MyISAM不支持聚簇索引。
  • 由于数据物理存储方式只能有一种,而每个mysql的表只能有一个聚簇索引,一般情况下就是该表的主键。
  • 如果没有定义主键,InnoDB会选择非空的唯一索引代替,如果没有这样的索引,InnoDB会隐式的定义一个主键来作为聚簇索引。
  • 为了充分利用聚簇索引的聚簇的特性,索引InnoDB表的主键列尽量选用有序的id,而不建议使用无需的id,比如uuid,md5,hash,字符串作为主键将无法保证数据的顺序增常。

3.2 非聚簇索引

非聚簇索引:不是根据主键构建的索引叫做非聚集索引或者二级索引或者辅助索引。

二级索引中如果将多个列作为索引,就叫做联合索引
如果索引类型为唯一索引,索引列的值必须唯一,但允许有空值。如果是组合索引,则列值的组合必须唯一

可视化数据结构的网址 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

这篇关于深入刨析 mysql 底层索引结构B+树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/918028

相关文章

SQL中的外键约束

外键约束用于表示两张表中的指标连接关系。外键约束的作用主要有以下三点: 1.确保子表中的某个字段(外键)只能引用父表中的有效记录2.主表中的列被删除时,子表中的关联列也会被删除3.主表中的列更新时,子表中的关联元素也会被更新 子表中的元素指向主表 以下是一个外键约束的实例展示

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

如何去写一手好SQL

MySQL性能 最大数据量 抛开数据量和并发数,谈性能都是耍流氓。MySQL没有限制单表最大记录数,它取决于操作系统对文件大小的限制。 《阿里巴巴Java开发手册》提出单表行数超过500万行或者单表容量超过2GB,才推荐分库分表。性能由综合因素决定,抛开业务复杂度,影响程度依次是硬件配置、MySQL配置、数据表设计、索引优化。500万这个值仅供参考,并非铁律。 博主曾经操作过超过4亿行数据

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

MySQL数据库宕机,启动不起来,教你一招搞定!

作者介绍:老苏,10余年DBA工作运维经验,擅长Oracle、MySQL、PG、Mongodb数据库运维(如安装迁移,性能优化、故障应急处理等)公众号:老苏畅谈运维欢迎关注本人公众号,更多精彩与您分享。 MySQL数据库宕机,数据页损坏问题,启动不起来,该如何排查和解决,本文将为你说明具体的排查过程。 查看MySQL error日志 查看 MySQL error日志,排查哪个表(表空间

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

[MySQL表的增删改查-进阶]

🌈个人主页:努力学编程’ ⛅个人推荐: c语言从初阶到进阶 JavaEE详解 数据结构 ⚡学好数据结构,刷题刻不容缓:点击一起刷题 🌙心灵鸡汤:总有人要赢,为什么不能是我呢 💻💻💻数据库约束 🔭🔭🔭约束类型 not null: 指示某列不能存储 NULL 值unique: 保证某列的每行必须有唯一的值default: 规定没有给列赋值时的默认值.primary key: