原来你是这样的 B+ 树
![原来你是这样的B+树](https://static001.geekbang.org/infoq/a0/a0480c538069abe960c46f34d3e5d1bd.png)
前言
B+树是目前最常用的一种索引数据结构,通常用于数据库和操作系统的文件系统中,本文就网上的知识点与个人理解结合分享,如有错误,欢迎探讨及指正.
定义
B+树是B树的一种变形形式,B+树上的叶子结点存储关键字以及相应记录的地址,叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下(==注意: B+树的阶数m表示一个节点最多能有m个子节点,也就是每个节点上最多的键值个数.==): 1.每个结点至多有m个子女; 2.除根结点外,每个结点至少有[m/2]个子女,根结点至少有两个子女; 3.有k个子女的结点必有k个关键字。
B+树的查找与B树不同,当索引部分某个结点的关键字与所查的关键字相等时,并不停止查找,应继续沿着这个关键字左边的指针向下,一直查到该关键字所在的叶子结点为止。
图文理解
下面我们通过图文详解来深入理解B+树
不同阶数的B+树对比
我们将数组[1,2,3,4...20]分别插入3阶、4阶、5阶、6阶B+数,最终存储的数据结构如下图:
3阶B+树 :
![](https://static001.geekbang.org/infoq/56/56cc72ad440a6fa34a2b569b330981be.png)
4阶B+数:
![](https://static001.geekbang.org/infoq/49/49b8e4bada850a716e3ddd59e5b8709e.png)
5阶B+数:
![](https://static001.geekbang.org/infoq/d4/d43bb3be16c437c082414cbd2bd44832.png)
6阶B+数:
![](https://static001.geekbang.org/infoq/24/248d65b6bf56d08ffaf7b969c6b6dbfb.png)
通过上面对比,我们不难发现以下特征:
所有节点均有序排列;
树节点总是树高平衡;
m阶的B+树除了根节点之外的每个节点都包含最少 m/2个元素,但最多包含 m-1 个元素(文末提供在线测试地址,可以自行删减元素,观察叶子结点的变化);
对于任意的节点有最多 m 个子指针;
对于所有内部节点,子指针的数目总是比元素的数目多一个;
阶数越大,数的高度越小.
所有数据存储在叶子结点上,非叶子节点不存储行数据,是为了能存储更多索引键,从而降低B+树的高度,进而减少IO次数.
B+树insert/delete操作后数据结构的变化
本次我们演示4阶B+树操作的变化过程
第一步:我们先插入数字1、2、3
![](https://static001.geekbang.org/infoq/d2/d200053c711ba00f11e7660d6a1d6c7c.png)
第二步:插入数字4,由于每个节点最多只能有m-1个元素,即超过3个后需要进行拆分页,而目前只有一个根节点,所以旋转后树的深度+1.
![](https://static001.geekbang.org/infoq/65/659967c3e2a01d162146004b6b01631c.png)
第三步:分别插入数字5、6,根据结构的特性拆分页,如下图
![](https://static001.geekbang.org/infoq/af/afa3f911c9c1203d28ec53382a6ca7f1.png)
![](https://static001.geekbang.org/infoq/b8/b8861c90c0ffa89fa5547e16ae82fc73.png)
第四步:分别插入数字7、8、9
![](https://static001.geekbang.org/infoq/20/2076f9d03089fd1c19d26c919fac6883.png)
![](https://static001.geekbang.org/infoq/fa/faee44d183ecf52ac03b55b16fd43756.png)
![](https://static001.geekbang.org/infoq/59/59aaaceddcd7ea8e52e45a144edec092.png)
插入10的时候,触发每个节点最多只能有m-1个元素的特性,同时触发了[任意的节点有最多 m 个子指针]的特性,所以继续旋转后树的深度+1.
![](https://static001.geekbang.org/infoq/84/84451d123ea307773a9928da23c624ab.png)
第五步:前面四步演示了树的旋转以及拆分页,接下来我们看下删除元素会是什么样的效果,先删除元素10看下:
![](https://static001.geekbang.org/infoq/4c/4cdfd165737092528d353f41d9fd7699.png)
在第四步最后我们增加一个元素10,触发了B+树的特性调整了树的高度,现在我们删除元素10,从上图可以看出树的高度没有变化,这点跟平衡树不一样,我们继续删元素.
![](https://static001.geekbang.org/infoq/84/84119ac8c2aff316b798c7cbf3de49fc.png)
![](https://static001.geekbang.org/infoq/e1/e16cf57cc0ac9282438e16c5a445ac5a.png)
![](https://static001.geekbang.org/infoq/d4/d4f615ce62d92014c1a691c4c7e3e5dd.png)
删除元素7之后,层级没有变化,但是第二级的右子节点元素值发生了旋转,由7变成了6,继续删除元素6:
![](https://static001.geekbang.org/infoq/44/44defadc360faf9419d6afb7056512a5.png)
我们发现删除元素6后,树的层级发生了变化,这是因为触发了[对于所有内部节点,子指针的数目总是比元素的数目多一个]这一特性,然后根据最优算法降低了树的高度,同时我们发现,此时的5个元素排列并没有恢复到我们之前从元素[1-5]插入后的结构,这点非常妙,不管接下来是新增、删除、查找你会发现效率都是最优的.
B+树的查找
我们还是以4阶树10个元素为例,查找元素6
![](https://static001.geekbang.org/infoq/ec/ecce79ab00707d341b3aef8d01151d7c.png)
![](https://static001.geekbang.org/infoq/5c/5c405a0f6c938d0d2004cb0a30061c04.png)
![](https://static001.geekbang.org/infoq/6f/6fdb576a8c235730933ec4a2ce377a15.png)
从上可以看出查找路线与二叉树的查找规则一致,继续查找元素5
![](https://static001.geekbang.org/infoq/02/02c3840eb2f127f666097600bcf1f549.png)
![](https://static001.geekbang.org/infoq/06/06f2d17ca107e34aed11e0add4aa0e4f.png)
![](https://static001.geekbang.org/infoq/cf/cf75466814dc7b96e00263fba46cbee0.png)
结合这两次查找,可以看出都消耗了3次IO找到数据,这个次数刚好等于数的高度,数据量少时看不出这个效率,假设是100阶的树,存储了400w+数据,实际也是3次IO就可以找到想要的数据,这个时候B+树的优势就体现出来了.
至此,相信你对B+树又有了更直观的认识,接下来我们再聊聊mysql应用的B+树索引.
mysql的B+树索引
mysql的B+树索引有多少阶?
对于这个问题,我们需要先了解下磁盘相关知识.
磁盘的最小存储单位是扇区(512字节)
磁盘的读取是以块为基本单位,一块大小为8个扇区,即4kb
B+树的每一个节点占用的空间就是一个块大小
![](https://static001.geekbang.org/infoq/bc/bc946b22c5275a1293f7be8902edb256.png)
由于B+树节点中只存储元素和指针.如果有n个元素,那么就有n+1个指针,假设现在索引存储int类型的值,一个int(32位)占用4个字节,一个指针占用8个字节,那么一个块最多能存4096/(4n+8(n+1))即340个元素,那么索引即为341阶(m阶数最多包含m-1个元素).
mysql的B+树索引能存多少数据?
以innodb引擎的索引数据结构为例,它的存储单元为一页,每页大小默认为16kb,该值可以通过参数调整,如下图.
![](https://static001.geekbang.org/infoq/df/df12e0d9419133d970fb281e5d345129.png)
假设每个节点中索引元素占8个字节,指针占用6个字节,那么每页可存(16*1024)/(8+6)=1170个索引元素
假设B+树的高度为3,一条数据大小为1k,那么:第一层可以存1170个元素;第二层可以存11701170=1368900个元素;第三层属于叶子结点,可以存的数据条数为页大小16k/每条数据大小1k,即16条,那么总共可以存储的数据条数即为161368900=21902400
总结:mysql 单表使用innodb引擎(表数据文件本身就是一个B+树组织的索结构文件),默认至少可以存2000w数据(实际每个节点不只存储了元素及指针),并且查找数据,最多3次io即可.
资料参考
欢迎关注个人订阅号:Java技术宝典 ,及时获取最新分享.
![](https://static001.geekbang.org/infoq/eb/eb48afa7f445554dace28bf228e3576f.png)
版权声明: 本文为 InfoQ 作者【Java技术宝典】的原创文章。
原文链接:【http://xie.infoq.cn/article/0c805169b11aba5d31da2054b】。文章转载请联系作者。
评论