B+树从零实现（Python语言手把手教你构建高效数据库索引结构）

什么是B+树？

B+树是一种自平衡的树数据结构，所有数据都存储在叶子节点中，而非叶子节点仅作为索引使用。这种设计使得B+树特别适合磁盘I/O操作，因此被广泛应用于数据库索引B+树的实现中。

B+树的关键特性

• 所有叶子节点位于同一层
• 非叶子节点只存储键值（key），不存储实际数据
• 叶子节点通过指针连接成链表，便于范围查询
• 每个节点最多包含 m 个子节点（m 称为阶数）

Python实现B+树

下面我们用Python B+树的方式逐步构建这个数据结构。我们将实现插入、查找和遍历等基本功能。

1. 定义节点类

class Node:    def __init__(self, leaf=False):        self.leaf = leaf          # 是否为叶子节点        self.keys = []            # 存储键值        self.children = []        # 存储子节点（非叶子）或数据（叶子）        self.next = None          # 叶子节点的下一个节点（用于链表）

2. 定义B+树主类

class BPlusTree:    def __init__(self, degree=3):        self.root = Node(leaf=True)        self.degree = degree  # 阶数，即每个节点最多有 degree 个子节点

3. 插入操作

插入是B+树中最复杂的操作，需要处理节点分裂。我们先实现辅助函数，再完成主插入逻辑。

def insert(self, key, value):    root = self.root    # 如果根节点已满，则创建新根    if len(root.keys) == self.degree - 1:        new_root = Node()        new_root.children.append(self.root)        self._split_child(new_root, 0)        self.root = new_root    self._insert_non_full(self.root, key, value)def _insert_non_full(self, node, key, value):    i = len(node.keys) - 1    if node.leaf:        # 在叶子节点中插入        node.keys.append(None)        node.children.append(None)        while i >= 0 and key < node.keys[i]:            node.keys[i + 1] = node.keys[i]            node.children[i + 1] = node.children[i]            i -= 1        node.keys[i + 1] = key        node.children[i + 1] = value    else:        # 找到合适的子树        while i >= 0 and key < node.keys[i]:            i -= 1        i += 1        if len(node.children[i].keys) == self.degree - 1:            self._split_child(node, i)            if key > node.keys[i]:                i += 1        self._insert_non_full(node.children[i], key, value)def _split_child(self, parent, index):    degree = self.degree    child = parent.children[index]    new_child = Node(leaf=child.leaf)        # 将后半部分移到新节点    parent.keys.insert(index, child.keys[degree // 2])    parent.children.insert(index + 1, new_child)        new_child.keys = child.keys[degree // 2 + 1:]    new_child.children = child.children[degree // 2 + 1:]    child.keys = child.keys[:degree // 2]    child.children = child.children[:degree // 2 + (0 if child.leaf else 1)]        # 连接叶子节点    if child.leaf:        new_child.next = child.next        child.next = new_child

4. 查找操作

def search(self, key, node=None):    if node is None:        node = self.root    i = 0    while i < len(node.keys) and key > node.keys[i]:        i += 1    if node.leaf:        if i < len(node.keys) and node.keys[i] == key:            return node.children[i]        else:            return None    else:        return self.search(key, node.children[i])

为什么B+树适合数据库索引？

B+树具有高度平衡、磁盘友好、支持高效范围查询等优点，使其成为构建数据库索引B+树的理想选择。通过上面的B+树数据结构实现，你可以更深入理解数据库底层的工作机制。

总结

本文详细讲解了如何用Python语言实现一个完整的B+树，包括节点定义、插入、查找等核心操作。通过动手实践，你不仅能掌握B+树实现的技巧，还能加深对数据库索引机制的理解。希望这篇教程对你有所帮助！