Aprenda B-Trees and B+ Trees in Storage Systems | Indexing and Search Structures

B-trees are foundational data structures in storage systems, designed specifically to address the limitations of traditional binary search trees when working with large datasets that reside on disk. The motivation for B-trees comes from the need to minimize disk I/O operations, which are much slower than in-memory operations. By allowing each node to contain multiple keys and children, B-trees keep their height low, ensuring that searches, insertions, and deletions require fewer disk accesses. The structure of a B-tree is defined by its order, which dictates the minimum and maximum number of keys each node can have. This multi-way branching makes B-trees ideal for disk-based storage, as they align well with the way data is read and written in blocks, maximizing throughput and efficiency in large-scale systems.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
            
class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # Minimum degree
        self.leaf = leaf
        self.keys = []
        self.children = []

    def insert_non_full(self, key):
        i = len(self.keys) - 1
        if self.leaf:
            self.keys.append(None)
            while i >= 0 and key < self.keys[i]:
                self.keys[i + 1] = self.keys[i]
                i -= 1
            self.keys[i + 1] = key
        else:
            while i >= 0 and key < self.keys[i]:
                i -= 1
            i += 1
            if len(self.children[i].keys) == 2 * self.t - 1:
                self.split_child(i)
                if key > self.keys[i]:
                    i += 1
            self.children[i].insert_non_full(key)

    def split_child(self, i):
        t = self.t
        y = self.children[i]
        z = BTreeNode(t, y.leaf)
        z.keys = y.keys[t:]
        y.keys = y.keys[:t-1]
        if not y.leaf:
            z.children = y.children[t:]
            y.children = y.children[:t]
        self.children.insert(i + 1, z)
        self.keys.insert(i, y.keys.pop())

    def search(self, key):
        i = 0
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        if i < len(self.keys) and key == self.keys[i]:
            return True
        if self.leaf:
            return False
        return self.children[i].search(key)

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

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            s = BTreeNode(self.t, False)
            s.children.insert(0, root)
            s.split_child(0)
            i = 0
            if key > s.keys[0]:
                i += 1
            s.children[i].insert_non_full(key)
            self.root = s
        else:
            root.insert_non_full(key)

    def search(self, key):
        return self.root.search(key)

# Example usage:
btree = BTree(2)
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
    btree.insert(k)

print(btree.search(6))   # True
print(btree.search(15))  # False

B+ trees build upon the basic B-tree concept but introduce a crucial difference: all actual data records are stored only at the leaf nodes, while internal nodes only store keys for routing. Additionally, leaf nodes in a B+ tree are linked together in a linked list, making them especially well-suited for range queries and sequential access patterns. This structure enables efficient traversal of large, ordered datasets — such as when scanning a range of values — since you can quickly move from one leaf to the next without traversing the upper layers of the tree. These properties make B+ trees the preferred choice for database indexing, where both point lookups and range queries are common and performance-critical.

Study More

Leading relational databases such as MySQL and PostgreSQL leverage B+ trees to implement their primary indexing mechanisms. By using B+ trees, these systems achieve fast lookups, efficient range queries, and maintain sorted order of indexed columns, all while minimizing disk I/O. Explore the official MySQL and PostgreSQL documentation for deeper insights into their use of B+ tree indexes.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 1

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Deslize para mostrar o menu


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
            
class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # Minimum degree
        self.leaf = leaf
        self.keys = []
        self.children = []

    def insert_non_full(self, key):
        i = len(self.keys) - 1
        if self.leaf:
            self.keys.append(None)
            while i >= 0 and key < self.keys[i]:
                self.keys[i + 1] = self.keys[i]
                i -= 1
            self.keys[i + 1] = key
        else:
            while i >= 0 and key < self.keys[i]:
                i -= 1
            i += 1
            if len(self.children[i].keys) == 2 * self.t - 1:
                self.split_child(i)
                if key > self.keys[i]:
                    i += 1
            self.children[i].insert_non_full(key)

    def split_child(self, i):
        t = self.t
        y = self.children[i]
        z = BTreeNode(t, y.leaf)
        z.keys = y.keys[t:]
        y.keys = y.keys[:t-1]
        if not y.leaf:
            z.children = y.children[t:]
            y.children = y.children[:t]
        self.children.insert(i + 1, z)
        self.keys.insert(i, y.keys.pop())

    def search(self, key):
        i = 0
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        if i < len(self.keys) and key == self.keys[i]:
            return True
        if self.leaf:
            return False
        return self.children[i].search(key)

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

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            s = BTreeNode(self.t, False)
            s.children.insert(0, root)
            s.split_child(0)
            i = 0
            if key > s.keys[0]:
                i += 1
            s.children[i].insert_non_full(key)
            self.root = s
        else:
            root.insert_non_full(key)

    def search(self, key):
        return self.root.search(key)

# Example usage:
btree = BTree(2)
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
    btree.insert(k)

print(btree.search(6))   # True
print(btree.search(15))  # False

Study More

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 1