对比B树

B+树对比B树主要有两点区别，分别是

  • 内部节点(非叶子节点)更新为索引节点，索引当时不放数据，将数据放置到叶子节点
  • 叶子节点直接指向下一个叶子节点，如果需要进行in查询或者连续遍历，相比B树有更大的优点

性质

  • B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
  • 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

演示地址

图

image.png
结构
相比B树增加了一个next节点，叶子节点指向下一个叶子节点

  1. private final class Node {
  2.     public int numberOfNodes = 0;
  3.     /**
  4.      * the array that holds the keys value.
  5.      */
  6.     public int key[];
  8.     /**
  9.      * 父亲节点
  10.      */
  11.     public Node parent;
  12.     /**
  13.      * the array that holds the references of the keys in the node.
  14.      */
  15.     public Node children[];
  16.     //next指针
  17.     public Node next;
  18. }

全部代码

点我查看B+树的基本实现全部代码

插入

B+树的数据插入一定发生在树的叶子节点，如果叶子节点不满足性质，则递归的向上处理，分裂。

  • 找到待插入的叶子节点 (叶子节点元素的个数<=m-1)
  • 插入数据后，如果节点元素的个数<=m-1，直接返回，插入结束。否则进行第三步
  • 以节点中间key作为间限，分裂为2个子树，key的前半部分为左子树Left，key的后半部分为右子树Right，key元素成为父节点元素数据的一部分，孩子分别指向Left和Right。由于key元素上移，parent成为新插入节点，递归执行第二步。
    • 新分裂的左右节点的parent指向新产生的parent节点
    • 新分裂的左右节点的children指向node的children节点

—— 这部分都满足B树的处理方式

  • 分裂后需要额外处理next指向，额外处理索引节点和叶子节点的信息

    核心的节点分裂，如果分裂后导致元素上移的parent节点满了，继续分裂parent节点 语雀展现长代码块有Bug，查看代码的可以到Github上查看

删除

[m/2]=m/2向上取整; [5/2] = 3; [3/1]=2;

  • 富裕节点: 节点的元素个数 >= [m/2]-1 ;

同B树删除方式，需额外处理next和节点信息
B 🌲【B Tree】

遍历

https://stackoverflow.com/questions/5890960/print-btree-by-level
同B树遍历方式

参考链接