B-Tree Visualization

Watch how B-Tree maintains balance during insertions and deletions

B-Tree is a self-balancing multi-way search tree widely used in databases and file systems. Each node can have multiple keys and children, keeping the tree height low for efficient disk I/O operations.

输入值并选择操作

B-Tree Properties

  • Each node has at most m children (m is the order)
  • Each internal node has at least ⌈m/2⌉ children
  • All leaves appear on the same level
  • A node with k children contains k-1 keys

Insert Operation

  1. Find the leaf node where the key should be inserted
  2. Insert the key in sorted order
  3. If the node overflows (has m keys), split it and promote the middle key
  4. Repeat splitting upward if necessary

Search Operation

  1. Start from the root node
  2. Compare the target with keys in the current node
  3. If found, return; otherwise, follow the appropriate child pointer
  4. Repeat until found or reaching a null pointer
Operation Average Worst
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)

Space Complexity: O(n)

Tree height: O(log_m n), where m is the order

Database Indexing

MySQL InnoDB uses B+ Tree for primary and secondary indexes

File Systems

NTFS, HFS+, ext4 use B-Tree variants for directory indexing

Key-Value Stores

LevelDB, RocksDB use LSM-Tree based on B-Tree principles

Implementation

class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf

class BTree:
    def __init__(self, order=4):
        self.root = BTreeNode()
        self.order = order  # Maximum children
        self.min_keys = (order + 1) // 2 - 1
    
    def search(self, key, node=None):
        """Search for a key in the B-Tree"""
        if node is None:
            node = self.root
        
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        
        if i < len(node.keys) and key == node.keys[i]:
            return (node, i)
        elif node.leaf:
            return None
        else:
            return self.search(key, node.children[i])
    
    def insert(self, key):
        """Insert a key into the B-Tree"""
        root = self.root
        if len(root.keys) == self.order - 1:
            # Root is full, need to split
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_non_full(self.root, key)
    
    def _split_child(self, parent, index):
        """Split a full child node"""
        order = self.order
        child = parent.children[index]
        mid = (order - 1) // 2
        
        # Create new node with right half
        new_node = BTreeNode(leaf=child.leaf)
        new_node.keys = child.keys[mid + 1:]
        if not child.leaf:
            new_node.children = child.children[mid + 1:]
        
        # Promote middle key
        parent.keys.insert(index, child.keys[mid])
        parent.children.insert(index + 1, new_node)
        
        # Truncate original child
        child.keys = child.keys[:mid]
        if not child.leaf:
            child.children = child.children[:mid + 1]

# Usage
btree = BTree(order=4)
for val in [10, 20, 5, 15, 25, 30]:
    btree.insert(val)
print(btree.search(15))  # Found

import java.util.ArrayList;
import java.util.List;

public class BTree {
    private BTreeNode root;
    private int order;
    
    public BTree(int order) {
        this.order = order;
        this.root = new BTreeNode(true);
    }
    
    public boolean search(int key) {
        return searchNode(root, key) != null;
    }
    
    private BTreeNode searchNode(BTreeNode node, int key) {
        int i = 0;
        while (i < node.keys.size() && key > node.keys.get(i)) {
            i++;
        }
        if (i < node.keys.size() && key == node.keys.get(i)) {
            return node;
        }
        if (node.leaf) {
            return null;
        }
        return searchNode(node.children.get(i), key);
    }
    
    public void insert(int key) {
        BTreeNode r = root;
        if (r.keys.size() == order - 1) {
            BTreeNode newRoot = new BTreeNode(false);
            newRoot.children.add(root);
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, key);
    }
    
    private void splitChild(BTreeNode parent, int index) {
        BTreeNode child = parent.children.get(index);
        int mid = (order - 1) / 2;
        
        BTreeNode newNode = new BTreeNode(child.leaf);
        for (int j = mid + 1; j < child.keys.size(); j++) {
            newNode.keys.add(child.keys.get(j));
        }
        if (!child.leaf) {
            for (int j = mid + 1; j <= child.children.size() - 1; j++) {
                newNode.children.add(child.children.get(j));
            }
        }
        
        parent.keys.add(index, child.keys.get(mid));
        parent.children.add(index + 1, newNode);
        
        // Truncate child
        while (child.keys.size() > mid) {
            child.keys.remove(child.keys.size() - 1);
        }
    }
    
    public static void main(String[] args) {
        BTree tree = new BTree(4);
        int[] values = {10, 20, 5, 15, 25, 30};
        for (int v : values) tree.insert(v);
        System.out.println(tree.search(15)); // true
    }
}

class BTreeNode {
    List<Integer> keys = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    boolean leaf;
    
    BTreeNode(boolean leaf) {
        this.leaf = leaf;
    }
}