文档章节

Mysql索引机制B+Tree

 万山红遍
发布于 02/17 17:30
字数 4116
阅读 102
收藏 6

1、问题引入

有一个用户表,为了查询的效率,需要基于id去构建索引。构建索引我们需要考虑两个方面的问题,1个是查询的效率,1个是索引数据的存储问题。该表的记录需要支持百万、千万、甚至上亿的数据量,如果将索引存储到内存中,尽管内存的访问速度非常快,查询效率非常高,但是,占用内存会非常大。
而且每次数据库重启后,索引数据就会丢失,需要在内存里重新构建索引。将索引存储到硬盘中,减少了内存的消耗,数据库重启,数据也不会丢失。

确定了硬盘存储索引数据,接下来就需要选择合适的数据结构存储索引数据。首先我们会想到散列表,散列表查询性能很好,时间复杂度为O(1),但是如果想要快速查询id 在1~3之间的数据,散列表就不能满足了。散列表不满足要求,我们自然会想到另一种数据结构树,树的种类有很多种,到底哪种树适合基于磁盘构建索引呢?mysql采用b-tree的增强版b+tree 这种树去构建索引,这种树可以大大减少磁盘io的操作,提高查询效率。

 

2、磁盘读写原理

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲B-Tree之前先了解下磁盘的相关知识。

 

2.1 硬盘组成:盘片(platter)、磁头(head)、磁道(track)、扇区(sector)、柱面(cylinder)。

硬盘中一般会有多个盘片(platter)组成,每个盘片包含两个面,每个盘面都对应地有一个读/写磁头。每个盘面都被划分为数目相等的磁道,并从外缘的“0”开始编号,具有相同编号的磁道形成一个圆柱,称之为磁盘的柱面。每个磁道被划分成若干个扇区(sector),扇区是磁盘的最小组成单元,通常是512字节。

系统将文件存储到磁盘上时,按柱面、磁头、扇区的方式进行,即最先是第1磁道的第一磁头下(也就是第1盘面的第一磁道)的所有扇区,然后,是同一柱面的下一磁头,一个柱面存储满后就推进到下一个柱面,直到把文件内容全部写入磁盘。读取顺序从上到下,然后从外到内。

2.2 磁盘读取响应时间:

  1. 寻道时间:磁头从开始移动到数据所在磁道所需要的时间,寻道时间越短,I/O操作越快,目前磁盘的平均寻道时间一般在3-15ms,一般都在10ms左右。
  2. 旋转延迟:盘片旋转将请求数据所在扇区移至读写磁头下方所需要的时间,旋转延迟取决于磁盘转速。普通硬盘一般都是7200rpm,慢的5400rpm。
  3. 数据传输时间:完成传输所请求的数据所需要的时间。

从上面的指标来看、其实最重要的、或者说、我们最关心的应该只有两个:寻道时间;旋转延迟。为提高磁盘传输效率,软件应着重考虑减少寻道时间和延迟时间。

如果一个文件存储在连续的扇区上,这样就可以减少寻道时间和旋转延迟,大大增加磁盘io读取的效率,这就是为什么大家常说随机读写速度将明显低于顺序读写。

2.3 磁盘块

由于扇区数目众多在寻址时比较困难,所以操作系统就将相邻的扇区组合在一起,形成一个块,再对块进行整体的操作,即块是操作系统中最小的逻辑存储单元。这样可以使操作系统忽略底层物理存储结构的设计。磁盘块是操作系统自己虚拟的概念,其大小由操作系统决定,通常一个块 = 单个扇区大小 * 2的n次方,其中n是可修改的。 

linux默认的块大小为4096个字节,也就是8个扇区的大小。

2.4 局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

所以,程序运行期间所需要的数据通常应当比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

注意:这里的页在主存中称为页,在磁盘中就是前面介绍的磁盘块。

 

3、平衡二叉树

如果采用平衡二叉树(红黑树)去构建索引,该如何做呢?

系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的,位于同一个磁盘块中的数据会被一次性读取出来,而不是需要什么取什么。

我们可以基于这一特性,将每个节点存储到磁盘块里,每次读取一个节点就只操作一次io。

存在的问题:如果索引过多,必然平衡二叉树的的层级就会很多,也就会增加磁盘io的操作,磁盘io操作是非常耗时的。

那么如何优化这个问题呢?

如果想优化,也就是要减少树的高度,进而减少磁盘的io操作。

如何减少树的高度呢?

可以采用多路平衡二叉树b-tree的数据结构存取索引。

 

4、多路平衡查找树b-tree

树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下

  1. 树中每个结点最多含有m个孩子(m>=2);
  2. 除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);
  3. 若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);
  4. 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的结点,实际上这些结点不存在,指向这些结点的指针都为null);
  5. 每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,......,Kn,Pn)。其中:
           a)   Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)< Ki。 
           b)  
    Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki,但都大于k(i-1)
           c)   关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1

 

如果我们想要通过语句SELECT * FROM user WHERE id >= 1AND id <= 3; 查找1~3之间的数据,很显然这种数据结构不太支持。

B-Tree每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小,当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。

所以就有了增强版的B+tree

4、B+tree

B+Tree相对于B-Tree有几点不同:

  1. 非叶子节点只存储键值信息。
  2. 所有叶子节点之间都有一个链指针。
  3. 数据记录都存放在叶子节点中。

B+Tree将所有的数据都存在叶子节点,并且叶子节点通过指针串联成一个链表。这样可以很容易查询某个区间的数据,同时遍历整个索引数据也变的非常快速简单。B+Tree中的所有数据都存在叶子节点中,这就可以大大加大每个内层节点存储的key值数量,降低B+Tree的高度。

 

5、B+Tree在MyISM引擎中的体现

一个名为`user_isam` 表,会生成下面三种文件。frm文件保存了表的结构,myd保存表的数据,myi保存了表的索引数据。

上图展示了采用主键id去构建索引,索引的各个节点存储的数据为id的值,整个树的叶子节点保存了指向数据的磁盘地址。

如果采用name去构建索引,也会有一个独立的索引树,整个树的叶子节点也保存了指向数据的磁盘地址。

叶节点并没有保存数据,而是保留一个逻辑指针指向对应数据块,这就是为什么大家常说“MyISM使用的是非聚簇索引”。

6、B+Tree在Innodb引擎中的体现

一个名为user的表,用Innodb存储引擎会生成下面两种文件,frm存储了表的结构,idb存储了数据。

Innodb存储引擎是以主键为索引组织数据,但是当一个表没有主键,或者没有一个索引,会根据如下规则产生主键:

  1. 如果一个主键被定义了,那么这个主键就是作为聚集索引
  2. 如果没有主键被定义,那么该表的第一个唯一非空索引被作为聚集索引
  3. 如果没有主键也没有合适的唯一索引,那么innodb内部会生成一个隐藏的主键作为聚集索引,这个隐藏的主键是一个6个字节的列,该列的值会随着数据的插入自增。

InnoDB使用的是聚簇索引,将主键组织到一棵B+树中,而行数据就储存在叶子节点上,若使用"where id = 1"这样的条件查找主键,则按照B+树的检索算法即可查找到对应的叶节点,之后获得行数据。若对Name列进行条件搜索,则需要两个步骤:第一步在辅助索引B+树中检索Name,到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作,最终到达叶子节点即可获取整行数据。

所谓聚簇索引,就是指主索引文件和数据文件为同一份文件,聚簇索引主要用在Innodb存储引擎中。

7、列的离散性

找出离散性最差的列?

很显然sex里的值就两种,离散型最差。

想想如果基于sex去构建b+tree?

从上面的图可以看出,如果用sex去检索数据,是不是选择性很差,不知道给往哪走,这时候mysql就会走全表扫描。所以这就是为什么大家常说

离散性差的数据不适合创建索引。

8、Mysql联合索引最左匹配原则

在mysql建立联合索引时会遵循最左前缀匹配的原则,即最左优先,在检索数据时从联合索引的最左边开始匹配。

如果我们创建一个联合索引(name,email),msql会基于(name,email)做为关键字构建索引树。

SELECT * FROM `user` WHERE `name`="tom" AND email = "test3@163.com"; 该条语句根据(name,email)去匹配,可以匹配成功。

SELECT * FROM `user` WHERE `name`="tom" ; 该条语句根据name去配置,最左匹配可以成功。

为什么要使用联合索引:

减少开销:建一个联合索引(col1,col2,col3),实际相当于建了(col1),(col1,col2),(col1,col2,col3)三个索引。每多一个索引,都会增加写操作的开销和磁盘空间的开销。对于大量数据的表,使用联合索引会大大的减少开销!

覆盖索引:对联合索引(col1,col2,col3),如果有如下的sql: select col1,col2,col3 from test where col1=1 and col2=2。那么MySQL可以直接通过遍历索引取得数据,而无需回表,这减少了很多的随机io操作。减少io操作,特别的随机io其实是dba主要的优化策略。所以,在真正的实际应用中,覆盖索引是主要的提升性能的优化手段之一。

效率高:索引列越多,通过索引筛选出的数据越少。有1000W条数据的表,有如下sql:select from table where col1=1 and col2=2 and col3=3,假设假设每个条件可以筛选出10%的数据,如果只有单值索引,那么通过该索引能筛选出1000W10%=100w条数据,然后再回表从100w条数据中找到符合col2=2 and col3= 3的数据,然后再排序,再分页;如果是联合索引,通过索引筛选出1000w10% 10% *10%=1w,效率提升可想而知!


9、为什么官方建议使用自增长主键作为索引。

结合B+Tree的特点,自增主键是连续的,在插入过程中尽量减少页分裂,即使要进行页分裂,也只会分裂很少一部分。并且能减少数据的移动,每次插入都是插入到最后。总之就是减少分裂和移动的频率。在这里也可以体会到,索引会导致数据增删效率变慢

可以到这个网站,体会b+tree的分裂过程

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

总结:

索引列的数据长度能少则少。(每个节点的磁盘大小是固定的,数据长度小了,可以增加节点中的关键字数,减少btree数的高度,进而减少io的操作次数。)
索引一定不是越多越好,越全越好,一定是建合适的。(创建了索引,就会产生一个B+ Tree,增删时会造成节点的分裂,影响效率)
匹配列前缀可用到索引 like 9999%,like %9999%、like %9999用不到索引;(后面两种数据的离散性太低)
Where 条件中 not in 和 <>操作无法使用索引;(还是离散性的问题)
匹配范围值,order by 也可用到索引;(b-tree的叶子节点本来就是已经排好序的链表)
多用指定列查询,只返回自己想到的数据列,少用select *;(如果查询的列是复合索引的列,会提高查询效率)
 

 

© 著作权归作者所有

共有 人打赏支持
上一篇: jvm的基本结构
下一篇: 高并发之缓存
粉丝 0
博文 57
码字总数 92019
作品 0
杨浦
私信 提问
十一、MySQL中的索引原理 -系统的撸一遍MySQL

MySQL支持的索引类型 MySQL支持多种索引类型,每一个存储引擎对其有着不同程度的支持。 MySQL支持以下四种索引,具体支持情况见下表: 索引 MyISAM InnoDB Memory B-Tree 支持 支持 支持 HA...

logbird
2016/11/13
44
0
财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

说在前面 财务平台进行分录分表以后,随着数据量的日渐递增,业务人员对账务数据的实时分析响应时间越来越长,体验性慢慢下降,之前我们基于mysql的性能优化做了一遍,可以说基于mysql该做的...

天河2018
2018/07/13
0
0
浅谈MySQL索引背后的数据结构及算法

摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,...

凯文加内特
2014/01/11
0
0
MySQL索引背后的数据结构及算法原理

本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如B...

小样
2013/02/22
0
0
MySQL索引背后的数据结构及算法原理

摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,...

asdf08442a
2017/12/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot引入第三方jar包或本地jar包的处理方式

在开发过程中有时会用到maven仓库里没有的jar包或者本地的jar包,这时没办法通过pom直接引入,那么该怎么解决呢 一般有两种方法 - 第一种是将本地jar包安装在本地maven库 - 第二种是将本地j...

独钓渔
今天
2
0
五、MyBatis缓存

一、MyBatis缓存介绍 缓存的使用可以明显的加快访问数据速度,提升程序处理性能,生活和工作中,使用缓存的地方很多。在开发过程中,从前端-->后端-->数据库等都涉及到缓存。MyBatis作为数据...

yangjianzhou
今天
2
0
最近研究如何加速UI界面开发,有点感觉了

最近在开发JFinal学院的JBolt开发平台,后端没啥说的,做各种极简使用的封装,开发者上手直接使用。 JBolt开发平台包含常用的用户、角色、权限、字典、全局配置、缓存、增删改查完整模块、电...

山东-小木
今天
3
0
《月亮与六便士》的读后感作文3000字

《月亮与六便士》的读后感作文3000字: 看完英国作家威廉.萨默塞特.毛姆所著《月亮与六便士》(李继宏译),第一疑问就是全书即没提到“月亮”,也没提到“六便士”。那这书名又与内容有什么...

原创小博客
昨天
2
0
微信网页授权获取用户信息(ThinkPHP5)+ 微信发送客服消息(一)

以thinkphp5为实例,创建控制器 class Kf extends Controller { /** * [protected description]微信公众号appid * @var [type] */ protected $appid = "xxxxxxxxxxxxxxx"; /** * [protected......

半缘修道半缘君丶
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部