python实现B/B+树_python 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 = leaf

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

    def 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_root
        self._insert(self.root, key)

    def _insert(self, node, key):
        if node.leaf:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1
            node.keys.insert(i, key)
        else:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1
            if len(node.children[i].keys) == (2 * self.t) - 1:
                self.split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert(node.children[i], key)

    def split_child(self, parent, index):
        t = self.t
        child = 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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 = leaf

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

    def 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_root
        self._insert(self.root, key)

    def _insert(self, node, key):
        if node.leaf:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1
            node.keys.insert(i, key)
        else:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1
            if len(node.children[i].keys) == (2 * self.t) - 1:
                self.split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert(node.children[i], key)

    def split_child(self, parent, index):
        t = self.t
        child = 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

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