python实现B/B+树

python实现–顺序查找
python实现–折半查找
python实现–分块查找
python实现B/B+树

B树和B+树都是一种多路搜索树，用于对大量数据进行排序和查找。它们在数据库系统中被广泛应用，特别是用于构建索引结构。

B树（B-Tree）

B树，又称多路平衡查找树，B树中所有结点的孩子结点数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:
1）树中每个结点至多有m棵子树（即至多含有m-1个关键字）。
2）若根结点不是终端结点，则至少有两棵子树。
3）除根结点外的所有非叶结点至少有[m/2]棵子树（即至少含有[m/2]-1个关键字）
4）所有叶子节点都在同一层。
5)每个节点中的关键字按照升序排列。

B树的优点包括：
减少访问磁盘的次数：B树的每个节点可以存储更多的关键字，因此树的高度相对较低，从而减少了访问磁盘的次数。
适应不同的数据规模：B树可以根据数据规模动态调整节点大小，适应不同的数据规模。

B+树（B-Plus Tree）

B+树是在B树的基础上进行改进的一种树结构，它与B树的区别在于：

所有关键字都出现在叶子节点中，而非内部节点。
内部节点仅用于索引，不存储数据，叶子节点包含了所有数据项。

B+树的特点包括：
叶子节点形成了有序链表，可以支持范围查找和范围查询。
内部节点不存储数据，只存储索引，因此可以存储更多的关键字。
由于关键字只出现在叶子节点中，因此B+树的查找性能更加稳定。

B树和B+树的比较：
查询性能：B+树的查询性能通常优于B树，因为B+树的叶子节点形成了有序链表，可以支持范围查询操作。
范围查询：B+树更适合范围查询操作，而B树的查询效率相对较低。
数据存储：B+树的数据仅存储在叶子节点中，而B树的数据可能分布在所有节点中，因此B+树更适合磁盘存储，减少了节点的访问次数。
内部节点：B树的内部节点可能包含数据，而B+树的内部节点仅用于索引，不存储数据。

总结：
B树和B+树都是常用的多路搜索树结构，在数据库系统中广泛应用。它们都具有平衡性和多路性的特点，但在一些方面有所不同，因此在实际应用中需要根据具体需求选择合适的树结构。

算法实现

B树的实现思路
定义B树节点类：B树的节点需要存储关键字和子节点的信息。我们可以定义一个节点类，其中包含关键字列表和子节点列表。
插入操作：B树的插入操作需要保持树的平衡性。当插入一个关键字时，需要根据B树的特性将关键字插入到合适的位置，并可能进行节点的分裂和合并操作，以维持B树的平衡性。
删除操作：B树的删除操作也需要保持树的平衡性。当删除一个关键字时，需要根据B树的特性对节点进行合并和移动操作，以维持B树的平衡性。

class BTreeNode:def __init__(self, leaf=False):self.keys = []self.children = []self.leaf = leafclass BTree:def __init__(self, t):self.root = BTreeNode()self.t = tdef insert(self, key):if len(self.root.keys) == (2 * self.t) - 1:new_root = BTreeNode()new_root.children.append(self.root)self.split_child(new_root, 0)self.root = new_rootself._insert(self.root, key)def _insert(self, node, key):if node.leaf:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1node.keys.insert(i, key)else:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1if len(node.children[i].keys) == (2 * self.t) - 1:self.split_child(node, i)if key > node.keys[i]:i += 1self._insert(node.children[i], key)def split_child(self, parent, index):t = self.tchild = parent.children[index]new_child = BTreeNode(leaf=child.leaf)parent.keys.insert(index, child.keys[t - 1])parent.children.insert(index + 1, new_child)new_child.keys = child.keys[t:]child.keys = child.keys[:t - 1]if not child.leaf:new_child.children = child.children[t:]child.children = child.children[:t]def __str__(self):return self.print_tree(self.root)def print_tree(self, node, level=0):ret = ""if node:ret += self.print_tree(node.children[-1], level + 1)for i in range(len(node.keys) - 1, -1, -1):ret += "\n" + ("    " * level) + str(node.keys[i])ret += self.print_tree(node.children[i], level + 1)return ret# 测试
btree = BTree(2)
keys = [3, 7, 1, 4, 9, 2, 6, 5, 8]
for key in keys:btree.insert(key)
print(btree)

B树实现讲解：
BTreeNode类：定义了B树的节点类，包含关键字列表 keys 和子节点列表 children，以及一个标志位 leaf 表示是否为叶子节点。
BTree类：定义了B树类，包含了B树的插入操作 insert、节点分裂操作 split_child，以及辅助方法 _insert 和打印方法 print_tree。
insert方法：首先判断根节点是否已满，如果是则分裂根节点；然后调用辅助方法 _insert 插入关键字。
_insert方法：递归地在合适的位置插入关键字，并在需要时进行节点分裂。
split_child方法：分裂节点，将中间的关键字提升到父节点，并将节点分裂成两个节点。

B+树的实现思路
定义B+树节点类：B+树的节点需要存储索引信息和叶子节点指针。我们可以定义一个节点类，其中包含关键字列表、子节点列表和叶子节点指针。
插入操作：B+树的插入操作与B树类似，但是需要额外处理叶子节点之间的连接关系，以保持叶子节点形成的有序链表。
删除操作：B+树的删除操作也与B树类似，但是同样需要额外处理叶子节点之间的连接关系。

class BPlusTreeNode:def __init__(self, leaf=False):self.keys = []self.children = []self.next_leaf = None  # 指向下一个叶子节点self.leaf = leafclass BPlusTree:def __init__(self, t):self.root = BPlusTreeNode(leaf=True)self.t = tdef insert(self, key):if len(self.root.keys) == (2 * self.t) - 1:new_root = BPlusTreeNode()new_root.children.append(self.root)self.split_child(new_root, 0)self.root = new_rootself._insert(self.root, key)def _insert(self, node, key):if node.leaf:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1node.keys.insert(i, key)else:i = 0while i < len(node.keys) and key > node.keys[i]:i += 1if len(node.children[i].keys) == (2 * self.t) - 1:self.split_child(node, i)if key > node.keys[i]:i += 1self._insert(node.children[i], key)def split_child(self, parent, index):t = self.tchild = parent.children[index]new_child = BPlusTreeNode(leaf=child.leaf)parent.keys.insert(index, child.keys[t - 1])parent.children.insert(index + 1, new_child)new_child.keys = child.keys[t:]child.keys = child.keys[:t - 1]if not child.leaf:new_child.children = child.children[t:]child.children = child.children[:t]def __str__(self):return self.print_tree(self.root)def print_tree(self, node, level=0):ret = ""if node:ret += self.print_tree(node.children[0], level + 1)for i in range(len(node.keys)):ret += "\n" + ("    " * level) + str(node.keys[i])ret += self.print_tree(node.children[i + 1], level + 1)return ret# 测试
bplustree = BPlusTree(2)
keys = [3, 7, 1, 4, 9, 2, 6, 5, 8]
for key in keys:bplustree.insert(key)
print(bplustree)

B+树实现讲解：
BPlusTreeNode类：定义了B+树的节点类，与B树节点类相似，但是多了一个指向下一个叶子节点的指针 next_leaf。
BPlusTree类：定义了B+树类，与B树类相似，但是插入和分裂操作需要额外处理叶子节点之间的连接关系。
insert方法：与B树的插入操作类似，但是需要在插入关键字时维护叶子节点之间的连接关系。
split_child方法：与B树的节点分裂操作类似，但是需要额外维护叶子节点之间的连接关系。