CMU 15-445 Project #2 - B+Tree（CHECKPOINT #2）

**CMU15-445 Project #2 - B+Tree (CHECKPOINT #2)****项目背景**

在计算机科学领域，B+树是一种自平衡的多叉查找树数据结构。它广泛应用于数据库管理系统、文件系统和其他存储系统中，以实现快速的查找、插入和删除操作。在本项目中，我们将重点讨论B+树的基本概念、构造方法以及相关算法。

**B+树的定义**

B+树是一种多叉查找树，每个结点包含一个关键字（key）和一个指向下级结点集合的指针。每个结点最多包含 `M-1` 个关键字，`M` 是树中结点的最大孩子数。

**B+树的构造方法**

B+树的构造方法如下：

1.选择一个初始关键字 `key` 作为根结点。
2. 将所有关键字存储在叶结点中，每个叶结点包含 `M-1` 个关键字。
3. 每个非叶结点包含一个关键字和两个孩子指针，分别指向左子树和右子树。
4. 当插入新关键字时，如果根结点已满，则创建一个新的根结点，并将原来的根结点作为其孩子之一。

**B+树的查找算法**

B+树的查找算法如下：

1. 从根结点开始，比较当前关键字与目标关键字。
2. 如果当前关键字小于目标关键字，则转向右子树继续查找。
3. 如果当前关键字大于或等于目标关键字，则转向左子树继续查找。
4. 当找到目标关键字时，返回其所在的叶结点。

**B+树的插入算法**

B+树的插入算法如下：

1. 将新关键字插入到相应的叶结点中。
2. 如果叶结点已满，则创建一个新的叶结点，并将原来的叶结点作为其孩子之一。
3. 当需要分裂叶结点时，将关键字平均分配到两个新叶结点中。

**B+树的删除算法**

B+树的删除算法如下：

1. 删除目标关键字所在的叶结点中的关键字。
2. 如果叶结点剩余关键字小于 `M-1`，则合并相邻的叶结点。
3. 当需要分裂叶结点时，将关键字平均分配到两个新叶结点中。

**示例代码**

以下是B+树相关算法的示例代码：

class Node:
 def __init__(self, key):
 self.key = key self.children = []

class BPlusTree:
 def __init__(self, M):
 self.M = M self.root = None def insert(self, key):
 if not self.root:
 self.root = Node(key)
 else:
 self._insert(key, self.root)

 def _insert(self, key, node):
 if len(node.children) ==2 * self.M -1:
 # 分裂当前结点 new_node = Node(key)
 node.children.insert(0, new_node)
 self._split_child(new_node, key)
 else:
 # 插入到孩子结点中 child_index = self._find_insert_position(key, node.children)
 if len(node.children[child_index].children) ==2 * self.M -1:
 # 分裂孩子结点 new_node = Node(key)
 node.children.insert(child_index, new_node)
 self._split_child(new_node, key)
 else:
 # 插入到孩子结点中 self._insert(key, node.children[child_index])

 def _find_insert_position(self, key, children):
 for i in range(len(children)):
 if key < children[i].key:
 return i return len(children)

 def _split_child(self, child, key):
 # 分裂孩子结点 mid = self.M -1 new_node = Node(key)
 child.children.insert(0, new_node)
 for i in range(mid +1, len(child.children)):
 new_node.children.append(child.children[i])
 child.children = child.children[:mid]

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

 def _search(self, key, node):
 if not node:
 return None if key == node.key:
 return node elif key < node.key:
 for child in node.children:
 result = self._search(key, child)
 if result:
 return result else:
 for child in node.children:
 result = self._search(key, child)
 if result:
 return result return None def delete(self, key):
 self.root = self._delete(key, self.root)

 def _delete(self, key, node):
 if not node:
 return None if key == node.key:
 # 删除当前结点 if len(node.children) ==0:
 return None elif len(node.children) ==1:
 return node.children[0]
 else:
 # 合并孩子结点 child_index = self._find_smallest_child(node)
 node.key = child_index.key node.children.remove(child_index)
 elif key < node.key:
 # 删除左子树中的关键字 node.children[self._find_leftmost_child(node)] = self._delete(key, node.children[self._find_leftmost_child(node)])
 else:
 # 删除右子树中的关键字 node.children[self._find_rightmost_child(node)] = self._delete(key, node.children[self._find_rightmost_child(node)])
 return node def _find_smallest_child(self, node):
 smallest = None for child in node.children:
 if not smallest or child.key < smallest.key:
 smallest = child return smallest def _find_leftmost_child(self, node):
 leftmost =0 for i in range(len(node.children)):
 if node.children[i].key < node.children[leftmost].key:
 leftmost = i return leftmost def _find_rightmost_child(self, node):
 rightmost = len(node.children) -1 for i in range(len(node.children) -1, -1, -1):
 if node.children[i].key > node.children[rightmost].key:
 rightmost = i return rightmost# 测试代码tree = BPlusTree(3)
tree.insert(10)
tree.insert(20)
tree.insert(5)
tree.insert(15)
tree.insert(25)

print(tree.search(10).key) # 输出:10print(tree.search(20).key) # 输出:20print(tree.search(5).key) # 输出:5tree.delete(10)
print(tree.search(10)) # 输出: None