文章目录

• 1. B+树的概念
• 2. B+树的查找
• 3. B-树 VS B+树
• 4. B+ 树的插入分析

  1. B+树的概念

  B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了一些改进优化。

  一棵m阶的B+树需满足下列条件：

  

  1. 每个分支结点最多有m棵子树(孩子结点)。
  2. 非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。

     （前面这两条其实还跟B树是一样的）

  3. 结点的子树个数与关键字个数相等。
  4. 结点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
  5. 所有叶子节点增加一个链接指针链接在一起
  6. 所有关键字及其映射数据都在叶子节点出现

  大家可以对照着图理解一下这几条性质。

  B+树的特性：

  1. 所有关键字都出现在叶子节点的链表中，且链表中的元素都是有序的。

  2. 查找不可能在分支节点中命中。

  3. 分支节点相当于是叶子节点的索引（仅含有其子树根结点中最大/最小关键码，我们这里图中是最小的），叶子节点才是存储数据的数据层（与B树不同）。

  2. B+树的查找

  B+树的查找上面有提到——查找不可能在分支节点中命中，如果能找到，应该在叶子节点的链表中：

  

  还是这棵B+树为例，比如我们要查找33

  从根结点开始33比5大，往后走，比28也大，再往后走，但是比65小。

  所以如果33存在的话，应该在28的子树中。

  所以进入28的子树中，然后比较比28大，比35小，所以再往这一层的28的子树p1中找，这就进入到叶子结点的链表中，往后遍历就找到了33。（如果查找的是28也要进入到叶子结点的链表中查找，即使分支结点中存在）

  那如果查找34（找不到），也是一样的，最终走到叶子结点的链表中，但是没有这个元素，所以就找不到。

  所以B+树的查找无论成功与否，都要走到最下面一层的叶子结点，而B-树的话，查找可能停止在任意一层。

  那除了上面的查找方法，其实B+树还有另外一种查找方法：

  上面提到对于B+树来说，所有叶子节点增加一个链接指针链接在一起

  

  而每个叶子结点的链表里面元素都是有序的。

  所以我们也可以通过这个链接指针去进行顺序查找，从前往后遍历每一个叶子结点的链表。

  3. B-树 VS B+树

  

  2.

  

  

  B+树分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层（与B树不同）。

  总结：

  

  4. B+ 树的插入分析

  这里简单画一个3阶B+树插入分裂的过程图，大家可以简单看看了解一下：

  

   
   中国建筑劳务承包网  代刷网站推广链接0元价格  建一个网站多少钱  东莞网站设计技术  网站制作报价的步骤  如何做个网站