【BTree】
Definition of BTree
GPT:
B-tree (B-tree) is a self-balancing tree data structure, originally proposed by Rudolf Bayer and Edward M. McCreight in 1972. It is usually used to achieve efficient data organization and retrieval in databases and file systems. The name “B” of the B-tree stands for “Bayer” (one of the inventors).
B-trees have the following main characteristics:1. Balance: B-tree is a balanced tree, which means that the difference between the longest path and the shortest path from the root node to the leaf node will not be too big. This ensures that the depth of each branch is relatively balanced, providing a predictable retrieval performance.
2. Multi-way search tree: Each node can contain multiple child nodes, usually more than two child nodes, which makes the B-tree a multi-way search tree. This helps reduce the height of the tree, thereby reducing the complexity of find, insert, and delete operations.
3. Orderliness: The nodes in the B-tree are usually arranged in ascending order. This ordering facilitates range query and range scan operations because related data is often stored adjacent to each other in a B-tree.
4. Hierarchical storage: B-trees are often used for data stored on disks or other hierarchical storage devices because its structure allows efficient disk I/O. The node size of a B-tree is usually set to the size of a disk block to minimize I/O operations.
5. Self-balancing: When a node is inserted or deleted, the B-tree will automatically perform a balancing operation to ensure that the balance of the tree is maintained. This is achieved by redistributing keys and nodes and merging or splitting nodes.B-trees are widely used as index structures in database management systems. For example, B+ trees are used for database indexes, file system management, and other applications that require efficient insertion, deletion, and search operations. Their balanced and multipath nature make them very useful in large-scale data storage and retrieval.
Code implementation
package DataStruction;
import java.util.Arrays;
/**
* Degree concept: Degree refers to the upper limit or maximum capacity of the number of child nodes of each node in the tree
*/
public class BTree {<!-- -->
//B tree implementation
static class Node {<!-- -->
int[] keys; //Value array of this node
Node[] children;//array of child nodes
int keyNumbers;//The length of the valid value in the array
boolean leaf = true;//Is it a leaf node?
int t;//degree, represents the number of children
public Node(int t) {<!-- -->
this.t = t;
children = new Node[2 * t]; //Maximum number of children
keys = new int[2 * t - 1]; //Maximum number of values,
}
@Override
public String toString() {<!-- -->
return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumbers));
}
Node get(int key) {<!-- -->
int i = 0;
while (i < keyNumbers) {<!-- -->
if (keys[i] == key) {<!-- -->
return this;
}
if (keys[i] > key) {<!-- -->
break;
}
i + + ;
}
if (leaf) {<!-- -->
return null;
}
return children[i].get(key);
}
void insertKey(int key, int index) {<!-- -->
if (index >= 0 & amp; & amp; index < keyNumbers & amp; & amp; keyNumbers < 2 * t - 1) {<!-- -->
//Move array elements to make room for insertion
System.arraycopy(keys, index, keys, index + 1, keyNumbers - index);
//Insert new key
keys[index] = key;
keyNumbers + + ;
} else {<!-- -->
System.out.println("Invalid index for key insertion.");
}
}
void insertChild(Node child, int index) {<!-- -->
if (index >= 0 & amp; & amp; index <= t & amp; & amp; keyNumbers < 2 * t - 1) {<!-- -->
//Move array elements to make room for insertion
System.arraycopy(children, index, children, index + 1, keyNumbers - index + 1);
//Insert new child
children[index] = child;
} else {<!-- -->
System.out.println("Invalid index for child insertion.");
}
}
/**
* Delete the key at the specified location from the current node
* @param index The location of the key to be deleted
*/
int deleteKey(int index) {<!-- -->
int ans = keys[index];
if (index >= 0 & amp; & amp; index < keyNumbers) {<!-- -->
//Move the array element to cover the deleted position
System.arraycopy(keys, index + 1, keys, index, keyNumbers - index - 1);
keyNumbers--;
} else {<!-- -->
System.out.println("Invalid index for key deletion.");
}
return ans;
}
/**
* Delete the leftmost key of the current node
*/
int deleteLeftmostKey() {<!-- -->
return deleteKey(0);
}
/**
* Delete the rightmost key of the current node
*/
int deleteRightmostKey() {<!-- -->
return deleteKey(keyNumbers - 1);
}
/**
* Delete the child at the specified position of the current node
* @param index The position of the child to be deleted
*/
Node deleteChild(int index) {<!-- -->
Node deleted = children[index];
if (index >= 0 & amp; & amp; index < keyNumbers + 1) {<!-- -->
//Move the array element to cover the deleted position
System.arraycopy(children, index + 1, children, index, keyNumbers - index);
children[keyNumbers] = null; // Set the rightmost child to null
} else {<!-- -->
System.out.println("Invalid index for child deletion.");
}
return deleted;
}
/**
* Delete the leftmost child of the current node
*/
Node deleteLeftmostChild() {<!-- -->
return deleteChild(0);
}
/**
* Delete the rightmost child of the current node
*/
Node deleteRightmostChild() {<!-- -->
return deleteChild(keyNumbers);
}
/**
* Copy all keys and children of the current node to the target node
* @param target target node
*/
void copyTo(Node target) {<!-- -->
//Copy keys array
System.arraycopy(this.keys, 0, target.keys, 0, this.keyNumbers);
//Copy children array
System.arraycopy(this.children, 0, target.children, 0, this.keyNumbers + 1);
//Update the keyNumbers of the target node
target.keyNumbers = this.keyNumbers;
}
/**
*
* @param index The left brother of the child at index
* @return left sibling node
*/
Node childLeftSibling(int index){<!-- -->
return index==0?null:children[index-1];
}
/**
*
* @param index The right brother of the child at index
* @return right sibling node
*/
Node childRightSibling(int index){<!-- -->
return index==keyNumbers-1?null:children[index + 1];
}
}
Node root;//root node
int t;//minimum degree
int MIN_KEY_NUMBER;//Minimum number of keys
int MAX_KEY_NUMBER;//Maximum number of keys
public BTree(int t) {<!-- -->
this.t = t;
root = new Node(t);
MIN_KEY_NUMBER = t - 1;//Each node can have at least t - 1 keywords.
MAX_KEY_NUMBER = 2 * t - 1;//Each node can contain up to 2 * t - 1 keywords (or data items). This is because each keyword needs to be separated by at least one child node.
}
public BTree() {<!-- -->
this(2);//Default is 2
}
//Include
public boolean contains(int key) {<!-- -->
return root.get(key) != null;
}
//Add new
void put(int key){<!-- -->
//
doPut(root,key,null,0);
}
void doPut(Node node,int key,Node parent,int index){<!-- -->
int i = 0;
while(i<node.keyNumbers){<!-- -->
if (node.keys[i]==key){<!-- -->
//This value already exists, update it, of course in the form of key-value pairs, values are omitted here for simplicity
return;
}
if (node.keys[i]>key){<!-- -->
break;
}
i + + ;
}
// Found a value larger than it. If it is a leaf node, just insert it directly into the node.
if (node.leaf){<!-- -->
node.insertKey(key,i);
}else {<!-- -->
//If it is not a leaf node, should we continue looking down?
doPut(node.children[i],key,node,i);
}
//After the new addition, does each node here need to be updated, and is the maximum t in the keys full? need to split
if (node.keyNumbers==MAX_KEY_NUMBER){<!-- -->
split(node,parent,index);
}
}
void split(Node left,Node parent,int index){<!-- -->
if (parent==null){<!-- -->
//The root node is split, and a new root node needs to be created.
Node newRoot = new Node(t);
newRoot.leaf = false;
newRoot.insertChild(left,0);
this.root = newRoot;
parent = newRoot;
}
//Split
//1. Create a right node, move the key after t to the right node and leave
//2. Move the key at t-1 to the parent node index
//3. Use right as the rightmost child index + 1 of parent
Node right = new Node(t);
right.leaf = left.leaf;
//1
System.arraycopy(left.keys,t,right.keys,0,t-1);
if (!left.leaf){<!-- -->
//It is not a leaf node, you need to divide the children there as well.
System.arraycopy(left.children,t,right.children,0,t);
}
//Set the effective length
right.keyNumbers = t-1;
//2
parent.insertKey(left.deleteKey(t-1),index);
left.keyNumbers = t-1;
//3
parent.insertChild(right,index + 1);
}
void doSplit(){<!-- -->
//Recursive implementation
}
void remove(int key){<!-- -->
doRemove(null,root,key,0);
}
void doRemove(Node parent,Node node,int key,int index){<!-- -->
int i = 0;
while(i<node.keyNumbers){<!-- -->
if (node.keys[i]>=key){<!-- -->
//turn up
break;
}
i + + ;
}
//Currently a leaf node
if (node.leaf){<!-- -->
if (found(node, key, i)){<!-- -->
//case 2: found, delete directly
node.deleteKey(i);
}else {<!-- -->
//case 1: not found
return;
}
}else {<!-- -->
if (found(node,key,i)){<!-- -->
//case 4: non-leaf node, found
//Idea, replace the successor node
Node p = node.children[i + 1];
while(!p.leaf){<!-- -->
p = p.children[0];
}
//This is the node where the successor value is located
node.keys[i] = p.keys[0];
doRemove(node,node.children[i + 1],p.keys[0],i + 1);
}else {<!-- -->
//case 3: non-leaf node, not found, go to the child i node to find it
doRemove(node,node.children[i],key,i);
}
}
//After deletion, you need to consider whether it is less than the minimum degree and needs balance adjustment?
if (node.keyNumbers<MIN_KEY_NUMBER){<!-- -->
//balance adjustment
balance(parent,node,index);
}
}
/**
*
* @param parent the parent node to be adjusted
* @param x Adjustment node
* @param The index where the i value is located
*/
void balance(Node parent,Node x,int i){<!-- -->
//case 6: root node
//case 5-1: The brother on the left is rich, and the brother on the right is right
//case 5-2: The brother on the right rotates left
//case 5-3: Neither is rich, merge
if (x==root){<!-- -->
//Adjust the root node so that the value of the root node is assigned to the current node
if (root.keyNumbers==0 & amp; & amp;root.children[0]!=null){<!-- -->
root = root.children[0];
}
return;
}
//Adjust the left and right children of the node
Node left = parent.childLeftSibling(i);
Node right = parent.childRightSibling(i);
//5-1
if (left!=null & amp; & amp;left.keyNumbers>MIN_KEY_NUMBER){<!-- -->
//right rotation
x.insertKey(parent.keys[i-1],0);//Get the predecessor key of the parent node
if (!left.leaf){<!-- -->
//If there are children, if the key is reduced, the children will also be reduced and given to the node with the new key.
x.insertChild(left.deleteRightmostChild(),0);
}
parent.keys[i-1] = left.deleteRightmostKey();//Get the rightmost key of the rich left brother to parent
return;
}
if (right!=null & amp; & amp;right.keyNumbers>MIN_KEY_NUMBER){<!-- -->
//left-hand rotation
x.insertKey(parent.keys[i],x.keyNumbers);//Unscrew the successor node of the current node in the parent node
if (!right.leaf){<!-- -->
//There is a child on the right
x.insertChild(right.deleteLeftmostChild(),x.keyNumbers + 1);
}
parent.keys[i] = right.deleteLeftmostKey();//Give the rich right brother’s leftmost key to his father
return;
}
//Both sides are not enough to borrow, merge: divided into those with left brothers and those without left brothers
parent.deleteChild(i);
if (left!=null){<!-- -->
//There is a left child
//a. Delete the currently unadjusted node from the parent node
//b. Merge to the left brother and move the successor node of the parent node to the left brother.
left.insertKey(parent.deleteKey(i-1), left.keyNumbers);
//c. Copy the current node to the left brother
x.copyTo(left);
}else {<!-- -->
//No, merge to yourself
x.insertKey(parent.deleteKey(i),x.keyNumbers);
right.copyTo(x);
}
}
private static boolean found(Node node, int key, int i) {<!-- -->
return i < node.keyNumbers & amp; & amp; node.keys[i] == key;
}
}