B Tree: An Efficient Data Structure

A B-Tree is a self‑balancing search tree data structure that maintains sorted data and allows efficient search, sequential access, insertions, and deletions in logarithmic time. Unlike binary search trees, B‑Trees can have more than two children per node, making them ideal for systems that read and write large blocks of data, such as databases and file systems.

Why B-Trees?

• Optimized for disk I/O: Each node can store multiple keys, reducing the number of disk accesses.
• Balanced: All leaf nodes are at the same level, guaranteeing O(log n) performance.
• Efficient range queries: In‑order traversal of leaf nodes provides sorted data.
• Dynamic: Handles insertion and deletion efficiently while maintaining balance.

Properties of a B-Tree

A B‑Tree of order m (or degree t) has the following properties:

• Node Capacity: Each node can have at most m children and m-1 keys.
• Minimum Children: Every node except the root must have at least ⌈m/2⌉ children.
• Root Flexibility: The root can have as few as 2 children (or 1 if it's a leaf).
• Sorted Keys: Keys within each node are stored in sorted order.
• Leaf Level: All leaf nodes are at the same depth.

Node Structure

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf          # True if leaf node
        self.keys = []            # List of keys
        self.children = []        # List of child pointers

Search Operation

Searching in a B‑Tree is similar to a binary search tree but with multiple branches.

def search(root, key):
    if root is None:
        return None
    i = 0
    while i < len(root.keys) and key > root.keys[i]:
        i += 1
    if i < len(root.keys) and key == root.keys[i]:
        return root  # or return (root, i)
    if root.leaf:
        return None
    return search(root.children[i], key)

Insertion Operation

Insertion follows a two‑step process:

1. Find the appropriate leaf node where the key should be inserted.
2. Insert the key into the leaf node. If the node overflows (exceeds m-1 keys), split it:
• Split the node into two nodes.
• Promote the middle key to the parent.
• If the parent overflows, continue splitting upward.

class BTree:
    def __init__(self, degree):
        self.root = None
        self.t = degree  # minimum degree (min_children = t, max_children = 2t)

    def insert(self, key):
        if self.root is None:
            self.root = BTreeNode(leaf=True)
            self.root.keys.append(key)
            return

        if len(self.root.keys) == 2 * self.t - 1:
            # Root is full, split it
            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 _insert_non_full(self, node, key):
        i = len(node.keys) - 1
        if node.leaf:
            # Insert key into sorted position
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            # Find child to insert into
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)

    def _split_child(self, parent, i):
        t = self.t
        child = parent.children[i]
        new_node = BTreeNode(leaf=child.leaf)

        # Move last (t-1) keys to new_node
        new_node.keys = child.keys[t:]
        child.keys = child.keys[:t-1]

        if not child.leaf:
            new_node.children = child.children[t:]
            child.children = child.children[:t]

        # Insert new_node as a child of parent
        parent.children.insert(i + 1, new_node)
        parent.keys.insert(i, child.keys.pop())

Deletion Operation

Deletion is more complex and involves three main cases:

1. Key in a leaf node: Simply remove the key.
2. Key in an internal node: Replace with its predecessor or successor, then recursively delete that key.
3. Underflow: If a node has fewer than t-1 keys after deletion, either:
   • Borrow a key from a sibling (rotation).
   • Merge with a sibling if both have t-1 keys.

def delete(self, key):
    if self.root is None:
        return
    self._delete(self.root, key)
    if len(self.root.keys) == 0:
        if not self.root.leaf:
            self.root = self.root.children[0]
        else:
            self.root = None

def _delete(self, node, key):
    t = self.t
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1

    if i < len(node.keys) and key == node.keys[i]:
        # Key found in this node
        if node.leaf:
            # Case 1: Leaf node - simply remove
            node.keys.pop(i)
        else:
            # Case 2: Internal node
            if len(node.children[i].keys) >= t:
                # Predecessor from left child
                pred = self._get_predecessor(node, i)
                node.keys[i] = pred
                self._delete(node.children[i], pred)
            elif len(node.children[i + 1].keys) >= t:
                # Successor from right child
                succ = self._get_successor(node, i)
                node.keys[i] = succ
                self._delete(node.children[i + 1], succ)
            else:
                # Merge children
                self._merge(node, i)
                self._delete(node.children[i], key)
    else:
        # Key not found in this node
        if node.leaf:
            return  # Key not found
        # Case 3: Child may need fixing
        if len(node.children[i].keys) < t:
            self._fix_child(node, i)
        self._delete(node.children[i], key)

Complexity

where m is the order of the B‑Tree and n is the number of keys.

B-Tree vs Binary Search Tree

B-Tree Variants

• B+ Tree: All keys are stored in leaf nodes (with linked lists), making range queries faster. Used in most modern databases.
• B* Tree: A variant that delays splitting by redistributing keys between siblings.
• 2-3 Tree: A B‑Tree of order 3 (each node can have 2 or 3 children).
• 2-3-4 Tree: A B‑Tree of order 4 (each node can have 2, 3, or 4 children).

Applications

• Database Indexing: Most relational databases (MySQL, PostgreSQL, Oracle) use B‑Trees or B+ Trees for indexing.
• File Systems: NTFS, ext4, and other file systems use B‑Trees for directory and file indexing.
• Key-Value Stores: Some NoSQL databases use B‑Trees for efficient lookups.
• Operating Systems: Memory management and paging systems.
• Search Engines: Indexing large collections of documents.

Key Takeaways

• B‑Trees are self‑balancing multi‑way search trees.
• They are optimized for disk I/O — ideal for large data sets.
• All operations (search, insert, delete) run in O(log n) time.
• B+ Trees (a variant) are the most widely used indexing structure in databases.