B+树数据结构

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

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

1&＃xff09;每个节点最多M减一个节点&＃xff0c;可以升序排列

2&＃xff09;每个节点最多有M个子节点

3&＃xff09;根节点至少有两个子节点

4&＃xff09;每个由key-value组成

B&＃43;树结构特点&＃xff1a;

在b树的基础上&＃xff1a;

1&＃xff09;非叶子节点仅具有索引作用&＃xff0c;也就是说&＃xff0c;非叶子节点只能存储key&＃xff0c;不能存储value

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

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

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

1&＃xff09;我们先向空树中添如4个数据&＃xff1a;

 2&＃xff09;插入16

 3&＃xff09;插入17

 4&＃xff09;插入18

5&＃xff09;根据上述操作插入6,9,19,20,21,22

6&＃xff09;插入7

 B树和B&＃43;树的对比&＃xff1a;

b&＃43;树优点&＃xff1a;

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

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

b树优点&＃xff1a;

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

B&＃43;树在数据库中的应用&＃xff1a;

数据库中的主键就相当于B&＃43;树的key,

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

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