正文 

当前位置： 首页 > 开发 > java教程

深入理解mysql索引底层数据结构与算法(代码片段)

pingping-joe pingping-joe     2022-12-20     576

关键词：

深入理解Mysql索引底层数据结构与算法

----->之前很多人还问我一些关于mysql索引的底层和使用，我就特意写一篇文章跟大家一起分享一下我对mysql索引的理解，大家有更深入的理解可以下面留言。

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

大家使用索引有没有想过这个问题？为什么索引能够帮助mysql高效获取数据？我一一给大家道来！在给大家讲之前，先更大家分享一些计算机基础知识，有助于理解

  • 我们都知道mysql数据是已文件的形式存储在磁盘上的。

  • 那磁盘是有一圈一圈的磁道组成的

  • 磁头移动到不同磁道，磁盘旋转，这样就可以读取到数据

  • 磁盘存取原理 1.寻道时间(速度慢，费时) 2.旋转时间(速度较快)

  • cpu读取数据都是从内存去读，内存去磁盘读取数据，内存读取磁盘数据大小都是已页的大小单位，一页=10kb

  • 技术图片

技术图片

技术图片

总结：

  1. 通过上面的一些知识，我们知道当磁头移动到另一个磁道读取诗句就是我们常说的一次I/O操作，但是我们知道mysql数据是分布到不同的磁道上的，每次读取数据都要把所有磁道读取一遍，那我们进行I/O次数就很多了，查询效率就很低

  2. 那索引就是把索引字段数据的地址保存起来，来帮助mysql直接定位到哪个磁道的哪个扇区，这样就减少I/O操作了，自然查询效率就提高了

2.数据结构那么多，mysql索引为什么要用B+Tree数据结构，而不是其他呢？肯定其他的数据不满足我们的要求

常见的数据结构

1.二叉树
2.红黑树
3.Hash
4.B Tree
5.B+Tree
a.二叉树

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

不使用原因：会出现极端情况，一个节点只有一度，就是只有一个子节点，那读取树的一层就是一次I/O，那性能也不好
b.红黑树

红黑树即为平衡二叉树的一种

不使用原因：极端情况下，一个节点有2个子节点，那就出现一层只有2个节点的情况，这种性能也不好
c.Hash
不使用原因：Hash是把索引数据进行Hash算法对应一个地址，我们会发现这个好像性能很好啊，直接找到，但是我们想想，它能满足我们日常开发大部分情况吗？比如通过大于或者小于去筛选数据，所以说也不合适，当然mysql还是提供了Hash索引，毕竟有些场合还是用起来也不错
d.B Tree

1.度(Degree)-节点的数据存储个数 2.叶节点具有相同的深度 3.叶节点的指针为空 4.节点中的数据key从左到右递增排列

技术图片

 

技术图片

不使用原因：虽然解决了每一层的节点数的极端情况下，但是我们会发现每个节点存储了索引和数据，那一层能存储的数据太多也不好,毕竟内存能读取的数据大小就是10kb
e.B+Tree

1.B+Tree(B-Tree变种) 2.非叶子节点不存储data，只存储key，可以增大度 3.叶子节点不存储指针 4.顺序访问指针，提高区间访问的性能

技术图片

 

技术图片

使用原因：设计有几个方面
1.非叶子节点不存储data，只存储key，可以增大度
2.叶子节点不存储指针
3.顺序访问指针，提高区间访问的性能
3.B+Tree索引的性能分析

  • 一般使用磁盘I/O次数评价索引结构的优劣

  • 预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存

  • 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用

  • B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O

  • B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)

     

4.不同的存储引擎有不同的索引实现

1.MyISAM索引实现(非聚集) 2.InnoDB索引实现(聚集)

 

a.MyISAM索引实现(非聚集)

--->MyISAM索引文件和数据文件是分离的

技术图片

 

技术图片

技术图片

b.InnoDB索引实现(聚集)

1.数据文件本身就是索引文件 2.表数据文件本身就是按B+Tree组织的一个索引结构文件 3.聚集索引-叶节点包含了完整的数据记录 4.为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？ 5.为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

技术图片

技术图片

技术图片

 

5.联合索引结构

---->联合索引的底层存储结构长什么样？

技术图片

6.索引最左前缀原理

mysql进阶-10深入理解redolog，undolog和binlog的底层原理(代码片段)

MySql系列整体栏目内容链接地址【一】深入理解mysql索引本质https://blog.csdn.net/zhenghuishengq/article/details/121027025【二】深入理解mysql索引优化以及explain关键字https://blog.csdn.net/zhenghuishengq/article/details/124552080【三】深入理解mysql的索引... 查看详情

mysql深入底层了解(代码片段)

索引数据结构#索引的本质：帮助mysql高效获取数据排好序的数据结构Myisam存储引擎索引实现#分三个文件存储：1：frm存储表结构2：MYD存储表数据3：MYI存储表索引数据底层查找过程：先通过MYI索引数据结构... 查看详情

mysql(11)—btree索引的数据结构以及具体实现原理深入解析(代码片段)

深入解析了Mysql的B+Tree索引底层数据结构，以及MyISAM和InnoDB存储引擎的索引底层原理。上一篇文章中，我们介绍了索引的概念以及MySQL常见索引类型：索引的概念以及MySQL七种索引类型。下面我们来看看常见的索引... 查看详情

详解mysql索引与底层原理(代码片段)

文章目录索引的底层原理一、MySQL缓冲池1、数据页与数据页管理2、free链表3、flush链表4、哈希表5、LRU链表补充二、索引的底层原理1、InnoDB索引I.行记录与页内索引II.页外索引页III.B+树结构IV.聚簇索引V.InnoDB索引文件2、MyISAM索... 查看详情

mysql深入理解mysql索引优化器原理（mysql专栏启动）(代码片段)

📫作者简介：小明java问道之路，专注于研究Java/Liunx内核/C++及汇编/计算机底层原理/源码，就职于大型金融公司后端高级工程师，擅长交易领域的高安全/可用/并发/性能的架构设计与演进、系统优化与稳... 查看详情

如何理解mysql的索引？(代码片段)

...为：索引（index）是帮助MySQL高效获取数据的数据结构（有序）。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在... 查看详情

[转帖]深入理解mysql—锁事务与并发控制(代码片段)

深入理解MySQL—锁、事务与并发控制 http://www.itpub.net/2019/04/28/1723/跟oracle也类似其实所有的数据库都有相同的机制..学习了机制才能够更好的工作,. 数据和云 2019-04-2810:45:07 本文共11796个字，预计阅读需要30分钟。... 查看详情

理解mysql索引与优化(代码片段)

理解MySql索引与优化1、索引是什么？1.1mysql数据存储在什么地方？1.2查询数据比较慢，一般情况下卡在哪里？1.3去磁盘读取数据，用多少读多少？1.4索引存储在哪里？1.5索引在存储的时候需要什么信息&#... 查看详情

mysql深入底层了解(代码片段)

索引数据结构#索引的本质：帮助mysql高效获取数据排好序的数据结构Myisam存储引擎索引实现#分三个文件存储：1：frm存储表结构2：MYD存储表数据3：MYI存储表索引数据底层查找过程：先通过MYI索引数据结构... 查看详情

mysql索引与优化(代码片段)

...内存中，为服务器存储引擎为了快速找到记录的一种数据结构。基本操作为数据表添加索引：ALTERTABLEtable_nameADDINDEXindex_name(column_list)//普通索引ALTERTABLEta 查看详情

掌握查询利器深入理解postgresql索引原理与优化(代码片段)

文章目录一、前言1.1PostgreSQL索引的重要性1.2本文的结构和目的二、索引概述2.1什么是索引2.2为什么要使用索引2.3索引如何工作三、索引类型3.1B-tree索引3.2Hash索引3.3GiST索引3.4GIN索引四、索引实践4.1创建索引4.2索引的使用4.3索引维... 查看详情

为了把mysql的索引底层原理讲清楚，我把计算机翻了个底朝天(代码片段)

...杜编程什么是索引概念：索引是提高mysql查询效率的数据结构。总的一句话概括就是索引是一种数据结构。数据库查询是数据库的最主要功能之一。设计者们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者... 查看详情

mysql底层索引结构探究(代码片段)

目录1索引的概念2索引的分类3索引的操作4索引效率的测试5索引的实现原则5.1磁盘存储5.2BTree5.3B+Tree6总结：索引的设计原则1索引的概念索引的预备知识:MySQL存储引擎我们之前学习过集合，其中的ArrayList集合的特点之一... 查看详情

mysql——索引的深度理解(代码片段)

...订阅专栏哦目录一.什么是索引？二.认识MySQL的存储1.理解磁盘2.MySQL与磁盘交互的基本单位总结三.数据页（page)1.理解单个数据页2.理解多个数据页四.索 查看详情

mysql——索引的深度理解(代码片段)

...订阅专栏哦目录一.什么是索引？二.认识MySQL的存储1.理解磁盘2.MySQL与磁盘交互的基本单位总结三.数据页（page)1.理解单个数据页2.理解多个数据页四.索 查看详情

《深入理解jvm——gc算法与内存分配策略》(代码片段)

 JVM深入理解JVM(2)——GC算法与内存分配策略 PostedbyCrowonAugust10,2017说起垃圾收集（GarbageCollection,GC），想必大家都不陌生，它是JVM实现里非常重要的一环，JVM成熟的内存动态分配与回收技术使Java（当然还有其他运行... 查看详情

腾讯一面：说一说mysql中索引的底层原理(代码片段)

...种经典问题不再是背八股文，而是深入底层原理以及数据结构。后续再碰到这类问题 查看详情

腾讯一面：说一说mysql中索引的底层原理(代码片段)

...种经典问题不再是背八股文，而是深入底层原理以及数据结构。后续再碰到这类问题 查看详情