Java教程
B+树原理分析及Java代码实现
本文主要是介绍B+树原理分析及Java代码实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
今天我们分析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+ 树有所帮助。参考文章如下：
参考
参阅
参考文章
这篇关于B+树原理分析及Java代码实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
手写消息中间件：从零开始的指南11-26
-
Java语音识别项目资料：新手入门教程11-26
-
JAVA语音识别项目资料：新手入门教程11-26
-
Java语音识别项目资料：入门与实践指南11-26
-
Java云原生资料入门教程11-26
-
Java云原生资料入门教程11-26
-
Java云原生资料：新手入门教程11-26
-
Java创意资料：新手入门的创意学习指南11-25
-
JAVA对接阿里云智能语音服务资料详解：新手入门指南11-25
-
Java对接阿里云智能语音服务资料详解11-25
-
Java对接阿里云智能语音服务资料详解11-25
-
JAVA副业资料：新手入门及初级提升指南11-25
-
Java副业资料：入门到实践的全面指南11-25
-
Springboot应用的多环境打包项目实战11-25
-
SpringBoot应用的生产发布项目实战入门教程11-25
栏目导航
