B+ 树和B树有什么区别，数据库索引为什么用B+树

本文主要是介绍B+ 树和B树有什么区别，数据库索引为什么用B+树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B树（B-tree）和B+树（B+ tree）是两种常见的自平衡搜索树数据结构，通常用于数据库索引以及文件系统等领域。

它们在设计上有一些区别，下面是它们的主要差异以及为什么数据库索引通常使用B+树：

结构差异：

B树：B树是一种平衡多路搜索树，其中每个节点包含一个有序数组。节点内的关键字按升序排列，并且每个节点通常有多个子节点。B树的特点是每个节点都包含数据，而不仅仅是叶子节点。

B+树：B+树也是一种平衡多路搜索树，与B树不同的是，B+树的非叶子节点只包含子节点的索引信息，而不包含数据。所有的关键字都在叶子节点上，叶子节点使用指针连接起来，形成一个有序链表。

查询效率：

由于B+树的所有关键字都在叶子节点上，查询时只需要遍历叶子节点，因此查询效率更稳定，且具有更好的局部性。

B树在查找时可能需要在内部节点和叶子节点之间进行多次跳转，因此其查询效率相对于B+树可能会有些许下降。

范围查询：

B+树更适合范围查询，因为在B+树中范围查询只需要遍历叶子节点上的链表即可，而在B树中可能需要进行多次跳转。
适用场景：

B树通常用于内存受限的环境或者需要随机访问的场景，例如文件系统索引。
B+树则更适合用于数据库索引，因为数据库系统通常需要大量的范围查询和顺序遍历，而B+树在这些操作上具有优势。

在数据库中，B+树索引相对于B树索引更受欢迎的原因主要有以下几点：

B+树的叶子节点构成了有序链表，方便范围查询和顺序遍历。
B+树的内部节点不包含实际数据，可以容纳更多的索引信息，减少树的高度，提高查询效率。
B+树的叶子节点通常更大，包含更多的关键字，从而减少树的深度，加速检索速度。
B+树的稳定性更高，有利于减少磁盘IO次数，提高查询性能。

使用Python实现一个B+树参考代码：

class Node:def __init__(self, leaf=False):self.keys = []self.children = []self.leaf = leafself.next_leaf = Noneclass BPlusTree:def __init__(self, degree):self.root = Node(leaf=True)self.degree = degreedef insert(self, key):if key in self.root.keys:returnif len(self.root.keys) == (2 * self.degree) - 1:new_root = Node()new_root.children.append(self.root)self.split(new_root, 0)self.root = new_rootself._insert(self.root, key)def _insert(self, node, key):if node.leaf:node.keys.append(key)node.keys.sort()else:index = len(node.keys) - 1while index >= 0 and key < node.keys[index]:index -= 1index += 1if len(node.children[index].keys) == (2 * self.degree) - 1:self.split(node, index)if key > node.keys[index]:index += 1self._insert(node.children[index], key)def split(self, parent, index):new_node = Node(leaf=self.root.leaf)node = parent.children[index]new_node.keys = node.keys[self.degree:]node.keys = node.keys[:self.degree]if not node.leaf:new_node.children = node.children[self.degree:]node.children = node.children[:self.degree]parent.keys.insert(index, new_node.keys[0])parent.children.insert(index + 1, new_node)def search(self, key):return self._search(self.root, key)def _search(self, node, key):if key in node.keys:return Trueelif node.leaf:return Falseelse:index = 0while index < len(node.keys) and key > node.keys[index]:index += 1return self._search(node.children[index], key)# Example usage:
tree = BPlusTree(2)
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(20)
tree.insert(25)print(tree.search(15))  # Output: True
print(tree.search(30))  # Output: False