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树叶子节点不相连需要向上层查找,所以效率很低。