本文暫時(shí)實(shí)現(xiàn)了B+樹(shù)插入锦积，查找和范圍查找功能，由于需求原因歉嗓，暫未實(shí)現(xiàn)刪除功能丰介。
本文B+樹(shù)Key為int類型，Value支持泛型遥椿。
Github開(kāi)源地址：https://github.com/1161140118/HIT-DataBase-Lab4/tree/master/src
感激您的star
數(shù)據(jù)結(jié)構(gòu)：
主類BPlusTree基矮，維護(hù)root結(jié)點(diǎn)。
非葉結(jié)點(diǎn)Node冠场，維護(hù)Key和子節(jié)點(diǎn)索引家浇。
葉結(jié)點(diǎn)Leaf，維護(hù)Key和Value索引碴裙。
主體思路：
主類BPlusTree維護(hù)root結(jié)點(diǎn)钢悲。
葉結(jié)點(diǎn)記錄父節(jié)點(diǎn)点额，非根中間結(jié)點(diǎn)記錄父節(jié)點(diǎn)。
初始狀態(tài)下莺琳，root結(jié)點(diǎn)為Node还棱，僅記錄1個(gè)索引唯一葉子。
插入開(kāi)始惭等，由root->leaf珍手，插入到leaf；
隨著插入進(jìn)行辞做，leaf發(fā)生分裂琳要，中間結(jié)點(diǎn)Key拷貝上溢到父節(jié)點(diǎn)Node類型結(jié)點(diǎn)。
倒數(shù)第二層的Node結(jié)點(diǎn)的分裂由Leaf分裂上溢引發(fā)秤茅，
Node結(jié)點(diǎn)的分裂分為兩種情況處理：
1. Node結(jié)點(diǎn)為根節(jié)點(diǎn)
下推：
當(dāng)前根節(jié)點(diǎn)分裂為兩個(gè)新子節(jié)點(diǎn)left和right稚补，分裂依據(jù)的Key稱為splitKey。
初始化當(dāng)前結(jié)點(diǎn)框喳，即重置當(dāng)前結(jié)點(diǎn)的Key List只包含splitKey课幕，而子節(jié)點(diǎn)引用只包含left和right。
即五垮，當(dāng)前節(jié)點(diǎn)仍未根節(jié)點(diǎn)乍惊，但Key和子節(jié)點(diǎn)引用都發(fā)生了改變。
2. Node結(jié)點(diǎn)為非根結(jié)點(diǎn)
上溢：
當(dāng)前節(jié)點(diǎn)分裂出一個(gè)新節(jié)點(diǎn)拼余，在父節(jié)點(diǎn)中插入splitKey和新節(jié)點(diǎn)的索引污桦。
主類BPlusTree數(shù)據(jù)結(jié)構(gòu)：
public class BPlusTree<V> {
public static int rank;
private Node<V> root;
public BPlusTree(int rank) {
BPlusTree.rank = rank;
// 根節(jié)點(diǎn)始終維護(hù)同一個(gè)Node
this.root = new Node<V>(null, false);
}
public void insertData(int key,V ref) {
root.insertData(key, ref);
}
/**
* 遞歸調(diào)用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);
}
插入部分算法
非葉結(jié)點(diǎn)Node：上溢匙监，或下推
/**
* 子節(jié)點(diǎn)分裂時(shí)凡橱，由子節(jié)點(diǎn)調(diào)用
* @param key 待插入關(guān)鍵字
*/
protected void insertNode(int key, Node<V> node) {
System.out.println("非葉節(jié)點(diǎn)插入 " + 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);
/**
* 判定分裂
* 非根節(jié)點(diǎn)：上溢分裂
* 根節(jié)點(diǎn)：下推分裂，當(dāng)前節(jié)點(diǎn)分裂為兩個(gè)新節(jié)點(diǎn)亭姥，當(dāng)前節(jié)點(diǎn)重置稼钩，新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)子節(jié)點(diǎn)
*/
if (keyList.size() >= BPlusTree.rank) {
System.out.println("非葉節(jié)點(diǎn)分裂." + key);
int split = BPlusTree.rank / 2;
Integer splitKey = keyList.get(split);
// 新節(jié)點(diǎn)：左右子樹(shù)
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("非葉節(jié)點(diǎn)上溢 "+splitKey);
} else {
// 根節(jié)點(diǎn)下推
// 更新當(dāng)前結(jié)點(diǎn)，分裂后下推
this.keyList.add(splitKey);
this.childNodes.add(leftChild);
this.childNodes.add(rightChild);
System.out.println("根節(jié)點(diǎn)下推"+splitKey);
}
}
}
葉結(jié)點(diǎn)Leaf：上溢
/**
* 在葉結(jié)點(diǎn)插入索引达罗，
* 可能觸發(fā)分裂
* @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("葉結(jié)點(diǎn)插入"+key);
/**
* 判定分裂
* 例：4階樹(shù)坝撑，達(dá)到4個(gè)數(shù)據(jù)結(jié)點(diǎn)，分裂粮揉，上溢第三個(gè)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++) {
// 執(zhí)行 size-split 此
keyList.remove(split);
refList.remove(split);
}
Leaf<V> newLeaf = new Leaf<V>(parent, newKeyList, newRefList);
this.next = newLeaf;
System.out.println("葉結(jié)點(diǎn)分裂."+key);
parent.insertNode(newKeyList.get(0), newLeaf);
}
System.out.println(key+" 插入最終結(jié)果 "+keyList);
// 檢查不變量
if (keyList.size() != refList.size()) {
System.err.println("Error : The length of keylist not equals to reflist!");
}
}
