DS B-树构建及查找

### B-Tree 数据结构概述

B-树是一种自平衡的树形数据结构，允许快速检索、顺序访问、插入和删除操作。这种树的特点在于每个节点可以有多个子节点，并且能够存储多个键值。这使得B-树非常适合用于文件系统以及数据库管理系统中的磁盘读写操作。

#### 特性描述

- 所有的叶子节点都位于同一层；
- 每个内部节点至少包含两个孩子（除了根节点外）；
- 如果不是根节点，则每个节点最多拥有 \(M\) 个孩子，其中 \(M\) 是预先定义的最大度数；
- 对于非叶节点而言，其关键字数量介于 \(\lceil M/2\rceil - 1\) 到 \(M-1\) 之间[^4]；

### 构建 B-Tree 的过程

创建一个新的B-树通常从一个空的根开始。当向树中插入新元素时：

- 若当前节点未满，则直接将该元素按序插入到适当位置；
- 这种方式一直持续直到找到合适的位置为止或者到达新的根部形成更高一层的层次结构[^5]。

class Node:
    def __init__(self, leaf=False):
        self.keys = []
        self.children = []
        self.leaf = leaf


def insert(tree, key):
    root = tree.root
    
    if not root:
        tree.root = Node(True)
        tree.root.keys.append(key)
    
    elif len(root.keys) == (2 * t) - 1:  
        s = Node()
        tree.root = s
        s.children.insert(0, root)
        split_child(s, 0)
        insert_non_full(s, key)

    else:
        insert_non_full(root, key)


def split_child(x, i): ...

上述代码片段展示了如何初始化节点并处理插入逻辑的一部分。完整的`split_child()`函数负责分割过载的节点以维持B-树属性[^6]。

### 查找操作流程

为了在一个已知的B-树内寻找特定的目标值，可以从根节点出发逐步向下遍历直至遇到相应的叶子节点或确认目标不存在于树中。具体做法如下：

- 当抵达最底层仍未发现匹配对象即表示查找失败[^7]。

def search(node, k):
    i = 0
    while i < len(node.keys) and k > node.keys[i]:
        i += 1
        
    if i < len(node.keys) and k == node.keys[i]:
        return True
    
    elif node.leaf:
        return False
    
    else:
        return search(node.children[i], k)

这段Python代码实现了基本的B-树查找功能，通过递归的方式沿着路径追踪直到定位所需记录或是得出结论说该项不在集合之内[^8]。