终于有篇看的懂的 B 树文章了!

索引,相信大多数人已经相当熟悉了,很多人都知道 MySQL 的索引主要以 B+ 树为主,但是要问到为什么用 B+ 树,恐怕很少有人能把前因后果讲述完整。本文就来从头到尾介绍下数据库的索引。

索引是一种数据结构,用于帮助我们在大量数据中快速定位到我们想要查找的数据。

索引最形象的比喻就是图书的目录了。注意这里的大量,数据量大了索引才显得有意义,如果我想要在 [1,2,3,4] 中找到 4 这个数据,直接对全数据检索也很快,没有必要费力气建索引再去查找。

索引在 MySQL 数据库中分三类: 

  • B+ 树索引
  • Hash 索引
  • 全文索引

我们今天要介绍的是工作开发中最常接触到的 InnoDB 存储引擎中的 B+ 树索引。

要介绍 B+ 树索引,就不得不提二叉查找树,平衡二叉树和 B 树这三种数据结构。B+ 树就是从他们仨演化来的。

二叉查找树

首先,让我们先看一张图:

从图中可以看到,我们为 user 表(用户信息表)建立了一个二叉查找树的索引。

图中的圆为二叉查找树的节点,节点中存储了键(key)和数据(data)。键对应 user 表中的 id,数据对应 user 表中的行数据。

二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值,右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点,没有子节点的节点我们称之为叶节点。 

如果我们需要查找 id=12 的用户信息,利用我们创建的二叉查找树索引,查找流程如下: 

  • 将根节点作为当前节点,把 12 与当前节点的键值 10 比较,12 大于 10,接下来我们把当前节点>的右子节点作为当前节点。 
  • 继续把 12 和当前节点的键值 13 比较,发现 12 小于 13,把当前节点的左子节点作为当前节点。 
  • 把 12 和当前节点的键值 12 对比,12 等于 12,满足条件,我们从当前节点中取出 data,即 id=12,name=xm。

利用二叉查找树我们只需要 3 次即可找到匹配的数据。如果在表中一条条的查找的话,我们需要 6 次才能找到。

平衡二叉树

上面我们讲解了利用二叉查找树可以快速的找到数据。但是,如果上面的二叉查找树是这样的构造:

这个时候可以看到我们的二叉查找树变成了一个链表。如果我们需要查找 id=17 的用户信息,我们需要查找 7 次,也就相当于全表扫描了。 导致这个现象的原因其实是二叉查找树变得不平衡了,也就是高度太高了,从而导致查找效率的不稳定。为了解决这个问题,我们需要保证二叉查找树一直保持平衡,就需要用到平衡二叉树了。 平衡二叉树又称 AVL 树,在满足二叉查找树特性的基础上,要求每个节点的左右子树的高度差不能超过 1。 

下面是平衡二叉树和非平衡二叉树的对比:

由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。平衡二叉树保证了树的构造是平衡的,当我们插入或删除数据导致不满足平衡二叉树不平衡时,平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。平衡二叉树相比于二叉查找树来说,查找效率更稳定,总体的查找速度也更快。

B 树

因为内存的易失性。一般情况下,我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比,从磁盘中读取数据的速度会慢上百倍千倍甚至万倍,所以,我们应当尽量减少从磁盘中读取数据的次数。另外,从磁盘中读取数据时,都是按照磁盘块来读取的,并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中,那一次磁盘读取操作就会读取更多数据,那我们查找数据的时间也会大幅度降低。如果我们用树这种数据结构作为索引的数据结构,那我们每查找一次数据就需要从磁盘中读取一个节点,也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么?说明每个磁盘块仅仅存储一个键值和数据!那如果我们要存储海量的数据呢?

可以想象到二叉树的节点将会非常多,高度也会极其高,我们查找数据时也会进行很多次磁盘 IO,我们查找数据的效率将会极低!

为了解决平衡二叉树的这个弊端,我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。 

B 树(Balance Tree)即为平衡树的意思,下图即是一棵 B 树:

图中的 p 节点为指向子节点的指针,二叉查找树和平衡二叉树其实也有,因为图的美观性,被省略了。图中的每个节点称为页,页就是我们上面说的磁盘块,在 MySQL 中数据读取的基本单位都是页,所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。从上图可以看出,B 树相对于平衡二叉树,每个节点存储了更多的键值(key)和数据(data),并且每个节点拥有更多的子节点,子节点的个数一般称为阶,上述图中的 B 树为 3 阶 B 树,高度也会很低。 基于这个特性,B 树查找数据读取磁盘的次数将会很少,数据的查找效率也会比平衡二叉树高很多。 假如我们要查找 id=28 的用户信息,那么我们在上图 B 树中查找的流程如下: 

  • 先找到根节点也就是页 1,判断 28 在键值 17 和 35 之间,那么我们根据页 1 中的指针 p2 找到页 3。 
  • 将 28 和页 3 中的键值相比较,28 在 26 和 30 之间,我们根据页 3 中的指针 p2 找到页 8。 
  • 将 28 和页 8 中的键值相比较,发现有匹配的键值 28,键值 28 对应的用户信息为(28,bv)。

B+ 树

B+ 树是对 B 树的进一步优化。让我们先来看下 B+ 树的结构图:

根据上图我们来看下 B+ 树和 B 树有什么不同:

①B+ 树非叶子节点上是不存储数据的,仅存储键值,而 B 树节点中不仅存储键值,也会存储数据。之所以这么做是因为在数据库中页的大小是固定的,InnoDB 中页的默认大小是 16KB。

如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的 IO 次数又会再次减少,数据查询的效率也会更快。

另外,B+ 树的阶数是等于键值的数量的,如果我们的 B+ 树一个节点可以存储 1000 个键值,那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。

一般根节点是常驻内存的,所以一般我们查找 10 亿数据,只需要 2 次磁盘 IO。 

②因为 B+ 树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的。

那么 B+ 树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点,要实现这一点是很不容易的。  

有心的读者可能还发现上图 B+ 树中各个页之间是通过双向链表连接的,叶子节点中的数据是通过单向链表连接的。

其实上面的 B 树我们也可以对各个节点加上链表。这些不是它们之前的区别,是因为在 MySQL 的 InnoDB 存储引擎中,索引就是这样存储的。

也就是说上图中的 B+ 树索引就是 InnoDB 中 B+ 树索引真正的实现方式,准确的说应该是聚集索引(聚集索引和非聚集索引下面会讲到)。

通过上图可以看到,在 InnoDB 中,我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中,B+ 树索引的叶子节点并不存储数据,而是存储数据的文件地址。

聚集索引 VS 非聚集索引

在上节介绍 B+ 树索引的时候,我们提到了图中的索引其实是聚集索引的实现方式。

那什么是聚集索引呢?在 MySQL 中,B+ 树索引按照存储方式的不同分为聚集索引和非聚集索引。

这里我们着重介绍 InnoDB 中的聚集索引和非聚集索引:

①聚集索引(聚簇索引):以 InnoDB 作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会帮你创建一个隐式的主键。

这是因为 InnoDB 是把数据存放在 B+ 树中的,而 B+ 树的键值就是主键,在 B+ 树的叶子节点中,存储了表中所有的数据。

这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引,我们称之为聚集索引。 

②非聚集索引(非聚簇索引):以主键以外的列值作为键值构建的 B+ 树索引,我们称之为非聚集索引。

非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据,而是存储该列对应的主键,想要查找数据我们还需要根据主键再去聚集索引中进行查找,这个再根据聚集索引查找数据的过程,我们称为回表。

明白了聚集索引和非聚集索引的定义,我们应该明白这样一句话:数据即索引,索引即数据。

利用聚集索引和非聚集索引查找数据

前面我们讲解 B+ 树索引的时候并没有去说怎么在 B+ 树中进行数据的查找,主要就是因为还没有引出聚集索引和非聚集索引的概念。

下面我们通过讲解如何通过聚集索引以及非聚集索引查找数据表中数据的方式介绍一下 B+ 树索引查找数据方法。

利用聚集索引查找数据

还是这张 B+ 树索引图,现在我们应该知道这就是聚集索引,表中的数据存储在其中。

现在假设我们要查找 id>=18 并且 id<40 的用户数据。对应的 sql 语句为:

select * from user where id>=18 and id <40

其中 id 为主键,具体的查找过程如下:

①一般根节点都是常驻内存的,也就是说页 1 已经在内存中了,此时不需要到磁盘中读取数据,直接从内存中读取即可。

从内存中读取到页 1,要查找这个 id>=18 and id<40 或者范围值,我们首先需要找到 id=18 的键值。

从页 1 中我们可以找到键值 18,此时我们需要根据指针 p2,定位到页 3。

②要从页 3 中查找数据,我们就需要拿着 p2 指针去磁盘中进行读取页 3。

从磁盘中读取页 3 后将页 3 放入内存中,然后进行查找,我们可以找到键值 18,然后再拿到页 3 中的指针 p1,定位到页 8。

③同样的页 8 页不在内存中,我们需要再去磁盘中将页 8 读取到内存中。

将页 8 读取到内存中后。因为页中的数据是链表进行连接的,而且键值是按照顺序存放的,此时可以根据二分查找法定位到键值 18。

此时因为已经到数据页了,此时我们已经找到一条满足条件的数据了,就是键值 18 对应的数据。

因为是范围查找,而且此时所有的数据又都存在叶子节点,并且是有序排列的,那么我们就可以对页 8 中的键值依次进行遍历查找并匹配满足条件的数据。

我们可以一直找到键值为 22 的数据,然后页 8 中就没有数据了,此时我们需要拿着页 8 中的 p 指针去读取页 9 中的数据。

④因为页 9 不在内存中,就又会加载页 9 到内存中,并通过和页 8 中一样的方式进行数据的查找,直到将页 12 加载到内存中,发现 41 大于 40,此时不满足条件。那么查找到此终止。最终我们找到满足条件的所有数据,总共 12 条记录:

(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。

下面看下具体的查找流程图:

利用非聚集索引查找数据

读者看到这张图的时候可能会蒙,这是啥东西啊?怎么都是数字。如果有这种感觉,请仔细看下图中红字的解释。

什么?还看不懂?那我再来解释下吧。首先,这个非聚集索引表示的是用户幸运数字的索引(为什么是幸运数字?一时兴起想起来的:-)),此时表结构是这样的。

在叶子节点中,不再存储所有的数据了,存储的是键值和主键。对于叶子节点中的 x-y,比如 1-1。左边的 1 表示的是索引的键值,右边的 1 表示的是主键值。

如果我们要找到幸运数字为 33 的用户信息,对应的 sql 语句为:

select * from user where luckNum=33

查找的流程跟聚集索引一样,这里就不详细介绍了。我们最终会找到主键值 47,找到主键后我们需要再到聚集索引中查找具体对应的数据信息,此时又回到了聚集索引的查找流程。  
下面看下具体的查找流程图:

在 MyISAM 中,聚集索引和非聚集索引的叶子节点都会存储数据的文件地址。

总结

本篇文章从二叉查找树,详细说明了为什么 MySQL 用 B+ 树作为数据的索引,以及在 InnoDB 中数据库如何通过 B+ 树索引来存储数据以及查找数据。

我们一定要记住这句话:数据即索引,索引即数据。

参考资料: 

  • 《MySQL 必知必会》  
  • 《MySQL 技术内幕 InnoDB 存储引擎第2版》  
  • https://www.cnblogs.com/vianzhang/p/7922426.html 
  • http://blog.codinglabs.org/articles/theory-of-mysql-index.html
Image placeholder
yuehongbo
未设置
  61人点赞

没有讨论,发表一下自己的看法吧

推荐文章
终于有人把中台说清楚了!

前一段朋友圈被中台刷屏了,那么今天我们来说说中台!缘起百度指数搜索“中台”,可以发现,中台一词前几年几乎都没有搜索,反倒是今年5月21号开始蹭蹭往上涨!百度指数仔细搜索了一下原来5月21号腾讯召开了全

全网最通俗易懂的Kafka入门

前言只有光头才能变强。文本已收录至我的GitHub仓库,欢迎Star:https://github.com/ZhongFuCheng3y/3y众所周知,消息队列的产品有好几种,这里我选择学习Kafka

宝宝也能看懂的 leetcode 周赛 - 169 - 2

1305.AllElementsinTwoBinarySearchTreesHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第2题,也是题目列表中的第13

宝宝也能看懂的 leetcode 周赛 - 169 - 1

1304.FindNUniqueIntegersSumuptoZeroHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第1题,也是题目列表中的第1304题

宝宝也能看懂的 leetcode 周赛 - 169 - 3

1306.JumpGameIIIHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第3题,也是题目列表中的第1306题--『JumpGameIII』题目描述

宝宝也能看懂的 leetcode 周赛 - 169 - 4

1307.VerbalArithmeticPuzzleHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第4题,也是题目列表中的第1307题--『Verba

程序员:我终于知道post和get的区别

IT界知名的程序员曾说:对于那些月薪三万以下,自称IT工程师的码农们,其实我们从来没有把他们归为我们IT工程师的队伍。他们虽然总是以IT工程师自居,但只是他们一厢情愿罢了。此话一出,不知激起了多少(码

太天真了!这简历一看就是包装过的!

前言上到职场干将下到职场萌新,都会接触到包装简历这个词语。当你简历投到心仪的公司,公司内负责求职的工作人员是如何甄别简历的包装程度的?Coody老师根据自己的经验写下了这篇文章,谁都不是天才,包装无可

中国顶级程序员图鉴,最后一个厉害了!

程序员圈子里有很多如明星般闪耀的牛人!有中国第一代程序员求伯君有获得图灵奖的姚期智有产品取得巨大成功的张小龙商业巨子张一鸣影响开源领域的章亦春……他们的最初都是程序员机遇与热爱,把他们送到了不同的方向

Spring Boot 面试,一个问题就干趴下了!

随着SpringBoot使用越来越广泛,SpringBoot已经成为Java程序员面试的知识点,很多同学对SpringBoot理解不是那么深刻,经常就会被几个连环跑给干趴下了!比如下面这一段的Spri

华为鸿蒙来了!八大亮点超越安卓,特殊情况随时可用!

大数据文摘编辑部出品鸿蒙OS来了!8月9日,在广东东莞举办的华为开发者大会HDC.2019上,华为消费者业务CEO余承东正式发布了“面向未来、多终端能力共享的操作系统”——鸿蒙HarmonyOS。鸿蒙

蓦然回首,Java 已经 24 岁了!

01、真没想到,Java竟然24岁了(算是90后)!提起Java,印象最深刻的当然就是:classCmower{ publicstaticvoidmain(String[]args){  System

尴尬了!四分之三的Sybase/ASE用户无意迁往SAP HANA

SAP战略,很大一部与SAP HANA有关。SAPHANA是SAP在2010年发布的一款产品,其全称是SAPHighPerformanceAnalyticApplication,简称SAPHANA,内

(PPT 下载,来了!)DTCC2019 中国数据库技术大会见证实录

2019年5月8日-10日,DTCC2019第十届中国数据库技术大会历时3天,圆满收官。作为国内顶级的数据领域技术盛会,共有23个技术场次,邀请超过125名专家,包括来自阿里、京东、苏宁、滴滴出行、百

能直接下载了!微软最爽命令行工具登陆Windows 10,GitHub标星已破4万6

乾明发自凹非寺 转自量子位 |公众号QbitAI微软正式放出命令行工具WindowsTerminal。这个在发布之际就引得开发者大呼“WoW!Awesome!MyGod!”,甚至引得不少人当场表态买P

Oculus CTO、传奇程序员John Carmack宣布离职:我要去搞AI了!

大数据文摘出品OculusCTO,也是游戏程序员大神、开源软件倡导者JohnCarmack昨天在Facebook上宣布,将辞去公司CTO职位,只担任咨询身份。而对于下一步的打算,John也毫不掩饰,直

我是程序员,每一天都太难了!

互联网圈子里有一个神奇的群体——程序员。他们每天穿着格子衫,背着双肩包挤地铁,一到公司就陷入了“打代码-喝水-上厕所-打代码-喝水-上厕所”的死循环。热(jia)爱(ban)工(yan)作(zhong

10后小学生都能教你学编程了!低龄编程的下限在哪?

大数据文摘出品作者:宁静最近,文摘菌经常收到读者留言,说b站上有一个10后小学生在教编程。小学生???教编程???话说文摘菌小学时候还只知道玩儿贪吃蛇……在感叹长江后浪推前浪的同时,文摘菌也赶紧去这位

阿里巴巴为什么能抗住90秒100亿?看完这篇你就明白了!

1、概述本文以淘宝作为例子,介绍从一百个并发到千万级并发情况下服务端的架构的演进过程,同时列举出每个演进阶段会遇到的相关技术,让大家对架构的演进有一个整体的认知,文章最后汇总了一些架构设计的原则。2、

分库分表就能无限扩容吗,解释得太好了!

像我这样的菜鸟,总会有各种疑问,刚开始是对JDKAPI的疑问,对NIO的疑问,对JVM的疑问,当工作几年后,对服务的可用性,可扩展性也有了新的疑问,什么疑问呢?其实是老生常谈的话题:服务的扩容问题。正

Java 与 Kotlin 系列文章 (一):性能问题

随着对Kotlin越来越深入的了解,我发现市面上关于Kotlin方面,比较深入的资料几乎是0,所以我决定,将Kotlin各个方面的研究作为我的研究生课题,而性能问题往往是程序员最佳关注的内容,所以第

一篇文章帮你了解 PHP 7.3 更新

PHP目前依旧是其它脚本语言强劲的竞争对手,这主要归功于其核心维护团队的快速更新。 自从PHP7.0发布以来,社区见证了许多新特性的诞生,极大地改进了开发者在项目中应用PHP的方式。提高PHP应用的性

一篇文章读懂“GAN”——生成式对抗网络

机器学习是一个不断发展的领域,因此对于很多人来说,时刻跟踪这一领域的最新进展是很难的。GAN(生成式对抗网络)是最近引起广泛关注的新兴领域之一,为了让大家能够更好地跟上技术发展的脚步,我们安排了一个简

一篇文章看懂,存储虚拟化在不同用例中的实践与优势

存储虚拟化是一种对物理存储资源进行抽象的技术,使其看起来像是一个集中的资源。虚拟化掩盖了管理内存、网络、服务器和存储中资源的复杂性。存储虚拟化运行在多个存储设备上,使它们看起来就像一个单一的存储池。这