B+树磁盘插入实现：多次分裂后树结构未更新求助

我用Python实现了磁盘版B+树的插入逻辑，其中_split_leaf_node方法负责处理叶节点分裂。测试时发现，当插入操作触发多次节点分裂后，树结构并没有正确更新——调试时能看到父节点的keys列表已经更新，分裂步骤执行正常，且变更已写回磁盘，但第二次及之后的分裂没有生效。

调用分裂方法的_insert_recursive代码 #

def _insert_recursive(self, node_addr: Address, parent_addr: Address, key: KT, value: VT):
    node = get_node(node_addr)
    node.parent_addr = parent_addr

    if node.is_leaf:
        node.insert_data(key, value)
        node.keys, node.data = self._sort_keys_data(node.keys, node.data)

        if len(node.keys) > self.L:
            # If the leaf node overflows, split it
            self._split_leaf_node(node)
        node.write_back()  # Update changes made to the leaf node

    else:
        # Finding the appropriate child node to insert the key
        idx = node.find_idx(key)
        child_addr = node.children_addrs[idx]
        self._insert_recursive(child_addr, node_addr, key, value)
        node.write_back()  # Update changes made to the internal node

_split_leaf_node方法代码 #

def _split_leaf_node(self, node: BTreeNode) -> None:
    mid = len(node.keys) // 2

    # Create a new leaf node
    new_node = BTreeNode(DISK.new(), node.parent_addr, None, True)
    new_node.keys = node.keys[mid:]
    new_node.data = node.data[mid:]

    # Update the node's keys and data
    node.keys = node.keys[:mid]
    node.data = node.data[:mid]

    # Update the parent's children addresses
    if node.parent_addr is not None:
        parent_node = get_node(node.parent_addr)
        idx = parent_node.children_addrs.index(node.my_addr)
        parent_node.children_addrs.insert(idx + 1, new_node.my_addr)
        parent_node.keys.insert(idx, new_node.keys[0])  # Update the keys in the parent node

        node.index_in_parent = idx
        new_node.index_in_parent = idx + 1
        DISK.write(parent_node.my_addr,parent_node)

        if len(parent_node.keys) > self.M - 1:
            self._split_internal(parent_node, node.parent_addr)

        # Update the index_in_parent of node and new_node in the new parent node
        if parent_node.parent_addr is not None:
            new_parent_node = get_node(parent_node.parent_addr)
            idx = new_parent_node.children_addrs.index(parent_node.my_addr)
            new_parent_node.children_addrs.insert(idx + 1, new_node.my_addr)
            new_parent_node.keys.insert(idx, parent_node.keys[-1])

            node.index_in_parent = idx
            new_node.index_in_parent = idx + 1
            new_parent_node.write_back()
            node.write_back()
            new_node.write_back()

    # Update the root node if necessary
    if node.my_addr == self.root_addr:
        root = BTreeNode(DISK.new(), None, None, False)
        root.keys = [new_node.keys[0]]  # Assign the mid key to the new root
        root.children_addrs = [node.my_addr, new_node.my_addr]  # Children are the split nodes
        node.index_in_parent = root.children_addrs.index(node.my_addr)
        new_node.index_in_parent = root.children_addrs.index(new_node.my_addr)
        node.parent_addr = root.my_addr
        new_node.parent_addr = root.my_addr
        self.root_addr = root.my_addr

        node.write_back()
        new_node.write_back()
        root.write_back()
    else:
        node.write_back()
        new_node.write_back()

测试用例 #

def test_big_tree():
    M = 3
    L = 3
    btree = BTree(M, L)
    for i in range(6):
        btree.insert(i, str(i))
    for i in range(6):
        assert btree.find(i) == str(i)

可能的问题原因分析 #

1. 跨层级修改祖父节点的逻辑完全错误
   在_split_leaf_node中，父节点溢出触发_split_internal后，你手动添加了一段更新祖父节点的代码，这违反了B+树自底向上的分裂规则：父节点的分裂应该由_split_internal自行处理，不需要手动把新叶节点直接插入到祖父节点中，这段代码会直接破坏树的层级结构。

2. 递归返回后的节点写回覆盖了正确修改
   在_insert_recursive的非叶节点分支中，递归调用后直接执行node.write_back()，但此时父节点可能已经被分裂逻辑修改并写回过磁盘。你在递归开始时读取的node是内存中的旧对象，写回操作会把旧数据覆盖掉磁盘上的正确更新。

3. 分裂逻辑冗余导致节点状态混乱
   _split_leaf_node中多处重复执行write_back，且在父节点处理后额外修改祖父节点的操作，会导致节点的父子关系、键值对出现不一致，后续插入时无法正确找到目标节点。

4. 父节点分裂后的状态未同步
   当_split_internal执行父节点分裂后，原父节点的父节点（祖父节点）的更新应该由_split_internal递归触发，而不是在_split_leaf_node中手动处理，这会导致祖父节点的键和子节点列表被错误修改。

内容的提问来源于stack exchange，提问作者Faren