b树（一篇文章带你理解）

一、引言

二、B树的基本定义

三、B树的性质与操作

1 查找操作

2 插入操作

3 删除操作

四、B树的应用场景

1 数据库索引

2 文件系统

3 网络路由表

五、哪些数据库系统不使用B树进行索引

1 列式数据库

2 图形数据库

3 内存数据库

4 NoSQL数据库

5 分布式数据库

六、总结

一、引言

在计算机科学中，B树是一种自平衡的树，它能够保持数据有序，其插入与删除操作都能在对数时间内完成。

B树在数据库和文件系统的实现中尤为关键，因为它们能高效地保持数据有序，同时允许对数级别的插入、删除和查找操作。

B树相对于二叉搜索树的优势在于，它可以有效地利用存储空间，特别是在磁盘或类似的直接存取辅助设备中。

二、B树的基本定义

B树是一种平衡的多路搜索树，它满足以下条件：

所有叶子节点位于同一层。
每个非叶子节点包含n个关键字（k1, k2, ..., kn），其中n满足ceil(m/2) <= n <= m-1。对于每个关键字ki，ki < ki+1。
非叶子节点的子树指针p1, p2, ..., pn。其中所有关键字ki，i的子树指针pi指向的子树中所有关键字的值均大于ki且小于ki+1。
非叶子节点的子树个数=关键字个数+1。
所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的节点是依次有序的。

其中，m是B树的阶数，它决定了树的最大和最小度数。一个m阶的B树，一个节点最多有m个子节点。

三、B树的性质与操作

B树作为一种自平衡树，其关键性质在于保持树的平衡，以保证查找、插入和删除操作的高效性。

1 查找操作

从根节点开始，根据键值比较进行路径选择，直到找到目标节点或到达叶子节点。B树的查找效率与树的高度相关，由于B树能够降低树的高度，因此查找效率较高。

从根节点开始搜索，找到合适的叶子节点进行插入。
如果插入后叶子节点关键字数不超过最大度数，则插入完成。
否则，需要分裂该叶子节点，并将中间关键字提升到父节点。
如果父节点也满了，则需要继续分裂并向上提升关键字，直到根节点或某个非满节点为止。
如果根节点也分裂了，则需要创建一个新的根节点，并将两个子树的根节点作为新根节点的子节点。

2 插入操作

当插入一个新元素时，首先找到合适的位置，如果节点未满，则直接插入；如果节点已满，则需要进行分裂操作，将节点中的部分元素移动到新的节点中，并更新父节点。

分裂操作可能导致父节点也满，此时需要递归地进行分裂和更新操作，直到根节点或某个非满节点为止。

从根节点开始搜索，找到包含要删除关键字的叶子节点。
如果该叶子节点的关键字数大于最小度数，则直接删除该关键字。
否则，需要从兄弟节点“借”一个关键字过来，或者与兄弟节点及父节点合并。
删除操作可能触发一系列的合并和调整操作，直到满足B树的性质为止

以下是B树插入操作的Python伪代码：

def insert(node, key):
    if node is None:
        return create_new_node(key)
    
    i = node.find_position(key)
    if key == node.keys[i]:
        return node  # Key already exists, no insertion
    
    if node.is_leaf():
        node.insert_non_full(i, key)
        if node.is_full():
            return split_node(node)
        else:
            return node
    else:
        child = node.children[i]
        child = insert(child, key)
        node.update_keys(i, child)
        if child is not None:
            return split_node(node) if node.is_full() else node
    
def split_node(node):
    t = node.degree  # Assume degree is set for the tree
    mid = t - 1
    new_node = create_new_node()
    new_node.keys = node.keys[mid:]
    new_node.children = node.children[mid+1:]
    node.keys = node.keys[:mid]
    node.children = node.children[:mid+1]
    new_node.children[-1] = None if node.is_leaf() else split_node(node.children[mid+1])
    node.parent = create_new_node() if node.parent is None else node.parent
    node.parent.keys.append(node.keys[mid])
    node.parent.children.append(new_node)
    return node.parent