泉州网站建设推广服务,整合营销的特点有哪些,天猫购物商城官网,受欢迎的免费网站建设文章目录B 树的定义B 树组织数据的方法往 B 树中插入键值对数据从 B 树中删除键值对把 B 树看作是 “真菌网络”——我理解并记忆 B 树的方法B 树的 C 代码实现初始化节点、B 树B 树节点内的二分查找B 树的数据插入操作B 树的删除数据操作范围查询与全局遍历销毁 B 树测试代码 树的定义B 树组织数据的方法往 B 树中插入键值对数据从 B 树中删除键值对把 B 树看作是 “真菌网络”——我理解并记忆 B 树的方法B 树的 C 代码实现初始化节点、B 树B 树节点内的二分查找B 树的数据插入操作B 树的删除数据操作范围查询与全局遍历销毁 B 树测试代码主函数推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习: https://github.com/0voice 链接。
B 树的定义
B 树与 B树 是有一定的相似性大家可以参考 这篇文章。
B 树是一个针对单个有序的索引指标的数据列键值对型的数据列 的高效查询算法它提供了一个组织数据的方法按照这个方法先行组织数据而后能高效率的对某个索引键的数据进行查询而后实现快速的范围查询。
对比发现红黑树是无法实现范围查询即对某一个范围内的键值进行数据查询。SPLAY 树和 B 树都能实现范围查询。这些 “树算法” 的搜索方法原理都是一样的通过让查询键和节点的各个键比大小从而确定查询的路径。不同于前面所例举的 “树”B 树是需要一直查到叶结点处才能获取具体数据。 B树 与 红黑树 的核心差别
特性红黑树 (Red-Black Tree)B 树 (B Tree)本质差异类型二叉平衡搜索树 (每个节点最多2个子节点)多路平衡搜索树 (每个节点有多个子节点m阶)节点分支数二叉 vs 多路平衡性通过颜色和旋转规则保持 大致平衡 (非绝对完美)通过节点分裂/合并保持 绝对平衡 (所有叶子同层)平衡严格性红黑树高度上限 2log₂(n1) B树更矮胖 (logₘn, m2)节点内容每个节点存储1. 键2. 数据指针3. 左右子节点指针4. 颜色标记内部节点只存 键 子节点指针。//////// 叶子节点存 键 数据指针 指向下一个叶子的指针数据位置红黑树数据分散在所有节点B树数据仅存于叶子内部节点纯路由范围查询效率中序遍历 (O(n)但需遍历整棵树内存跳跃访问缓存不友好)叶子节点链表顺序遍历 (O(n)但连续内存访问缓存极友好)范围查询性能B树碾压式优势 (链表连续访问 vs 树的递归遍历)树高相对 较高 (O(log₂n))相对 极矮 (O(logₘn), m 通常数百)访问局部性B树单节点载入大量键减少I/O (对磁盘关键)主要设计目标内存内高效操作 (插入/删除/查找 O(log₂n))减少磁盘I/O次数 (树矮节点匹配磁盘块大小)优化方向红黑树优化CPU计算B树优化磁盘I/O适用存储内存 (RAM)磁盘/SSD (辅存)主战场不同内存 vs 外存
我们常说的 B 树通常都是说 “ m 阶的 B 树 ” 即每一个节点都不能有超过 m-1 个键不超过 m 个子节点那也就是说共 2m−12m-12m−1 项内容。B 树有 8 条定义律 内部节点 – 存储 k 个路由键⌈m/2⌉−1≤k≤m−1⌈m/2⌉-1 ≤ k ≤ m-1⌈m/2⌉−1≤k≤m−1 –包含 k1 个子节点指针 –不存储任何数据指针 叶子节点 –存储 k 个键值对⌈m/2⌉−1≤k≤m−1⌈m/2⌉-1 ≤ k ≤ m-1⌈m/2⌉−1≤k≤m−1 –包含 k 个数据指针 –包含指向下一个叶子节点的指针 所有叶子节点必须位于同一深度 –从根到任意叶子的路径长度相等 –树完全平衡 键值继承原则 –内部节点的键 Ki其对应子树的最小键K_i 其对应子树的最小键Ki其对应子树的最小键 –即Kimin(children[i1])K_i \min(children[i1])Kimin(children[i1]) 路由键范围划分 –对任意内部节点键 K_i – 子节点 children[i]中所有键≤Kichildren[i] 中所有键 ≤ K_ichildren[i]中所有键≤Ki – 子节点 children[i1]中所有键Kichildren[i1] 中所有键 K_ichildren[i1]中所有键Ki 数据位置限定 – 实际数据只存储在叶子节点 – 内部节点仅包含路由信息 – 叶子节点包含完整键集合 叶子节点必须按键顺序组成单向链表 – 通过 next 指针连接 – 链表按键升序排列 当根节点作为中间节点而存在时它是一个特殊的中间节点构成性的例外它可以仅拥有一个键两个子节点。这样能为算法在不断插入新节点的时候节点不断地在分裂和上溢时更新 B 树的同时作定义上的兜底。
节点类型键数量范围指针数量存储内容根节点1 ≤ k ≤ m-1k1路由键子节点指针内部节点⌈m/2⌉-1 ≤ k ≤ m-1k1路由键子节点指针叶子节点⌈m/2⌉-1 ≤ k ≤ m-1k键数据指针
根据以上定义我们以 4 阶 B 树为例具体解释这些定义条的作用。 每个节点至多拥有 3−123-123−12 个键至多 3 个指针。我们可以想象它的中间节点是长这样的2 个键键是某个具体数据块的索引 keykey 是可以用来与查询键比大小而后查询出数据的具体位置从哪条通路走下去3 个路由指针每个路由指针指向字节点的地址这就是导引查询数据的通路。
┌------------------------------------┐
│ 指针0 │ 键K₁ │ 指针1 │ 键K₂ │ 指针2 │
└------------------------------------┘叶子节点是长这样的他和中间节点一样共有 3 个指针3 个键。键是具体数据块本身的索引 key其中的 2 个指针是具体数据块的指针1 个指针是指向下一个叶子节点的指针。
┌-----------------------------------------┐
│ 键K₁:数据指针 │ 键K₂:数据指针 │ next指针 │
└-----------------------------------------┘3 阶 B 树的叶子节点和中间节点的关系则如下所示
_____________中间节点_________________┌------------------------------------┐│ 指针0 │ 键K3 │ 指针1 │ 键K5 │ 指针2 │└------------------------------------┘/ | |______________________________________________/ | |_______________| _____________| |\|/ / |_|_ _\|/_ _\|/_
┌-----------------------------------------┐ ┌-----------------------------------------┐ ┌-----------------------------------------┐
│ 键K1:数据指针 │ 键K2:数据指针 │ 叶子2 的指针 │ │ 键K3:数据指针 │ 键K4:数据指针 │ 叶子3 的指针 │ │ 键K5:数据指针 │ 键K6:数据指针 │ 叶子4 的指针 │
└-----------------------------------------┘ └-----------------------------------------┘ └-----------------------------------------┘
______________叶子节点 1__________________ _______________ 叶子节点 2__________________ ________________叶子节点 3__________________B 树组织数据的方法
只有合理的组织数据才会有高效率的查询。所谓的 ‘’组织数据“ 就是插入键值对数据注意这不是插入节点原因是一个节点有可能会有好几份数据。以及删除键值对数据。
下面我将以 4 阶的 B 树为例去介绍其数据插入和数据删除。
叶子节点的形式约定如下。 A 代表 32 键的 valueB 代表 46 键的 value“–” 代表指向下一个叶子节点的指针。
---------
|A|32|B|46|--|
---------中间节点、根节点的形式约定是空白间隔条就是 “路由指针”走向下一层的节点。
----
||32||46||
----往 B 树中插入键值对数据
是插入键值对数据而非插入节点原因是一个节点有可能会有好几份数据。
情况一根节点满员导致的节点分裂键信息上溢注意数据 value 并没上传。至于叶子节点的分裂也是类似的。我们需要注意到的是不同层的中间节点的键是可以重复的。
增加键 50 与 D 值
------------
|A|32|B|46|C|47|--|
------------节点满员了需要键的上溢与节点分裂---------------|A|32|B|46|C|47|D|50|--|-----------------||47||--/ \/ \/ \
--------- ---------
|A|32|B|46|--| |C|47|D|50|--|
--------- ---------情况二已满员的中间节点插入数据导致节点分裂我们需要注意到的是不同层的中间节点的键是可以重复的。
插入一个 45 的新键----||33||49||----/ | \__/ | \__/ | \/ | \
---- ------ ----
||25||30|| ||33||43||44|| ||49||50||
---- ------ ----
发现节点数据超员了进行节点分裂----||32||46||----/ | \__/ | \_________/ | \/ | \
---- -------- ----
||25||30|| ||33||43||44||45|| ||49||50||
---- -------- ----节点数据平分两份中间的 44 键上传------||32||44||46||------/ | | \__/ | | \_________/ | \ \/ | \ \
---- ---- ---- ----
||25||30|| ||33||43|| ||44||45|| ||49||50||
---- ---- ---- ----情况三中间节点的节点正常插入和叶子节点的正常插入就不展示了。
从 B 树中删除键值对
是删除键值对数据而非删除节点原因是一个节点有可能会有好几份数据。
情况一叶子节点的删除数据发现删除之后低于半数向兄弟节点借数据。中间节点的数据删除也是类似的。会连带的把上面带有 33 的键的节点进行数据删除递归式的删除。
删除数据 33 ----||33||47||----/ | \__/ \ \____/ | \/ \ \
--------- ------ ---------
|A|25|B|30|--| |C|33|--| |D|47|E|50|--|
--------- ------ ---------向兄弟节点借数据先抵押给父节点----||32||47||----/ | \__/ \ \____/ | \/ \ \
--------- ---------
|A|25|B|30|--| |D|47|E|50|--|
--------- ---------父节点换数据再进行数据下渗----||30||47||----/ | \__/ \ \____/ | \/ \ \
------ ------ ---------
|A|25|--| |B|30|--| |D|47|E|50|--|
------ ------ ---------
情况二叶子节点的删除数据发现删除之后低于半数而且兄弟节点数据刚好在半数也无法借出数据。中间节点的数据删除也是类似的。会连带的把上面带有 33 的键的节点进行数据删除递归式的删除。故而只好合并节点。
删除键为 30 的节点----||30||47||----/ | \__/ \ \____/ | \/ \ \
------ ------ ------
|A|25|--| |B|30|--| |D|47|--|
------ ------ ------
节点合并----||30||47||----/ | \__/ \ \____/ | \/ \ \
------ ------
|A|25|--| |D|47|--|
------ --------||47||--/ \__/ \____/ \/ \
------ ------
|A|25|--| |D|47|--|
------ ------情况三正常的中间节点删除、叶子节点删除数据就不罗列了。
把 B 树看作是 “真菌网络”——我理解并记忆 B 树的方法 B树的真菌生长比喻 想象一片数字森林其中生长着一种名为 B 菌的神奇真菌 孢子萌发初始状态 1、森林中诞生一个初始孢子细胞根节点兼叶子节点 2、这个细胞通过吸收数据养分插入键值对逐渐长大 质配阶段节点填充 1、细胞通过菌丝网络指针与其他细胞交换遗传物质键值传递 2、细胞膜节点容量不断扩张容纳更多染色体片段键值对 3、当细胞达到临界质量阶数M时进入减数分裂准备期 减数分裂节点分裂 1、细胞核发生均等裂变键值均匀分裂 2、产生两个子细胞新叶子节点 3、关键染色体最小键K3通过菌丝管道提升到上层细胞父节点 菌丝网络形成叶子链表 1、子细胞间分泌信息素导管next指针 2、形成地下菌丝网络叶子节点链表 3、养分数据可通过网络连续输送范围查询 子实体发育树结构生长 1、当上层细胞也达到临界质量时触发级联分裂 2、最终在森林地表形成 3、菌盖根节点指挥中心 4、菌褶内部节点传输通道 5、菌丝体叶子链表营养交换网络
B 树的 C 代码实现
我们需要明确的一点是 数据结构数据定义数据的操作方法。数据结构 数据定义 数据的操作方法。数据结构数据定义数据的操作方法。
首先是数据定义。
// B树阶数 - 每个节点最多M-1个键M个孩子
#define M 4
#define MIN_KEYS ((M) / 2)// B树节点结构
typedef struct BPlusTreeNode {bool is_leaf; // 是否为叶子节点int key_count; // 当前键的数量int keys[M]; // 键数组union {struct BPlusTreeNode* children[M 1]; // 内部节点的子节点指针void* data_ptrs[M]; // 叶子节点的数据指针};struct BPlusTreeNode* next; // 叶子节点的链表指针
} BPlusTreeNode;// B树结构
typedef struct {BPlusTreeNode* root;
} BPlusTree;
B 树的数据结构
叶子节点 leaf 和中间节点 internal 还是是有区分的。在范围查询上叶子节点的链表指针提供了便利叶子节点负责储存数据理论上叶子节点和中间节点都有 M1 阶个指针只是叶子节点有 M 个数据指针和 1 个叶子链表指针而中间节点有 M1 个路由指针。但实际上路由指针数组的指针和数据指针被统一在联合体中降低了节点的内存叶子和中间点都可以共用同一个数据结构。key_count、0 和 MIN_KEYS 是三个重要的数字在节点合并、节点分裂、借兄弟数据、叶子删数据和叶子加数据都有涉及。所有节点都有最多有 M 个键它们是 M1 阶的。第 K 个键大于第 K 个路由指针下的任何一个键第 K 个键小于等于第 K1 个路由指针下的任何一个键。父节点的第 K 个键等于第 K1 个子节点的第 0 个键
初始化节点、B 树
// 创建新节点
BPlusTreeNode* create_node(bool is_leaf) {BPlusTreeNode* node (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));node-is_leaf is_leaf;node-key_count 0;// 务必要注意节点的所有 key 一定要初始化成一个不会与所插入键重复的值否则很麻烦。node-next NULL;for (int i 0; i M; i) {node-keys[i] INT_MAX; // 初始化为最大值}return node;
}// 初始化B树
BPlusTree* init_bplus_tree() {BPlusTree* tree (BPlusTree*)malloc(sizeof(BPlusTree));tree-root create_node(true); // 初始为叶子节点return tree;
}B 树节点内的二分查找
// 在节点中查找键的位置或者找到合适往下走的通路
int btree_bin_search(BPlusTreeNode *node, int low, int high, int key) {// 二分查找法的时间复杂度是 O(log N)int mid;if (low high || low 0 || high 0) {return -1;}while (low high) {mid (low high) / 2; // 向 0 取整吗if (key node-keys[mid]) {low mid 1;} else {high mid - 1;}}return low;
}B 树的数据插入操作
insert_recursive 的递归实现思想不是 B 树的 “防患于未然的未雨绸缪”而是把 “底层的暗流涌动逐层的浮于水面之上”
叶子节点的数据插入是递归的边界条件只有叶子节点的插入所导致的节点分裂才有可能导致中间节点键的插入因而需要逐层递归回溯性地产生兄弟节点、以及需要提升的键只要有一层说不用分裂节点那之后的递归的回溯都会 trivival 化
bplus_tree_insert 函数是从 root 节点往下探索的最终会包含对根节点的重塑 // 插入键到叶子节点
void insert_into_leaf(BPlusTreeNode* leaf, int key, void* value) {int idx btree_bin_search(leaf, 0, leaf-key_count, key);// 如果键已存在更新值if (idx leaf-key_count leaf-keys[idx] key) {leaf-data_ptrs[idx] value;return;}// 移动键和值以腾出空间for (int i leaf-key_count; i idx; i--) {leaf-keys[i] leaf-keys[i - 1];leaf-data_ptrs[i] leaf-data_ptrs[i - 1];}// 插入新键值leaf-keys[idx] key;leaf-data_ptrs[idx] value;leaf-key_count;
}// 分裂叶子节点
BPlusTreeNode* split_leaf_node(BPlusTreeNode* leaf) {// BPlusTreeNode* new_leaf create_node(true); // true 代表生产叶子节点int split_index leaf-key_count / 2; // 中间指标是下一个叶子节点的键的开始指标// 移动后半部分键值到新叶子节点for (int i split_index; i leaf-key_count; i) {new_leaf-keys[i - split_index] leaf-keys[i];new_leaf-data_ptrs[i - split_index] leaf-data_ptrs[i];leaf-keys[i] INT_MAX; // 重置原位置}new_leaf-key_count leaf-key_count - split_index;leaf-key_count split_index;// 维护叶子节点链表new_leaf-next leaf-next;leaf-next new_leaf;return new_leaf;
}// 分裂内部节点这是从终端由下往上传来的压力
BPlusTreeNode* split_internal_node(BPlusTreeNode* internal) {BPlusTreeNode* new_internal create_node(false);int split_index internal-key_count / 2; // 分裂的位置int promote_key internal-keys[split_index]; // 需要提升的键// 移动键和子节点指针分裂出的右兄弟节点不包含需要提升for (int i split_index 1; i internal-key_count; i) {new_internal-keys[i - split_index - 1] internal-keys[i];new_internal-children[i - split_index - 1] internal-children[i];internal-keys[i] INT_MAX;}// 处理最后一个子节点指针new_internal-children[internal-key_count - split_index - 1] internal-children[internal-key_count];new_internal-key_count internal-key_count - split_index - 1;internal-key_count split_index;return new_internal;
}// 插入操作的递归实现
void insert_recursive(BPlusTreeNode* node, int key, void* value, BPlusTreeNode** new_child, int* promote_key) {// node 和 new_child 是同级别的node 分裂之后会产生右兄弟节点去到更上一层后还会继续被更新的// 如果是叶子节点if (node-is_leaf) {insert_into_leaf(node, key, value); // 叶子先插入数据// 检查是否需要分裂如果现在满员了我们可以未雨绸缪先行分裂if (node-key_count M) {BPlusTreeNode* new_node split_leaf_node(node);*new_child new_node;*promote_key new_node-keys[0]; // 提升新节点的第一个键叶子节点允许与中间节点用同样的键} else {*new_child NULL;}return; // 叶子节点是不会执行下面这些代码的是递归函数的边界条件}// 内部节点 - 找到合适的子节点int idx btree_bin_search(node, 0, node-key_count, key);// 找到分裂的位置BPlusTreeNode* child node-children[idx]; BPlusTreeNode* new_child_node NULL;int new_key INT_MAX;insert_recursive(child, key, value, new_child_node, new_key); // 递归插入子节点递归展开//------------------- 回溯 --------------------//// new_child_node 和 new_key 会被回溯定义直至浮于水面层层向上反映// 如果子节点分裂了需要判断当前更高一层的节点是否需要分裂if (new_child_node) {// 在内部节点中为新键腾出空间for (int i node-key_count; i idx; i--) {node-keys[i] node-keys[i - 1];node-children[i 1] node-children[i];}// 插入新键和子节点指针node-keys[idx] new_key;node-children[idx 1] new_child_node;node-key_count;// 检查是否需要分裂当前节点if (node-key_count M) {BPlusTreeNode* new_node split_internal_node(node);// 反射回草稿纸记录新产生的节点和需要提升的键*new_child new_node; *promote_key node-keys[node-key_count]; // 提升新分裂节点的首键} else {*new_child NULL; // 本层节点不需要分裂}} else {*new_child NULL; // 子节点没有分裂那父节点更没有分裂}
}// B树插入操作
void bplus_tree_insert(BPlusTree* tree, int key, void* value) {// 以下两个变量取什么值并不重要它们本身只是用来迭代求解的一张草稿纸BPlusTreeNode* new_child NULL; // 或许会分裂出的新节点int promote_key INT_MAX; // 或许有需要提升的键// 由于这两个变量会经历递归求解最终有可能反射为当前根节点的兄弟节点insert_recursive(tree-root, key, value, new_child, promote_key); // 递归展开// 底层插入数据的行为会一层一层地反映到根结点处// root 和 new_child 是同级别的// 处理根节点分裂产生一个新的根节点if (new_child) {BPlusTreeNode* new_root create_node(false); // 中间节点new_root-keys[0] promote_key;new_root-children[0] tree-root;new_root-children[1] new_child;new_root-key_count 1;tree-root new_root;}
}
B 树的删除数据操作
delete_recursive 的递归实现思想依然是把 “底层的暗流涌动逐层的浮于水面之上”
只有叶子的删除有可能导致节点合并节点合并会导致中间节点的键删除这又有可能导致节点的再次合并。叶子节点的数据删除是递归的边界条件回溯性的判断本层次是否需要节点合并、借兄弟节点数据如果是后者或者都没必要此后的递归回溯都会 trivival 化 // 在叶子节点处删除键值对数据
void delete_from_leaf(BPlusTreeNode* leaf, int key) {int idx btree_bin_search(leaf, 0, leaf-key_count, key);if (idx leaf-key_count leaf-keys[idx] key) {// 移动键和值以填充空隙for (int i idx; i leaf-key_count - 1; i) {leaf-keys[i] leaf-keys[i 1];leaf-data_ptrs[i] leaf-data_ptrs[i 1];}leaf-keys[leaf-key_count - 1] INT_MAX;leaf-key_count--;}
}// 从兄弟节点借键叶子节点
void borrow_from_sibling(BPlusTreeNode* node, BPlusTreeNode* sibling, BPlusTreeNode* parent, int parent_key_index, bool is_left_sibling) {// sibling 指代兄弟节点if (is_left_sibling) {// 从左侧兄弟借键只能借最大键和其对应的数据或者路标指针int last_key sibling-keys[sibling-key_count - 1];if (node-is_leaf) {// 叶子节点的兄弟借数据void* last_value sibling-data_ptrs[sibling-key_count - 1];// 移动当前节点的键值挪位置for (int i node-key_count; i 0; i--) {node-keys[i] node-keys[i - 1];node-data_ptrs[i] node-data_ptrs[i - 1];} // 插入借来的键值node-keys[0] last_key;node-data_ptrs[0] last_value;node-key_count; } else {// 中间节点的兄弟借数据BPlusTreeNode* last_child sibling-children[sibling-key_count];// 移动当前节点的键值挪位置for (int i node-key_count; i 0; i--) {node-keys[i] node-keys[i - 1];node-children[i] node-data_ptrs[i - 1];}// 插入借来的键值node-keys[0] last_key;node-children[0] last_child;node-key_count;}// 更新兄弟节点sibling-keys[sibling-key_count - 1] INT_MAX;sibling-key_count--;// 更新父节点键parent-keys[parent_key_index-1] node-keys[0];} else {// 从右侧兄弟借键只能借最小键和其对应的数据int first_key sibling-keys[0];if (node-is_leaf) {// 叶子节点的兄弟借数据void* first_value sibling-data_ptrs[0];// 插入借来的键值node-keys[node-key_count] first_key;node-data_ptrs[node-key_count] first_value;node-key_count;// 更新兄弟节点for (int i 0; i sibling-key_count - 1; i) {sibling-keys[i] sibling-keys[i 1];sibling-data_ptrs[i] sibling-data_ptrs[i 1];}} else {// 中间节点的兄弟借数据BPlusTreeNode* first_child sibling-children[0];// 插入借来的键值node-keys[node-key_count] first_key;node-children[node-key_count] first_child;node-key_count;// 更新兄弟节点for (int i 0; i sibling-key_count - 1; i) {sibling-keys[i] sibling-keys[i 1];sibling-children[i] sibling-children[i 1];}}sibling-keys[sibling-key_count - 1] INT_MAX;sibling-key_count--;// 更新父节点键node-keys[parent_key_index] sibling-keys[0];}
}// 合并节点
void merge_nodes(BPlusTreeNode* left, BPlusTreeNode* right) {// 节点一旦合并就意味着兄弟节点都没有余粮可借了// 移动右侧节点的键值到左侧if (left-is_leaf) {for (int i 0; i right-key_count; i) {left-keys[left-key_count i] right-keys[i];left-data_ptrs[left-key_count i] right-data_ptrs[i];}left-key_count right-key_count;left-next right-next;// 释放右侧节点free(right);} else {for (int i 0; i right-key_count; i) {left-keys[left-key_count i] right-keys[i];left-children[left-key_count i] right-data_ptrs[i];}left-children[left-key_count right-key_count] right-children[right-key_count];left-key_count right-key_count;// 释放右侧节点free(right);}}// 删除操作的递归实现
bool delete_recursive(BPlusTreeNode* node, int key, int* min_key) {// min_key 指代 node 更新后的最小键值它会被递归更新的直至浮出水面// 返回值 bool 表示操作是否需要进一步回溯修改。在叶子节点层次删除 node 的一个数据后数据的容量是否低于最小限度。 在中间节点层次适应底层修改后数据的容量是否低于最小限度。// 节点合并有可能会导致问题上传借节点则不会导致问题上传// 叶子节点处理if (node-is_leaf) {// 这是递归的边界条件int idx btree_bin_search(node, 0, node-key_count, key);if (idx node-key_count node-keys[idx] key) {delete_from_leaf(node, key);*min_key (node-key_count 0) ? node-keys[0] : INT_MAX;return node-key_count MIN_KEYS; // 节点数据量严重缺乏}return false; // 键不存在}// 内部节点 - 找到合适的子节点int idx btree_bin_search(node, 0, node-key_count, key); // idx 相位所对应的路由指针上所有的键都小于本节点第 idx 位的键BPlusTreeNode* child node-children[idx]; // 找到路牌往下走int new_min_key;bool child_underflow delete_recursive(child, key, new_min_key); // 展开递归递归的最内层就是叶子节点//-------------------------- 回溯 ----------------------------//// 子节点已完成更新键值现在父节点对应的路牌也要更新成对应子节点的最小keyif (idx 0 new_min_key ! INT_MAX new_min_key ! node-keys[idx - 1]) {node-keys[idx - 1] new_min_key;}// 处理子节点下溢if (child_underflow) {BPlusTreeNode* left_sibling (idx 0) ? node-children[idx - 1] : NULL;BPlusTreeNode* right_sibling (idx node-key_count) ? node-children[idx 1] : NULL;// 尝试从左兄弟借键if (left_sibling left_sibling-key_count MIN_KEYS) {// 借数据并不会导致上层结构的变化borrow_from_sibling(child, left_sibling, node, idx, true);return false;} // 尝试从右兄弟借键else if (right_sibling right_sibling-key_count MIN_KEYS) {// 借数据并不会导致上层结构的变化borrow_from_sibling(child, right_sibling, node, idx, false);return false;}// 合并节点else {if (left_sibling) {// 与左兄弟合并if (child-is_leaf) {merge_nodes(left_sibling, child);}// 更新父节点for (int i idx; i node-key_count; i) {node-keys[i - 1] node-keys[i];node-children[i] node-children[i 1];}node-keys[node-key_count - 1] INT_MAX;node-key_count--;} else if (right_sibling) {// 与右兄弟合并if (child-is_leaf) {merge_nodes(child, right_sibling);}// 更新父节点for (int i idx 1; i node-key_count; i) {node-keys[i - 1] node-keys[i];node-children[i] node-children[i 1];}node-keys[node-key_count - 1] INT_MAX;node-key_count--;}return node-key_count MIN_KEYS;}}return false;
}// B树删除操作
void bplus_tree_delete(BPlusTree* tree, int key) {int min_key;bool root_underflow delete_recursive(tree-root, key, min_key); // 让所有问题浮出水面// 处理根节点下溢if (root_underflow !tree-root-is_leaf tree-root-key_count 0) {BPlusTreeNode* old_root tree-root;tree-root tree-root-children[0];free(old_root);}
}
范围查询与全局遍历
B 树的范围查询要远比 B 树的好写因为 B 树的叶子节点是可以指向下一个相邻的叶子节点。
// 查找键对应的值
void* bplus_tree_search(BPlusTree* tree, int key) {BPlusTreeNode* node tree-root;while (!node-is_leaf) {int idx btree_bin_search(node, 0, node-key_count, key);node node-children[idx];}int idx btree_bin_search(node, 0, node-key_count, key);if (idx node-key_count node-keys[idx] key) {return node-data_ptrs[idx];}return NULL; // 未找到
}// 范围查询
void bplus_tree_range_query(BPlusTree* tree, int start, int end) {BPlusTreeNode* node tree-root;// 找到起始键所在的叶子节点while (!node-is_leaf) {int idx btree_bin_search(node, 0, node-key_count, start);node node-children[idx];}// 在叶子节点链表中遍历while (node ! NULL) {for (int i 0; i node-key_count; i) {// 键在范围内if (node-keys[i] start node-keys[i] end) {printf(Key: %d, Value: %d\n, node-keys[i], *(int*)(node-data_ptrs[i])); // %p 是指针占位符}// 超过范围停止查询if (node-keys[i] end) {return;}}node node-next;}
}
我们亦可按照树的层次去打印 B 树的结构
// 打印B树辅助函数
void print_bplus_tree(BPlusTreeNode* node, int level) {if (node NULL) return;printf(Level %d: , level);for (int i 0; i node-key_count; i) {printf(%d , node-keys[i]);}printf(\n);if (!node-is_leaf) {for (int i 0; i node-key_count; i) {print_bplus_tree(node-children[i], level 1);}}
}销毁 B 树
// 释放B树内存
void free_bplus_tree(BPlusTreeNode* node) {if (node NULL) return;if (!node-is_leaf) {for (int i 0; i node-key_count; i) {free_bplus_tree(node-children[i]);}}free(node);
}测试代码主函数
测试量为 200 个插入。
// 测试用例
int main() {BPlusTree* tree init_bplus_tree();// 插入测试printf(Inserting keys...\n);for (int i 1; i 200; i) {int* value (int*)malloc(sizeof(int));*value i * 100;bplus_tree_insert(tree, i, value);}printf(B Tree structure:\n);print_bplus_tree(tree-root, 0);// 搜索测试printf(\nSearching keys:\n);for (int i 5; i 15; i 3) {void* result bplus_tree_search(tree, i);if (result) {printf(Key %d found. Value: %d\n, i, *((int*)result));} else {printf(Key %d not found.\n, i);}}// 范围查询测试printf(\nRange query [7, 15]:\n);bplus_tree_range_query(tree, 7, 15);// 删除测试printf(\nDeleting keys 8, 12, 15...\n);bplus_tree_delete(tree, 8);bplus_tree_delete(tree, 12);bplus_tree_delete(tree, 15);printf(\nB Tree structure after deletion:\n);print_bplus_tree(tree-root, 0);// 再次范围查询printf(\nRange query [7, 15] after deletion:\n);bplus_tree_range_query(tree, 7, 15);// 清理free_bplus_tree(tree-root);free(tree);return 0;
}运行效果还 OK。
qimingqiming:~/share/CTASK/data-structure$ gcc -o bp bptree_test.c
qimingqiming:~/share/CTASK/data-structure$ ./bp
Inserting keys...
B Tree structure:
Level 0: 55 109 163
Level 1: 19 37
Level 2: 7 13
Level 3: 3 5
Level 4: 1 2
Level 4: 3 4
Level 4: 5 6
Level 3: 9 11
Level 4: 7 8
Level 4: 9 10
Level 4: 11 12
Level 3: 15 17
Level 4: 13 14
Level 4: 15 16
Level 4: 17 18
Level 2: 25 31
Level 3: 21 23
Level 4: 19 20
Level 4: 21 22
Level 4: 23 24
Level 3: 27 29
Level 4: 25 26
Level 4: 27 28
Level 4: 29 30
Level 3: 33 35
Level 4: 31 32
Level 4: 33 34
Level 4: 35 36
Level 2: 43 49
Level 3: 39 41
Level 4: 37 38
Level 4: 39 40
Level 4: 41 42
Level 3: 45 47
Level 4: 43 44
Level 4: 45 46
Level 4: 47 48
Level 3: 51 53
Level 4: 49 50
Level 4: 51 52
Level 4: 53 54
Level 1: 73 91
Level 2: 61 67
Level 3: 57 59
Level 4: 55 56
Level 4: 57 58
Level 4: 59 60
Level 3: 63 65
Level 4: 61 62
Level 4: 63 64
Level 4: 65 66
Level 3: 69 71
Level 4: 67 68
Level 4: 69 70
Level 4: 71 72
Level 2: 79 85
Level 3: 75 77
Level 4: 73 74
Level 4: 75 76
Level 4: 77 78
Level 3: 81 83
Level 4: 79 80
Level 4: 81 82
Level 4: 83 84
Level 3: 87 89
Level 4: 85 86
Level 4: 87 88
Level 4: 89 90
Level 2: 97 103
Level 3: 93 95
Level 4: 91 92
Level 4: 93 94
Level 4: 95 96
Level 3: 99 101
Level 4: 97 98
Level 4: 99 100
Level 4: 101 102
Level 3: 105 107
Level 4: 103 104
Level 4: 105 106
Level 4: 107 108
Level 1: 127 145
Level 2: 115 121
Level 3: 111 113
Level 4: 109 110
Level 4: 111 112
Level 4: 113 114
Level 3: 117 119
Level 4: 115 116
Level 4: 117 118
Level 4: 119 120
Level 3: 123 125
Level 4: 121 122
Level 4: 123 124
Level 4: 125 126
Level 2: 133 139
Level 3: 129 131
Level 4: 127 128
Level 4: 129 130
Level 4: 131 132
Level 3: 135 137
Level 4: 133 134
Level 4: 135 136
Level 4: 137 138
Level 3: 141 143
Level 4: 139 140
Level 4: 141 142
Level 4: 143 144
Level 2: 151 157
Level 3: 147 149
Level 4: 145 146
Level 4: 147 148
Level 4: 149 150
Level 3: 153 155
Level 4: 151 152
Level 4: 153 154
Level 4: 155 156
Level 3: 159 161
Level 4: 157 158
Level 4: 159 160
Level 4: 161 162
Level 1: 181
Level 2: 169 175
Level 3: 165 167
Level 4: 163 164
Level 4: 165 166
Level 4: 167 168
Level 3: 171 173
Level 4: 169 170
Level 4: 171 172
Level 4: 173 174
Level 3: 177 179
Level 4: 175 176
Level 4: 177 178
Level 4: 179 180
Level 2: 187 193
Level 3: 183 185
Level 4: 181 182
Level 4: 183 184
Level 4: 185 186
Level 3: 189 191
Level 4: 187 188
Level 4: 189 190
Level 4: 191 192
Level 3: 195 197 199
Level 4: 193 194
Level 4: 195 196
Level 4: 197 198
Level 4: 199 200 Searching keys:
Key 5 not found.
Key 8 not found.
Key 11 not found.
Key 14 not found.Range query [7, 15]:
Key: 7, Value: 700
Key: 8, Value: 800
Key: 9, Value: 900
Key: 10, Value: 1000
Key: 11, Value: 1100
Key: 12, Value: 1200
Key: 13, Value: 1300
Key: 14, Value: 1400
Key: 15, Value: 1500Deleting keys 8, 12, 15...B Tree structure after deletion:
Level 0: 55 109 163
Level 1: 19 37
Level 2: 7 21997
Level 3: 3 32545
Level 4: 1 2
Level 4: 3 4
Level 4: 5 6
Level 3: 9 11
Level 4: 7 8
Level 4: 9 10
Level 4: 11 12
Level 3: 15 17
Level 4: 13 14
Level 4: 15 16
Level 4: 17 18
Level 2: 25 31
Level 3: 21 23
Level 4: 19 20
Level 4: 21 22
Level 4: 23 24
Level 3: 27 29
Level 4: 25 26
Level 4: 27 28
Level 4: 29 30
Level 3: 33 35
Level 4: 31 32
Level 4: 33 34
Level 4: 35 36
Level 2: 43 49
Level 3: 39 41
Level 4: 37 38
Level 4: 39 40
Level 4: 41 42
Level 3: 45 47
Level 4: 43 44
Level 4: 45 46
Level 4: 47 48
Level 3: 51 53
Level 4: 49 50
Level 4: 51 52
Level 4: 53 54
Level 1: 73 91
Level 2: 61 67
Level 3: 57 59
Level 4: 55 56
Level 4: 57 58
Level 4: 59 60
Level 3: 63 65
Level 4: 61 62
Level 4: 63 64
Level 4: 65 66
Level 3: 69 71
Level 4: 67 68
Level 4: 69 70
Level 4: 71 72
Level 2: 79 85
Level 3: 75 77
Level 4: 73 74
Level 4: 75 76
Level 4: 77 78
Level 3: 81 83
Level 4: 79 80
Level 4: 81 82
Level 4: 83 84
Level 3: 87 89
Level 4: 85 86
Level 4: 87 88
Level 4: 89 90
Level 2: 97 103
Level 3: 93 95
Level 4: 91 92
Level 4: 93 94
Level 4: 95 96
Level 3: 99 101
Level 4: 97 98
Level 4: 99 100
Level 4: 101 102
Level 3: 105 107
Level 4: 103 104
Level 4: 105 106
Level 4: 107 108
Level 1: 127 145
Level 2: 115 121
Level 3: 111 113
Level 4: 109 110
Level 4: 111 112
Level 4: 113 114
Level 3: 117 119
Level 4: 115 116
Level 4: 117 118
Level 4: 119 120
Level 3: 123 125
Level 4: 121 122
Level 4: 123 124
Level 4: 125 126
Level 2: 133 139
Level 3: 129 131
Level 4: 127 128
Level 4: 129 130
Level 4: 131 132
Level 3: 135 137
Level 4: 133 134
Level 4: 135 136
Level 4: 137 138
Level 3: 141 143
Level 4: 139 140
Level 4: 141 142
Level 4: 143 144
Level 2: 151 157
Level 3: 147 149
Level 4: 145 146
Level 4: 147 148
Level 4: 149 150
Level 3: 153 155
Level 4: 151 152
Level 4: 153 154
Level 4: 155 156
Level 3: 159 161
Level 4: 157 158
Level 4: 159 160
Level 4: 161 162
Level 1: 181
Level 2: 169 175
Level 3: 165 167
Level 4: 163 164
Level 4: 165 166
Level 4: 167 168
Level 3: 171 173
Level 4: 169 170
Level 4: 171 172
Level 4: 173 174
Level 3: 177 179
Level 4: 175 176
Level 4: 177 178
Level 4: 179 180
Level 2: 187 193
Level 3: 183 185
Level 4: 181 182
Level 4: 183 184
Level 4: 185 186
Level 3: 189 191
Level 4: 187 188
Level 4: 189 190
Level 4: 191 192
Level 3: 195 197 199
Level 4: 193 194
Level 4: 195 196
Level 4: 197 198
Level 4: 199 200 Range query [7, 15] after deletion:
Key: 7, Value: 700
Key: 8, Value: 800
Key: 9, Value: 900
Key: 10, Value: 1000
Key: 11, Value: 1100
Key: 12, Value: 1200
Key: 13, Value: 1300
Key: 14, Value: 1400
Key: 15, Value: 1500
qimingqiming:~/share/CTASK/data-structure$
