专栏首页小强的进阶之路BAT大厂都会问的MySQL底层数据结构

BAT大厂都会问的MySQL底层数据结构

索引是帮助MySQL高效获取数据的排好序的数据结构

索引数据结构对比

二叉树

左边子节点的数据小于父节点数据,右边子节点的数据大于父节点数据。如果col2是索引,查找索引为89的行元素,那么只需要查找两次,就可以获取到行元素所在的磁盘指针地址。

如果col1是索引,查找索引为6的行元素,那么需要查找六次,就可以获取到行元素所在的磁盘指针地址,即得到了该索引为6的行元素。因此二叉树不适合存储单边增长的序列字段,近乎全表扫描获取数据。

红黑树

本质二叉树,属于二叉平衡树,jdk1.8 hashmap的底层实现;存储大数据量,树的高度不可控, 数量越大,树的高度越高;500w行数据,2的n次方=500w数据量, n是树的高度,也就是查询次数;

hash表

通过散列可以快速获取磁盘文件指针,对于指定索引查找文件非常快,但是对于范围查找没法支持。

B树

本质是多路二叉树;叶节点具有相同的深度,叶节点的指针为空;所有索引元素不重复;节点中数据索引从左到右依次递增的;

B+树(B树的变种)

非叶子节点不存储数据,只存储索引(冗余)和指针,可以放更多的索引,树高降低 ;叶子节点包含所有索引字段;叶子节点比b树增加了指针连接;叶子节点有双向指针链接(首尾子节点还通过指针连接),提高区间访问的性能,范围查找;

为什么mysql页文件默认16K?

MySQL每个B+树节点最大存储容量:16KB (指针+数据+索引)。假设我们一行数据大小为1K,那么一页就能存16条数据,也就是一个叶子节点能存16条数据;再看非叶子节点,假设主键ID为bigint类型,那么长度为8B,指针大小在Innodb源码中为6B,一共就是14B,那么一页里就可以存储16K/14=1170个(主键+指针) 那么一颗高度为2的B+树能存储的数据为:117016=18720条,一颗高度为3的B+树能存储的数据为:11701170*16=21902400(千万级条)

show global status like `Innodb_page_size`

因此,B+树存储大数据量的表也可以非常高效的获取数据,MySQL使用B+树作为索引的数据结构。

存储引擎

存储引擎最终作用于:表 ,不是数据库 在mysql的安装的根目录下,有一个data目录,里面存放的是所有表的数据。

  • MyISAM:MyISAM索引文件和数据文件是分离的(非聚集或稀疏);主键索引和辅助主键索引存储类似;

frm文件:存储这张表的表结构 MYD文件:存储这张表的所有数据行 MYI文件:存储这张表的索引字段

  • InnoDB(聚集):

表数据文件本身是按照B+tree组织的一个索引结构文件 frm文件:存储这张表的表结构 ibd文件:存储这张表的所有数据行和索引字段 聚集(聚簇)索引----叶节点包含完整数据记录

为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?

  • 首先,为了满足MySQL的索引数据结构B+树的特性,必须要有索引作为主键,可以有效提高查询效率,因此InnoDB必须要有主键。如果不手动指定主键,InnoDB会从插入的数据中找出不重复的一列作为主键索引,如果没找到不重复的一列,InnoDB会在后台增加一列rowId做为主键索引。
  • 其次,索引的数据类型是整型,一方面整型占有的磁盘空间或内存空间相比字符串更少,另一方面整型比较比字符串比较更快速,字符串比较是先转换为ASCII码,然后再比较的。
  • 最后,B+树本质是多路多叉树,如果主键索引不是自增的,那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡,影响数据插入的效率,如果是自增主键,只用在尾节点做增加就可以。

为什么非主键索引结构叶子节点存储的是主键值?

  • 主键索引和非主键索引维护各自的B+树结构,当插入的数据的时候,由于数据只有一份,通过非主键索引获取到主键值,然后再去主键索引的B+树数据结构中找到对应的行数据,节省了内存空间;
  • 如果非主键索引的叶子节点也存储一份数据,如果通过非主键索引插入数据,那么要向主键索引对应的行数据进行同步,那么会带来数据一致性问题。可以通过事务的方式解决,我们都知道使用事务后,就会对性能有所消耗。

联合索引

  • 联合索引的底层存储结构长什么样? 定义联合索引(员工级别,员工姓名,员工出生年月),将联合索引按照索引顺序放入节点中,新插入节点时,先按照联合索引中的员工级别比较,如果相同会按照是员工姓名比较,如果员工级别和员工姓名都相同 最后是员工的出生年月比较。可以从图中从上到下,从左到右看,第一个B+树的节点 是通过联合索引的员工级别比较的,第二个节点是 员工级别相同,会按照员工姓名比较,第三个节点是 员工级别和员工姓名都相同,会按照员工出生年月比较。

End

本文分享自微信公众号 - 小强的进阶之路(xiaoqiang_code),作者:小强的进阶之路

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 各位,我把MySQL脱皮剔骨了,你吃不?

    在数据库中存的就是一张张有着千丝万缕关系的表,所以表的设计的好坏,将直接影像这整个数据库。而在设计表的时候,我们都关注一个问题,使用什么存储引擎。接下来小编将重...

    程序员小强
  • zookeeper特性与节点说明

    这些问题可以统一归纳为多节点协调问题,如果靠节点自身进行协调这是非常不可靠的,性能上也不可取。必须由一个独立的服务做协调工作,它必须可靠,而且保证性能。

    程序员小强
  • 聊聊Redis SDS

    Redis面试中经常被问到,Redis效率为什么这么快,很多同学往往回答:① Redis基于内存操作;② Redis是单线程的,采用了IO多路复用技术;③ Re...

    程序员小强
  • 一文带你深入理解Mysql索引底层数据结构与算法

    首先看一下,在数据库没有加索引的情况下,SQL中的where语句是如何查找目标记录的,首先看到下图的Col2字段,如果我们要查找where col2 = 89的...

    黎明大大
  • 从千万级数据查询来聊一聊索引结构和数据库原理

    在日常工作中我们不可避免地会遇到慢SQL问题,比如笔者在之前的公司时会定期收到DBA彪哥发来的Oracle AWR报告,并特别提示我某条sql近阶段执行明显很慢...

    Java_老男孩
  • SQL学习笔记之B+树

    任意节点,它的左子树如果不为空,那么左子树上所有节点的值都小于根节点的值; 任意节点,他的右子树如果不为空,那么右子树上的所有节点的值大于根节点的值。

    Jetpropelledsnake21
  • 数据库索引

    数据库索引,在日常工作中会经常接触到,比如某一个 SQL 查询比较慢,分析原因后,经常会说 “给某个字段加个索引”,索引又是如何工作的?

    王小明_HIT
  • 图解:深入理解MySQL索引底层数据结构与算法

    以Col1为主键,则上图是一个MyISAM表的主索引(Primary key)示意

    你好戴先生
  • MySQL|索引背后

    01 索引 以MySQL中的索引为例子总结。 数据库查询是数据库的最主要功能之一,实现高效的查询速度一定是MySQL非常关心的事情。 索引(Index)正是帮...

    double
  • Real World Performance 经典性能优化案例-索引竞争

    编辑手记:Real World Performance(RWP)团队是个天才的性能优化团队,不断的寻找和创造新的方法分析诊断当今世界业务系统的性能。在他们眼里,...

    数据和云

扫码关注云+社区

领取腾讯云代金券