一、介紹
- B+樹索引是B+樹在資料庫中的一種實作，是最常見也是資料庫中使用最為頻繁的一種索引。
- B+樹中的B代表平衡（balance）。（平衡多路查找樹）
- B+樹是從最早的平衡二叉樹演化而來的。
二、B-Tree
- B-Tree是為磁盤等外儲存設備設計的一種平衡查找樹。
- 每個節點最多有m個孩子。
- 除了根節點和葉子節點外，其它每個節點至少有Ceil(m/2)個孩子。
- 若根節點不是葉子節點，則至少有2個孩子
- 所有葉子節點都在同一層，且不包含其它關鍵字資訊
- 每個非終端節點包含n個關鍵字資訊（P0,P1,…Pn, k1,…kn）
- 關鍵字的個數n滿足：ceil(m/2)-1 <= n <= m-1
- ki(i=1,…n)為關鍵字，且關鍵字升序排序。
- Pi(i=1,…n)為指向子樹根節點的指針。P(i-1)指向的子樹的所有節點關鍵字均小于ki，但都大于k(i-1)
（個人了解：關鍵字上的資料存儲在本節點上，每個範圍内的資料存儲在下一個節點上，葉子節點隻存儲資料）
如果data資料較大時将會導緻每個節點（即一個頁）能存儲的key的數量很小，當存儲的資料量很大時同樣會導緻B-Tree的深度較大，進而影響查詢效率。
原文 https://blog.csdn.net/baidu_29961857/article/details/89879739
package com.numberone.tree;
import java.util.LinkedList;
/**
* Created on 2020/1/7.
*
* @author Gray
* @since 1.0
*/
public class BTree<K extends Comparable<K>,V> {
private final class Node{
int keynum;
Node parent;
LinkedList<Entry> entries;
LinkedList<Node> childs;
}
private final class Entry{
K k;
V v;
public Entry(){}
public Entry(K k, V v) {
this.k = k;
this.v = v;
}
@Override
public String toString() {
return "{"+ k +
"," + v +
'}';
}
}
private final class Result{
Node ptr;int i;boolean tag;
public Result(Node ptr, int i, boolean tag) {
this.ptr = ptr;
this.i = i;
this.tag = tag;
}
}
private int degree;
private Node root;
public BTree(int degree, Node root) {
this.degree = degree;
this.root = root;
}
private Result searchTree(Node T,K k){
Node p=T,q=null;
boolean found=false;
int i=0;
while(p!=null && !found){
i=search(p,k);
if(i>0 && eq(k,p.entries.get(i).k))found=true;
else{
q=p;
p=p.childs.get(i);
}
}
if(found)return new Result(p,i,true);
else return new Result(q,i,false);
}
//index
private int search(Node p,K k){
int j=0;
for(;j<p.keynum;j++){
if(lt(k,p.entries.get(j+1).k))break;
}
return j;
}
public void put(K k,V v){
Entry entry=new Entry(k,v);
Result result=searchTree(root,entry.k);
if(!result.tag) insertBTree(result.ptr,entry,result.i);
else{
result.ptr.entries.set(result.i,entry);
}
//result.ptr.entries.set(result.i,entry);
}
public void insertBTree(Node q,Entry entry,int i){
int s;Entry x=entry;Node ap=null,tmp=null;boolean finished=false;
while(q!=null && !finished){
insert(q,i,x,ap);
if(q.keynum<degree)finished=true;
else{
s=degree%2==0?degree/2:degree/2+1;
x=q.entries.get(s);
ap=new Node();
split(q,x,s,ap);
tmp=q;
q=q.parent;
if(q!=null){i=search(q,entry.k);}
}
}
if(!finished){
root=tmp;
newRoot(q,x,ap);
}
}
public void insert(Node q,int i,Entry entry,Node ap){
q.childs.add(i+1,ap);
q.entries.add(i+1,entry);
if(ap != null) ap.parent=q;
q.keynum++;
}
public void newRoot(Node q,Entry entry,Node ap){
q=new Node();
q.entries=new LinkedList<>();
q.childs=new LinkedList<>();
q.parent=null;
q.entries.add(null);
q.entries.add(entry);
q.keynum=1;
q.childs.add(root);
q.childs.add(ap);
for(int i=0;i<=q.keynum;i++){
if(q.childs.get(i)!=null){
q.childs.get(i).parent=q;
}
}
root=q;
}
public void split(Node q,Entry entry,int s,Node ap){
ap.childs=new LinkedList<>();
ap.entries=new LinkedList<>();
ap.entries.add(null);
ap.entries.addAll(q.entries.subList(s+1,degree+1));
ap.childs.add(q.childs.get(s));
ap.childs.addAll(q.childs.subList(s+1,degree+1));
ap.keynum=degree-s;
q.keynum=s-1;
for(int i=degree;i>q.keynum;i--){
q.entries.removeLast();
q.childs.removeLast();
}
for(int i=0;i<=ap.keynum;i++){
if(ap.childs.get(i)!=null){
ap.childs.get(i).parent=ap;
}
}
}
/*
delete---------------------------------
*/
public boolean deleteKey(K k){
Result result=searchTree(root,k);
if(result.tag) return deleteTree(result);
else return false;
}
public boolean deleteTree(Result result){
Node q=result.ptr;
Result minResult=null;
int i=0;
Node node=null;
if(q.childs.get(result.i)!=null){
minResult=searchMinKey(q);
}
if(minResult!=null){
node=minResult.ptr;
i=minResult.i;
}else{
node=result.ptr;
i=result.i;
}
//when the node and q refers to the same object exceptions accured
LinkedList<Entry> tmplist=new LinkedList<>();
tmplist.addAll(node.entries);
q.entries.remove(result.i);
q.entries.add(result.i,tmplist.get(i));
return delete(node ,i);
}
private boolean delete(Node q,int i){
int s,tag=0;
Node p=null,lc,rc;
s=degree%2==0?degree/2:(degree/2+1);
int order=-1;
p=q.parent;
if(p==null){
tag=1;
}else{
order=foundIndexOfParent(q,p);
if(q.keynum>=s){
tag=2;//delete the entry directyly
}else{
if(tag==0 && order<p.keynum && p.childs.get(order+1).keynum>=s){ tag=3; }
if(tag==0 && order>0 && p.childs.get(order-1).keynum>=s){ tag=4; }
if(tag==0 && order<p.keynum && p.childs.get(order+1).keynum==s-1){ tag=5; }
if(tag==0 && order>0 && p.childs.get(order-1).keynum==s-1){ tag=6; }
}
}
switch (tag){
case 0:return false;
case 1:
removeKeyAndChild(q,i);
if(q.keynum==1 && i==1) root=q.childs.get(0);
q.keynum--;
break;
case 2:
removeKeyAndChild(q,i);
q.keynum--;
break;
case 3:
rc=p.childs.get(order+1);
removeKeyAndChild(q,i);
q.entries.add(p.entries.get(order+1));
q.childs.add(rc.childs.get(0));
p.entries.remove(order+1);
p.entries.add(order+1,rc.entries.get(1));
rc.childs.remove(0);
rc.entries.remove(1);
rc.keynum--;
break;
case 4:
lc=p.childs.get(order-1);
removeKeyAndChild(q,i);
q.childs.add(0,lc.childs.get(lc.keynum));
q.entries.add(1,p.entries.get(order));
p.entries.remove(order);
p.entries.add(order,lc.entries.get(lc.keynum));
removeKeyAndChild(lc,lc.keynum);
lc.keynum--;
break;
case 5:
rc=p.childs.get(order+1);
removeKeyAndChild(q,i);
q.entries.add(p.entries.get(order+1));
q.keynum=q.keynum+rc.keynum;
removeKeyAndChild(p,order+1);
q.childs.addAll(rc.childs);
q.entries.addAll(rc.entries.subList(1,rc.entries.size()));
p.keynum--;
if(p.keynum<s-1){
p.keynum=p.keynum+1;
q=p;
delete(q,q.keynum);
}
break;
case 6:
lc = p.childs.get(order - 1);
lc.entries.add(p.entries.get(order));
lc.keynum++;
removeKeyAndChild(q, i);
q.keynum--;
removeKeyAndChild(p, order);
p.keynum--;
lc.childs.addAll(q.childs);
q.entries.removeFirst();
lc.entries.addAll(q.entries);
lc.keynum += q.keynum;
if(p.keynum < s - 1){
p.keynum++;
q = p;
delete(q,q.keynum);
}
break;
}
return true;
}
private void removeKeyAndChild(Node q,int i){
if(i>q.entries.size()-1) return;
q.childs.remove(i);
q.entries.remove(i);
}
public int foundIndexOfParent(Node q,Node p){
int count;
for(count=0;p.childs.get(count)!=q;count++);
return count;
}
public Result searchMinKey(Node p){
while(p!=null && p.childs.get(0)!=null)
p=p.childs.get(0);
return new Result(p,1,true);
}
//--------------------------------------------
private boolean lt(K k1, K k2){return k1.compareTo(k2)<0;}
private boolean eq(K k1,K k2){return k1.compareTo(k2)==0;}
private boolean gt(K k1,K k2){return k1.compareTo(k2)>0;}
public Node getRoot(){return root;}
public V get(K k){
Result result=searchTree(root,k);
return result.ptr.entries.get(result.i).v;
}
}
三、B+Tree
B+Tree是在B-Tree基礎上的一種優化，使其更适合實作外存儲索引結構，InnoDB存儲引擎就是用B+Tree實作其索引結構。
與B-Tree的差別
- 非葉子節點隻存儲鍵值資訊。
- 所有葉子節點之間都有一個鍊指針。
- 資料記錄都存放在葉子節點中。
package com.numberone.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Created on 2020/1/7.
*
* @author Gray
* @since 1.0
*/
public class BPlusTree<T>{
private static final String NODE = "NODE";
static final String INT = "INT";
private static final String PRENODE = "PRENODE";
private static final String NEXTNODE = "NEXTNODE";
//B+樹的階數
private int rank;
//根節點
private Node root;
//頭結點
private Node head;
BPlusTree(int rank) {
this.rank = rank;
}
public Node getRoot() {
return root;
}
public void put(int k, T v) {
KeyAndValue entry = new KeyAndValue(k,v);
List<KeyAndValue> keyAndValues1 = new ArrayList<>();
//插入第一個節點
if (head == null) {
keyAndValues1.add(entry);
head = new Node(null, keyAndValues1, null, null, null);
root = new Node(null, keyAndValues1, null, null, null);
} else {
Node node = head;
//周遊連結清單，找到插入鍵值對對應的節點
while (node != null) {
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
int exitFlag = 0;
//如果插入的鍵的值和目前節點鍵值對集合中的某個鍵的值相等，則直接替換value
for (KeyAndValue KV : keyAndValues) {
if (KV.getKey() == entry.getKey()) {
KV.setValue(entry.getValue());
exitFlag = 1;
break;
}
}
//如果插入的鍵已經有了，則退出循環
if (exitFlag == 1) {
break;
}
//如果目前節點是最後一個節點或者要插入的鍵值對的鍵的值小于下一個節點的鍵的最小值，則直接插入目前節點
if (node.getNextNode() == null || node.getNextNode().getKeyAndValue().get(0).getKey() >= entry.getKey()) {
splidNode(node, entry);
break;
}
//移動指針
node = node.getNextNode();
}
}
}
//判斷是否需要拆分節點
private void splidNode(Node node, KeyAndValue addkeyAndValue) {
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
if (keyAndValues.size() == rank - 1) {
//先插入待添加的節點
keyAndValues.add(addkeyAndValue);
Collections.sort(keyAndValues);
//取出目前節點的鍵值對集合
//取出原來的key-value集合中間位置的下标
int mid = keyAndValues.size() / 2;
//取出原來的key-value集合中間位置的鍵
int midKey = keyAndValues.get(mid).getKey();
//構造一個新的鍵值對，不是葉子節點的節點不存儲value的資訊
KeyAndValue midKeyAndValue = new KeyAndValue(midKey, "");
//将中間位置左邊的鍵值對封裝成集合對象
List<KeyAndValue> leftKeyAndValues = new ArrayList<>();
for (int i = 0; i < mid; i++) {
leftKeyAndValues.add(keyAndValues.get(i));
}
//将中間位置右邊邊的鍵值對封裝成集合對象
List<KeyAndValue> rightKeyAndValues = new ArrayList<>();
//如果是葉子節點則在原節點中保留上移的key-value，否則原節點删除上移的key-value
int k;
if (node.isLeaf()) {
k = mid;
} else {
k = mid + 1;
}
for (int i = k; i < rank; i++) {
rightKeyAndValues.add(keyAndValues.get(i));
}
//對左右兩邊的元素重排序
Collections.sort(leftKeyAndValues);
Collections.sort(rightKeyAndValues);
//以mid為界限将目前節點分列成兩個節點，維護前指針和後指針
Node rightNode;
Node leftNode;
// if (node.isLeaf()) {
//如果是葉子節點維護前後指針
rightNode = new Node(null, rightKeyAndValues, node.getNextNode(), null, node.getParantNode());
leftNode = new Node(null, leftKeyAndValues, rightNode, node.getPreviousNode(), node.getParantNode());
rightNode.setPreviousNode(leftNode);
// } else {
// //如果不是葉子不維護前後指針
// rightNode = new Node(null, rightKeyAndValues, null, null, node.getParantNode());
// leftNode = new Node(null, leftKeyAndValues, null, null, node.getParantNode());
// }
//如果目前分裂的節點有孩子節點,設定分裂後節點和孩子節點的關系
if (node.getNodes() != null) {
//取得所有地孩子節點
List<Node> nodes = node.getNodes();
List<Node> leftNodes = new ArrayList<>();
List<Node> rightNodes = new ArrayList<>();
for (Node childNode : nodes) {
//取得目前孩子節點的最大鍵值
int max = childNode.getKeyAndValue().get(childNode.getKeyAndValue().size() - 1).getKey();
if (max < midKeyAndValue.getKey()) {
//小于mid處的鍵的數是左節點的子節點
leftNodes.add(childNode);
childNode.setParantNode(leftNode);
} else {
//大于mid處的鍵的數是右節點的子節點
rightNodes.add(childNode);
childNode.setParantNode(rightNode);
}
}
leftNode.setNodes(leftNodes);
rightNode.setNodes(rightNodes);
}
//目前節點的前節點
Node preNode = node.getPreviousNode();
//分裂節點後将分裂節點的前節點的後節點設定為左節點
if (preNode != null) {
preNode.setNextNode(leftNode);
}
//目前節點的後節點
Node nextNode = node.getNextNode();
//分裂節點後将分裂節點的後節點的前節點設定為右節點
if (nextNode != null) {
nextNode.setPreviousNode(rightNode);
}
//如果由頭結點分裂，則分裂後左邊的節點為頭節點
if (node == head) {
head = leftNode;
}
//父節點的子節點
List<Node> childNodes = new ArrayList<>();
childNodes.add(rightNode);
childNodes.add(leftNode);
//分裂
//目前節點無父節點
if (node.getParantNode() == null) {
//父節點的鍵值對
List<KeyAndValue> parentKeyAndValues = new ArrayList<>();
parentKeyAndValues.add(midKeyAndValue);
//構造父節點
Node parentNode = new Node(childNodes, parentKeyAndValues, null, null, null);
//将子節點與父節點關聯
rightNode.setParantNode(parentNode);
leftNode.setParantNode(parentNode);
//目前節點為根節點
root = parentNode;
} else {
Node parentNode = node.getParantNode();
//将原來的孩子節點（除了被拆分的節點）和新的孩子節點（左孩子和右孩子）合并之後與父節點關聯
childNodes.addAll(parentNode.getNodes());
//移除正在被拆分的節點
childNodes.remove(node);
//将子節點與父節點關聯
parentNode.setNodes(childNodes);
rightNode.setParantNode(parentNode);
leftNode.setParantNode(parentNode);
if (parentNode.getParantNode() == null) {
root = parentNode;
}
//目前節點有父節點,遞歸調用拆分的方法,将父節點拆分
splidNode(parentNode, midKeyAndValue);
}
} else {
keyAndValues.add(addkeyAndValue);
//排序
Collections.sort(keyAndValues);
}
}
//列印B+樹
void printBtree(Node root) {
if (root == this.root) {
//列印根節點内的元素
printNode(root);
System.out.println();
}
if (root == null) {
return;
}
//列印子節點的元素
if (root.getNodes() != null) {
//找到最左邊的節點
Node leftNode = null;
Node tmpNode = null;
List<Node> childNodes = root.getNodes();
for (Node node : childNodes) {
if (node.getPreviousNode() == null) {
leftNode = node;
tmpNode = node;
}
}
while (leftNode != null) {
//從最左邊的節點向右列印
printNode(leftNode);
System.out.print("|");
leftNode = leftNode.getNextNode();
}
System.out.println();
printBtree(tmpNode);
}
}
//列印一個節點内的元素
private void printNode(Node node) {
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
for (int i = 0; i < keyAndValues.size(); i++) {
if (i != (keyAndValues.size() - 1)) {
System.out.print(keyAndValues.get(i).getKey() + ",");
} else {
System.out.print(keyAndValues.get(i).getKey());
}
}
}
public T findValue(int key) {
return (T)search(key,this.root,INT);
}
public Object search(int key, Node node, String mode) {
//如果是葉子節點則直接取值
if (node.isLeaf()) {
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
for (KeyAndValue keyAndValue : keyAndValues) {
if (keyAndValue.getKey() == key) {
switch (mode) {
case NODE:
return node;
case INT:
return keyAndValue.getValue();
}
}
}
return null;
}
List<Node> nodes = node.getNodes();
//如果尋找的key小于節點的鍵的最小值
int minKey = node.getKeyAndValue().get(0).getKey();
if (key < minKey) {
for (Node n : nodes) {
List<KeyAndValue> keyAndValues = n.getKeyAndValue();
//找到子節點集合中最大鍵小于父節點最小鍵節點
if (keyAndValues.get(keyAndValues.size() - 1).getKey() < minKey) {
return search(key, n, mode);
}
}
}
//如果尋找的key大于節點的鍵的最大值
int maxKey = getMaxKeyInNode(node);
if (key >= maxKey) {
for (Node n : nodes) {
List<KeyAndValue> keyAndValues = n.getKeyAndValue();
//找到子節點集合中最小鍵大于等于父節點最小大鍵節點
if (keyAndValues.get(0).getKey() >= maxKey) {
return search(key, n, mode);
}
}
}
//如果尋找的key在最大值和最小值之間，首先定位到最窄的區間
int min = getLeftBoundOfKey(node, key);
int max = getRightBoundOfKey(node, key);
//去所有的子節點中找鍵的範圍在min和max之間的節點
for (Node n : nodes) {
List<KeyAndValue> kvs = n.getKeyAndValue();
//找到子節點集合中鍵的範圍在min和max之間的節點
if (kvs.get(0).getKey() >= min && kvs.get(kvs.size() - 1).getKey() < max) {
return search(key, n, mode);
}
}
return null;
}
public boolean delete(int key) {
System.out.println("delete:" + key);
System.out.println();
//首先找到要删除的key所在的節點
Node deleteNode = (Node) search(key, root, NODE);
//如果沒找到則删除失敗
if (deleteNode == null) {
return false;
}
if (deleteNode == root) {
delKeyAndValue(root.getKeyAndValue(), key);
return true;
}
if (deleteNode == head && isNeedMerge(head)) {
head = head.getNextNode();
}
return merge(deleteNode, key);
}
//平衡目前節點和前節點或者後節點的數量，使兩者的數量都滿足條件
private boolean balanceNode(Node node, Node bratherNode, String nodeType) {
if (bratherNode == null) {
return false;
}
List<KeyAndValue> delKeyAndValues = node.getKeyAndValue();
if (isMoreElement(bratherNode)) {
List<KeyAndValue> bratherKeyAndValues = bratherNode.getKeyAndValue();
int bratherSize = bratherKeyAndValues.size();
//兄弟節點删除挪走的鍵值對
KeyAndValue keyAndValue = null;
KeyAndValue keyAndValue1;
switch (nodeType) {
case PRENODE:
keyAndValue = bratherKeyAndValues.remove(bratherSize - 1);
keyAndValue1 = getKeyAndValueinMinAndMax(node.getParantNode(), keyAndValue.getKey(), getMinKeyInNode(node));
keyAndValue1.setKey(keyAndValue.getKey());
break;
case NEXTNODE:
keyAndValue = bratherKeyAndValues.remove(0);
keyAndValue1 = getKeyAndValueinMinAndMax(node.getParantNode(), getMaxKeyInNode(node), keyAndValue.getKey());
keyAndValue1.setKey(bratherKeyAndValues.get(0).getKey());
break;
}
//目前節點添加從前一個節點得來的鍵值對
delKeyAndValues.add(keyAndValue);
//對鍵值對重排序
Collections.sort(delKeyAndValues);
return true;
}
return false;
}
public boolean merge(Node node, int key) {
List<KeyAndValue> delKeyAndValues = node.getKeyAndValue();
//首先删除該key-vaule
delKeyAndValue(delKeyAndValues, key);
//如果要删除的節點的鍵值對的數目小于節點最大鍵值對數目*填充因子
if (isNeedMerge(node)) {
Boolean isBalance;
//如果左節點有富餘的鍵值對，則取一個到目前節點
Node preNode = getPreviousNode(node);
isBalance = balanceNode(node, preNode, PRENODE);
//如果此時已經平衡，則已經删除成功
if (isBalance) return true;
//如果右兄弟節點有富餘的鍵值對，則取一個到目前節點
Node nextNode = getNextNode(node);
isBalance = balanceNode(node, nextNode, NEXTNODE);
return isBalance || mergeNode(node, key);
} else {
return true;
}
}
//合并節點
//key 待删除的key
private boolean mergeNode(Node node, int key) {
if (node.isRoot()) {
return false;
}
Node preNode;
Node nextNode;
Node parentNode = node.getParantNode();
List<Node> childNodes = parentNode.getNodes();
List<Node> childNodes1 = node.getNodes();
List<KeyAndValue> parentKeyAndValue = parentNode.getKeyAndValue();
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
if (node.isLeaf()) {
if (parentKeyAndValue.size() == 1 && parentNode != root) {
return true;
}
preNode = getPreviousNode(node);
nextNode = getNextNode(node);
if (preNode != null) {
List<KeyAndValue> preKeyAndValues = preNode.getKeyAndValue();
keyAndValues.addAll(preKeyAndValues);
if (preNode.isHead()) {
head = node;
node.setPreviousNode(null);
} else {
preNode.getPreviousNode().setNextNode(node);
node.setPreviousNode(preNode.getPreviousNode());
}
//将合并後節點的後節點設定為目前節點的後節點
preNode.setNextNode(node.getNextNode());
KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, getMinKeyInNode(preNode), key);
delKeyAndValue(parentKeyAndValue, keyAndValue.getKey());
if (parentKeyAndValue.isEmpty()) {
root = node;
} else {
//删除目前節點
childNodes.remove(preNode);
}
Collections.sort(keyAndValues);
merge(parentNode, key);
return true;
}
if (nextNode != null) {
List<KeyAndValue> nextKeyAndValues = nextNode.getKeyAndValue();
keyAndValues.addAll(nextKeyAndValues);
if (nextNode.isTail()) {
node.setPreviousNode(null);
} else {
nextNode.getNextNode().setPreviousNode(node);
node.setNextNode(nextNode.getNextNode());
}
KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, key, getMinKeyInNode(nextNode));
delKeyAndValue(parentKeyAndValue, keyAndValue.getKey());
if (parentKeyAndValue.isEmpty()) {
root = node;
node.setParantNode(null);
} else {
//删除目前節點
childNodes.remove(nextNode);
}
Collections.sort(keyAndValues);
merge(parentNode, key);
return true;
}
//前節點和後節點都等于null那麼是root節點
return false;
} else {
preNode = getPreviousNode(node);
nextNode = getNextNode(node);
if (preNode != null) {
//将前一個節點和目前節點還有父節點中的相應Key-value合并
List<KeyAndValue> preKeyAndValues = preNode.getKeyAndValue();
preKeyAndValues.addAll(keyAndValues);
int min = getMaxKeyInNode(preNode);
int max = getMinKeyInNode(node);
//父節點中移除這個key-value
KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, min, max);
parentKeyAndValue.remove(keyAndValue);
if (parentKeyAndValue.isEmpty()) {
root = preNode;
node.setParantNode(null);
preNode.setParantNode(null);
} else {
childNodes.remove(node);
}
assert nextNode != null;
preNode.setNextNode(nextNode.getNextNode());
//前節點加上一個目前節點的所有子節點中最小key的key-value
KeyAndValue minKeyAndValue = getMinKeyAndValueInChildNode(node);
assert minKeyAndValue != null;
KeyAndValue keyAndValue1 = new KeyAndValue(minKeyAndValue.getKey(), minKeyAndValue.getValue());
preKeyAndValues.add(keyAndValue1);
List<Node> preChildNodes = preNode.getNodes();
preChildNodes.addAll(node.getNodes());
//将目前節點的孩子節點的父節點設為目前節點的後節點
for (Node node1 : childNodes1) {
node1.setParantNode(preNode);
}
Collections.sort(preKeyAndValues);
merge(parentNode, key);
return true;
}
if (nextNode != null) {
//将後一個節點和目前節點還有父節點中的相應Key-value合并
List<KeyAndValue> nextKeyAndValues = nextNode.getKeyAndValue();
nextKeyAndValues.addAll(keyAndValues);
int min = getMaxKeyInNode(node);
int max = getMinKeyInNode(nextNode);
//父節點中移除這個key-value
KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, min, max);
parentKeyAndValue.remove(keyAndValue);
childNodes.remove(node);
if (parentKeyAndValue.isEmpty()) {
root = nextNode;
nextNode.setParantNode(null);
} else {
childNodes.remove(node);
}
nextNode.setPreviousNode(node.getPreviousNode());
//後節點加上一個當後節點的所有子節點中最小key的key-value
KeyAndValue minKeyAndValue = getMinKeyAndValueInChildNode(nextNode);
assert minKeyAndValue != null;
KeyAndValue keyAndValue1 = new KeyAndValue(minKeyAndValue.getKey(), minKeyAndValue.getValue());
nextKeyAndValues.add(keyAndValue1);
List<Node> nextChildNodes = nextNode.getNodes();
nextChildNodes.addAll(node.getNodes());
//将目前節點的孩子節點的父節點設為目前節點的後節點
for (Node node1 : childNodes1) {
node1.setParantNode(nextNode);
}
Collections.sort(nextKeyAndValues);
merge(parentNode, key);
return true;
}
return false;
}
}
//得到目前節點的前節點
private Node getPreviousNode(Node node) {
if (node.isRoot()) {
return null;
}
Node parentNode = node.getParantNode();
//得到兄弟節點
List<Node> nodes = parentNode.getNodes();
List<KeyAndValue> keyAndValues = new ArrayList<>();
for (Node n : nodes) {
List<KeyAndValue> list = n.getKeyAndValue();
int maxKeyAndValue = list.get(list.size() - 1).getKey();
if (maxKeyAndValue < getMinKeyInNode(node)) {
keyAndValues.add(new KeyAndValue(maxKeyAndValue, n));
}
}
Collections.sort(keyAndValues);
if (keyAndValues.isEmpty()) {
return null;
}
return (Node) keyAndValues.get(keyAndValues.size() - 1).getValue();
}
//得到目前節點的後節點
private Node getNextNode(Node node) {
if (node.isRoot()) {
return null;
}
Node parentNode = node.getParantNode();
//得到兄弟節點
List<Node> nodes = parentNode.getNodes();
List<KeyAndValue> keyAndValues = new ArrayList<>();
for (Node n : nodes) {
List<KeyAndValue> list = n.getKeyAndValue();
int minKeyAndValue = list.get(0).getKey();
if (minKeyAndValue > getMaxKeyInNode(node)) {
keyAndValues.add(new KeyAndValue(minKeyAndValue, n));
}
}
Collections.sort(keyAndValues);
if (keyAndValues.isEmpty()) {
return null;
}
return (Node) keyAndValues.get(0).getValue();
}
private int getMinKeyInNode(Node node) {
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
return keyAndValues.get(0).getKey();
}
private int getMaxKeyInNode(Node node) {
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
return keyAndValues.get(keyAndValues.size() - 1).getKey();
}
private int getLeftBoundOfKey(Node node, int key) {
int left = 0;
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
for (int i = 0; i < keyAndValues.size(); i++) {
if (keyAndValues.get(i).getKey() <= key && keyAndValues.get(i + 1).getKey() > key) {
left = keyAndValues.get(i).getKey();
break;
}
}
return left;
}
private int getRightBoundOfKey(Node node, int key) {
int right = 0;
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
for (int i = 0; i < keyAndValues.size(); i++) {
if (keyAndValues.get(i).getKey() <= key && keyAndValues.get(i + 1).getKey() > key) {
right = keyAndValues.get(i + 1).getKey();
break;
}
}
return right;
}
private void delKeyAndValue(List<KeyAndValue> keyAndValues, int key) {
for (KeyAndValue keyAndValue : keyAndValues) {
if (keyAndValue.getKey() == key) {
keyAndValues.remove(keyAndValue);
break;
}
}
}
//找到node的鍵值對中在min和max中的鍵值對
private KeyAndValue getKeyAndValueinMinAndMax(Node node, int min, int max) {
if (node == null) {
return null;
}
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
KeyAndValue keyAndValue = null;
for (KeyAndValue k : keyAndValues) {
if (k.getKey() > min && k.getKey() <= max) {
keyAndValue = k;
break;
}
}
return keyAndValue;
}
private KeyAndValue getMinKeyAndValueInChildNode(Node node) {
if (node.getNodes() == null || node.getNodes().isEmpty()) {
return null;
}
List<KeyAndValue> sortKeyAndValues = new ArrayList<>();
List<Node> childNodes = node.getNodes();
for (Node childNode : childNodes) {
List<KeyAndValue> keyAndValues = childNode.getKeyAndValue();
KeyAndValue minKeyAndValue = keyAndValues.get(0);
sortKeyAndValues.add(minKeyAndValue);
}
Collections.sort(sortKeyAndValues);
return sortKeyAndValues.get(0);
}
private boolean isNeedMerge(Node node) {
if (node == null) {
return false;
}
List<KeyAndValue> keyAndValues = node.getKeyAndValue();
return keyAndValues.size() < rank / 2;
}
//判斷一個節點是否有富餘的鍵值對
private boolean isMoreElement(Node node) {
return node != null && (node.getKeyAndValue().size() > rank / 2);
}
private final class KeyAndValue implements Comparable<KeyAndValue> {
/*存儲索引關鍵字*/
public int key;
/*存儲資料*/
public Object value;
public KeyAndValue(){}
public KeyAndValue(int key, Object value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
@Override
public int compareTo(KeyAndValue o) {
return this.key - o.key;
}
}
private final class Node {
//節點的子節點
List<Node> nodes;
//節點的鍵值對
List<KeyAndValue> keyAndValue;
//節點的後節點
Node nextNode;
//節點的前節點
Node previousNode;
//節點的父節點
private Node parantNode;
public Node( List<Node> nodes, List<KeyAndValue> keyAndValue, Node nextNode,Node previousNode, Node parantNode) {
this.nodes = nodes;
this.keyAndValue = keyAndValue;
this.nextNode = nextNode;
this.parantNode = parantNode;
this.previousNode = previousNode;
}
boolean isLeaf() {
return nodes==null;
}
boolean isHead() {
return previousNode == null;
}
boolean isTail() {
return nextNode == null;
}
boolean isRoot() {
return parantNode == null;
}
List<Node> getNodes() {
return nodes;
}
void setNodes(List<Node> nodes) {
this.nodes = nodes;
}
List<KeyAndValue> getKeyAndValue() {
return keyAndValue;
}
Node getNextNode() {
return nextNode;
}
void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
Node getParantNode() {
return parantNode;
}
void setParantNode(Node parantNode) {
this.parantNode = parantNode;
}
Node getPreviousNode() {
return previousNode;
}
void setPreviousNode(Node previousNode) {
this.previousNode = previousNode;
}
}
}