B树与B+树
外观
B树与B+树是计算机科学中用于组织大量数据的自平衡树数据结构,广泛应用于数据库和文件系统。它们通过保持平衡和优化磁盘I/O操作来提高查询效率。
概述[编辑 | 编辑源代码]
B树(B-Tree)和B+树(B+ Tree)是多路平衡查找树的两种变体,设计用于减少磁盘访问次数。它们的主要区别在于数据存储方式和查询性能优化:
- B树:所有节点存储数据,键值分散在各层节点中。
- B+树:仅叶子节点存储数据,非叶子节点作为索引,且叶子节点通过指针连接。
B树[编辑 | 编辑源代码]
定义与特性[编辑 | 编辑源代码]
B树是满足以下条件的m阶树:
- 每个节点最多有m个子节点
- 除根节点外,每个非叶子节点至少有⌈m/2⌉个子节点
- 根节点至少有2个子节点(除非它是叶子节点)
- 所有叶子节点位于同一层
数学表达式:对于包含n个键的节点,有个子指针,且
结构示例[编辑 | 编辑源代码]
操作[编辑 | 编辑源代码]
查找[编辑 | 编辑源代码]
从根节点开始,按键值范围选择子节点递归查找。
插入[编辑 | 编辑源代码]
可能导致节点分裂: 1. 找到合适叶子节点插入 2. 若节点键数超过m-1,则分裂为两个节点,中间键提升到父节点
删除[编辑 | 编辑源代码]
可能导致节点合并: 1. 删除键后若节点键数低于⌈m/2⌉-1 2. 向兄弟节点借键或与兄弟节点合并
B+树[编辑 | 编辑源代码]
核心特征[编辑 | 编辑源代码]
1. 非叶子节点仅存储索引(键值) 2. 所有数据存储在叶子节点 3. 叶子节点通过指针形成链表 4. 查询必须到达叶子节点
结构优势[编辑 | 编辑源代码]
与B树对比[编辑 | 编辑源代码]
特性 | B树 | B+树 |
---|---|---|
数据存储位置 | 所有节点 | 仅叶子节点 |
查询性能 | 可能提前终止 | 必须到叶子节点 |
范围查询效率 | 低 | 高(链表结构) |
空间利用率 | 较低 | 较高 |
代码实现示例[编辑 | 编辑源代码]
以下是B+树插入操作的Python简化实现:
class BPlusTreeNode:
def __init__(self, is_leaf=False):
self.keys = []
self.children = []
self.is_leaf = is_leaf
self.next_leaf = None # 仅用于叶子节点
class BPlusTree:
def __init__(self, order):
self.root = BPlusTreeNode(is_leaf=True)
self.order = order # 最大子节点数
def insert(self, key, value):
node = self._find_leaf(key)
self._insert_into_leaf(node, key, value)
if len(node.keys) > self.order - 1:
self._split_leaf(node)
def _find_leaf(self, key):
current = self.root
while not current.is_leaf:
# 找到第一个大于key的位置
i = 0
while i < len(current.keys) and key >= current.keys[i]:
i += 1
current = current.children[i]
return current
# 其他方法实现...
实际应用[编辑 | 编辑源代码]
数据库索引:MySQL的InnoDB引擎使用B+树作为主键索引结构,因为: 1. 减少磁盘I/O(3-4层树可存储数百万数据) 2. 范围查询高效(通过叶子节点链表) 3. 全表扫描只需遍历叶子节点链
文件系统:NTFS、ReiserFS等使用B+树变种管理文件元数据。
复杂度分析[编辑 | 编辑源代码]
对于包含N个元素的m阶B树/B+树:
- 查找/插入/删除:
- 空间:
进阶话题[编辑 | 编辑源代码]
- B*树:在节点分裂前尝试重新分配键给兄弟节点
- 前缀压缩:优化键的存储方式
- 并发控制:B-link树等变种支持高并发操作