[{"createTime":1735734952000,"id":1,"img":"hwy_ms_500_252.jpeg","link":"https://activity.huaweicloud.com/cps.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=V1g3MDY4NTY=&utm_medium=cps&utm_campaign=201905","name":"华为云秒杀","status":9,"txt":"华为云38元秒杀","type":1,"updateTime":1735747411000,"userId":3},{"createTime":1736173885000,"id":2,"img":"txy_480_300.png","link":"https://cloud.tencent.com/act/cps/redirect?redirect=1077&cps_key=edb15096bfff75effaaa8c8bb66138bd&from=console","name":"腾讯云秒杀","status":9,"txt":"腾讯云限量秒杀","type":1,"updateTime":1736173885000,"userId":3},{"createTime":1736177492000,"id":3,"img":"aly_251_140.png","link":"https://www.aliyun.com/minisite/goods?userCode=pwp8kmv3","memo":"","name":"阿里云","status":9,"txt":"阿里云2折起","type":1,"updateTime":1736177492000,"userId":3},{"createTime":1735660800000,"id":4,"img":"vultr_560_300.png","link":"https://www.vultr.com/?ref=9603742-8H","name":"Vultr","status":9,"txt":"Vultr送$100","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":5,"img":"jdy_663_320.jpg","link":"https://3.cn/2ay1-e5t","name":"京东云","status":9,"txt":"京东云特惠专区","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":6,"img":"new_ads.png","link":"https://www.iodraw.com/ads","name":"发布广告","status":9,"txt":"发布广告","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":7,"img":"yun_910_50.png","link":"https://activity.huaweicloud.com/discount_area_v5/index.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=aXhpYW95YW5nOA===&utm_medium=cps&utm_campaign=201905","name":"底部","status":9,"txt":"高性能云服务器2折起","type":2,"updateTime":1735660800000,"userId":3}]
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树叶子节点不相连需要向上层查找,所以效率很低。