Mysql索引原理及各种tree的比较

一、mysql体系结构

二、mysql索引

1、定义

索引是为了加速对表中的数据行的检索而创造的一种分散存储的数据结构

2、索引的实现

mysql的索引是由存储引擎来实现,不同的存储引擎实现方式不同。

3、存放位置

一般是存放在磁盘中

4、作用

  • 减少扫描的数据行
  • 可以把随机IO变成顺序IO
  • 可以帮助我们在分组、排序等操作时,避免使用临时表

5、索引结构

我们都知道mysql的索引使用B树来实现的,那么为什么会考虑B树,不考虑其他数据结构呢?

5.1 首先我们来看普通的二叉树。

普通的二叉树不是绝对平衡的,会有一个问题,如下图:

它有可能会形成一个链表,这样就失去了二叉树的优势,需要遍历查找,性能查。

5.2 那么如果我们选择平衡二叉树呢?如下图:

平衡二叉树没有普通二叉树可能会形成链表的问题,但是它还有其他的问题。

a、它太深了
  • 这里的太深是指树的高度,大家不要想歪了~
  • 如果在数据量很大的情况下,这棵树的高度很可能成千上万,因此它的IO次数也会很频繁,会严重影响性能
b、它太小了
  • 太小指的是每一个磁盘块(节点)保存的数据量太小了
  • 没有利用好操作磁盘IO的数据交换特性(4K)
  • 没有利用好磁盘IO的预读能力(空间局部性原理)

这里解释下为什么说没有利用好。 1、操作系统磁盘IO的数据交换一次默认是4KB大小,但是我们的节点里面存储的数据远远小于4KB,即我们进行了一次IO但是没有完全利用这次IO的数据交换大小,造成浪费。 2、操作系统磁盘IO具备预读能力,是什么意思呢?比如我们要读取一张20KB大小的jpg图片,我们第一次读了4KB的头内容,操作系统会认为我们可能需要接下来的16KB的剩余内容,所以会一次性把剩余的内容都传输给我们。

5.3 那么如果我们选择B-Trees即多路平衡查找树呢?如下图:

这里我选择的是一个3路的平衡查找树。(即一个节点最多可以有3-1=2个元素)

可以看出同样的高度,它比平衡二叉树存储的数据多得多,减少了IO次数,同时每次IO获取的数据也更多,提升了IO效率。

5.4 最后来看下B+Trees即加强版多路平衡查找树。如下图:

它有以下几个特点:

  • 采用闭合区间
  • 非叶子节点不保存数据,只保存关键字和子节点的引用
  • 关键字对应的数据保存在叶子节点中
  • 叶子节点是顺序排列的,并且相邻的节点具有顺序引用的关系
5.5 那么我们为什么要采用B+Trees呢?
  • 拥有多路的优势
  • 扫表能力强
  • 磁盘IO能力强
  • 排序能力强
  • 查询能力更稳定

这里我解释下为什么说B+Trees的查询能力更稳定: B-Trees可能扫秒到第一层就返回,也可能扫秒到最后一层才返回。可能很快也可能很慢。 B+Trees每次都要扫面到最后一层,因此速度更加稳定。

6、B树在存储引擎中的实现方式

6.1、Myisam
  • 非聚簇索引,数据和索引分别存储。
  • 索引文件xx.MYI
  • 数据文件xx.MYD
  • 叶子节点保存的是引用地址而非数据
6.2、InnoDB
  • 聚簇索引,数据和索引保存在一起
  • 文件xx.ibd
  • 在叶子节点保存对应的所有数据
  • 以主键索引来组织数据,没有主键的话,会帮我们隐式创建主键索引
  • 辅助索引不存地址,存主键,这样便于维护

7、列的离散性

  • 列的离散性在索引中是一种很重要的指标。
  • 列的离散性 x = count(distinct col) : count(col)
  • 比例越大,离散性越高,选择性就越好
  • 下面我们看个例子来理解:
  • name的列的离散性 x1 = 5 : 5 = 1
  • sex的列的离散性 x2 = 2 : 5 = 0.4
  • x1>x2,所以sex的列的离散性低,可选择性差。
  • 可选择性差是什么意思呢?比如有如上100W的数据,现在我们要查找sex=男的,那么在索引中我们可选择的范围太大了,因为只有男或者女,查询效率就很低
  • 在mysql查询优化器中,如果列的离散性低的话,可能就不走索引,直接全表扫描

8、联合索引

8.1 建立联合索引的原则:
  • 经常用的列优先
  • 离散性高的列优先
  • 宽度小的列优先
8.2 适用性:
  • 如果不是最左匹配,则无法使用联合索引
  • 范围查询之后的不走联合索引
  • where id = 1 and age > 10 and sex = 女 只有id、age走联合索引
  • where id > 1 and age = 10 只有id走联合索引
  • where id = 1 and age = 10 and sex > 女 id、age、sex走联合索引

9、覆盖索引

  • 定义:如果查询的列可以通过索引节点的关键字直接返回,则称之为覆盖索引
  • 索引名称: index_name 索引列:name 覆盖:select name from user where name= ? 非覆盖:select * from user where name= ?
  • 覆盖索引可以减少数据库IO操作,不需要回表,而是在子节点就可以获取关键字进行返回。

10、建立索引的原则

  • 索引不易建多:维护B+Trees成本高,插入、更新、删除等操作要做很多逻辑判断
  • 索引列的长度不易过长:会影响B+Trees的路数,进而影响IO效率

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java建设者

MyBatis 二级缓存详解

我们在上一篇文章介绍了 MyBatis 的一级缓存的作用,如何开启,一级缓存的本质是什么,一级缓存失效的原因是什么?MyBatis 只有一级缓存吗?来找找答案吧...

7820
来自专栏Java建设者

MyBatis 核心配置综述之 ResultSetHandler

我们之前介绍过了MyBatis 四大核心配置之 Executor、StatementHandler、 ParameterHandler,今天本文的主题是介绍一下...

12630
来自专栏Tech爬虫(公众号php_pachong)

ThinkPHP中自动填充日期时间

如果是用自己的函数那就要用callback,第二个参数默认当前模块能调用的方法;用function的话第二个参数为函数名,而这个函数可以是PHP自带的,也可以是...

8820
来自专栏Java识堂

如果有人问你数据库的原理,叫他看这篇文章-4

国内大佬翻译的文章,因为文章较长,不适合碎片化阅读,因此分为几篇文章来转载,满满的干货,外链在微信上不能显示,建议从第一篇文章开始看起

11220
来自专栏Java架构学习路线

还怕不记得Spring Boot注解吗?5类注解全在这里了(建议收藏)

Spring Boot的核心就是注解。Spring Boot通过各种组合注解,极大地简化了Spring项目的搭建和开发。在Spring Boot中有一些注解是...

6300
来自专栏专利

2000万专利大数据国际IPC分类A01部批量打包下载目录

A01B农业或林业的整地;一般农业机械或农具的部件、零件或附件(用于播种、种植或施厩肥的开挖沟穴或覆盖沟穴入A01C 5/00;收获根作物的机械入A01D;可变...

13010
来自专栏Java识堂

如果有人问你数据库的原理,叫他看这篇文章-2

国内大佬翻译的文章,因为文章较长,不适合碎片化阅读,因此分为几篇文章来转载,满满的干货,外链在微信上不能显示

11420
来自专栏Tech爬虫(公众号php_pachong)

模型技术 - 数据库连接

在使用模型操作之前,我们首先创建一个数据库:thinkphp。创建一个用户表:user。添加一些数据即可。 ThinkPHP 内置了抽象数据库访问层,把不同的数...

9730
来自专栏Java识堂

如果有人问你数据库的原理,叫他看这篇文章-3

国内大佬翻译的文章,因为文章较长,不适合碎片化阅读,因此分为几篇文章来转载,满满的干货,外链在微信上不能显示,建议从第一篇文章开始看起

9830
来自专栏微信公众号:Java团长

[灵魂拷问]MySQL面试高频100问(工程师方向)

本文主要受众为开发人员,所以不涉及到MySQL的服务部署等操作,且内容较多,大家准备好耐心和瓜子矿泉水.

13410

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励