A B-Tree is a self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. B-Trees are widely used in databases and file systems to store large amounts of data that cannot fit entirely into memory.
Consider a B-Tree of order 3 with the following structure:
[10 | 20]
/ | \
[5] [15] [25 | 30 | 35]
In this B-Tree, each node can have at most 3 children and can contain at most 2 keys. The tree is balanced, and all leaves are at the same level.
B-Trees have several important properties:
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t # Minimum degree (defines the range for number of keys)
self.leaf = leaf # True if leaf node, else false
self.keys = [] # List of keys
self.children = [] # List of child pointers
class BTree:
def __init__(self, t):
self.root = BTreeNode(t, True)
self.t = t # Minimum degree
def traverse(self, node):
for i in range(len(node.keys)):
if not node.leaf:
self.traverse(node.children[i])
print(node.keys[i], end=' ')
if not node.leaf:
self.traverse(node.children[len(node.keys)])
def search(self, k, node=None):
if node is None:
node = self.root
i = 0
while i < len(node.keys) and k > node.keys[i]:
i += 1
if i < len(node.keys) and k == node.keys[i]:
return node
if node.leaf:
return None
return self.search(k, node.children[i])
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
new_root = BTreeNode(self.t, False)
new_root.children.append(self.root)
self.split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, k)
def split_child(self, parent, i):
t = self.t
node = parent.children[i]
new_node = BTreeNode(t, node.leaf)
parent.children.insert(i + 1, new_node)
parent.keys.insert(i, node.keys[t - 1])
new_node.keys = node.keys[t:]
node.keys = node.keys[:t - 1]
if not node.leaf:
new_node.children = node.children[t:]
node.children = node.children[:t]
def _insert_non_full(self, node, k):
if node.leaf:
i = len(node.keys) - 1
node.keys.append(None)
while i >= 0 and k < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = k
else:
i = len(node.keys) - 1
while i >= 0 and k < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == (2 * self.t) - 1:
self.split_child(node, i)
if k > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], k)
# Example usage:
btree = BTree(3) # A B-Tree with minimum degree 3
keys = [10, 20, 5, 6, 12, 30, 7, 17]
for key in keys:
btree.insert(key)
btree.traverse(btree.root) # Output: 5 6 7 10 12 17 20 30
This code defines a B-Tree with methods for inserting nodes and performing search and traversal operations.
There are several variations of B-Trees, each with distinct characteristics:
B-Trees are a fundamental data structure that provides efficient management of large datasets. Understanding their components, properties, and applications is crucial for implementing various algorithms and solving complex problems in databases, file systems, and other areas.