往期链接
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+树：常用于数据库和文件系统，尤其在需要进行范围查询和顺序访问时表现更好。
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