本文目录
- 09 B树(B-tree)
- S1 说明
- S2 示例
- S3 B树的应用Python代码
- 应用1：文件系统索引
- 应用2：数据库索引
- 应用3：B树构建字典
- 应用4：范围快速查询
往期链接
| 01 数组 | 02 链表 | 03 栈 | 04 队列 | 05 二叉树 | 06 二叉搜索树 | 07 AVL树 | 08 红黑树 |
|---|
09 B树(B-tree)
S1 说明
B树是一种自平衡的树数据结构，它的主要特点是：
- 多路搜索树：B树的每个节点可以有多个子节点，而不是二叉树的两个子节点。每个节点可以存储多个键值。
- 平衡性：B树的所有叶子节点都在同一层级，保证了树的高度尽可能低，从而提高了查找效率。
- 节点的填充因子：每个节点的键值数量在一定范围内，通常是 [⌈m/2⌉, m-1]，其中 m 是树的最大度数（每个节点的最大子节点数量）。⌈m/2⌉ 为m/2向上取整。
- 插入与删除：B树支持高效的插入和删除操作，保持树的平衡性。
B树的实际应用
- 数据库索引：B树常用于数据库管理系统中的索引，因为它们可以有效处理大量数据的存储和检索。
- 文件系统：许多现代文件系统使用 B树来管理文件的元数据，以支持快速的查找和插入。
- 内存管理：B树可以用于动态内存分配中的分区管理，保持内存块的有序性。
- 网络路由表：在网络路由中，B树可以用来存储和快速查找路由信息。
S2 示例
import matplotlib.pyplot as pltclass BTreeNode:def __init__(self, t, leaf=True):self.t = t # 最小度数self.keys = [] # 存储键值self.children = [] # 存储子节点self.leaf = leaf # 是否为叶子节点class BTree:def __init__(self, t):self.root = BTreeNode(t) # 创建根节点self.t = t # 设置B树的最小度数def insert(self, k):root = self.root# 如果根节点已满，需要分裂if len(root.keys) == (2 * self.t) - 1:temp = BTreeNode(self.t, False)self.root = temptemp.children.insert(0, root)self.split_child(temp, 0)self.insert_non_full(temp, k)else:self.insert_non_full(root, k)def insert_non_full(self, x, k):i = len(x.keys) - 1if x.leaf:# 如果是叶子节点，直接插入键值x.keys.append(None)while i >= 0 and k < x.keys[i]:x.keys[i + 1] = x.keys[i]i -= 1x.keys[i + 1] = kelse:# 如果不是叶子节点，找到合适的子节点进行插入while i >= 0 and k < x.keys[i]:i -= 1i += 1if len(x.children[i].keys) == (2 * self.t) - 1:# 如果子节点已满，需要先分裂self.split_child(x, i)if k > x.keys[i]:i += 1self.insert_non_full(x.children[i], k)def split_child(self, x, i):t = self.ty = x.children[i]z = BTreeNode(t, y.leaf)x.children.insert(i + 1, z)x.keys.insert(i, y.keys[t - 1])z.keys = y.keys[t: (2 * t) - 1]y.keys = y.keys[0: t - 1]if not y.leaf:z.children = y.children[t: 2 * t]y.children = y.children[0: t]def visualize(self):fig, ax = plt.subplots(figsize=(12, 8))self._draw_tree(self.root, ax, 0, 0, 100)ax.axis('off')plt.show()def _draw_tree(self, node, ax, x, y, width):if node:node_text = ', '.join(map(str, node.keys))ax.text(x, y, node_text