数据结构-B树和B+树

一、B树

一个节点包含多个key-value值

假设一棵B树由M个参数构建，我们将其称为M阶B树

        每个节点最多有M-1个key-value值，并且key值升序排列，每个节点最多能有M个叉

1.1 分类

二节点

三节点

四节点

五节点

key:  给每一个文件进行标号（主键）

value:  页（存储数据的地址）

1.2 例子

例：构建5阶B树

1.3 优点

        每一个节点都包含key和value,根据key找value时，只需找到key值，value就可以找到。 

而B+树只有遍历到叶子节点才能找到 value值。

---

二、B+树

B+树的非叶子节点仅具有索引作用，也就是说非叶子节点只存储key值，不存储value值

B+树的所有叶子节点构成一个有序链表。

优点：

B+树的叶子节点不包含value值，只做索引使用，所以节点大小相同的情况下，B+树的非叶子节点能存放更多的key值，树的高度越低。

B+树的叶子节点构成了有序链表，所以遍历整棵树只需要遍历叶子节点即可，便于区间查找。

例子

构建5阶B+树：