AVL、B树和B+树
AVL树定义
AVL树（Adelson-Velsky 和 Landis 树）是一种自平衡的二叉搜索树（Binary Search Tree, BST），由苏联数学家Georgy Adelson-Velsky和Evgenii Landis在1962年提出。AVL树通过在每个节点上维护一个平衡因子（Balance Factor），确保树的高度始终保持在对数级别，从而保证查找、插入和删除操作的时间复杂度为O(log N)。
主要特性
-
二叉搜索树性质：
- 每个节点的左子树中所有节点的值均小于该节点的值。
- 每个节点的右子树中所有节点的值均大于该节点的值。
-
高度平衡：
- 对于每个节点，其左子树和右子树的高度差（平衡因子）最多为1，即：
∣ 左子树高度 − 右子树高度 ∣ ≤ 1 | \text{左子树高度} - \text{右子树高度} | \leq 1 ∣左子树高度−右子树高度∣≤1 - 通过旋转操作在插入或删除节点后保持树的平衡。
- 对于每个节点，其左子树和右子树的高度差（平衡因子）最多为1，即：
-
平衡因子：
- 每个节点维护一个平衡因子，定义为其左子树的高度减去右子树的高度：
平衡因子 = 左子树高度 − 右子树高度 \text{平衡因子} = \text{左子树高度} - \text{右子树高度} 平衡因子=左子树高度−右子树高度 - 平衡因子的取值范围为-1、0、+1。
- 每个节点维护一个平衡因子，定义为其左子树的高度减去右子树的高度：
旋转操作
当插入或删除节点导致某个节点的平衡因子超出范围时，需要通过旋转操作来恢复AVL树的平衡。主要的旋转操作包括：
-
单右旋（Right Rotation）：
- 用于解决左-左（LL）失衡的情况。
-
单左旋（Left Rotation）：
- 用于解决右-右（RR）失衡的情况。
-
双旋转（Left-Right Rotation 和 Right-Left Rotation）：
- 用于解决左-右（LR）和右-左（RL）失衡的情况。
优点
- 高效的查找性能：由于严格的平衡条件，AVL树的查找、插入和删除操作的时间复杂度均为O(log N)。
- 动态平衡：插入和删除操作后自动调整，保持树的平衡，避免退化为链表结构。
缺点
- 维护复杂性：插入和删除操作后可能需要进行多次旋转，增加了实现的复杂性。
- 额外的内存消耗：每个节点需要存储平衡因子或高度信息，增加了内存开销。
应用场景
AVL树适用于需要频繁查找、插入和删除操作的动态数据集，如：
- 数据库索引：保证高效的数据检索和更新。
- 内存中的符号表：如编译器中的符号表管理。
- 实时系统：需要快速响应的应用场景。
示例
以下是一个简单的AVL树节点结构的示例（以C语言为例）：
typedef struct AVLNode {
int key;
struct AVLNode *left;
struct AVLNode *right;
int height;
} AVLNode;
在这个结构中，每个节点包含一个键值、指向左子节点和右子节点的指针，以及存储该节点高度的字段。
总结
AVL树通过严格的高度平衡条件，确保了二叉搜索树的操作效率，特别适合需要频繁动态更新和高效查找的应用场景。尽管在实现上比普通的二叉搜索树更为复杂，但其在性能上的优势使其在许多系统中得到了广泛应用。
B树
早上好！我很乐意帮你修改文本，让我们添加适当的LaTeX标记。
B树的结构与性质分析
- 节点的孩子数：
- 每个节点最多有 m m m 个子节点（ m ≥ 2 m \geq 2 m≥2）。
- 除根节点和叶子节点外，其他每个非叶子节点必须至少有 ⌈ m / 2 ⌉ \lceil m / 2 \rceil ⌈m/2⌉ 个孩子。
- ⌈ m / 2 ⌉ \lceil m / 2 \rceil ⌈m/2⌉：表示向上取整的函数，它确保了树的平衡性。例如，对于 m = 5 m = 5 m=5，最少需要 ⌈ 5 / 2 ⌉ = 3 \lceil 5 / 2 \rceil = 3 ⌈5/2⌉=3 个子节点。
- 根节点的特殊情况：
- 根节点必须至少有2个孩子，除非根节点是叶子节点。在这种情况下，整棵树只有根节点，它既是叶子节点也是根节点。
- 叶子节点的特性：
- 所有叶子节点都出现在同一层级：这确保了树的平衡性，所有查找操作的路径长度一致，从而提高查找效率。
- 叶子节点不包含关键字信息：叶子节点通常不包含实际的关键字数据，可能包含数据的指针或者是表示查询失败的空指针。实际上，这些节点依然存在，只是它们没有指向其他子节点的指针。
- 非叶子节点的结构：
每个非叶子节点包含若干个关键字（ n n n个）和指向子树的指针（ P 0 , P 1 , . . . , P n P_0, P_1, ..., P_n P0,P1,...,Pn）。具体结构如下：
- 关键字：每个非叶子节点包含有 n n n 个关键字 K 1 , K 2 , . . . , K n K_1, K_2, ..., K_n K1,K2,...,Kn，且这些关键字按升序排列，即 K i − 1 < K i K_{i-1} < K_i Ki−1<Ki（ i = 1 , 2 , . . . , n i = 1, 2, ..., n i=1,2,...,n）。
- 子树指针：每个非叶子节点有 n + 1 n+1 n+1 个子树指针 P 0 , P 1 , . . . , P n P_0, P_1, ..., P_n P0,P1,...,Pn，每个子树指针 P i P_i Pi 指向一个子树，且子树中的所有关键字都小于 K i K_i Ki 并大于 K i − 1 K_{i-1} Ki−1（对于 i = 1 i = 1 i=1，指针 P 0 P_0 P0 指向所有小于 K 1 K_1 K1 的关键字）。
- 关键字的个数：
- 对于每个非根节点（即非叶子节点），包含的关键字数 n n n 必须满足以下条件： ⌈ m / 2 ⌉ − 1 ≤ n ≤ m − 1 \lceil m / 2 \rceil - 1 \leq n \leq m - 1 ⌈m/2⌉−1≤n≤m−1
这意味着每个节点的关键字数至少是 ⌈ m / 2 ⌉ − 1 \lceil m / 2 \rceil - 1 ⌈m/2⌉−1，而最多是 m − 1 m - 1 m−1，从而控制了节点的密度，防止树的某部分过于稀疏或过于密集，保证了树的平衡。
图示结构说明
假设我们考虑一个3阶（ m = 3 m = 3 m=3）B树的例子。按照您给出的规则，3阶B树的结构会是这样的：
- 节点最多含有2个子节点。
- 每个非根节点至少含有1个子节点。
- 每个节点最多含有2个关键字。
- 所有叶子节点都在同一层。
例如，一棵3阶B树的具体结构如下：
[30]
/ \
[10,20] [40,50]
其中：
- 根节点包含一个关键字 30 30 30 和两个子树指针。
- 每个子树的根节点（如 [ 10 , 20 ] [10,20] [10,20] 和 [ 40 , 50 ] [40,50] [40,50]）分别包含两个关键字，并且每个子树都至少有 1 个子节点。
- 所有叶子节点（ [ 10 , 20 ] [10,20] [10,20] 和 [ 40 , 50 ] [40,50] [40,50]）都在同一层，且没有子节点，通常这些叶子节点会存储实际的数据（在实际应用中可能是指向数据记录的指针）。
B树（B-Tree）实现示例
下面将以 Python 语言实现一个 B树，遵循您提供的详细定义和属性。此实现包括节点结构、插入和搜索操作。由于删除操作相对复杂，为了保持示例简洁，本文主要集中在插入和搜索功能上。
1. B树的基本结构
首先，定义B树节点的结构。每个节点包含以下部分：
- keys：存储节点中的关键字，按照升序排列。
- children：指向子节点的指针列表。
- leaf：布尔值，指示节点是否为叶子节点。
2. B树类的实现
以下是B树的完整实现，包括插入和搜索功能：
import math
class BTreeNode:
def __init__(self, t, leaf=False):
"""
初始化B树节点
:param t: 最小度数（ceil(m/2)）
:param leaf: 是否为叶子节点
"""
self.t = t # 最小度数
self.keys = [] # 存储关键字
self.children = [] # 存储子节点
self.leaf = leaf # 是否为叶子节点
def __str__(self):
return f'Keys: {self.keys}, Leaf: {self.leaf}'
class BTree:
def __init__(self, m):
"""
初始化B树
:param m: 阶数
"""
if m < 3:
raise ValueError("阶数m必须大于等于3")
self.m = m # 阶数
self.t = math.ceil(m / 2) # 最小度数
self.root = BTreeNode(self.t, leaf=True)
def search(self, k, x=None):
"""
在B树中搜索关键字k
:param k: 关键字
:param x: 当前节点
:return: 节点和关键字的位置
"""
if x is None:
x = self.root
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
if i < len(x.keys) and k == x.keys[i]:
return (x, i)
elif x.leaf:
return None
else:
return self.search(k, x.children[i])
def insert(self, k):
"""
向B树中插入关键字k
:param k: 关键字
"""
root = self.root
if len(root.keys) == self.m - 1:
# 根节点已满，需要分裂
s = BTreeNode(self.t, leaf=False)
s.children.insert(0, self.root)
self.split_child(s, 0)
self.root = s
self.insert_non_full(s, k)
else:
self.insert_non_full(root, k)
def insert_non_full(self, x, k):
"""
在非满节点x中插入关键字k
:param x: 当前节点
:param 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) == self.m - 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):
"""
分裂子节点x.children[i]
:param x: 父节点
:param i: 子节点的索引
"""
t = self.t
y = x.children[i]
z = BTreeNode(t, leaf=y.leaf)
# 分裂y的keys和children到z
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]
# 插入z到x的children
x.children.insert(i + 1, z)
# 将中间键上移到x
x.keys.insert(i, y.keys.pop(-1))
def traverse(self, x=None, depth=0):
"""
遍历B树并打印
:param x: 当前节点
:param depth: 当前深度
"""
if x is None:
x = self.root
print(" " * depth + str(x))
if not x.leaf:
for child in x.children:
self.traverse(child, depth + 1)
def delete(self, k):
"""
删除B树中的关键字k
:param k: 关键字
"""
self.delete_internal(self.root, k)
# 如果根节点的关键字为空，调整根
if len(self.root.keys) == 0 and not self.root.leaf:
self.root = self.root.children[0]
def delete_internal(self, x, k):
"""
在节点x中删除关键字k
:param x: 当前节点
:param k: 关键字
"""
t = self.t
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
if i < len(x.keys) and k == x.keys[i]:
if x.leaf:
# 情况1: k在叶子节点x中
x.keys.pop(i)
else:
# 情况2: k在非叶子节点x中
y = x.children[i]
z = x.children[i + 1]
if len(y.keys) >= t:
pred = self.get_predecessor(y)
x.keys[i] = pred
self.delete_internal(y, pred)
elif len(z.keys) >= t:
succ = self.get_successor(z)
x.keys[i] = succ
self.delete_internal(z, succ)
else:
self.merge(x, i)
self.delete_internal(y, k)
elif not x.leaf:
# 情况3: k不在节点x中，且x不是叶子节点
flag = (i == len(x.keys))
if len(x.children[i].keys) < t:
self.fill(x, i)
if flag and i > len(x.keys):
self.delete_internal(x.children[i - 1], k)
else:
self.delete_internal(x.children[i], k)
def get_predecessor(self, x):
"""
获取节点x的前驱关键字
:param x: 当前节点
:return: 前驱关键字
"""
while not x.leaf:
x = x.children[-1]
return x.keys[-1]
def get_successor(self, x):
"""
获取节点x的后继关键字
:param x: 当前节点
:return: 后继关键字
"""
while not x.leaf:
x = x.children[0]
return x.keys[0]
def fill(self, x, i):
"""
确保x.children[i]有至少t个关键字
:param x: 当前节点
:param i: 子节点索引
"""
t = self.t
if i != 0 and len(x.children[i - 1].keys) >= t:
self.borrow_from_prev(x, i)
elif i != len(x.children) - 1 and len(x.children[i + 1].keys) >= t:
self.borrow_from_next(x, i)
else:
if i != len(x.children) - 1:
self.merge(x, i)
else:
self.merge(x, i - 1)
def borrow_from_prev(self, x, i):
"""
从x.children[i-1]借一个关键字到x.children[i]
:param x: 当前节点
:param i: 子节点索引
"""
child = x.children[i]
sibling = x.children[i - 1]
# 移动x的key
child.keys.insert(0, x.keys[i - 1])
if not child.leaf:
child.children.insert(0, sibling.children.pop(-1))
x.keys[i - 1] = sibling.keys.pop(-1)
def borrow_from_next(self, x, i):
"""
从x.children[i+1]借一个关键字到x.children[i]
:param x: 当前节点
:param i: 子节点索引
"""
child = x.children[i]
sibling = x.children[i + 1]
# 移动x的key
child.keys.append(x.keys[i])
if not child.leaf:
child.children.append(sibling.children.pop(0))
x.keys[i] = sibling.keys.pop(0)
def merge(self, x, i):
"""
合并x.children[i]和x.children[i+1]
:param x: 当前节点
:param i: 子节点索引
"""
child = x.children[i]
sibling = x.children[i + 1]
t = self.t
# 移动x的key到child
child.keys.append(x.keys.pop(i))
# 合并sibling的keys到child
child.keys.extend(sibling.keys)
# 合并sibling的子节点到child
if not child.leaf:
child.children.extend(sibling.children)
# 移除sibling
x.children.pop(i + 1)
# 示例使用
if __name__ == "__main__":
# 创建一个阶数为4的B树（每个节点最多有3个关键字和4个子节点）
btree = BTree(m=4)
# 插入关键字
keys_to_insert = [10, 20, 5, 6, 12, 30, 7, 17]
for key in keys_to_insert:
btree.insert(key)
print(f"插入关键字 {key} 后的B树结构:")
btree.traverse()
print("-" * 50)
# 搜索关键字
search_keys = [6, 15]
for key in search_keys:
result = btree.search(key)
if result:
node, idx = result
print(f"找到关键字 {key} 在节点: {node}, 索引位置: {idx}")
else:
print(f"关键字 {key} 不存在于B树中。")
# 删除关键字
keys_to_delete = [6, 13, 7, 4, 2, 16]
for key in keys_to_delete:
print(f"\n删除关键字 {key} 后的B树结构:")
btree.delete(key)
btree.traverse()
print("-" * 50)
3. 代码详解
3.1 BTreeNode 类
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t # 最小度数
self.keys = [] # 存储关键字
self.children = [] # 存储子节点
self.leaf = leaf # 是否为叶子节点
def __str__(self):
return f'Keys: {self.keys}, Leaf: {self.leaf}'
- t（最小度数）：根据阶数 ( m )，最小度数 ( t = \lceil m/2 \rceil )。
- keys：关键字列表，始终保持有序。
- children：子节点列表。
- leaf：布尔值，指示节点是否为叶子节点。
3.2 BTree 类
class BTree:
def __init__(self, m):
if m < 3:
raise ValueError("阶数m必须大于等于3")
self.m = m # 阶数
self.t = math.ceil(m / 2) # 最小度数
self.root = BTreeNode(self.t, leaf=True)
- m（阶数）：每个节点最多有 ( m-1 ) 个关键字和 ( m ) 个子节点。
- t（最小度数）：每个节点至少有 ( t-1 ) 个关键字（根节点除外）。
- root（根节点）：初始时为叶子节点。
3.3 插入操作
插入操作分为两部分：
insert方法：处理根节点是否需要分裂的情况。insert_non_full方法：在非满节点中插入关键字。split_child方法：分裂满节点。
def insert(self, k):
root = self.root
if len(root.keys) == self.m - 1:
# 根节点已满，需要分裂
s = BTreeNode(self.t, leaf=False)
s.children.insert(0, self.root)
self.split_child(s, 0)
self.root = s
self.insert_non_full(s, 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) == self.m - 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, leaf=y.leaf)
# 分裂y的keys和children到z
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]
# 插入z到x的children
x.children.insert(i + 1, z)
# 将中间键上移到x
x.keys.insert(i, y.keys.pop(-1))
- 将满的子节点
y分裂为两个节点y和z，并将中间关键字上移到父节点x。
3.4 搜索操作
def search(self, k, x=None):
if x is None:
x = self.root
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
if i < len(x.keys) and k == x.keys[i]:
return (x, i)
elif x.leaf:
return None
else:
return self.search(k, x.children[i])
- 从根节点开始，递归搜索关键字
k。 - 若找到，返回包含关键字的节点和索引；否则，返回
None。
3.5 遍历操作
def traverse(self, x=None, depth=0):
if x is None:
x = self.root
print(" " * depth + str(x))
if not x.leaf:
for child in x.children:
self.traverse(child, depth + 1)
- 以层级形式遍历并打印B树结构，便于可视化。
3.6 删除操作
删除操作较为复杂，涉及多种情况的处理。以下是删除关键字的主要方法：
def delete(self, k):
self.delete_internal(self.root, k)
# 如果根节点的关键字为空，调整根
if len(self.root.keys) == 0 and not self.root.leaf:
self.root = self.root.children[0]
- 调用内部方法
delete_internal删除关键字。 - 若删除后根节点无关键字且不是叶子节点，则更新根节点。
def delete_internal(self, x, k):
t = self.t
i = 0
while i < len(x.keys) and k > x.keys[i]:
i += 1
if i < len(x.keys) and k == x.keys[i]:
if x.leaf:
# 情况1: k在叶子节点x中
x.keys.pop(i)
else:
# 情况2: k在非叶子节点x中
y = x.children[i]
z = x.children[i + 1]
if len(y.keys) >= t:
pred = self.get_predecessor(y)
x.keys[i] = pred
self.delete_internal(y, pred)
elif len(z.keys) >= t:
succ = self.get_successor(z)
x.keys[i] = succ
self.delete_internal(z, succ)
else:
self.merge(x, i)
self.delete_internal(y, k)
elif not x.leaf:
# 情况3: k不在节点x中，且x不是叶子节点
flag = (i == len(x.keys))
if len(x.children[i].keys) < t:
self.fill(x, i)
if flag and i > len(x.keys):
self.delete_internal(x.children[i - 1], k)
else:
self.delete_internal(x.children[i], k)
- 情况1：关键字在叶子节点中，直接删除。
- 情况2：关键字在非叶子节点中，找到前驱或后继关键字替代后递归删除。
- 情况3：关键字不在当前节点中，递归到合适的子节点删除，确保节点至少有
t个关键字。
其他辅助方法包括获取前驱、后继、借用关键字以及合并节点等。
4. 示例运行
if __name__ == "__main__":
# 创建一个阶数为4的B树（每个节点最多有3个关键字和4个子节点）
btree = BTree(m=4)
# 插入关键字
keys_to_insert = [10, 20, 5, 6, 12, 30, 7, 17]
for key in keys_to_insert:
btree.insert(key)
print(f"插入关键字 {key} 后的B树结构:")
btree.traverse()
print("-" * 50)
# 搜索关键字
search_keys = [6, 15]
for key in search_keys:
result = btree.search(key)
if result:
node, idx = result
print(f"找到关键字 {key} 在节点: {node}, 索引位置: {idx}")
else:
print(f"关键字 {key} 不存在于B树中。")
# 删除关键字
keys_to_delete = [6, 13, 7, 4, 2, 16]
for key in keys_to_delete:
print(f"\n删除关键字 {key} 后的B树结构:")
btree.delete(key)
btree.traverse()
print("-" * 50)
4.1 插入操作输出示例
插入关键字 10 后的B树结构:
Keys: [10], Leaf: True
--------------------------------------------------
插入关键字 20 后的B树结构:
Keys: [10, 20], Leaf: True
--------------------------------------------------
插入关键字 5 后的B树结构:
Keys: [5, 10, 20], Leaf: True
--------------------------------------------------
插入关键字 6 后的B树结构:
Keys: [5, 6, 10, 20], Leaf: True
--------------------------------------------------
插入关键字 12 后的B树结构:
Keys: [5, 6, 10, 12, 20], Leaf: True
--------------------------------------------------
插入关键字 30 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5, 6], Leaf: True
Keys: [10, 12, 20, 30], Leaf: True
--------------------------------------------------
插入关键字 7 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5, 6, 7], Leaf: True
Keys: [10, 12, 20, 30], Leaf: True
--------------------------------------------------
插入关键字 17 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5, 6, 7], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
4.2 搜索操作输出示例
找到关键字 6 在节点: Keys: [5, 6, 7], Leaf: True, 索引位置: 1
关键字 15 不存在于B树中。
4.3 删除操作输出示例
删除关键字 6 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5, 7], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
删除关键字 13 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5, 7], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
删除关键字 7 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
删除关键字 4 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
删除关键字 2 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
删除关键字 16 后的B树结构:
Keys: [10, 20], Leaf: False
Keys: [5], Leaf: True
Keys: [10, 12, 17, 20, 30], Leaf: True
--------------------------------------------------
5. 代码功能总结
- 节点分裂：当插入导致节点关键字数量超过最大限制时，节点被分裂，并将中间关键字上移到父节点。
- 关键字插入：关键字被插入到合适的位置，保持节点内关键字有序。
- 关键字搜索：通过递归搜索找到目标关键字所在的节点。
- 关键字删除：处理多种删除情况，确保B树的平衡性，包括关键字的借用和节点的合并。
6. 扩展功能
为了全面实现B树，您可以考虑添加以下功能：
- 删除操作的完整实现：当前实现已包含基本的删除逻辑，但在某些复杂情况下可能需要更多测试和调整。
- 可视化工具：使用图形库如
graphviz进行B树的可视化展示。 - 批量插入与删除：优化插入和删除操作以支持批量处理，提高效率。
7. 参考资料
- 《算法导论》（Introduction to Algorithms） - Cormen, Leiserson, Rivest, Stein
- Wikipedia - B-tree
希望这个B树的Python实现能够帮助您更好地理解和应用B树数据结构。如有任何疑问或需要进一步的功能扩展，请随时提问！