B+树与B树的核心差异是什么 为何B+树更适合作为数据库索引的底层结构

一、开始了解B树和B+树

在数据库的世界里，索引就像是一本书的目录，能让我们快速找到想要的数据。而B树和B+树就是构建这个目录的两种“工具”。要明白它们的核心差异以及为啥B+树更适合当数据库索引的底层结构，咱得先知道它们各自是啥样的。

1.1 B树

想象一下，B树就像是一棵大树，每个节点就像大树的树枝，上面挂着一些数据。这些树枝（节点）可以有多个分叉，每个分叉又连着其他节点。B树的特点是，每个节点既存数据，又存指向其他节点的指针。比如说，有一个简单的B树，它的每个节点最多能存3个数据，现在有一组数据：10、20、30、40、50、60。当我们把这些数据插入到B树里时，B树会根据一定的规则把它们分配到不同的节点上。

以下是用Python语言模拟B树插入数据的示例：

# Python技术栈
# 定义B树节点类
class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []

# 定义B树类
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.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) - 1
        if x.leaf:
            x.keys.append(None)
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self.insert_non_full(x.child[i], k)

    def split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t:]
        y.keys = y.keys[:t - 1]
        if not y.leaf:
            z.child = y.child[t:]
            y.child = y.child[:t]

# 创建一个B树实例，每个节点最多存3个数据
b_tree = BTree(2)
data = [10, 20, 30, 40, 50, 60]
for num in data:
    b_tree.insert(num)

1.2 B+树

B+树和B树有点像，但也有不同。B+树的所有数据都存放在叶子节点上，非叶子节点只存索引信息（也就是指向其他节点的指针）。还是用上面那组数据10、20、30、40、50、60，插入到B+树里时，数据都会被放到最底层的叶子节点上，非叶子节点只起到引导我们找到对应叶子节点的作用。

以下是用Python语言模拟B+树插入数据的示例：

# Python技术栈
# 定义B+树节点类
class BPlusTreeNode:
    def __init__(self, is_leaf=False):
        self.is_leaf = is_leaf
        self.keys = []
        self.child = []
        self.next = None

# 定义B+树类
class BPlusTree:
    def __init__(self, degree):
        self.root = BPlusTreeNode(True)
        self.degree = degree

    def insert(self, key):
        root = self.root
        if len(root.keys) == (2 * self.degree) - 1:
            new_root = BPlusTreeNode()
            self.root = new_root
            new_root.child.append(root)
            self.split_child(new_root, 0)
            self.insert_non_full(new_root, key)
        else:
            self.insert_non_full(root, key)

    def insert_non_full(self, node, key):
        i = len(node.keys) - 1
        if node.is_leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.child[i].keys) == (2 * self.degree) - 1:
                self.split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self.insert_non_full(node.child[i], key)

    def split_child(self, parent, index):
        degree = self.degree
        child = parent.child[index]
        new_node = BPlusTreeNode(child.is_leaf)
        parent.keys.insert(index, child.keys[degree - 1])
        parent.child.insert(index + 1, new_node)
        new_node.keys = child.keys[degree:]
        child.keys = child.keys[:degree - 1]
        if not child.is_leaf:
            new_node.child = child.child[degree:]
            child.child = child.child[:degree]
        else:
            new_node.next = child.next
            child.next = new_node

# 创建一个B+树实例，每个节点最多存3个数据
b_plus_tree = BPlusTree(2)
data = [10, 20, 30, 40, 50, 60]
for num in data:
    b_plus_tree.insert(num)

二、B+树与B树的核心差异

2.1 数据存储位置不同

B树的每个节点都可以存数据，而非叶子节点除了存数据还存指针。就像前面说的B树示例，数据分散在各个节点上。而B+树只有叶子节点存数据，非叶子节点只存索引。这就好比B树是把书的内容分散放在不同的书架层，而B+树是把书的内容都放在最底层，上面的层只放指引我们去底层书架的标签。

2.2 节点关系不同

B树的节点之间没有特定的顺序关系，查找数据时可能需要在不同的节点之间跳来跳去。而B+树的叶子节点之间是有顺序的，它们通过指针相连，形成一个有序链表。比如我们要查找一个范围的数据，在B+树里可以沿着叶子节点的链表依次查找，而在B树里可能就需要多次在不同节点间跳转，效率就没那么高。

2.3 查找方式不同

在B树中，查找一个数据可能在任何一个节点找到。因为数据分散在各个节点，所以查找时需要在不同层次的节点间进行比较。而在B+树中，查找数据必须到叶子节点才能找到，非叶子节点只是引导我们找到对应的叶子节点。例如，我们要查找数字30，在B树中可能在某个中间节点就找到了，而在B+树中必须到叶子节点才能找到。

三、为何B+树更适合作为数据库索引的底层结构

3.1 范围查询更高效

在数据库中，经常会有范围查询的需求，比如查询年龄在20到30岁之间的用户。由于B+树的叶子节点是有序的，并且通过指针相连，我们可以从起始的叶子节点开始，沿着链表依次查找，直到找到满足条件的所有数据。而B树因为节点之间没有这种有序链表的关系，范围查询时就需要多次在不同节点间跳转，效率相对较低。

3.2 磁盘读写更优化

数据库的数据通常存放在磁盘上，磁盘读写是比较耗时的操作。B+树的非叶子节点只存索引信息，不存数据，这样每个节点可以存放更多的索引，树的高度相对较低。每次查询时，需要访问的磁盘块数就会减少，从而减少了磁盘读写次数，提高了查询效率。而B树因为每个节点都存数据，节点所能存放的索引数量相对较少，树的高度可能会更高，磁盘读写次数也就更多。

3.3 插入和删除操作更稳定

B+树的插入和删除操作主要在叶子节点进行，不会影响非叶子节点的结构，所以操作相对稳定。而B树在插入和删除数据时，可能会导致节点的分裂和合并，影响整个树的结构，操作复杂度相对较高。

四、应用场景

4.1 B树的应用场景

B树适用于一些对随机查找性能要求较高，且数据更新不频繁的场景。比如文件系统，文件系统需要快速定位文件的位置，B树可以满足这种需求。

4.2 B+树的应用场景

B+树广泛应用于数据库系统，如MySQL、Oracle等。因为数据库经常需要进行范围查询、插入和删除操作，B+树的特性正好满足这些需求。

五、技术优缺点

5.1 B树的优缺点

优点

• 随机查找性能较好，能快速定位到数据。
• 适用于数据更新不频繁的场景。

缺点

• 范围查询效率较低。
• 插入和删除操作可能会导致节点的分裂和合并，影响性能。

5.2 B+树的优缺点

优点

• 范围查询效率高，适合数据库的范围查询需求。
• 磁盘读写优化，减少了磁盘读写次数。
• 插入和删除操作稳定，不会影响非叶子节点的结构。

缺点

• 由于数据都存放在叶子节点，插入和删除操作可能会导致叶子节点的分裂和合并，需要一定的维护成本。

六、注意事项

6.1 B树的注意事项

在使用B树时，要注意数据的更新频率。如果数据更新频繁，可能会导致节点的频繁分裂和合并，影响性能。同时，要合理设置B树的节点大小，以平衡磁盘读写和内存使用。

6.2 B+树的注意事项

在使用B+树时，要注意叶子节点的分裂和合并操作。当数据插入或删除导致叶子节点满或空时，需要进行相应的处理，以保证B+树的结构稳定。

七、文章总结

B树和B+树都是非常重要的数据结构，在不同的场景下有各自的优势。B树适合随机查找且数据更新不频繁的场景，而B+树因为其范围查询高效、磁盘读写优化和插入删除操作稳定等特点，更适合作为数据库索引的底层结构。在实际应用中，我们要根据具体的需求选择合适的数据结构，以提高系统的性能。