B-Tree

A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class BTreeNode {
  boolean isLeaf;
  int numKeys;
  BTreeNode[] children; 
  int[] keys;
}

// Search for key
BTreeNode search(BTreeNode root, int key) {
  int i = 0;
  while (i < root.numKeys && key > root.keys[i]) 
    i++;
  if (i < root.numKeys && key == root.keys[i]) {
    return root; 
  } else if (root.isLeaf) {
    return null;
  } else {
    return search(root.children[i], key);
  }  
}  

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
struct BTreeNode {
  bool isLeaf;
  int numKeys;
  BTreeNode* children[order];
  int keys[order-1];    
};

// Insert key
void insert(BTreeNode* root, int key) {
  if (root->numKeys == order-1) { 
    split(root);
    insertNonFull(root, key);
  }
  else {
    insertNonFull(root, key);
  }
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class BTreeNode:
  def __init__(self, isLeaf, numKeys, children, keys):
    self.isLeaf = isLeaf
    self.numKeys = numKeys
    self.children = children
    self.keys = keys

# Delete key  
def delete(root, key):
  root = deleteNode(root, key)
  
  if (root.numKeys == 0):
    # ... rebalance tree
    pass
    
  return root
  

Key traits are search, insert, delete in O(log n) time and efficient sequential access. Useful for databases and file systems.

A B-Tree is a balanced tree data structure commonly used in databases and file systems to store and manage large sets of sorted data. The tree remains balanced by maintaining a certain number of keys in each node, often referred to as the “order” of the B-Tree (t). Each node can have at most 2t-1 keys and at least t-1 keys, except for the root.

The primary advantage of a B-Tree is that it requires fewer disk reads or writes, which is beneficial for systems with high-latency storage access.

Below are simplified examples to insert keys into a B-Tree.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class BTreeNode {
    int[] keys;
    int t;
    BTreeNode[] children;
    int n;
    boolean leaf;

    BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.n = 0;
    }
}

public class BTree {
    BTreeNode root;
    int t;

    BTree(int t) {
        this.t = t;
        this.root = new BTreeNode(t, true);
    }

    // Insert key
    public void insert(int k) {
        // Implementation here
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;

struct BTreeNode {
    vector<int> keys;
    vector<BTreeNode*> children;
    int t;
    bool leaf;

    BTreeNode(int t, bool leaf) : t(t), leaf(leaf) {
        keys.resize(2 * t - 1);
        children.resize(2 * t);
    }
};

class BTree {
public:
    BTreeNode* root;
    int t;

    BTree(int t) : t(t) {
        root = new BTreeNode(t, true);
    }

    // Insert key
    void insert(int k) {
        // Implementation here
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class BTreeNode:
    def __init__(self, t, leaf):
        self.t = t
        self.leaf = leaf
        self.keys = [None] * (2 * t - 1)
        self.children = [None] * (2 * t)
        self.n = 0

class BTree:
    def __init__(self, t):
        self.t = t
        self.root = BTreeNode(t, True)

    # Insert key
    def insert(self, k):
        # Implementation here

These examples provide the framework for a B-Tree. They include the key properties but do not contain the complete insertion or traversal logic.