B-Tree Python代码实现

以下是一个简单的 B-Tree Python 代码实现：

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 x is not None:
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 __str__(self):
r = self.root
return self.traverse(r)

def traverse(self, x):
# 这里是中序遍历
result = []
for i in range(len(x.keys)):
if not x.leaf:
result.extend(self.traverse(x.child[i]))
result.append(x.keys[i])
if not x.leaf:
result.extend(self.traverse(x.child[-1]))
return result

# 示例
tree = BTree(t=3)
for i in range(10):
tree.insert(i)
print(tree) # 输出 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]