B-树模拟实现详解

B-树

定义

B-树是一种平衡的 M（M≥2）路查找树，B-树也可以是空树。每个节点可以拥有多个子节点，从而有效减少树的高度，提高查找效率。

特性

根节点至少有两个孩子；

每个非根节点至少有 M/2(上取整) 个关键字，至多有 M-1 个关键字，并且以升序排列；

每个非根节点至少有 M/2(上取整) 个孩子，至多有 M 个孩子；

key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i]、key[i+1] 之间；

B-树通过节点的分裂和合并操作来保持树的平衡，所有叶子节点都位于同一层。

B-树的插入分析

以 M=3 为例，每个节点中存储两个数据，两个数据可以将区间分割为三部分，即最多有两个关键字，三个孩子。

但是为了方便，对于每个节点，当插入第三个关键字时不分裂，在插入第三个关键字之后再分裂，可以想象成每个节点最多有三个关键字，最多有四个孩子。即：

文章配图

下面以插入序列【53,139,75,49,145,36,101】为例构建 B 树：

【1】插入 53

文章配图

【2】插入 139

文章配图

【3】插入 75

文章配图

【4】引发分裂

文章配图

【5】插入 49 和 145

文章配图

【6】插入 36

文章配图

public class MyBtree { static class BTRNode { public int[] keys; // 关键字 public BTRNode[] subs; // 孩子 public BTRNode parent; // 存储当前孩子节点的父亲节点 public int usedSize; // 记录当前节点中关键字的数量 public BTRNode () { // 说明一下：这里多给一个是为了好进行分裂 this.keys = new int[M]; this.subs = new BTRNode[M+1]; } } public static final int M = 3; public BTRNode root; // 当前 B 树的根节点 public boolean insert(int key) { // 1、如果 B 树为空的时候 if(root == null) { root = new BTRNode(); root.keys[0] = key; root.usedSize++; return true; } // 2、当 B 树不为空的时候，我们需要查看当前 B 树当中是否存在我的 Key Pair<BTRNode,Integer> pair = find(key); // 判断这里获取到的 val 值是不是 -1 来确定当前是否存在该 key if(pair.getVal() != -1) { return false; } // 3、说明不存在这个 key 我们要进行插入 BTRNode parent = pair.getKey(); int index = parent.usedSize-1; for (; index >= 0;index--) { if(parent.keys[index] >= key) { parent.keys[index+1] = parent.keys[index]; }else { break; } } parent.keys[index+1] = key; parent.usedSize++; // 为什么不处理孩子呢因为你每次插入都是再叶子节点，所以叶子节点都是 null if(parent.usedSize < M) { // 没有满 return true; }else { // 满了->分裂 split(parent); return true; } } private void split(BTRNode cur) { BTRNode newNode = new BTRNode(); // 1. 先存储当前需要分裂节点的父节点 BTRNode parent = cur.parent; // 2. 开始挪数据 int mid = cur.usedSize >> 1; int i = mid+1; int j = 0; for( ; i < cur.usedSize;i++) { newNode.keys[j] = cur.keys[i]; newNode.subs[j] = cur.subs[i]; // 处理刚刚拷贝过来的孩子节点的父亲节点为新分裂的节点 if(newNode.subs[j]!=null) { newNode.subs[j].parent = newNode; } j++; } // 多拷贝一次孩子 newNode.subs[j] = cur.subs[i]; if(newNode.subs[j]!=null) { newNode.subs[j].parent = newNode; } // 更新当前新节点的有效数据 newNode.usedSize = j; // 这里的 -1 指的是将来要提到父亲节点的 key cur.usedSize = cur.usedSize - j - 1; // 特殊：处理根节点的情况 if(cur == root) { root = new BTRNode(); root.keys[0] = cur.keys[mid]; root.subs[0] = cur; root.subs[1] = newNode; root.usedSize = 1; cur.parent = root; newNode.parent = root; return; } // 更新当前新的节点的父亲节点 newNode.parent = parent; // 开始移动父亲节点 int endT = parent.usedSize-1; int midVal = cur.keys[mid]; for (; endT >= 0 ; endT--) { if(parent.keys[endT] >= midVal) { parent.keys[endT+1] = parent.keys[endT]; parent.subs[endT+2] = parent.subs[endT+1]; }else { break; } } parent.keys[endT+1] = midVal; // 将当前父节点的孩子节点新增为 newNode parent.subs[endT+2] = newNode; parent.usedSize++; if(parent.usedSize >= M) { split(parent); } } private Pair<BTRNode,Integer> find(int key) { BTRNode cur = root; BTRNode parent = null; while (cur != null) { int i = 0; while (i < cur.usedSize) { if(cur.keys[i] == key) { // 返回一个当前找到的节点和当前这个数据在节点当中的下标 return new Pair<>(cur,i); }else if(cur.keys[i] < key) { i++; }else { break; } } parent = cur; cur = cur.subs[i]; } return new Pair<>(parent,-1); } private void inorder(BTRNode root){ if(root == null) return; for(int i = 0; i < root.usedSize; ++i){ inorder(root.subs[i]); System.out.println(root.keys[i]); } inorder(root.subs[root.usedSize]); } }