编辑“︁B+树索引结构”︁（章节）

= B+树索引结构 =

== 简介 ==  
'''B+树索引结构'''是数据库系统中广泛使用的一种索引技术，用于高效地存储、检索和管理数据。它是B树的一种变体，特别适合磁盘存储系统，因为它最大限度地减少了磁盘I/O操作。B+树的主要特点包括：
* 所有数据都存储在叶子节点中，内部节点仅包含键值用于导航。
* 叶子节点通过指针连接，支持高效的范围查询。
* 树的高度平衡，确保操作时间复杂度为O(log n)。

B+树是关系型数据库（如MySQL、PostgreSQL）默认的索引实现方式，尤其适用于范围查询和排序操作。

== 结构解析 ==  
=== 节点组成 ===  
B+树的节点分为两种：
* '''内部节点（非叶子节点）'''：存储键值和子节点指针，不存储实际数据。
* '''叶子节点'''：存储键值和对应的数据记录（或数据指针），并通过链表连接相邻叶子节点。

<mermaid>
graph TD
    A[内部节点: 键1, 键2] --> B[子节点1]
    A --> C[子节点2]
    D[叶子节点: 键1→数据1, 键2→数据2] --> E[下一个叶子节点]
</mermaid>

=== 数学特性 ===  
B+树的阶数（m）决定其分支数量：
* 内部节点最多有m个子节点，最少有<math>\lceil m/2 \rceil</math>个子节点（根节点除外）。
* 叶子节点最多存储m-1个键值，最少存储<math>\lfloor (m-1)/2 \rfloor</math>个键值。

== 操作详解 ==  
=== 查找 ===  
从根节点开始，逐层比较键值，直到找到目标叶子节点。  
'''示例流程'''：  
1. 比较根节点的键值，确定下一层子节点。  
2. 重复步骤1，直到到达叶子节点。  
3. 在叶子节点中线性或二分查找目标键值。

=== 插入 ===  
插入可能导致节点分裂：  
1. 找到目标叶子节点并插入键值。  
2. 若叶子节点已满，则分裂为两个节点，并将中间键值提升到父节点。  
3. 若父节点已满，递归分裂直至根节点。

<mermaid>
graph LR
    A[叶子节点: 1, 2, 3, 4] -- 插入5 --> B[分裂为 1,2 和 3,4,5]
    B -- 提升3 --> C[父节点新增键3]
</mermaid>

=== 删除 ===  
删除可能导致节点合并：  
1. 从叶子节点删除键值。  
2. 若节点键值数低于最小值，尝试从兄弟节点借键或合并节点。  
3. 递归调整父节点直至根节点。

== 代码示例 ==  
以下是Python实现的简化B+树查找逻辑：  
<syntaxhighlight lang="python">
class BPlusTreeNode:
    def __init__(self, is_leaf=False):
        self.keys = []
        self.children = []
        self.is_leaf = is_leaf
        self.next_leaf = None  # 仅叶子节点使用

def search(node, key):
    while not node.is_leaf:
        # 找到第一个大于等于key的子节点
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:
            i += 1
        node = node.children[i]
    # 在叶子节点中查找
    for i, k in enumerate(node.keys):
        if k == key:
            return f"Found key {key} at position {i}"
    return "Key not found"

# 示例树结构
root = BPlusTreeNode(is_leaf=False)
root.keys = [10, 20]
root.children = [
    BPlusTreeNode(is_leaf=True, keys=[5, 7, 10]),
    BPlusTreeNode(is_leaf=True, keys=[15, 20])
]
root.children[0].next_leaf = root.children[1]

print(search(root, 15))  # 输出: Found key 15 at position 0
</syntaxhighlight>

== 实际应用 ==  
=== 数据库索引 ===  
MySQL的InnoDB引擎使用B+树作为主键索引（聚簇索引）：
* 叶子节点直接存储行数据，非叶子节点存储主键值和页指针。
* 范围查询如`SELECT * FROM users WHERE id BETWEEN 10 AND 20`只需遍历叶子节点链表。

=== 文件系统 ===  
如NTFS、ReiserFS使用B+树管理文件块，支持快速定位大文件中的任意片段。

== 对比其他结构 ==  
{| class="wikitable"
|-
! 特性 !! B+树 !! B树 !! 哈希索引
|-
| 范围查询效率 || 高（叶子节点链表） || 中 || 低
|-
| 磁盘I/O优化 || 最优 || 优 || 差
|-
| 插入/删除复杂度 || O(log n) || O(log n) || O(1)
|}

== 总结 ==  
B+树因其平衡性、高扇出和顺序访问优势，成为数据库索引的首选结构。初学者应重点理解：
* 节点分裂/合并的平衡机制。
* 叶子节点链表对范围查询的优化。
* 与B树的区别（数据仅存于叶子节点）。

[[Category:计算机科学]]
[[Category:数据库与信息系统]]
[[Category:数据库索引与查询优化]]