往期链接

01 数组	02 链表	03 栈	04 队列	05 二叉树	06 二叉搜索树	07 AVL树	08 红黑树	09 B树

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 示例

python">from graphviz import Digraphclass 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 = orderdef insert(self, key):"""向 B+ 树中插入一个键值"""node = self.rootparents = []# 找到叶子节点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_rootbreakelse: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 = parentdef _split_node(self, node):"""分裂节点，返回新节点和提升的键值"""mid_index = (self.order - 1) // 2mid_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.nextnode.next = new_nodereturn new_node, mid_keydef _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 ireturn len(keys)def search(self, key):"""在 B+ 树中搜索键值"""node = self.rootwhile 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 Nonedef display(self, node=None, level=0):"""显示 B+ 树结构"""node = node or self.rootif node.is_leaf:print