本文暂时实现了B+树插入，查找和范围查找功能，由于需求原因，暂未实现删除功能。
本文B+树Key为int类型，Value支持泛型。
Github开源地址：https://github.com/1161140118/HIT-DataBase-Lab4/tree/master/src
感激您的star
数据结构：
主类BPlusTree，维护root结点。
非叶结点Node，维护Key和子节点索引。
叶结点Leaf，维护Key和Value索引。
主体思路：
主类BPlusTree维护root结点。
叶结点记录父节点，非根中间结点记录父节点。
初始状态下，root结点为Node，仅记录1个索引唯一叶子。
插入开始，由root->leaf，插入到leaf；
随着插入进行，leaf发生分裂，中间结点Key拷贝上溢到父节点Node类型结点。
倒数第二层的Node结点的分裂由Leaf分裂上溢引发，
Node结点的分裂分为两种情况处理：
1. Node结点为根节点
下推：
当前根节点分裂为两个新子节点left和right，分裂依据的Key称为splitKey。
初始化当前结点，即重置当前结点的Key List只包含splitKey，而子节点引用只包含left和right。
即，当前节点仍未根节点，但Key和子节点引用都发生了改变。
2. Node结点为非根结点
上溢：
当前节点分裂出一个新节点，在父节点中插入splitKey和新节点的索引。
主类BPlusTree数据结构：
public class BPlusTree<V> {
public static int rank;
private Node<V> root;
public BPlusTree(int rank) {
BPlusTree.rank = rank;
// 根节点始终维护同一个Node
this.root = new Node<V>(null, false);
}
public void insertData(int key,V ref) {
root.insertData(key, ref);
}
/**
* 递归调用Node.search方法，查询索引
* @param key 索引键
* @return
*/
public V search(int key) {
return root.search(key);
}
/**
* range search from start to end
* @param start start key, include
* @param end end key, include
* @return value list
*/
public List<V> rangeSearch(int start,int end){
return root.rangeSearch(start, end);
}
插入部分算法
非叶结点Node：上溢，或下推
/**
* 子节点分裂时，由子节点调用
* @param key 待插入关键字
*/
protected void insertNode(int key, Node<V> node) {
System.out.println("非叶节点插入 " + key);
int i = 0;
for (i = 0; i < keyList.size(); i++) {
if (key < keyList.get(i)) {
break;
}
}
keyList.add(i, key);
childNodes.add(i + 1, node);
/**
* 判定分裂
* 非根节点：上溢分裂
* 根节点：下推分裂，当前节点分裂为两个新节点，当前节点重置，新节点作为当前节点子节点
*/
if (keyList.size() >= BPlusTree.rank) {
System.out.println("非叶节点分裂." + key);
int split = BPlusTree.rank / 2;
Integer splitKey = keyList.get(split);
// 新节点：左右子树
List<Integer> leftKeyList = new LinkedList<>();
List<Node<V>> leftChilds = new LinkedList<>();
List<Integer> rightKeyList = new LinkedList<>();
List<Node<V>> rightChilds = new LinkedList<>();
// copy
for (int j = 0; j < split; j++) {
leftKeyList.add(keyList.get(j));
leftChilds.add(childNodes.get(j));
}
leftChilds.add(childNodes.get(split));
for (int j = split + 1; j < keyList.size(); j++) {
rightKeyList.add(keyList.get(j));
rightChilds.add(childNodes.get(j));
}
rightChilds.add(childNodes.get(keyList.size()));
this.keyList.clear();
this.childNodes.clear();
Node<V> leftChild = new Node<V>(this, leftKeyList, leftChilds);
Node<V> rightChild = new Node<V>(this, rightKeyList, rightChilds);
if (parent != null) {
// 上溢
this.keyList = leftKeyList;
this.childNodes = leftChilds;
parent.insertNode(splitKey, rightChild);
System.out.println("非叶节点上溢 "+splitKey);
} else {
// 根节点下推
// 更新当前结点，分裂后下推
this.keyList.add(splitKey);
this.childNodes.add(leftChild);
this.childNodes.add(rightChild);
System.out.println("根节点下推"+splitKey);
}
}
}
叶结点Leaf：上溢
/**
* 在叶结点插入索引，
* 可能触发分裂
* @return
*/
@Override
protected void insertData(int key, V ref) {
int i = 0;
for (i = 0; i < refList.size(); i++) {
if (key < keyList.get(i)) {
break;
}
}
keyList.add(i, key);
refList.add(i, ref);
System.out.println("叶结点插入"+key);
/**
* 判定分裂
* 例：4阶树，达到4个数据结点，分裂，上溢第三个key（index=2）
*/
if (refList.size() >= BPlusTree.rank) {
int split = BPlusTree.rank / 2;
List<Integer> newKeyList = new LinkedList<>();
List<V> newRefList = new LinkedList<>();
// copy
for (int j = split; j < keyList.size(); j++) {
newKeyList.add(keyList.get(j));
newRefList.add(refList.get(j));
}
// remove
int len = keyList.size();
for (int j = split; j < len; j++) {
// 执行 size-split 此
keyList.remove(split);
refList.remove(split);
}
Leaf<V> newLeaf = new Leaf<V>(parent, newKeyList, newRefList);
this.next = newLeaf;
System.out.println("叶结点分裂."+key);
parent.insertNode(newKeyList.get(0), newLeaf);
}
System.out.println(key+" 插入最终结果 "+keyList);
// 检查不变量
if (keyList.size() != refList.size()) {
System.err.println("Error : The length of keylist not equals to reflist!");
}
}
