龙空技术网

图解mysql BTREE和B+TREE数据结构实现过程

波波说运维 500

前言:

当前小伙伴们对“treecss”大体比较关心,兄弟们都需要学习一些“treecss”的相关文章。那么小编也在网摘上汇集了一些关于“treecss””的相关资讯,希望兄弟们能喜欢,朋友们快快来了解一下吧!

概述

今天主要分享一个有趣的数据结构地址,通过这个地址可以让大家更有效的理解BTREE和B+TREE数据结构实现过程。

数据结构:

一、B tree数据结构

这里有一个陌生区关于 Max. Degree,这个你可以理解为阶,也可以理解为度,即B+ 树的阶数(一个节点存储的键的数量)

例如现在这个值设置的是 4,那么在一个节点中最多就可以存储 3 条数据,设置为 5那就可以最多放 4 条记录。

1、插入数据

现在可以看到目前只插入了 3 条数据:

再加一条数据,节点就会进行分裂,这个也就验证了当阶设置为 n 时,一个节点可存 n-1 条数据

想要达到快速检索数据,那就需要满足俩个特性,一个是有序,另一个就是平衡。

从下图中可以看到 BTree 是有一定的顺序性的,平衡性更满足

2、查找数据

》》查找数据为9的过程如下:

当查找数值9,首先看到的数据是 4,9 是大于 4 的,所以会往 4 的右节点寻找。继续找到范围在 6 到 8 的节点,9 又大于 8,所以还需要往右节点寻找,最有一步就找到了数据 9,这个过程就是 BTree 数据结构查找数据的执行过程。

》》查找数据为6的过程如下:

当查找数值6,首先看到的数据是 4,6 是大于 4 的,所以会往 4 的右节点寻找。继续找到范围在 6 到 8 的节点,然后就找到了数据6,此时只需要2次IO。

3、删除数据

假设删除数据为6的记录,过程如下:

删除数据为7的记录,过程如下:

这里大家可以考虑:BTree三层可以存储多少数据?这样大家就可以理解mysql数据库为什么要用B+Tree结构了。

三、B+ Tree数据结构

1、插入数据

现在可以看到目前只插入了 3 条数据:

再插入一条数据:

共插入十条记录,结构如下:

2、查找数据

当查找数值9,首先看到的数据是 4,9 是大于 4 的,所以会往 4 的右节点寻找。继续找到范围在 6 到 8 的节点,9 又大于 8,所以还需要往右节点寻找,最有一步就找到了数据 9,这个过程就是 B+Tree 数据结构查找数据的执行过程。

演变过程如下:

当查找数值为5的过程,如下:

当查找数值5,首先看到的数据是 7,5 是小于 7 的,所以会往 7 的左节点寻找。继续找到范围在 3 到 5 的节点,然后再往右节点寻找,最后在叶子结点找到了数据 5,总共需要3次IO。

3、删除数据

假设删除数据为6的记录,过程如下:

假设删除数据为5的记录,过程如下:

从前面的结构可以看出

1)B+Tree 所有的数据都存储在叶子节点上。

2)B+Tree 所有的叶子节点之间是一种链式环结构。

如果说 B+Tree 读取数据的深度跟 B-Tree 的深度一样,都是三层,那么同样的道理每个磁盘的大小为 16kb。

那在 B+Tree 中非叶子节点可以存储多少数据呢!一般来说我们每个表都会存在一个主键。

根据三层来计算,第一层跟第二层存储的是 key 值,也就是主键值。

都知道 int 类型所占的内存时 4Byte(字节),指针的存储就给个 6Byte,一共就是 10Tybe,那么第一层节点就可以存储 16*1000/10=1600。

同理第二层每个节点也是可以存储 1600 个 key。

第三层是叶子节点,每个磁盘存储大小同样安装 BTree 的计算一样,每条数据占 1kb。

那么在 B+Tree 中三层可以存储的数据就是 1600*1600*16=40960000。

从这点来看 B+Tree 存储的数据跟 BTree 存储的数据根本就不是一个级别。

前面经过了特别漫长的画图截图现在基本可以知道:

B+Tree 叶子节点上存储的是全量数据(key+data),而非叶子节点只存储 key。B+Tree 在同样的深度下存储的数据是远远大于 BTree 的。B+Tree 每个叶子节点都有指向下一个叶子节点的链接。这样的好处在于可以从任意一个叶子节点开始遍历,获取接下来所有的数据。B+Tree 树查询效率稳定,任何数据的查找都是必须从叶子节点到非叶子节点,所以说每个数据查找的效率几乎都是相同的

后面会分享更多devops和DBA方面内容,感兴趣的朋友可以关注下。。。

标签: #treecss