B+树与索引

发布时间:2023年12月17日
作者简介:大家好,我是smart哥,前中兴通讯、美团架构师,现某互联网公司CTO

联系qq:184480602,加我进群,大家一起学习,一起进步,一起对抗互联网寒冬

对于60%的程序员而言,Java的三层架构Controller、Service、Dao可以说是“越往后走天越黑”,特别是到了Dao层,提着灯笼也只能看到脚边一米开外的河边小石子,只闻对岸风啸马嘶却不知到底是人是鬼,只能借着MyBatis或JPA这些ORM框架隔着宽宽的河举行一场又一场的刺刀战,你砍我一刀,我刺你一剑。

诚然,很多人对MySQL数据库的印象就是一个模糊的大铁柜,闭上眼睛深吸一口气仿佛还能嗅到一股铁锈味。只知柜子里藏着很多张表,表里面存着很多行数据,再详细一点的呢?不知道。

本系列文章旨在帮大家以全新的视角重新认识MySQL的数据组织方式以及工作中最常用的SQL优化常识,带大伙乘一叶扁舟,到对岸亲眼瞧一瞧到底都是些什么神仙鬼怪。由于SQL优化是比较高深的内容,所以学习本文之前,请务必对SQL基础烂熟于心。

MySQL有太多太多细节,根本无法用四、五篇文章说透,但我仍希望这个系列的文章能成为非常好的入门教程,让从来没接触过SQL优化的同学也能快速建立较为系统的知识框架,方便日后学习其他专栏时进一步拓展。


柏青哥

大家小时候在游戏厅看过下面这种机器吗:

日本人管它叫柏青哥(パチンコ),玩法是:

从机器最上方的唯一入口投入一颗钢珠,由于重力的作用,钢珠会往下落。机器是直立的,面板上有很多突出的圆柱,它们的作用是随机改变钢珠的落点。最终,钢珠掉落在下方的某个槽中。

这里提柏青哥,是为后面的B+树及分析B+树搜索过程做铺垫。到时你会发现,沿着索引树搜索的过程和柏青哥小钢珠的下落过程是多么相似!

很多人都听过数据库索引,但是很少人会去思考下面几个问题:

  • 索引是什么
  • 为什么需要索引
  • 索引怎么起作用

在历史的长河中,索引的出现几乎是必然的。不信?那就跟我重走一遍历史吧。

请大家先忘了MySQL、Oracle等乱七八糟的玩意儿,就假设你是上世纪第一批程序员,此时连正儿八经的数据库都没有,需要由你来开天辟地。目前摆在你面前的最大难题是:如何较为高效地存取数据?

线性结构

最直观的想法就是存“格子”里,也就是将数据存在线性结构的容器中,比如数组或链表。

用线性结构存储数据短期看是没问题的,但是一家名为SUN的公司发现,随着公司业务增长,平台要经手的用户数据越来越多,特别是今年,他们收到了很多客户的信件投诉,说网页数据的加载越来越慢了!

SUN的工程师做了个实验,一个线性表如果存了42亿条数据,想要找到id=100的数据,游标只需爬99格即可返回,但如果id=10000000,就要爬将近1000w个格子才能返回。对于这42亿条数据,平均查询次数是21亿次!!

二叉查找树

作为改进,有人提出用树结构来存储数据。比如,如果要找id=6的数据,那么只要比较3次,小于爬格子次数(5次)

如果要找id=9的数据,只要比较4次,小于爬格子次数(8次)。

结合两次实验,SUN的工程师发现:

在一棵树中找到目标数据所需的比较次数 = 目标数据所在的层级

如果用一棵树来存储42亿条数据,即232=42亿,树的层级是32,最差的情况也只要查32次(需要是二叉平衡树),远远小于线性结构的平均21亿次,这是非常夸张的。

注意,在线性结构的案例中,不是我故意不用二分查找,而是不能使用二分查找。一般来说,对于线性结构的数据集合,如果要使用二分查找,那么整个数据都要事先在内存中,但显然没人会这样做!相比在内存中对线性结构进行二分查找,树在逻辑上天然支持二分查找。

然而,树结构也分好几种:

  • Binary Search Tree(二叉查找树)
  • AVL Tree(二叉平衡树)
  • B Tree(平衡树)
  • B+ Tree(大名鼎鼎的B+树,对B Tree的改进)
  • ...

大家可以访问Data Structure Visualizations这个网站动手玩一下,特别注意上面的4种树:

如果你听我的建议,打开上面的网站选择Binary Search Tree并按1,2,3,4...的顺序插入数据时,它其实变成了线性结构:

显然,这不是我们想要的结果,因为刚才已经讨论过,线性结构不适合存储大数据,等后期数据量大了以后要爬很多“格子”。

二叉平衡树

相比来说,AVL Tree更符合SUN工程师的需求:

二叉平衡树会在数据插入完毕后自动调整节点,好让“树的层级”不至于太深。(赶紧去动手玩一下)

按理来说,如果我们按二叉平衡树组织表数据的话,应该是非常完美的。你想啊,42亿数据中找一条记录最多只需比较32次,尤其是对于CPU来说,别说32次比较,哪怕32w次简单数据的比较都不会超过0.1秒。但是!问题在于这里所谓的“32w次简单数据的比较不会超过0.1秒”有个前提条件:数据必须全部在内存中。

而我们的表数据因为数据量很大,而且需要持久化,所以一般来说是存在磁盘中,等需要使用时再从磁盘载入内存,也就是涉及磁盘-内存的IO操作。

通常情况下,没有人会直接把500w行数据一次性加载到内存中进行二分查找,内存极有可能顶不住(同时访问多张表,全部加载)。所以,最终我们组织数据库的方式只能是:

  • 把数据存在磁盘中
  • 数据按树结构组织
  • 查询时分块读取数据并比较,持续进行磁盘IO读取节点,直到找到目标数据

每一个节点存储“一小块数据”,分多次IO读取每一块数据到内存判断,直到找到匹配的数据。

二叉平衡树与磁盘IO

数据存在磁盘中,没问题。

数据桉树结构组织,没问题。

查询时分块读取数据,有一点点问题。

磁盘IO是非常耗时的操作,耗时到什么程度呢?大家可能都听过各个语言的执行效率:

C > C++ > Java >> Python

但这些都是在内存层面谈论语言自身的执行效率,而实际上开发一个Web应用,无论用上述哪个语言,对于普通应用而言,都是可以满足用户需求的,真正的瓶颈是IO(网络IO和磁盘IO)。就好比F1赛车、奥迪A4和拖拉机一起跑在北京4环的路上,限制它们的不是引擎,而是堵车。

所以,二叉平衡树虽然查找42亿数据最多只需32次,但是32次磁盘IO还是不能接受的。

B树

基于上面的分析,如果考虑磁盘IO,那么原本优秀的二叉平衡树将显得不再那么优秀。错的不是二叉平衡树,而是我们没有那么大的内存,也不方便把数据都放内存(考虑数据丢失与持久化)。

但现在不是考虑谁对谁错的时候,要想优化当前数据库,关键是减少磁盘IO次数,而影响IO次数的关键因素就是树的层级(深度)!举个例子,如果目标数据在第二层,那么只要比较到第二层,就找到目标数据直接返回,不用再继续磁盘IO读取下一个节点。而如果数据在32层,那么就需要进行32次磁盘IO,比较到最后一层的节点。

那么,如何减少树的层级呢(让树变矮)?

请大家思考一下232中的“2”指的是什么?

其实就是“二叉平衡树”的“二”,而指数32代表树的层级。也就是说,如果以二叉平衡树的结构组织42亿行数据,那么树的深度是32。如果是“三叉平衡树”呢?

3?? =?232?

3的指数大概为21。也就是说,如果用“三叉树”组织数据,那么层级将会减少到21,也就意味着磁盘IO次数最多为21次。

所以,到这里我们已经有答案了:要想减少二叉平衡树的磁盘IO次数,需要增加它的“叉”,变成“N叉平衡树”,从而减少树的深度。

此时有位长者说了一句:你们心里没点B树吗。

听到这,SUN的工程师颇受启发:对哦,直接用B树就好了。

B树有个“阶”的概念,比如“三叉平衡”的B树其实叫“3阶B树”。

通过上面的图,我们会发现“N阶B树”每个节点可以存N-1个数据(二叉平衡树每个节点只存1个数据),且每个节点至多可以连接N个子节点。

这样组织的好处是,每次加载一个节点时都可以从磁盘带出更多条数据,从而减少磁盘IO的次数。比如原先比完id=3,接下来要和id=5比较,需要再从磁盘中把id=5的数据读出来。而现在当前节点已经有id=3,id=5的数据了,直接比较即可,无需做磁盘IO。

这是典型的“空间换时间”。

但B树最难的地方不是结构本身,而是如何实现这种结构,尤其是如何通过B树组织数据库的表数据?

举个例子,当我要找id=7的数据时,需要先找到根节点,和id=4的节点比较,由于7>4,所以选择右侧那一支,接着因为6<7<8,所以这个节点中三个addr选择中间的addr,顺着这个地址找到7的节点,然后取出数据。

需要注意的是,当一个节点被加载到内存后,这个节点内部的数据就可以通过二分查找得到啦,所以那么id=7去上图右边节点查找正确的addr是很快的。

上面只是演示了3阶B树,实际上1个节点可以存更多数据,做成N阶B树:

分析到这里,历史的话剧就告一个段落,让我们看看MySQL索引的真正实现方式吧。

B+树与索引

实际上MySQL索引采用的是B+树,而不是B树。

为什么不用B树呢?

在操作系统中有个叫“页”的概念,是用来存储数据的一种单位,大小为4k。MySQL中也有“页”的概念,但大小为16k,你可以理解为MySQL中的“页”就是上面B树的一个个节点。

那么问题来了:你知道日常开发中,表中的一行数据大概占多少字节吗?

让我们来计算一下:

在上面这张表中,按每列数据类型推算,一行数据大概 8+150+150+150+150+9+2+9+750+5+5+8+8=1404字节,就算1k好了,因为节点最大size是16k,所以每个节点最多只能存16行数据。

我们之前之所以从二叉平衡树转为B树,是因为B树的每个节点可以存更多数据。但上面的计算告诉我们,其实也就是比二叉平衡树多了15条数据而已。

但原则是对的,为了尽可能使树“变矮”从而减少磁盘IO,最好的做法是让一个节点尽可能地塞入更多的数据。

不过把整行数据塞到节点中,有点太浪费了,我们其实可以把每一行数据的主键存进去。即使用bigint类型做主键,一个主键也就8个字节。假设每个主键对应一个addr(指针),MySQL中一个指针为6个字节,那么节点内每个主键-地址这样形式的数据能存16*1024/14=1170个。

这其实就是B+树对B树的改造。

所谓的B+树,就是把原先B树中分散在各个节点的数据都“赶到”最底层的叶子节点,非叶子节点只存储主键-addr形式的数据:

最终,一棵3层的B+树,最底下的叶子节点总共能存2000w条数据。

有部分同学可能还是不明白B+树为什么比B树能存储更多数据,这里再举个最极端的例子,假设一行表数据8k,而一个节点容量是16k,如果是B Tree,那么一个节点只能存两行数据,最终每个节点只能“夹带”3个addr,只能指向3个子节点:

但如果是B+ Tree,只存主键:

那么最上面的节点可以存更多的主键,指向更多的下级节点,就有更多的“16k数据”。上面还只是分析单个节点的情况,如果放眼整棵索引树,最终叶子节点会多很多很多的“16k数据”。

从MySQL学习者的角度而言,我们只需要知道B+树2个很重要的特征:

  • 非叶子节点不存数据
  • 叶子节点数据用链表相连

所以更详细的版本是:

叶子节点是有序链表,可以帮助做范围查询。

最后,还有个问题,如果我不提估计很少有人会考虑:B+树如何查找数据。

为什么会有这个疑问呢?

之前说过,B树的节点存了完整的数据,假设数据总共3层,而你要找的数据在第2层的某个节点,当你找到后便可以直接返回整行数据。而B+树为了一个节点能存入更多的addr,节点内部只存了主键id,所以即使你在第二层找到匹配的id,还是不能直接返回,必须继续往下,直到在叶子节点读取完整数据。

讨论到这,我们来对比一下B树和B+树:

  • B树的节点都会存储整行数据,占用空间大存储addr少,而B+树的非叶子节点只存储主键,能容纳更多addr
  • 由于非叶子节点能容纳更多addr,那么同一个节点能指向更多下级节点,所以相同数据量时,B+树通常更加“矮”,IO更少
  • B树的查询效率是不稳定的,最好情况是根节点,最差情况是叶子节点,而B+树是稳定的,每次都要查询到叶子节点
  • B+树的叶子节点是有序列表,非常便于范围查询

对于第三点,很多人可能觉得B+树每次都是稳定地查询叶子节点,还不如B树(最好情况根节点就返回了)。其实上面分析过了,B+树每个节点能存储的数据是B树的1170/16≈73倍,意味着B+树每个节点可以连接的分支更多,相同数据量的情况下,B+树远远矮于B树。比如B树的查询IO次数是1~100,而B+树恒定为3,你觉得哪个效率高?

回头看看柏青哥,钢珠掉落的过程是不是很像沿着索引查找数据呢~

学到这里,相信Dao层的对岸到底是什么,大家心里已经有B+树了:

至此,我们回过头来给索引下个定义:

索引是一种数据结构,用于高效搜索目标数据,在MySQL中具体实现为B+树(InnoDB引擎)。

最后说一句,没有所谓的“B减树”,很多人可能看到B树的英文表示法是"B-Tree",误读为“B减树”。

作者简介:大家好,我是smart哥,前中兴通讯、美团架构师,现某互联网公司CTO

进群,大家一起学习,一起进步,一起对抗互联网寒冬

文章来源:https://blog.csdn.net/smart_an/article/details/135028982
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。