pythonB-树代码

下面是一个简单的 Python 实现 B-树的代码：

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

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

    def search(self, k, x=None):
        if isinstance(x, BTreeNode):
            i = 0
            while i < len(x.keys) and k > x.keys[i]:
                i += 1
            if i < len(x.keys) and k == x.keys[i]:
                return (x, i)
            elif x.leaf:
                return None
            else:
                return self.search(k, x.child[i])
        else:
            return self.search(k, self.root)

    def insert(self, k):
        r = self.root
        if len(r.keys) == (2*self.t) - 1:
            s = BTreeNode()
            self.root = s
            s.child.insert(0, r)
            self._split_child(s, 0)
            self._insert_nonfull(s, k)
        else:
            self._insert_nonfull(r, k)

    def _insert_nonfull(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append(0)
            while i >= 0 and k < x.keys[i]:
                x.keys[i+1] = x.keys[i]
                i -= 1
            x.keys[i+1] = k
        else:
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2*self.t) - 1:
                self._split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self._insert_nonfull(x.child[i], k)

    def _split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i+1, z)
        x.keys.insert(i, y.keys[t-1])
        z.keys = y.keys[t:(2*t - 1)]
        y.keys = y.keys[0:(t-1)]
        if not y.leaf:
            z.child = y.child[t:(2*t)]
            y.child = y.child[0:(t-1)]

    def __repr__(self):
        return '<BTree:t='+str(self.t)+',root='+str(self.root)+'>'

这个实现中，`BTreeNode` 表示 B 树的节点，其中 `keys` 是节点中存储的关键字，`child` 是节点的子节点。`BTree` 表示整个 B 树，其中 `root` 是根节点，`t` 是 B 树的参数。

函数 `search` 可以在 B 树中查找关键字，函数 `insert` 可以插入新的关键字。函数 `_insert_nonfull` 是插入关键字的内部实现，函数 `_split_child` 是分裂节点的内部实现。