跳转到内容

B树与B+树

来自代码酷


B树与B+树是计算机科学中用于组织大量数据的自平衡树数据结构,广泛应用于数据库和文件系统。它们通过保持平衡和优化磁盘I/O操作来提高查询效率。

概述[编辑 | 编辑源代码]

B树(B-Tree)和B+树(B+ Tree)是多路平衡查找树的两种变体,设计用于减少磁盘访问次数。它们的主要区别在于数据存储方式和查询性能优化:

  • B树:所有节点存储数据,键值分散在各层节点中。
  • B+树:仅叶子节点存储数据,非叶子节点作为索引,且叶子节点通过指针连接。

B树[编辑 | 编辑源代码]

定义与特性[编辑 | 编辑源代码]

B树是满足以下条件的m阶树:

  1. 每个节点最多有m个子节点
  2. 除根节点外,每个非叶子节点至少有⌈m/2⌉个子节点
  3. 根节点至少有2个子节点(除非它是叶子节点)
  4. 所有叶子节点位于同一层

数学表达式:对于包含n个键的节点,有n+1个子指针,且m/21nm1

结构示例[编辑 | 编辑源代码]

graph TD A[50, 100] --> B[20, 30] A --> C[70, 80] A --> D[110, 120] B --> E[10] B --> F[25] B --> G[35]

操作[编辑 | 编辑源代码]

查找[编辑 | 编辑源代码]

从根节点开始,按键值范围选择子节点递归查找。

插入[编辑 | 编辑源代码]

可能导致节点分裂: 1. 找到合适叶子节点插入 2. 若节点键数超过m-1,则分裂为两个节点,中间键提升到父节点

删除[编辑 | 编辑源代码]

可能导致节点合并: 1. 删除键后若节点键数低于⌈m/2⌉-1 2. 向兄弟节点借键或与兄弟节点合并

B+树[编辑 | 编辑源代码]

核心特征[编辑 | 编辑源代码]

1. 非叶子节点仅存储索引(键值) 2. 所有数据存储在叶子节点 3. 叶子节点通过指针形成链表 4. 查询必须到达叶子节点

结构优势[编辑 | 编辑源代码]

graph TD A[50, 100] --> B[20, 30] A --> C[70, 80] A --> D[110] B --> E[10, 15] B --> F[20, 25] B --> G[30, 35] E --> H[...] F --> I[...] G --> J[...] linkStyle 4,5,6 stroke:blue,stroke-width:1px;

与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+树:

  • 查找/插入/删除:O(logmN)
  • 空间:O(N)

进阶话题[编辑 | 编辑源代码]

  • B*树:在节点分裂前尝试重新分配键给兄弟节点
  • 前缀压缩:优化键的存储方式
  • 并发控制:B-link树等变种支持高并发操作

模板:数据结构导航