Mysql的InnoDB引擎的数据结构(B+树)以及聚簇索引的介绍

前言:自己的对知识的复习和归纳,参考网上资料和书籍(Mysql高性能),部分概念便于理解会做简单处理。

数据库中使用什么数据结构作为索引呢?

  • 数组:如果是二分查询,查询时间OK,但是插入、更新慢。
  • 链表、环形链表:查询慢。
  • 跳表:作为索引,思想是ok的,但是不贴合磁盘特性。

  • hash : 虽然可以快速定位,但是没有顺序,不支持区间查询。
  • 树结构:B+的设计,very good。

数据库的需求?

比较常见的查找需求:

  • 根据某个值查找数据,比如 select * from user where https://www.centos.bz/wp-content/uploads/2019/07/1-2.png” alt=”” />

    那如果采用最简单的二叉树(平衡二叉树)作为数据库的索引存储,有什么问题呢?

    首先,索引是存储存在在硬盘的。
    (比如:给某张表,1亿的数据记录建立二叉查找树索引,索引中大概会有一亿的节点,假设每个节点占用16字节,大约需要1GB)

    1.不支持区间查找 — > 非叶子节点不存储数据,只做索引(叶子节点的索引),然后把叶子节点连接起来,就可以支持区间查找。
    2.速度慢(把数据存储在硬盘,每个节点的读取或者访问,都对应一次磁盘IO操作(ms级别),数的高度就对应每次查询的IO次数。) — > 降低树的高度,M叉树。

    如果M位100, 100叉树,一亿的索引节点,树的高度为3,所以最多3次磁盘IO操作就能获取到数据。
    所以,索引的查找从磁盘IO读取变成内存查找。

    这就是B+树(有序数组链表+平衡多叉树)

    什么是B树(多路平衡查找树):

    只是一个每个节点的子节点个数不能小于 m/2 的m叉树 –> 有序数组 + 平衡多叉树

    B+树、磁盘 == 非常快的查找速度(索引):

    • 程序的访问局部性:当一个数据被用到时,其附近的数据也通常会马上被使用。
      • 时间局部性:被使用的数据,未来很大概率会被再次使用。
      • 空间局部性: 被使用的数据,其附近的数据,大概率会被使用。
    • 磁盘的预读取:磁盘是按页(简单理解为4KB)读取。 — > 如果是B+树,让一个节点的大小 == 一个磁盘页,一次磁盘IO读取就是一个节点,而B+树中,一个节点内的数据是连续的,所以能充分利用程序的访问局部性原理。(索引可以将随机I/O变为顺序I/O。)

    比较:二叉树 — >如果索引数据大,树高度深,相邻数据的节点在物理位置距离远,每次预读取的数据基本基本不会被用到。

    那我们来看下磁盘是怎么读取数据的?

    先看下磁盘结构:

    磁盘的读写:读写主要是通过传动手臂上的读写磁头来完成。实际运行时,主轴让磁盘盘片转动,然后传动手臂可伸展让读写磁头在盘片上进行读写操作。

    扩展:磁盘顺序读取的效率很高。合理利用,顺序读取的速度甚至比内存高(kafka、rocketMq等中间件,就是利用磁盘的顺序读取,来实现高性能)。

    聚簇索引和非聚簇索引

    聚簇索引和非聚簇索引概念

    • 聚簇索引的叶子节点就是数据节点

    聚簇的意思:数据行被按照一定顺序一个个紧密地排列在一起存储。(索引是有序的)
    InnoDB : 主键索引和数据文件简单理解为同一份文件

    • 非聚簇索引的叶子节点仍然是索引节点,只不过有指向对应数据块的指针

    从MYISAM存储的物理文件我们能看出,MYISAM引擎的索引文件(.MYI)和数据文件(.MYD)是相互独立的。

    聚簇索引的优点和缺点

    • 优点
      • 1.查询通过聚簇索引可以直接获取数据,相比非聚簇索引需要第二次查询(非覆盖索引的情况下)效率要高。
      • 2.聚簇索引对于范围查询的效率很高,因为其数据是按照大小排列的。(磁盘顺序读取)
    • 缺点
      • 1.索引的更新代价高:数据更新,为了保持聚簇索引的有序,需要将数据移动到相应的位置,而且可能导致页分裂(页已满)。
      • 2.插入的速度严重依赖插入的顺序,如果是按照主键索引的速度插入,非常快,非主键索引的插入,慢。
      • 3.二级索引访问需要两次索引查找,而不是一次。
      • 4.聚簇索引可能导致全表扫描变慢,尤其是行比较稀疏,或者由于页分裂导致数据存储不连续的时候。(未get到)

    扩展:

    InnoDB的插入:
    首先,操作系统写磁盘是定期flush将缓存刷到磁盘。

    多条记录如果是按照主键索引的顺序插入:

    • 插入的数据很大概率在同一个磁盘页,并且以及加载到内存中,按多条记录按主键索引顺序的插入,可能简单理解为在一个节点的内存中,插入多条数据,然后一次性flush到磁盘。

    多条记录的非主键索引的插入:

    • 数据很大概率不在同一个磁盘页或者(或者目标页已经从缓存刷到磁盘),所以可能需要多次IO操作,增加来很多开销。
    • 频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

    基础知识

    1亿 = 100000000
    1G等于1024M,1M等于1024KB,1KB等于1024B,1B等于8位(bit)
    1秒=1000毫秒(ms), 1秒=1000000微妙(μs), 1秒=1000000000纳秒(ns)

    简单总结:

    寄存区 = 1ns
    CPU缓存的读取的速度 == 1 – 10ns
    内存的读取速度 = 100 -150ns
    硬盘 = 3 – 15ms
    网络去读 = 10ms

    所以,简单理解为 硬盘差内存的1w倍, 内存差CPU缓存100 倍,CPU缓存差寄存器10倍;

    原文出处:juejin -> https://juejin.im/post/5d21edadf265da1bcf5dfdb7

本站所发布的一切资源仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。如果侵犯你的利益,请发送邮箱到 [email protected],我们会很快的为您处理。
超哥软件库 » Mysql的InnoDB引擎的数据结构(B+树)以及聚簇索引的介绍