今天我们分析B+树原理及Java代码实现，以前我写过一篇关于mysql 存储引擎B+Tree、 B-Tree和hash三种原理及区别，可以先参考
我们都知道B+树，是B树的一个变种，需要先明确一下B树的定义：
一、B/B+树的基本定义：
1、B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
下图是一个M=4 阶的B树:
可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。
B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。下面是往B树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
的演示动画：
2、B+树既然是对B树的一种变种树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
如下图，是一个M=4的B+树:
下图是B+树的插入动画：动画参考
3、B和B+树的区别在于，B+树的非叶子结点只包含导航索引信息，不包含实际的值（这样可以放更多的key索引），所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
4、B+ 树的优点在于：
- 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
- B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
二、代码实现：我们先贴出代码，在逐个方法分析
1、核心代码：
-
/**
-
* @author wanghuainan
-
* @date 2021/4/14 19:05
-
*/
-
public
class CatalogBTree<Key extends Comparable<Key>, Value> {
-
-
//参数M 定义每个节点的链接数
-
private
static
final
int M =
4;
-
-
private Node root;
-
-
//树的高度 最底层为0 表示外部节点 根具有最大高度，此高度是根之后的高度
-
private
int height;
-
-
//键值对总数
-
private
int n;
-
-
//节点数据结构定义
-
private
static
final
class Node{
-
//值的数量
-
private
int m;
-
private Entry[] children =
new Entry[M];
-
private Node(int k){
-
m = k;
-
}
-
}
-
-
//节点内部每个数据项定义
-
private
static
class Entry{
-
private Comparable key;
-
private
final Object val;
-
//下一个节点
-
private Node next;
-
public Entry(Comparable key, Object val, Node next){
-
this.key = key;
-
this.val = val;
-
this.next = next;
-
}
-
@Override
-
public String toString() {
-
StringBuilder builder =
new StringBuilder();
-
builder.append(
"Entry [key=");
-
builder.append(key);
-
builder.append(
"]");
-
return builder.toString();
-
}
-
-
}
-
-
public CatalogBTree(){
-
root =
new Node(
0);
-
}
-
-
public int size(){
-
return n;
-
}
-
-
public boolean isEmpty(){
-
return size() ==
0;
-
}
-
-
public int height(){
-
return height;
-
}
-
-
/**
-
* 查询接口
-
* @param key
-
* @return
-
*/
-
public Value get(Key key){
-
return search(root, key, height);
-
}
-
-
private Value search(Node x, Key key, int ht) {
-
Entry[] children = x.children;
//首次进入，相当于根节点
-
//外部节点 这里使用顺序查找
-
//如果M很大 可以改成二分查找
-
if(ht ==
0){
//到了有数据的子节点（也可能是根节点，如果键值对小于M），此次查询数据。
-
for(
int j=
0; j<x.m; j++){
-
if(equal(key, x.children[j].key))
//遍历查询
-
return (Value)children[j].val;
-
}
-
}
-
//内部节点 寻找下一个节点
-
else{
-
for(
int j=
0; j<x.m; j++){
-
//最后一个节点 或者 插入值小于某个孩子节点值
-
if(j+
1==x.m || less(key, x.children[j+
1].key))
//定位数据在哪个节点下，然后继续递归查询
-
return search(x.children[j].next, key, ht-
1);
//去下一层继续查询
-
}
-
}
-
return
null;
-
}
-
-
/**
-
* 新增数据接口
-
* @param key
-
* @param val
-
*/
-
public void put(Key key, Value val){
-
//插入后的节点，如果节点分裂，则返回分裂后产生的新节点
-
Node u = insert(root, key, val, height);
-
n++;
//键值对总数加一
-
if(u ==
null)
return;
//根节点没有分裂 直接返回
-
//分裂根节点,已满节点进行分裂，将已满节点后M/2节点生成一个新节点，并将新节点的第一个元素指向父节点，此处是M>>1 = 2（因为M=4）
-
Node t =
new Node(M>>
1);
-
//旧根节点第一个孩子和新分裂节点第一个孩子 共同 组成新节点作为根
-
t.children[
0] =
new Entry(root.children[
0].key,
null, root);
-
t.children[
1] =
new Entry(u.children[
0].key,
null, u);
-
root = t;
//新的根节点
-
height++;
//节点高度加1
-
}
-
-
private Node insert(Node h, Key key, Value val, int ht) {
-
int j;
-
//新建待插入数据数据项
-
Entry t =
new Entry(key, val,
null);
-
if(ht ==
0){
//高度为零时，直接遍历
-
for(j=
0; j<h.m; j++){
// 外部节点 找到带插入的节点位置j
-
if(less(key, h.children[j].key))
-
break;
-
}
-
}
else{
-
//内部节点 找到合适的分支节点
-
for(j=
0; j<h.m; j++){
-
if(j+
1==h.m || less(key, h.children[j+
1].key)){
-
Node u = insert(h.children[j++].next, key, val, ht-
1);
-
if(u ==
null)
return
null;
-
t.key = u.children[
0].key;
-
t.next = u;
-
break;
-
}
-
}
-
}
-
//j为带插入位置，将顺序数组j位置以后后移一位(从后往前处理) 将t插入
-
for(
int i=h.m; i>j; i--){
-
h.children[i] = h.children[i-
1];
-
}
-
System.out.println(j + t.toString());
-
h.children[j] = t;
//此处插入成功
-
h.m++;
//值的数量加一
-
if(h.m < M)
return
null;
-
//如果节点已满 则执行分类操作（从根节点开始）
-
else
return split(h);
-
}
-
-
private Node split(Node h) {
-
//将已满节点h的后，一般M/2节点后的节点分裂到新节点并返回
-
Node t =
new Node(M/
2);
-
h.m = M /
2;
-
for(
int j=
0; j<M/
2; j++){
-
t.children[j] = h.children[M/
2+j];
//把h节点中M/2节点后的节点分裂到新节点
-
h.children[M/
2+j] =
null;
//把h节点中M/2节点后的节点设置为空，以尽快GC
-
}
-
return t;
//返回新节点
-
}
-
-
/**
-
* 删除数据
-
* @param key
-
*/
-
public void remove(Key key){
-
remove(root, key, height);
-
-
}
-
-
private void remove(Node x, Key key, int ht){
-
Entry[] children = x.children;
//首次进入，相当于根节点
-
//外部节点 这里使用顺序查找
-
//如果M很大 可以改成二分查找
-
if(ht ==
0){
//到了有数据的子节点（也可能是根节点，如果键值对小于M），此次查询数据。
-
for(
int j=
0; j<x.m; j++){
-
if(equal(key, x.children[j].key)){
//遍历查询
-
children[j] =
null;
//删除此节点数据
-
x.m--;
//值的数量减一
-
}
-
}
-
}
-
//内部节点 寻找下一个节点
-
else{
-
for(
int j=
0; j<x.m; j++){
-
//最后一个节点 或者 插入值小于某个孩子节点值
-
if(j+
1==x.m || less(key, x.children[j+
1].key))
//定位数据在哪个节点下，然后继续递归查询
-
remove(x.children[j].next, key, ht-
1);
//去下一层继续查询
-
}
-
}
-
}
-
-
private boolean equal(Comparable k1, Comparable k2){
-
return k1.compareTo(k2)==
0;
-
}
-
-
private boolean less(Comparable k1, Comparable k2){
-
return k1.compareTo(k2)<
0;
-
}
-
-
public String toString() {
-
return toString(root, height,
"") +
"\n";
-
}
-
-
private String toString(Node h, int ht, String indent) {
-
StringBuilder s =
new StringBuilder();
-
Entry[] children = h.children;
//此数据相当于根节点
-
-
//外部节点
-
if (ht ==
0) {
-
for (
int j =
0; j < h.m; j++) {
-
s.append(indent + children[j].key +
" " + children[j].val +
"\n");
-
}
-
}
-
else {
-
for (
int j =
0; j < h.m; j++) {
-
s.append(indent +
"(" + children[j].key +
")\n");
-
s.append(toString(children[j].next, ht-
1, indent +
" "));
-
}
-
}
-
return s.toString();
-
}
-
-
}
2、分析测试添加数据put方法：
insert等方法可以去代码里查看，下面进行main方法测试打印：
-
public static void main(String[] args) {
-
-
/**
-
* 添加的顺序不同，最后树的结构也不同
-
*/
-
CatalogBTree<Integer,String> bt =
new CatalogBTree<>();
-
bt.put(
5,
"a");
-
bt.put(
8,
"b");
-
// bt.put(9,"c");
-
bt.put(
10,
"d");
-
bt.put(
15,
"e");
-
// bt.put(18,"f");
-
bt.put(
20,
"g");
-
bt.put(
26,
"h");
-
// bt.put(27,"i");
-
-
bt.put(
28,
"i");
-
bt.put(
30,
"j");
-
// bt.put(33,"k");
-
bt.put(
35,
"l");
-
bt.put(
38,
"m");
-
// bt.put(50,"n");
-
bt.put(
56,
"o");
-
bt.put(
60,
"p");
-
// bt.put(63,"q");
-
-
bt.put(
65,
"r");
-
bt.put(
73,
"s");
-
// bt.put(79,"t");
-
bt.put(
80,
"u");
-
bt.put(
85,
"v");
-
// bt.put(88,"w");
-
bt.put(
90,
"x");
-
bt.put(
96,
"y");
-
bt.put(
99,
"z");
-
-
-
/**
-
* 插入第三个元素
-
*/
-
bt.put(
9,
"c");
-
bt.put(
18,
"f");
-
bt.put(
27,
"i");
-
bt.put(
33,
"k");
-
bt.put(
50,
"n");
-
bt.put(
63,
"q");
-
bt.put(
79,
"t");
-
bt.put(
88,
"w");
-
-
System.
out.println(
"高度："+bt.height());
-
System.
out.println(
"查询："+bt.
get(
9));
-
System.
out.println( bt.toString());
-
}
用此种顺序添加，最后的结构图是这样的：
控制台打印也可以验证：（自己可以测试验证）
一张没有截完，在来一张
注意：添加节点时经常会出现分裂节点，这块一定要详细琢磨。 比如添加一个34 节点：
添加的后面过程中会分裂出一个新的节点；如下图：
3、分析测试查询数据get方法：比如get(99),会一直向下循环，循环三次就找到；代码如下图：
4、分析测试删除数据remove方法：此方法和get方法类似，遍历找到后设置为空就行，然后数值减一，如下图：
删除节点时可能出现合并节点，
比如现在删除一个 80 节点：删除后此处还有一个分支，然后就会合并到左边，如图：
到此，B+树的原理和实现分析告一段落。
另外，B/B+树经常用做数据库的索引，这方面推荐您直接看张洋的MySQL索引背后的数据结构及算法原理 这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。
总结
在前面两篇文章介绍了平衡查找树中的2-3树，红黑树之后，本文介绍了文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：
- Windows：HPFS文件系统
- Mac：HFS，HFS+文件系统
- Linux：ResiserFS，XFS，Ext3FS，JFS文件系统
- 数据库：ORACLE，MYSQL，SQLSERVER等中
希望本文对您了解B/B+ 树有所帮助。参考文章如下：
转载：https://blog.csdn.net/nandao158/article/details/115701213
查看评论