B+树经常用于数据库存储的数据结构,例如mysql,mysql也是存储在磁盘上的。b+树是在b树的基础上构建的更利于查找连续存储的数据。

b树特点:b树中允许一个节点包含多个key,也就是上面所说的2-3-4树类型的树,但是它包含的节点数可以更多,所以我们可以称它为M阶B树。特点:

1)每个节点最多M减一个节点,可以升序排列

2)每个节点最多有M个子节点

3)根节点至少有两个子节点

4)每个由key-value组成

B+树结构特点:

在b树的基础上:

1)非叶子节点仅具有索引作用,也就是说,非叶子节点只能存储key,不能存储value

2)树的所有叶子节点构成一个有序链表,可以按照key排序的次序依次遍历全部数据。

我们构建一个b+树 ,依次插入的数据为5,8,10,15,16,17,18,6,9,19,20,21,22,7

如果M选择为5,那每个节点包含4个键值对,5个分叉

1)我们先向空树中添如4个数据:

 2)插入16

 3)插入17

 4)插入18

 

5)根据上述操作插入6,9,19,20,21,22

 

6)插入7

 

 B树和B+树的对比:

b+树优点:

1)由于b+树在非叶子节点不包含真正的数据,只能当索引使用,因此在内存相同情况下,能存放更多key

2)b+树的叶子节点都是相连的,因此对整颗树的遍历只需要一次线性遍历叶子节点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而b树则需要进行每一层递归遍历。

b树优点:

由于B树的每个节点都包含key和value,因此我们根据key查找value时,只需要找到key的位置,就能找到value,但b+树只有叶子节点存储数据,索引每一次查找,都必须一次一次,一直找到树的最大深度处,也就是叶子节点的深度,才能找到value。

B+树在数据库中的应用:

数据库中的主键就相当于B+树的key,

在数据库的操作中,查询操作可以说是最频繁的一种操作,因此在设计数据库时,必须要考虑到查询的效率问题,在很多数据库中,都是用到了B+树来提高查询的效率;在操作数据库时,我们为了提高查询效率,可以基于某张表的某个字段建立索引,就可以提高查询效率,那其实这个索引就是B+树这种数据结构实现的。

建立主键id后,想要查询id在10-18之内的数据,B+树就会发挥很大的作用,因为数据都在叶子节点上,并且叶子用链表相连,所以直接在叶子上一依次遍历就可以,效率很高,而B树叶子节点不相连需要向上层查找,所以效率很低。

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信