B+树python代码

B+树是一种常用的数据结构，用于在数据库和文件系统中进行索引操作。下面是一个简单的B+树的Python代码示例：

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.values = []
        self.next = None

class BPlusTree:
    def __init__(self, degree):
        self.root = BPlusTreeNode(True)
        self.degree = degree

    def insert(self, key, value):
        if key in self.keys:
            # 如果键已存在，则更新对应的值
            index = self.keys.index(key)
            self.values[index] = value
        else:
            if len(self.keys) == 0:
                # 如果树为空，则直接插入键值对
                self.keys.append(key)
                self.values.append(value)
            else:
                # 否则，递归地插入键值对
                if len(self.keys) == 2 * self.degree - 1:
                    # 如果当前节点已满，则进行分裂
                    new_root = BPlusTreeNode()
                    new_root.children.append(self.root)
                    self.root = new_root
                    self.split_child(self.root, 0)

                self.insert_non_full(self.root, key, value)

    def insert_non_full(self, node, key, value):
        i = len(node.keys) - 1
        if node.leaf:
            # 如果是叶子节点，则直接插入键值对
            node.keys.append(None)
            node.values.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                node.values[i + 1] = node.values[i]
                i -= 1
            node.keys[i + 1] = key
            node.values[i + 1] = value
        else:
            # 如果是内部节点，则找到合适的子节点递归插入
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.degree - 1:
                # 如果子节点已满，则进行分裂
                self.split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self.insert_non_full(node.children[i], key, value)

    def split_child(self, parent, index):
        child = parent.children[index]
        new_child = BPlusTreeNode(child.leaf)
        parent.keys.insert(index, child.keys[self.degree - 1])
        parent.values.insert(index, child.values[self.degree - 1])
        parent.children.insert(index + 1, new_child)
        new_child.keys = child.keys[self.degree:]
        new_child.values = child.values[self.degree:]
        child.keys = child.keys[:self.degree - 1]
        child.values = child.values[:self.degree - 1]

    def search(self, key):
        return self.search_recursive(self.root, key)

    def search_recursive(self, node, key):
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            return node.values[i]
        elif node.leaf:
            return None
        else:
            return self.search_recursive(node.children[i], key)