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

往期链接

10 B+树(B+ Tree)

S1 说明

1. 数据结构
B+树是一种自平衡的树数据结构，主要用于数据库和文件系统中，具有以下特征：

• 节点结构：
  • 内部节点：仅存储键，用于指引搜索。
  • 叶子节点：存储实际的数据记录，并通过指针顺序链接，形成链表。
• 高度平衡：所有叶子节点在同一层，确保访问时间一致。
• 度：每个节点可以有多个子节点，具体数量取决于树的度数（最小度数 t）。

2. 特点

• 高效的查找：由于数据仅存储在叶子节点，查找操作通常更快。
• 范围查询：叶子节点的链表结构使得范围查询非常高效。
• 动态调整：插入和删除操作可以动态调整树的形状，保持平衡。
• 空间利用率高：内部节点仅存储键，可以提高存储效率。

3. 应用领域

• 数据库系统：用于索引数据库中的数据，以提高查询效率。
• 文件系统：用于管理文件和目录的存储，支持快速访问和检索。
• 内存数据库：在内存中高效存储数据，以提供快速访问。

S2 B+树和B树的区别

B+树和B树是两种广泛使用的自平衡搜索树，虽然它们在结构和功能上有许多相似之处，但也有一些关键的区别：

1. 节点结构

• B树：每个节点可以存储多个键值对和指向子节点的指针。每个节点中的键可以用于查找、插入和删除。
• B+树：内部节点仅存储键，而不存储实际的数据。所有数据都存储在叶子节点中。内部节点的主要作用是引导搜索。

2. 叶子节点

• B树：叶子节点不一定形成一个链表，数据散布在各个节点中。
• B+树：所有叶子节点通过指针相连，形成一个链表。这使得范围查询更高效，因为可以顺序访问所有叶子节点。

3. 搜索效率

• B树：搜索时可能需要在多个节点中查找数据。
• B+树：由于所有数据在叶子节点中，搜索时可以直接找到叶子节点，避免了在内部节点中查找数据的复杂性。

4. 插入和删除

• B树：每次插入或删除可能会影响多个节点的结构。
• B+树：插入和删除操作主要影响叶子节点，内部节点的结构相对稳定。

5. 空间利用率

• B树：由于每个节点存储键值对，可能会存在空间浪费。
• B+树：内部节点只存储键，通常能更高效地利用空间。

6. 应用场景

• B树：适用于对数据的随机访问和修改频繁的场景。
• B+树：常用于数据库和文件系统，尤其在需要进行范围查询和顺序访问时表现更好。

总结来说，B+树在范围查询和顺序访问方面比B树更高效，而B树在随机访问和修改时具有更好的灵活性。

S3 示例

from graphviz import Digraph

class BPlusTreeNode:
    def __init__(self, order, is_leaf=False):
        self.order = order  # B+ 树的阶数
        self.is_leaf = is_leaf  # 是否为叶子节点
        self.keys = []  # 键值列表
        self.children = []  # 子节点指针或数据指针
        self.next = None  # 叶子节点的下一个叶子节点

class BPlusTree:
    def __init__(self, order=5):
        self.root = BPlusTreeNode(order, True)
        self.order = order

    def insert(self, key):
        """
        向 B+ 树中插入一个键值
        """
        node = self.root
        parents = []
        # 找到叶子节点
        while not node.is_leaf:
            parents.append(node)
            index = self._find_index(node.keys, key)
            node = node.children[index]

        # 插入键值到叶子节点
        self._insert_into_leaf(node, key)

        # 检查是否需要分裂
        while len(node.keys) > self.order - 1:
            if node == self.root:
                # 根节点分裂
                new_node, mid_key = self._split_node(node)
                new_root = BPlusTreeNode(self.order)
                new_root.keys = [mid_key]
                new_root.children = [node, new_node]
                self.root = new_root
                break
            else:
                parent = parents.pop()
                new_node, mid_key = self._split_node(node)
                index = self._find_index(parent.keys, mid_key)
                parent.keys.insert(index, mid_key)
                parent.children.insert(index + 1, new_node)
                node = parent

    def _split_node(self, node):
        """
        分裂节点，返回新节点和提升的键值
        """
        mid_index = (self.order - 1) // 2
        mid_key = node.keys[mid_index]

        # 创建新节点
        new_node = BPlusTreeNode(self.order, node.is_leaf)
        new_node.keys = node.keys[mid_index + (0 if node.is_leaf else 1):]
        new_node.children = node.children[mid_index + 1:]

        # 更新当前节点
        node.keys = node.keys[:mid_index + (1 if node.is_leaf else 0)]
        node.children = node.children[:mid_index + 1]

        if node.is_leaf:
            # 更新叶子节点的 next 指针
            new_node.next = node.next
            node.next = new_node
        return new_node, mid_key

    def _insert_into_leaf(self, leaf, key):
        """
        将键值插入到叶子节点中
        """
        index = self._find_index(leaf.keys, key)
        leaf.keys.insert(index, key)
        leaf.children.insert(index, key)  # 叶子节点的 children 存储数据，这里简化为与键值相同

    def _find_index(self, keys, key):
        """
        找到应插入的位置
        """
        for i, item in enumerate(keys):
            if key < item:
                return i
        return len(keys)

    def search(self, key):
        """
        在 B+ 树中搜索键值
        """
        node = self.root
        while not node.is_leaf:
            index = self._find_index(node.keys, key)
            node = node.children[index]
        for i, item in enumerate(node.keys):
            if item == key:
                return node.children[i]
        return None

    def display(self, node=None, level=0):
        """
        显示 B+ 树结构
        """
        node = node or self.root
        if node.is_leaf:
            print