当前位置:网站首页>B-tree series
B-tree series
2022-07-01 06:20:00 【qq_ fifty-two million twenty-five thousand two hundred and eight】
B Trees
It's a balanced tree , be called B Trees .
A tree M rank (M>2) Of B Trees , It's a balanced M Road balance search tree .
B Implementation of tree :
public class BTreeNode {
// One B- In the tree node , Can save key The upper limit of the number of
public static final int KEY_LIMIT = 4;
//KEY_LIMIT+1: It is because the insertion space is full and will not be split , Insert one more key bring >4 Will split
public long[] keyList = new long[KEY_LIMIT+1];
// Record currently owned key The number of
public int size = 0;
// Range
public BTreeNode[] childList = new BTreeNode[KEY_LIMIT+2];
public BTreeNode parent = null;
@Override
public String toString() {
return String.format("%d: %s", size, Arrays.toString(Arrays.copyOf(keyList, size)));
}
/** * lookup key In which sub tree */
public BTreeNode findKey(long key) {
if (key > keyList[size-1]) {
// Last number
return childList[size];
}
for (int i = 0; i < size; i++) {
if (key == keyList[i]) {
return this;
} else if (key < keyList[i]) {
// The first one is greater than key Keyword element of
return childList[i];
}
}
return null;
}
public InsertResult insertKeyWithChild(long key, BTreeNode node) {
// 1. Give Way key Insert in order keyList in
int index = insertIntoKeyList(key);
// 2. according to index Conduct child Insertion
// childList[0, size]
// [0, index] Immobility
// [index + 1] Location To insert node The subscript
// [index + 1, size] Moved to [index + 2, size + 1] Element number == size - index
System.arraycopy(childList,index+1,childList,index+2,size-index);
childList[index+1] = node;
size++;
// 2. Determine whether it is necessary to split
// 3. If necessary , Split nodes
if (shouldSplit()) {
return splitNotLeaf();
}
return null;
}
// Splitting of non leaf nodes
private InsertResult splitNotLeaf() {
int size = this.size;
//1. Find the middle
int index = size / 2;
//2. Save what you want to split key
InsertResult result = new InsertResult();
result.key = keyList[index];
/** * 3. Handle key Division * Which? key It should be left in the current node [0,index) altogether index individual * Which one? key It is split key [index] * Which? key It should be in the new node (index,size) altogether size-index-1 individual */
// take (index,size) In position key Move to the new node
BTreeNode node = new BTreeNode();// Create a new node
System.arraycopy(keyList,index+1,node.keyList,0,size-index-1);
node.size = size-index-1;
// hold [index,size) be-all key Reset to 0, Reset size
Arrays.fill(keyList,index,size,0);
this.size = index;
//4. Split non leaf nodes
System.arraycopy(this.childList, index + 1, node.childList, 0, size - index);
//[index + 1, size + 1)
Arrays.fill(this.childList, index + 1, size + 1, null);
for (int i = 0; i < size - index; i++) {
node.childList[i].parent = node;
}
/** * 5. Dealing with split parent problem * 1)this.parent unchanged , Division does not affect the relationship between father and son * 2)node.parent and this The same father */
node.parent = this.parent;
result.node = node;
return result;
}
public static class InsertResult{
public long key; // Split key
public BTreeNode node;// Split new nodes
}
public InsertResult insertKey(long key) {
//key Insert in order keyList in
insertIntoKeyList(key);
size++;
// Decide whether to split
if (shouldSplit( )) {
return splitLeaf();
}
return null;
}
// Node splitting
private InsertResult splitLeaf() {
int size = this.size;
//1. Find the middle
int index = size / 2;
//2. Save what you want to split key
InsertResult result = new InsertResult();
result.key = keyList[index];
/** * 3. Handle key Division * Which? key It should be left in the current node [0,index) altogether index individual * Which one? key It is split key [index] * Which? key It should be in the new node (index,size) altogether size-index-1 individual */
// take (index,size) In position key Move to the new node
BTreeNode node = new BTreeNode();// Create a new node
System.arraycopy(keyList,index+1,node.keyList,0,size-index-1);
node.size = size-index-1;
// hold [index,size) be-all key Reset to 0, Reset size
Arrays.fill(keyList,index,size,0);
this.size = index;
//4. Split leaf nodes , If childList == null, There is no need to split
/** * 5. Dealing with split parent problem * 1)this.parent unchanged , Division does not affect the relationship between father and son * 2)node.parent and this The same father */
node.parent = this.parent;
result.node = node;
return result;
}
// Decide whether to split
private boolean shouldSplit() {
return size > KEY_LIMIT;
}
//key Insert in order keyList in
private int insertIntoKeyList(long key) {
int i;
for (i = size-1; i >= 0; i--) {
if (keyList[i] < key) {
break;
}
// Move the value back one space , Continue to find
keyList[i+1] = keyList[i];
}
keyList[i+1] = key;
return i+1;
}
}
public class BTree {
//B- Root node of tree
public BTreeNode root = null;
//B- In the tree key The number of
public int size = 0;
public boolean insert(long key) {
if (insertWithoutSize(key)) {
size++;
return true;
}
return false;
}
private boolean insertWithoutSize(long key) {
// Determine whether it is an empty tree
if(root == null) {
root = new BTreeNode();
root.keyList[0] = key;
root.size = 1;
return true;
}
// It's not an empty tree
BTreeNode cur = root;
while (true) {
BTreeNode node = cur.findKey(key);
if (node == cur) {
//key It's just cur In nodes
// You can't insert it repeatedly
return false;
} else if (node == null) {
//cur That's the leaf node , Directly inserted into the
break;
} else {
// Find a child , and cur It's not a leaf
cur = node;
}
}
// Conduct key Insertion
BTreeNode.InsertResult result = cur.insertKey(key);
while (true) {
if (result == null) {
// No node splitting occurred during insertion
return true;
}
// It means there is a split
// It needs to be split up key Insert the corresponding node with the new node
BTreeNode parent = cur.parent;
if (parent == null) {
//cur Root node
// The root node split
// Need a new root node , To preserve the split key
root = new BTreeNode();
root.keyList[0] = result.key;
root.size = 1;
root.childList[0] = cur;
root.childList[1] = result.node;
// Because originally current It is the root node. , So its parent == null
// Naturally split nodes , So did I null
// So set a new parent node for them
cur.parent = result.node.parent = root;
return true;
}
// Not root insertion
result = parent.insertKeyWithChild(result.key,result.node);
cur = parent;
}
}
}
B+ Trees
B+ Tree search and B- The trees are basically the same , The difference is that B+ Only when the tree reaches the leaf node can it hit (B- Trees can hit in non leaf nodes ).
key Must keep a copy in the leaves . Leaf nodes are linked by a chain structure .
The database often needs all key Scan .
B+ Characteristics of trees :
(1) All keywords appear in the linked list of leaf nodes ( Dense index ), And the nodes in the linked list are ordered .
(2) It is impossible to hit... In a non leaf node .
(3) A non leaf node is the index of a leaf node ( Sparse index ), Leaf nodes are equivalent to the data layer that stores data .
(4) More suitable for file index system
B+ Trees and B- The difference between trees :
B- Trees : Multiple search trees , Each node stores M/2 To M Key words , Non leaf nodes store nodes that point to keyword ranges ; All keywords appear in the whole tree , And only once , Non leaf nodes can hit ;
B+ Trees : stay B- On the basis of trees , Add a linked list pointer to the leaf node , All keywords appear in the leaf node , The non leaf node is used as the index of the leaf node ;B+ The tree always hits the leaf node .
边栏推荐
- Arcserver password reset (account cannot be reset)
- 连续四年入选Gartner魔力象限,ManageEngine卓豪是如何做到的?
- FPGA - 7 Series FPGA internal structure clocking-01-clock Architecture Overview
- DEV XPO对比之UOW
- Servlet
- make: g++:命令未找到
- 指数法和Random Forest实现山东省丰水期地表水体信息
- Recueillir des trésors dans le palais souterrain (recherche de mémoire profonde)
- PLA不粘貼在床上:6個簡單的解决方案
- Projects and dependencies in ABP learning solutions
猜你喜欢
Geoffrey Hinton: my 50 years of in-depth study and Research on mental skills
HCM Beginner (II) - information type
Top 10 Free 3D modeling software for beginners in 2022
浅谈SIEM
Arcserver password reset (account cannot be reset)
SystemVerilog learning-08-random constraints and thread control
69 Cesium代码datasource加载geojson
[summary of knowledge points] chi square distribution, t distribution, F distribution
无限水平大理石游戏
图片服务器项目测试
随机推荐
HCM Beginner (II) - information type
Minio error correction code, construction and startup of distributed Minio cluster
ABP 学习解决方案中的项目以及依赖关系
srpingboot security demo
HCM Beginner (III) - quickly enter pa70 and pa71 to browse employee information PA10
[file system] how to run squashfs on UBI
PLA不粘貼在床上:6個簡單的解决方案
Understanding of C manualresetevent class
无限水平大理石游戏
Thesis learning record essay multi label lift
Index method and random forest to realize the information of surface water body in wet season in Shandong Province
MySQL中 in 和 exists 的区别
Fixed height of the first column in El table dynamic header rendering
Teach you how to implement a deep learning framework
jdbc 数据库操作
讓田頭村變甜頭村的特色農產品是仙景芋還是白菜
ManageEngine卓豪助您符合ISO 20000标准(四)
three. JS summary
Highmap gejson data format conversion script
Smartinstantiationawarebeanpostprocessor of the extension point series determines which construction method to execute - Chapter 432