当前位置:网站首页>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 .
边栏推荐
- ABP 学习解决方案中的项目以及依赖关系
- 【ManageEngine卓豪】局域网监控的作用
- 让厦门灌口镇田头村变甜头村的特色农产品之一是蚂蚁新村
- 地宮取寶(記憶化深搜)
- Small guide for rapid completion of mechanical arm (VI): stepping motor driver
- SystemVerilog learning-07-class inheritance and package use
- Database problems, how to optimize Oracle SQL query statements faster and more efficient
- 利用百度地图查询全国地铁线路
- 阶乘约数(唯一分解定理)
- What if the data in the cloud disk is harmonious?
猜你喜欢
[summary of knowledge points] chi square distribution, t distribution, F distribution
ManageEngine卓豪助您符合ISO 20000标准(四)
Database problems, how to optimize Oracle SQL query statements faster and more efficient
Top 10 Free 3D modeling software for beginners in 2022
图片服务器项目测试
【自动化运维】自动化运维平台有什么用
Pla ne colle pas sur le lit: 6 solutions simples
解决麒麟V10上传文件乱码问题
Infinite horizontal marble game
记磁盘扇区损坏导致的Mysql故障排查
随机推荐
kotlin位运算的坑(bytes[i] and 0xff 报错)
MySQL中 in 和 exists 的区别
Projects and dependencies in ABP learning solutions
连续四年入选Gartner魔力象限,ManageEngine卓豪是如何做到的?
Skywalking integrated Nacos dynamic configuration
kubeadm搭建kubenetes 集群(个人学习版)
Transformer le village de tiantou en un village de betteraves sucrières
three. JS summary
OpenGL es: (3) EGL, basic steps of EGL drawing, eglsurface, anativewindow
ForkJoin和Stream流测试
MySQL里记录货币
Make: g++: command not found
Differences between in and exists in MySQL
【ManageEngine卓豪】移动终端管理解决方案,助力中州航空产业数字化转型
make: g++:命令未找到
Multi label lsml for essay learning records
MySQL怎么存储emoji?
Distributed lock implementation
Pol8901 LVDS to Mipi DSI supports rotating image processing chip
Thoughts on a "01 knapsack problem" expansion problem