B 树：多关键字查找（范围查询 / 前缀匹配）实现
B 树是一种自平衡的树数据结构，它被广泛应用于数据库和文件系统中。B 树的特点是能够有效地处理大量数据的存储和检索，特别是在多关键字查找的场景中，如范围查询和前缀匹配。本文将围绕 B 树的数据结构与算法，实现多关键字查找的功能。
B 树概述
B 树是一种多路平衡查找树，它的每个节点可以有多个关键字，并且每个节点中的关键字数量是有限的。B 树的节点通常包含以下信息：
- 关键字：用于排序和查找的数据。
- 前指针：指向父节点的指针。
- 子指针：指向子节点的指针。
B 树的几个关键特性如下：
- 每个节点包含多个关键字，且每个节点的关键字数量在某个范围内。
- 每个节点最多有 m 个子节点，其中 m 是一个固定的整数，称为 B 树的阶。
- 根节点至少有两个子节点，除非它是根节点且包含一个关键字。
- 每个非根节点至少有 m/2 个子节点。
- 所有叶子节点都在同一层。
B 树的插入和删除操作
B 树的插入和删除操作需要保持树的平衡，以下是这两个操作的基本步骤：
插入操作
1. 将新关键字插入到叶节点。
2. 如果叶节点未满，则插入操作完成。
3. 如果叶节点已满，则分裂节点，并将中间的关键字提升到父节点。
4. 如果父节点已满，则继续分裂父节点，直到找到一个未满的节点或根节点。
删除操作
1. 删除关键字。
2. 如果被删除的关键字在非叶节点，则从子节点中移动一个关键字到父节点，以保持排序。
3. 如果被删除的关键字在叶节点，并且其子节点不为空，则从子节点中移动一个关键字到父节点。
4. 如果被删除的关键字在叶节点，并且其子节点为空，则从父节点中删除关键字，并合并节点。
多关键字查找
范围查询
范围查询是指查找所有在给定范围内的关键字。以下是实现范围查询的步骤：
1. 从根节点开始，使用二分查找找到第一个大于等于范围的起始关键字的节点。
2. 遍历该节点及其所有子节点，收集所有小于等于范围的结束关键字的节点。
3. 将收集到的节点中的关键字返回。
前缀匹配
前缀匹配是指查找所有以给定前缀开头的关键字。以下是实现前缀匹配的步骤：
1. 从根节点开始，使用二分查找找到第一个大于等于前缀的第一个关键字的节点。
2. 遍历该节点及其所有子节点，收集所有以给定前缀开头的节点。
3. 将收集到的节点中的关键字返回。
代码实现
以下是一个简单的 B 树实现，包括插入、删除和范围查询：
python
class BTreeNode:
def __init__(self, leaf=False, t=2):
self.leaf = leaf
self.t = t
self.keys = []
self.children = []
class BTree:
def __init__(self, t=2):
self.root = BTreeNode(leaf=True, t=t)
def insert(self, key):
root = self.root
if len(root.keys) == (2 root.t) - 1:
new_root = BTreeNode(t=root.t)
new_root.children.insert(0, root)
self.root = new_root
self.split_child(new_root, 0)
self.insert_non_full(new_root, key)
else:
self.insert_non_full(root, key)
def split_child(self, parent, i):
t = parent.t
child = parent.children[i]
new_child = BTreeNode(t=t, leaf=child.leaf)
mid = t - 1
parent.keys.insert(i, child.keys[mid])
new_child.keys = child.keys[mid + 1:t]
child.keys = child.keys[:mid]
parent.children.insert(i + 1, new_child)
def insert_non_full(self, node, key):
i = len(node.keys) - 1
if node.leaf:
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == (2 node.t) - 1:
self.split_child(node, i)
if key > node.keys[i]:
i += 1
self.insert_non_full(node.children[i], key)
def range_query(self, start, end):
result = []
self.range_query_recursive(self.root, start, end, result)
return result
def range_query_recursive(self, node, start, end, result):
if node is None:
return
if node.leaf:
for key in node.keys:
if start <= key <= end:
result.append(key)
else:
for i in range(len(node.keys)):
if start <= node.keys[i] <= end:
self.range_query_recursive(node.children[i], start, end, result)
elif start < node.keys[i]:
self.range_query_recursive(node.children[i], start, end, result)
break
使用示例
b_tree = BTree()
b_tree.insert(10)
b_tree.insert(20)
b_tree.insert(30)
b_tree.insert(40)
b_tree.insert(50)
b_tree.insert(25)
b_tree.insert(5)
b_tree.insert(35)
b_tree.insert(60)
b_tree.insert(55)
print("Range Query (20, 50):", b_tree.range_query(20, 50))
总结
本文介绍了 B 树的数据结构与算法，并实现了多关键字查找的功能，包括范围查询和前缀匹配。B 树是一种高效的数据结构，特别适用于处理大量数据的存储和检索。通过理解 B 树的插入、删除和查找操作，我们可以更好地利用这种数据结构来优化我们的应用程序。
Comments NOTHING