
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

#include <vector>
#include <iostream>
#include <algorithm>
#include <memory> // For std::unique_ptr, std::make_unique

// 假设 Key 类型是 int
using Key = int;

// 前向声明 BTree 类，以便 BTreeNode 可以引用它
template <int M> // M 是 B 树的阶 (Order)
class BTree;

// B 树节点结构体
template <int M> // M is the order of the B-Tree
struct BTreeNode {
    bool isLeaf = true;
    std::vector<Key> keys; // 节点中的键
    std::vector<std::unique_ptr<BTreeNode<M>>> children; // 指向子节点的指针向量
                                                       // 对于内部节点，数量 = keys.size() + 1
                                                       // 对于叶节点，此向量通常为空或未使用

    // (为了简化，省略构造函数、析构函数等)

    // --- 搜索辅助函数 ---
    // 在节点内查找键或应该插入的位置 (返回索引 i)
    //使得 keys[i] >= key 或者 i == keys.size()
    int find_location(const Key& key) const {
        // 简单的线性扫描 (对于大的 M，二分查找更优)
        int i = 0;
        while (i < keys.size() && key > keys[i]) {
            i++;
        }
        return i;
    }

    // --- 插入辅助函数 ---
    // 在叶节点中插入键 (不处理溢出)
    void insert_key_leaf(const Key& key) {
        int i = find_location(key);
        keys.insert(keys.begin() + i, key);
    }

    // 在内部节点中插入键和子节点指针 (不处理溢出)
    void insert_key_internal(const Key& key, std::unique_ptr<BTreeNode<M>> left_child, std::unique_ptr<BTreeNode<M>> right_child) {
         int i = find_location(key);
         keys.insert(keys.begin() + i, key);
         // 在 i+1 处插入新的右子节点，原来的 children[i] 成为新左子节点
         children.erase(children.begin() + i); // 移除原来的指针
         children.insert(children.begin() + i, std::move(left_child)); // 插入左子节点
         children.insert(children.begin() + i + 1, std::move(right_child)); // 插入右子节点
    }
};

// --- 分裂结果结构体 ---
// 用于在递归插入中向上传递分裂信息
template<int M>
struct SplitResult {
    bool split_occurred = false;
    Key promoted_key;                 // 提升到父节点的键
    std::unique_ptr<BTreeNode<M>> new_sibling; // 分裂产生的新右兄弟节点
};


// B 树类
template <int M> // M 是 B 树的阶 (Order)
class BTree {
    static_assert(M >= 3, "B-Tree order M must be at least 3");

private:
    std::unique_ptr<BTreeNode<M>> root_ = nullptr;
    const int minKeys_ = (M + 1) / 2 - 1; // 最小键数 (ceil(M/2) - 1)
    const int maxKeys_ = M - 1;           // 最大键数

    // --- 搜索的私有递归辅助函数 ---
    bool _search(const BTreeNode<M>* node, const Key& key) const {
        if (!node) {
            return false; // 空树或未找到
        }

        int i = node->find_location(key);

        // 检查是否在当前节点找到
        if (i < node->keys.size() && node->keys[i] == key) {
            return true;
        }

        // 如果是叶节点且未找到，则键不存在
        if (node->isLeaf) {
            return false;
        }

        // --- 模拟磁盘读取 ---
        // 在实际应用中，这里需要从磁盘加载 node->children[i]
        // std::unique_ptr<BTreeNode<M>> child_node = fetchChild(node->children_raw_pointers[i]);

        // 向下递归到正确的子节点
        return _search(node->children[i].get(), key);
    }


    // --- 插入的私有递归辅助函数 ---
    SplitResult<M> _insert(BTreeNode<M>* node, const Key& key) {
        SplitResult<M> result; // 默认 split_occurred = false

        if (node->isLeaf) {
            // 1. 如果是叶节点，直接插入
            node->insert_key_leaf(key);

            // 2. 检查是否溢出
            if (node->keys.size() > maxKeys_) {
                // 需要分裂
                result = split_node(node);
            }
            // 返回结果 (可能分裂，也可能没分裂)
            return result;

        } else {
            // 3. 如果是内部节点，找到应该插入的子树
            int i = node->find_location(key);

             // --- 模拟磁盘读取子节点 ---
             // BTreeNode<M>* child_node = fetchChild(node->children_raw_pointers[i]);

            // 4. 递归插入到子节点
            SplitResult<M> child_split_result = _insert(node->children[i].get(), key);

            // 5. 检查子节点是否发生了分裂
            if (child_split_result.split_occurred) {
                // 子节点分裂了，需要将提升的键和新兄弟节点插入当前节点
                node->insert_key_internal(child_split_result.promoted_key,
                                          std::move(node->children[i]), // 旧的子节点成为新左子节点
                                          std::move(child_split_result.new_sibling));

                // 6. 检查当前节点是否因为插入提升的键而溢出
                if (node->keys.size() > maxKeys_) {
                    // 当前节点也需要分裂
                    result = split_node(node);
                }
            }
            // 返回结果 (可能因为子节点分裂导致当前节点分裂，也可能没有)
            return result;
        }
    }

    // --- 分裂节点的辅助函数 ---
    SplitResult<M> split_node(BTreeNode<M>* node) {
        SplitResult<M> result;
        result.split_occurred = true;

        // 找到中间位置
        int median_idx = node->keys.size() / 2;
        result.promoted_key = node->keys[median_idx]; // 提升中间键

        // 创建新的右兄弟节点
        result.new_sibling = std::make_unique<BTreeNode<M>>();
        result.new_sibling->isLeaf = node->isLeaf;

        // 将中间键之后的键移动到新兄弟节点
        result.new_sibling->keys.assign(node->keys.begin() + median_idx + 1, node->keys.end());

        // 如果不是叶节点，还需要移动相应的子节点
        if (!node->isLeaf) {
            int children_median_idx = (node->children.size() + 1) / 2; // 子节点分裂点
             result.new_sibling->children.assign(
                std::make_move_iterator(node->children.begin() + children_median_idx),
                std::make_move_iterator(node->children.end())
            );
             node->children.resize(children_median_idx); // 从原节点移除移动的子节点
        }

        // 从原节点移除中间键及移动的键
        node->keys.resize(median_idx);

        return result;
    }


public:
    // --- 公共搜索接口 ---
    bool search(const Key& key) const {
        return _search(root_.get(), key);
    }

    // --- 公共插入接口 ---
    void insert(const Key& key) {
        // 1. 如果树为空，创建根节点
        if (!root_) {
            root_ = std::make_unique<BTreeNode<M>>();
            root_->isLeaf = true;
            root_->keys.push_back(key);
            return;
        }

        // 2. 从根节点开始递归插入
        SplitResult<M> root_split_result = _insert(root_.get(), key);

        // 3. 处理根节点分裂的特殊情况
        if (root_split_result.split_occurred) {
            // 创建新的根节点
            auto new_root = std::make_unique<BTreeNode<M>>();
            new_root->isLeaf = false;
            new_root->keys.push_back(root_split_result.promoted_key);
            new_root->children.push_back(std::move(root_)); // 旧根成为左子节点
            new_root->children.push_back(std::move(root_split_result.new_sibling)); // 新兄弟成为右子节点
            root_ = std::move(new_root); // 更新树的根
        }
    }

    // (可以添加打印树结构、删除等其他方法)
};
BTree Analysis
BTree 属性回顾
Height Analysis
分析目标与策略
推导最小节点数和最小键数
为了找到高度 h 的 B 树包含的最小键数 n_min，我们首先计算最稀疏 (节点数最少) 的 B 树结构。
推导高度的上界
我们从上面得到的关于最小键数的不等式出发，来求解 h 的上界：
Motivation

为什么需要 B 树？

问题：巨大的访问时间差异

为什么标准树 (如 AVL 树) 在磁盘上表现不佳

BTree Basic

Motivation

B 树节点结构

BTree Operations

Insertion

BTree Properties

Search

Code Example

BTree Analysis

BTree 属性回顾

Height Analysis

分析目标与策略

推导最小节点数和最小键数

推导高度的上界

示例计算
