数据结构编程实践20讲(Python版)—09B树

往期链接

09 B树(B-tree)

S1 说明

B树是一种自平衡的树数据结构，它的主要特点是：

• 多路搜索树：B树的每个节点可以有多个子节点，而不是二叉树的两个子节点。每个节点可以存储多个键值。
• 平衡性：B树的所有叶子节点都在同一层级，保证了树的高度尽可能低，从而提高了查找效率。
• 节点的填充因子：每个节点的键值数量在一定范围内，通常是 [⌈m/2⌉, m-1]，其中 m 是树的最大度数（每个节点的最大子节点数量）。⌈m/2⌉ 为m/2向上取整。
• 插入与删除：B树支持高效的插入和删除操作，保持树的平衡性。

B树的实际应用

• 数据库索引：B树常用于数据库管理系统中的索引，因为它们可以有效处理大量数据的存储和检索。
• 文件系统：许多现代文件系统使用 B树来管理文件的元数据，以支持快速的查找和插入。
• 内存管理：B树可以用于动态内存分配中的分区管理，保持内存块的有序性。
• 网络路由表：在网络路由中，B树可以用来存储和快速查找路由信息。

S2 示例

import matplotlib.pyplot as plt

class BTreeNode:
    def __init__(self, t, leaf=True):
        self.t = t  # 最小度数
        self.keys = []  # 存储键值
        self.children = []  # 存储子节点
        self.leaf = leaf  # 是否为叶子节点

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t)  # 创建根节点
        self.t = t  # 设置B树的最小度数

    def insert(self, k):
        root = self.root
        # 如果根节点已满，需要分裂
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode(self.t, False)
            self.root = temp
            temp.children.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, k)
        else:
            self.insert_non_full(root, k)

    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            # 如果是叶子节点，直接插入键值
            x.keys.append(None)
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            # 如果不是叶子节点，找到合适的子节点进行插入
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == (2 * self.t) - 1:
                # 如果子节点已满，需要先分裂
                self.split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self.insert_non_full(x.children[i], k)

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

    def visualize(self):
        fig, ax = plt.subplots(figsize=(12, 8))
        self._draw_tree(self.root, ax, 0, 0, 100)
        ax.axis('off')
        plt.show()

    def _draw_tree(self, node, ax, x, y, width):
        if node:
            node_text = ', '.join(map(str, node.keys))
            ax.text(x, y, node_text