【数据结构】B 树——高度近似可”独木成林“的榕树——详细解说与其 C 代码实现
文章目录
- B 树的严格定义
- B 树的组织数据的方法
- B 树插入一个新的键值对数据的方法
- B 树删除一个键值对数据的方法
- 把 B 树看作是 “可独木成林的榕树” —— 我记忆和理解 B 树的方法
- B 树的 C 代码实现
- 创建节点、删除节点与初始化 B 树
- B 树节点内的二分查找
- 插入数据（带有节点分裂的功能）
- 删除数据（带有向兄弟节点借数据以及节点合并的功能）
- B 树的打印功能
- 测试代码（主函数）
推荐一个零声教育学习教程，个人觉得老师讲得不错，分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，点击立即学习: https://github.com/0voice 链接。
B 树的严格定义
B 树是一个针对单个有序的索引指标的数据列（键值对型的数据列 ）的高效查询算法，它提供了一个组织数据的方法，按照这个方法先行组织数据，而后能高效率的对某个索引键的数据进行查询，而后实现快速的范围查询。
B树是一种多路平衡查找树，它满足以下性质：
我们常说的 B+ 树，通常都是说 “ m 阶的 B+ 树 ” ，即每一个节点都不能有超过 m-1 个键，不超过 m 个子节点（那也就是说共 2m−12m-12m−1 项内容）。B 树有 7 条定义律（从 3 个方面来讲述） ：
- 节点结构：
1、每个节点包含若干个键值（key）和子节点指针。
2、每个节点最多有 M 个子节点，最少有 ⌈M/2⌉⌈M/2⌉⌈M/2⌉ 个子节点（根节点除外）。
3、每个节点最多有 M−1 个键值，最少有 ⌈M/2⌉−1⌈M/2⌉−1⌈M/2⌉−1 个键值。
4、每个节点的键值是有序的，子节点指针将数据划分为不同的区间。 - 根节点：
5、根节点至少有两个子节点（如果根节点不是叶子节点）。根节点是一个构成性的例外，这样能为算法在不断插入新节点的时候，节点不断地在分裂和上溢时，更新 B+ 树的同时，作定义上的兜底。
6、如果根节点是叶子节点，则它可以至少只包含一个键值。 - 叶子节点：
7、所有叶子节点都在同一层。
根据以上定义，我们以 3 阶 B 树为例，具体解释这些定义的作用。 每个节点至多拥有 3−1=23-1=23−1=2 个键，至多 3 个子节点。我们可以想象它的节点是长这样的，2 个键值对数据，键是某个具体数据块的索引 key，key 是可以用来与查询键比大小而后查询出数据的具体位置，从哪条通路走下去；3 个路由指针，每个路由指针指向子节点的地址，这就是导引查询数据的通路。（这只是其中一种情况，可以是 1 个键值对数据，两个路由指针）
+-------------+--------------+---------------+--------------+---------------+
| 指针0 (p0) | (k1) + data | 指针1 (p1) | (k2) + data | 指针2 (p2) |
+-------------+--------------+---------------+--------------+---------------+
3 阶 B 树的叶子节点和中间节点的关系则如下所示（不要介意，下图的键值不重要，只是演示一下）
+-------------+--------------+---------------+--------------+---------------+| 指针0 (p0) | (k1) + data | 指针1 (p1) | (k2) + data | 指针2 (p2) |+-------------+--------------+---------------+--------------+---------------+| | |___________________________________________________________________________________| | |_______________________| | |\ | / \ | / \ | /\|/ \|/ \|/
+-------------+--------------+---------------+--------------+---------------+ +-------------+--------------+---------------+--------------+---------------+ +-------------+--------------+---------------+--------------+---------------+
| 指针0 (p0) | (k1) + data | 指针1 (p1) | (k2) + data | 指针2 (p2) | | 指针0 (p0) | (k1) + data | 指针1 (p1) | (k2) + data | 指针2 (p2) | | 指针0 (p0) | (k1) + data | 指针1 (p1) | (k2) + data | 指针2 (p2) |
+-------------+--------------+---------------+--------------+---------------+ +-------------+--------------+---------------+--------------+---------------+ +-------------+--------------+---------------+--------------+---------------+B 树的组织数据的方法
只有合理的组织数据，才会有高效率的查询。所谓的 ‘’组织数据“ ，就是插入键值对数据（注意，这不是插入节点！原因是一个节点有可能会有好几份数据。）以及删除键值对数据。
我们仍以 3 阶的 B 树为例子，去讲述插入键值数据和删除键值数据的步骤。为方便展示，我把数据和路由指针略去，仅展示键信息，比如下图的 32、46 我将之指代为键 key 的数值，路由指针用一条小缝表示。
++--++--++
||32||46||
++--++--++B 树插入一个新的键值对数据的方法
情况一：根节点满员，往根节点再插入一个节点
在根节点满员之后，增加数据键 56++--++--++--++||32||46||50||++--++--++--++
增加数据键 56 之后，超员了，往中间分裂++--++--++--++--++||32||46||50||56||++--++--++--++--++
节点分裂++--++||50||++--++/ \/ \/ \++--++--++ ++--++||32||46|| ||56||++--++--++ ++--++
情况二：正常插入
插入 56 键++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++--++ ++--++--++
||25||30|| ||33||43|| ||47||50||
++--++--++ ++--++--++ ++--++--++++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++--++ ++--++--++--++
||25||30|| ||33||43|| ||47||50||56||
++--++--++ ++--++--++ ++--++--++--++
情况三：所插入的节点满员了，进行节点分裂，中间数据上溢。
插入键 45 的数据（往中间插入的节点）++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++--++--++ ++--++--++
||25||30|| ||33||43||44|| ||49||50||
++--++--++ ++--++--++--++ ++--++--++
插入数据后，发现所插入的节点数据超员了，进行节点分裂，数据上溢++--++--++||32||46||++--++--++/ | \__/ | \_________/ | \/ | \
++--++--++ ++--++--++--++--++ ++--++--++
||25||30|| ||33||43||44||45|| ||49||50||
++--++--++ ++--++--++--++--++ ++--++--++
中间节点上溢，之后的节点分成两半++--++--++--++||32||43||46||++--++--++--++/ | | \__/ | | \_________/ | | \/ | | \
++--++--++ ++--++ ++--++--++ ++--++--++
||25||30|| ||33|| ||44||45|| ||49||50||
++--++--++ ++--++ ++--++--++ ++--++--++
情况四：父节点和插入数据的节点都满员了。——我们可以参考下文的代码，我所采用的策略是预先节点分裂，确保这种情况不会出现（父节点一定不会埋怨）。
++--++--++--++||32||46||55||++--++--++--++/ | \ \______________ __/ | \__ \__ / | \ \/ | \ \
++--++--++ ++--++--++--++ ++--++--++ ++--++--++
||25||30|| ||33||43||44|| ||49||50|| ||49||50||
++--++--++ ++--++--++--++ ++--++--++ ++--++--++
B 树删除一个键值对数据的方法
情况一：删除一个键值对数据后，该结点处的数据数量还在半数以上，正常删除
删除 43 键对应的数据++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++--++ ++--++--++
||25||30|| ||33||43|| ||47||50||
++--++--++ ++--++--++ ++--++--++删除后++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++ ++--++--++
||25||30|| ||33|| ||46||50||
++--++--++ ++--++ ++--++--++
情况二：删除一个键值对数据后，该节点的数据不够半数。兄弟节点的需要抵押给父节点，父节点再把自身对应的数据过继给子节点。
删除 33 键所对应的数据++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++ ++--++--++
||25||30|| ||33|| ||46||50||
++--++--++ ++--++ ++--++--++删除后，发现不满足 B树的定义++--++--++||32||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++--++ ++--++--++
||25||30|| ||47||50||
++--++--++ ++--++--++
向兄弟节点借数据（优先向数据量多的节点借，左右节点数量相同的话优先向左节点借）兄弟节点的需要抵押给父节点，父节点再把自身对应的数据过继给子节点。++--++--++||30||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++ ++--++ ++--++--++
||25|| ||32|| ||47||50||
++--++ ++--++ ++--++--++
情况三：删除一个键值对数据后，该节点的数据不够半数。左右兄弟节点都刚好在半数，不能再往外借数据。
删除 32 键，对应的节点只有 32 键这一对数据。++--++--++||30||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++ ++--++ ++--++
||25|| ||32|| ||50||
++--++ ++--++ ++--++兄弟节点全部都刚好在半数，无法借出数据++--++--++||30||46||++--++--++/ | \__/ | \__/ | \/ | \
++--++ ++--++
||25|| ||50||
++--++ ++--++优先与右节点合并，并且，继承来自父节点的数据++--++||30||++--++/ | __/ | / | / |
++--++ ++--++--++
||25|| ||46||50||
++--++ ++--++--++
情况四：删除一个键值对数据后，该节点的数据不够半数。父节点与兄弟节点都刚好在半数，无法输出数据。——我们可以参考下文的代码，我所采用的策略是预先合并，确保这种情况不会出现。
++--++||30||++--++/ \__/ \__/ \/ \
++--++ ++--++
||25|| ||50||
++--++ ++--++
把 B 树看作是 “可独木成林的榕树” —— 我记忆和理解 B 树的方法
榕树是南方最常见的树种之一，我发现它的气生根现象高度与 B 树的数据结构契合
以下将高山榕/垂叶榕的气生根独木成林现象作为核心比喻，系统化映射到 B树 的数据结构与操作上，涵盖数据定义、插入、删除、查询等全过程：
B树的榕树化定义
| 计算机科学术语 | 榕树生物学比喻 | 核心逻辑 |
|---|---|---|
| B树节点 | 榕树的枝条系统 | 每条枝条（节点）承载果实（键值对数据）和分叉点（指针） |
| 节点键值 k[i] | 枝条上的果实 | 果实按大小有序排列（键值有序） |
| 子节点指针 p[i] | 枝条的分叉点 | 分叉点长出次级枝条（子树） |
| 节点容量上限 M | 枝条的承重极限 | 枝条果实过多会下垂气生根（触发分裂） |
| 根节点 | 主树干 | 最初生长起点，支撑整棵树结构 |
| 叶子节点 | 最外层小枝条 | 无次级分叉（无子树指针），直接结果 |
| 内部节点 | 中层分枝 | 既结果又分叉（存键值+子树指针） |
| 节点填充因子 | 枝条疏密程度 | 最低 ⌈M/2⌉-1 果保障承重效率（防枝条枯萎） |
B树操作在榕树比喻中的演绎
-
插入键值 → 枝条结果触发气根下垂
场景：向节点插入新键值 k
比喻：在枝条某处新结一颗果实（插入键值）→ 若果实总数超过枝条承重极限（M） → 枝条末端下垂气生根（标记分裂需求）。 -
节点分裂 → 气根入土成新支柱
场景：节点键值数 > M-1
比喻：分裂三步骤：
1、气根触地：下垂气生根接触土壤（分裂开始）
2、果实分配：原枝条保留左侧 ⌈M/2⌉-1 颗果实，中间果实上升至父枝条分叉处（如[果15]上升），右侧 ⌊M/2⌋ 颗果实移入新生的支柱根（兄弟节点）
3、结构重组：新支柱根继承原枝条的次级分叉（子树指针），父枝条在上升果实处分出新叉口连接支柱根 -
递归分裂 → 主干分叉层叠生长
场景：上升键导致父节点超限
比喻：若上升果实使父枝条也超重 → 父枝条同样下垂气生根 → 分裂向主干递归，直至树根。根分裂时：原主干成新支柱根，上升果实成为新主干（树增高）。 -
删除键值 → 枝条枯萎引发结构重组
场景：删除后 节点键值数<⌈M/2⌉−1节点键值数 < ⌈M/2⌉-1节点键值数<⌈M/2⌉−1
比喻：三种修复策略：
1、借果邻枝：相邻枝条通过气根导管传递一颗果实（兄弟节点重分配）
2、合并支柱根：若邻枝果实也紧张 → 两根支柱融合为一根，父枝条分叉点减少（节点合并）
3、主干收缩：若合并导致父枝条过疏 → 递归向上调整直至主干（根节点可能高度降低） -
键值查询 → 养料运输路径搜索
场景：查找键 k
比喻：从主干开始：
1、检测枝条果实序列，找到包含 k 的区间（如 果5 < k < 果15）
2、沿对应分叉点进入次级枝条
3、重复直至最外层枝条找到目标果实（或确认不存在）如同水分从主干经分叉导管流向特定叶片。
为何此比喻契合B树本质？
-
动态平衡性：
气生根遇土成支柱 ≈ 节点分裂实现原位扩展，合并支柱 ≈ 删除时的结构收缩，保持 O(log n) 稳定性。 -
多层级导航
主干→分枝→叶枝 ≈ B树多级索引结构，内部节点同时存导航键与数据（区别于B+树）。 -
自底向上递归
分裂/合并从叶向根传递 ≈ 气生根生长由枝条末端触发，最终改变主干形态。 -
空间约束
枝条承重极限 ≈ 节点大小受磁盘页限制（数据库核心设计点）。
B 树的 C 代码实现
我们需要明确的一点是
数据结构=数据定义+数据的操作方法。数据结构 = 数据定义 + 数据的操作方法。数据结构=数据定义+数据的操作方法。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>#define DEGREE 3
typedef int KEY_VALUE;typedef struct _btree_node {KEY_VALUE *keys; // 键数组struct _btree_node **childrens; // 路由指针数组void** values;// 考虑具体情况，增加万能指针int num; // 当前节点有多少个数据int leaf; // 判断是否为叶子节点，区分叶子节点是因为，叶子是无子节点的
} btree_node;typedef struct _btree {btree_node *root; // 根节点int t; // 这不是 B 树的阶数，2t 才是阶数，能承接 2t-1 个数据
} btree;- KEY_VALUE 不一定非就得整型
- 0 和 num-1 是最特殊的两个数字，因为借数据的时候需要经常使用
- num 用来判断是否有足够的余粮（t 个是足够的）；是否过载需要分裂 （2t-1 就是过载）
- 区分叶子节点，叶子节点在删除、插入时无需关注子节点，因为它们就无子节点；另一方面，叶子节点无需关心其父节点的节点分裂、节点合并、向兄弟借数据，因为早已有一套未雨绸缪机制，先行处理了这些隐患
- 2t-1 是数据承载量，2t 是阶数（最多有多少个子节点），t-1 是小半数
创建节点、删除节点与初始化 B 树
t 不是 B 树的阶数，2t 才是阶数，能承接 2t-1 个数据
btree_node *btree_create_node(int t, int leaf) {// 根节点一开始是一个叶子节点btree_node *node = (btree_node*)calloc(1, sizeof(btree_node));if (node == NULL) assert(0); // 用来终止程序的node->leaf = leaf;node->keys = (KEY_VALUE*)calloc(1, (2*t-1)*sizeof(KEY_VALUE)); // 能承接 2t-1 个数据// 必须要注意，keys 的初始化一定要设置一个最小值，不能与任何一个插入值重复，否则会判定为曾经插入，而没有把真正的数据插入，导致路标指针无效化。node->values = calloc(1, (2*t-1)*sizeof(void*));node->childrens = (btree_node**)calloc(1, (2*t) * sizeof(btree_node*)); // 2t 才是阶数memset(node->childrens, 0, (2*t)*sizeof(btree_node*));node->num = 0; // 一开始只有 0 个数据return node;
}void btree_destroy_node(btree_node *node) {assert(node); //输入错误则终止程序// 一个节点只有键数组、路由指针数组是通过 malloc 创造的free(node->childrens);free(node->keys);free(node);// 如果设置了数据
}btree* btree_create(int t) {btree* T =(btree*)malloc(sizeof(btree));T->t = t; // t-1 指代一个节点的最低半数btree_node *x = btree_create_node(t, 1); // 创造一个节点（初始状态、节点分裂的时候会调用）T->root = x;return T;
}B 树节点内的二分查找
// 在节点中查找键的位置，找到就最好，找不到那就以此为路标走向下一层
int btree_bin_search(btree_node *node, int low, int high, KEY_VALUE 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;
}
插入数据（带有节点分裂的功能）
函数 btree_insert_nonfull 是有预先触发节点分裂的效果的。
void btree_split_child(btree *T, btree_node *x, int i) {// 这就是插入过量数据时产生的节点分裂// 左兄弟点沿用原来的节点，新分裂的节点要自己创建// i 指代第几个子节点（本节点的第几个路由指针）// x 是所操作节点的父节点，分裂的时候产生一个右兄弟节点 z // x 和 z （父节点、右子节点）的数据排布大改int t = T->t;btree_node *y = x->childrens[i]; // y 和 z 是成对的，z 承接来自 y 的溢出，x 是 y 和 z 共同的父亲btree_node *z = btree_create_node(t, y->leaf); // 同一层级产生的节点具有相同的性质z->num = t - 1; // 除了根节点之外，其余的节点创立时，都继承来自左兄弟节点的 t-1 个数据int j = 0;for (j = 0;j < t-1;j ++) {z->keys[j] = y->keys[j+t]; // z 节点继承左兄弟节点 y 的数据，注意到 y 的第 t 位数据，将会上供给父节点z->values[j] = y->values[j+t];}if (y->leaf == 0) { // 兄弟节点要么都是叶子，要么都不是叶子for (j = 0;j < t;j ++) {z->childrens[j] = y->childrens[j+t]; // 右子节点继承左兄弟节点的路由指针，刚好够平分}}y->num = t - 1; // 左兄弟节点只剩下 t-1 个数据，至于当前 y 还未清除的后 t 个数据不着急删除，num 的更改相当于让他们都被除名了for (j = x->num;j >= i+1;j --) { // 处理父节点 x 处的路由指针x->childrens[j+1] = x->childrens[j]; // 为了塞一个路由指针，而腾挪空间}x->childrens[i+1] = z;for (j = x->num-1;j >= i;j --) { // 处理父节点 x 处的键列x->keys[j+1] = x->keys[j]; // 为了塞一个键，而腾挪空间x->values[j+1] = x->values[j];}x->keys[i] = y->keys[t-1];x->values[i] = y->values[t-1];x->num += 1; // 父节点的计数 +1
}void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k, void* value) {// 这就是插入适量的数据，没超过节点的数据承载量，只需简单的调整//int idx = find_key_index(x, k);int idx = btree_bin_search(x, 0, x->num, k);if (x->leaf == 1) { // 叶子节点可以直接插入，而无需管路由指针// 如果键已存在，更新值，或者做出提醒if ( x->keys[idx] == k) {//leaf->data_ptrs[idx] = value;printf("the key (%d) has been inserted\n", x->keys[idx]);return;}for (int i=x->num; i>idx; i--) {x->keys[i] = x->keys[i-1];x->values[i] = x->values[i-1];}x->keys[idx] = k; // 此时的 i 有可能就是 -1x->values[idx] = value;x->num += 1;} else {// 中间节点则找目标节点的 ”后继点“// 如果键已存在，更新值if ( x->keys[idx] == k) {//leaf->data_ptrs[idx] = value;printf("the key (%d) has been inserted\n", x->keys[idx]);return;}// 这是要做保险的，因为在向内搜索到最终端的叶子节点，先要检查子节点是否到了承载上限了，如果是，则要节点分裂，向上传递数据入父节点// 因为真到了终端的叶子节点处发生节点分裂，那么上面的父节点也必定是需要分裂节点的，这是未雨绸缪的思路if (x->childrens[idx]->num == (2*(T->t))-1) {btree_split_child(T, x, idx); // 注意，当左子节点分裂时，本父节点是发生了变化的if (x->keys[idx] < k) idx++; // 注意，当左子节点分裂时，本父节点是发生了变化的}btree_insert_nonfull(T, x->childrens[idx], k, value); // 递归向下地搜索子节点}
}void btree_insert(btree *T, KEY_VALUE key, void* value) {//int t = T->t;// 这个函数也是未雨绸缪的思路btree_node *r = T->root;if (r->num == 2 * (T->t) - 1) {btree_node *node = btree_create_node(T->t, 0); // 节点分裂，数据上溢时，父节点在这里创建，而右子节点在 btree_split_child 函数里创建T->root = node;node->childrens[0] = r;btree_split_child(T, node, 0);int i = 0;if (node->keys[0] < key) i++;btree_insert_nonfull(T, node->childrens[i], key, value);} else {// 根节点已经做好兜底了，可以安心的插入，安心的节点分裂btree_insert_nonfull(T, r, key, value);}
}删除数据（带有向兄弟节点借数据以及节点合并的功能）
函数 btree_delete_key 是可以预先触发节点合并与向兄弟节点借数据的，不一定非得到点到情况才触发。
//{child[idx], key[idx], child[idx+1]}
void btree_merge(btree *T, btree_node *node, int idx) {// idx 指代第几个键，也就对应着第几个路由指针// node 是所删数据对应节点的父节点，这是配合函数 btree_delete_key 的递归// 这就是删除过量数据且兄弟节点无数据可借时产生的节点合并（兄弟节点的数据量都是 t-1 个），删除数据所对应节点的右兄弟节点合并到本节点上，既然是合并节点，那么父节点处的数据也必须少一个// 本节点相应的数据还没被删除，我们是先合并后删除，合并右节点（获取 t-1 个数据），父节点失去一个数据（本节点获取 1 个数据），本节点共获取 t 个数据，完成该函数后共有 2t-1 个数据，满数据了btree_node *left = node->childrens[idx]; // 第 idx 个键的左子节点（所删数据对应的节点）btree_node *right = node->childrens[idx+1]; // 第 idx 个键的右子节点（所需合并的右子节点）int i = 0;/////data mergeleft->keys[T->t-1] = node->keys[idx]; // 从父结点处借一个数据，把右兄弟节点的都搬到本节点处left->values[T->t-1] = node->values[idx];for (i = 0;i < T->t-1;i ++) {left->keys[T->t+i] = right->keys[i]; // 把右兄弟节点的都搬到本节点处left->values[T->t+i] = right->values[i];}if (!left->leaf) { // 叶子节点暂时还没有子节点的路由指针for (i = 0;i < T->t;i ++) {left->childrens[T->t+i] = right->childrens[i];}}left->num += T->t; // 本节点共获取了 t = (t-1) + 1 个数据//destroy rightbtree_destroy_node(right); // 现在右节点的数据已经搬完了，可以过河拆桥了//node for (i = idx+1;i < node->num;i ++) { // 父结点处删减一个数据后需要重新排列数据node->keys[i-1] = node->keys[i];node->values[i-1] = node->values[i];node->childrens[i] = node->childrens[i+1];}node->childrens[i+1] = NULL;node->num -= 1;if (node->num == 0) { // 只有根节点会出现这种情况T->root = left;btree_destroy_node(node);}
}void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) {// node 是用来作函数递归的，一开始是从 root 无限递归下去if (node == NULL) return;int idx = 0, i;idx = btree_bin_search(node, 0, node->num, key); // 在本节点中寻找最合适的通路（决定是否往下走或者是找到目标点了）if (idx < node->num && key == node->keys[idx]) {// 在本节点中找到了对应的数据if (node->leaf) {// 叶子节点free(node->values[idx]);for (i = idx;i < node->num-1;i ++) {node->keys[i] = node->keys[i+1]; // 删除一个键后，往前挪node->values[i] = node->values[i+1];}node->keys[node->num - 1] = 0;node->num--;if (node->num == 0) { //rootfree(node);T->root = NULL;}return ;} else if (node->childrens[idx]->num >= T->t) {// 非叶子节点，需要找 “前驱点” 去代替这个节点的数据块被删// 寻找 “前驱点” ，并且把沿途的值全部接力式的往上搬free(node->values[idx]);btree_node *left = node->childrens[idx]; node->keys[idx] = left->keys[left->num - 1];node->values[idx] = left->values[left->num - 1];btree_delete_key(T, left, left->keys[left->num - 1]);} else if (node->childrens[idx+1]->num >= T->t) {// 非叶子节点，需要找 “后继点” 去代替这个节点的数据块被删// 寻找 “后继点”free(node->values[idx]);btree_node *right = node->childrens[idx+1];node->keys[idx] = right->keys[0];node->values[idx] = right->values[0];btree_delete_key(T, right, right->keys[0]);} else {// 左右子节点的数据块都不够了，那就合并，再继续往下找替死鬼 （后继点或者前驱点）// 这里体现了 "未雨绸缪"，尽管当前各个节点都不缺数据，但是一旦在底部删了一个数据而后又出现了父节点，或者兄弟节点不够多余数据的时候，又会触发合并，不如提前合并了好。btree_merge(T, node, idx); // 先合并btree_delete_key(T, node->childrens[idx], key); // 后删除}} else {// 在本节点中找不到目标键btree_node *child = node->childrens[idx]; // 左子节点if (child == NULL) {printf("Cannot del key = %d\n", key);return ;}if (child->num == T->t - 1) {// 意思是左子节点不够数据块了，需要找左子节点的左兄弟节点和右子兄弟节点去借btree_node *left = NULL;btree_node *right = NULL;if (idx - 1 >= 0)left = node->childrens[idx-1];if (idx + 1 <= node->num) right = node->childrens[idx+1];if ((left && left->num >= T->t) || (right && right->num >= T->t)) {// 至少有一个兄弟是足够数据块的int richR = 0;if (right) richR = 1; // 暂且认为右兄弟更有钱if (left && right) richR = (right->num > left->num) ? 1 : 0; // 判断哪个兄弟更有钱if (right && right->num >= T->t && richR) { //borrow from next 向右兄弟去借，右兄弟给父节点，父节点的给本节点child->keys[child->num] = node->keys[idx];child->values[child->num] = node->values[idx];child->childrens[child->num+1] = right->childrens[0];child->num ++;node->keys[idx] = right->keys[0];node->values[idx] = right->values[0];for (i = 0;i < right->num - 1;i ++) { // 右兄弟调整right->keys[i] = right->keys[i+1];right->values[i] = right->values[i+1];right->childrens[i] = right->childrens[i+1];}right->keys[right->num-1] = 0;right->values[right->num-1] = NULL;right->childrens[right->num-1] = right->childrens[right->num];right->childrens[right->num] = NULL;right->num --;} else { //borrow from prev// 发现左兄弟更有钱，左兄弟把自己的数据块抵押给父亲，父亲在汇款给本节点for (i = child->num;i > 0;i --) {child->keys[i] = child->keys[i-1];child->values[i] = child->values[i-1];child->childrens[i+1] = child->childrens[i];}child->childrens[1] = child->childrens[0];child->childrens[0] = left->childrens[left->num];child->keys[0] = node->keys[idx-1];child->values[0] = node->values[idx-1];child->num ++;node->keys[idx-1] = left->keys[left->num-1];node->values[idx-1] = left->values[left->num-1];left->keys[left->num-1] = 0;left->values[left->num-1] = NULL;left->childrens[left->num] = NULL;left->num --;}} else if ((!left || (left->num == T->t - 1)) && (!right || (right->num == T->t - 1))) {// 发现左右兄弟家里都没余粮了，优先和左兄弟家合并。if (left && left->num == T->t - 1) {btree_merge(T, node, idx-1); child = left;} else if (right && right->num == T->t - 1) {btree_merge(T, node, idx);}}}btree_delete_key(T, child, key); // 路径安全了，再删节点}}int btree_delete(btree *T, KEY_VALUE key) {if (!T->root) return -1;btree_delete_key(T, T->root, key); // 从根节点往下找起，找 key 这一点后把它删掉return 0;
}B 树的打印功能
// 其实就是中序遍历
void btree_traverse(btree_node *x) {// 按顺序打印子 B 树 x 的所有数据if (x==NULL) return;int i = 0;for (i = 0;i < x->num;i ++) {if (x->leaf == 0) btree_traverse(x->childrens[i]); // 递归向下，走到终端，打印叶子节点的数据printf("%d ", x->keys[i]); // 数字转字符表出，把子节点的内容打印一遍后，才打印父节点的一个数据点}if (x->leaf == 0) btree_traverse(x->childrens[i]); // 节点就只有 x->num 个数据，但是父节点却有 (x->num) + 1 个子节点，这行代码正是为了弥补最后一个子节点//printf("\n");
}void btree_print(btree *T, btree_node *node, int layer)
{// layer 是程序员人为设定的 node 现在处于第几层，比如 root 就是在第 0 层btree_node* p = node; // 打印 node 及其子节点int i;if (p) {printf("\nlayer = %d keynum = %d is_leaf = %d\n", layer, p->num, p->leaf); // 先描述统计，而后打印for(i = 0; i < node->num; i++) printf("%d ", p->keys[i]);printf("\n");layer++; // 每个分支都是在打完本节点内容后，把层数 +1，然后才是打印若干子节点for(i = 0; i <= p->num; i++) // 连同最后一个子节点（路由指针）都遍历完if(p->childrens[i]) btree_print(T, p->childrens[i], layer); // 递归向下}else printf("the print task has some errors in key\n"); // 结束//printf("the print task is end\n");
}测试代码（主函数）
#define test_num 1000
int main() {btree* T = btree_create(10); // 树的根节点, 6 阶的 B 树//srand(48);int keys[test_num]={0}, i = 0;int** values = malloc(test_num*sizeof(int*));for (i = 50;i < test_num/2;i ++) {//keys[i] = rand() ;keys[i] =i+10;values[i] = malloc(sizeof(int));*(values[i]) = i+7;btree_insert(T, keys[i], values[i]);}for (i = test_num/2;i < test_num;i ++) {//keys[i] = rand() ;keys[i] =i+100;values[i] = malloc(sizeof(int));*(values[i]) = i+7;btree_insert(T, keys[i], values[i]);}btree_print(T, T->root, 0);printf("\n---------------------------------\n");for (i = 0;i < 26;i ++) {printf("the key %d has been deleted\n", keys[i]);btree_delete(T, keys[i]);//btree_traverse(T.root);}printf("\n---------------------------------\n");btree_traverse(T->root);btree_print(T, T->root, 0);printf("\n---------------------------------\n");}
运行代码。运行情况是 OK 的。
qiming@qiming:~/share/CTASK/data-structure$ gcc -o btree btree.c
qiming@qiming:~/share/CTASK/data-structure$ ./btreelayer = 0 keynum = 8 is_leaf = 0
159 259 359 459 649 749 849 949 layer = 1 keynum = 9 is_leaf = 0
69 79 89 99 109 119 129 139 149 layer = 2 keynum = 9 is_leaf = 1
60 61 62 63 64 65 66 67 68 layer = 2 keynum = 9 is_leaf = 1
70 71 72 73 74 75 76 77 78 layer = 2 keynum = 9 is_leaf = 1
80 81 82 83 84 85 86 87 88 layer = 2 keynum = 9 is_leaf = 1
90 91 92 93 94 95 96 97 98 layer = 2 keynum = 9 is_leaf = 1
100 101 102 103 104 105 106 107 108 layer = 2 keynum = 9 is_leaf = 1
110 111 112 113 114 115 116 117 118 layer = 2 keynum = 9 is_leaf = 1
120 121 122 123 124 125 126 127 128 layer = 2 keynum = 9 is_leaf = 1
130 131 132 133 134 135 136 137 138 layer = 2 keynum = 9 is_leaf = 1
140 141 142 143 144 145 146 147 148 layer = 2 keynum = 9 is_leaf = 1
150 151 152 153 154 155 156 157 158 layer = 1 keynum = 9 is_leaf = 0
169 179 189 199 209 219 229 239 249 layer = 2 keynum = 9 is_leaf = 1
160 161 162 163 164 165 166 167 168 layer = 2 keynum = 9 is_leaf = 1
170 171 172 173 174 175 176 177 178 layer = 2 keynum = 9 is_leaf = 1
180 181 182 183 184 185 186 187 188 layer = 2 keynum = 9 is_leaf = 1
190 191 192 193 194 195 196 197 198 layer = 2 keynum = 9 is_leaf = 1
200 201 202 203 204 205 206 207 208 layer = 2 keynum = 9 is_leaf = 1
210 211 212 213 214 215 216 217 218 layer = 2 keynum = 9 is_leaf = 1
220 221 222 223 224 225 226 227 228 layer = 2 keynum = 9 is_leaf = 1
230 231 232 233 234 235 236 237 238 layer = 2 keynum = 9 is_leaf = 1
240 241 242 243 244 245 246 247 248 layer = 2 keynum = 9 is_leaf = 1
250 251 252 253 254 255 256 257 258 layer = 1 keynum = 9 is_leaf = 0
269 279 289 299 309 319 329 339 349 layer = 2 keynum = 9 is_leaf = 1
260 261 262 263 264 265 266 267 268 layer = 2 keynum = 9 is_leaf = 1
270 271 272 273 274 275 276 277 278 layer = 2 keynum = 9 is_leaf = 1
280 281 282 283 284 285 286 287 288 layer = 2 keynum = 9 is_leaf = 1
290 291 292 293 294 295 296 297 298 layer = 2 keynum = 9 is_leaf = 1
300 301 302 303 304 305 306 307 308 layer = 2 keynum = 9 is_leaf = 1
310 311 312 313 314 315 316 317 318 layer = 2 keynum = 9 is_leaf = 1
320 321 322 323 324 325 326 327 328 layer = 2 keynum = 9 is_leaf = 1
330 331 332 333 334 335 336 337 338 layer = 2 keynum = 9 is_leaf = 1
340 341 342 343 344 345 346 347 348 layer = 2 keynum = 9 is_leaf = 1
350 351 352 353 354 355 356 357 358 layer = 1 keynum = 9 is_leaf = 0
369 379 389 399 409 419 429 439 449 layer = 2 keynum = 9 is_leaf = 1
360 361 362 363 364 365 366 367 368 layer = 2 keynum = 9 is_leaf = 1
370 371 372 373 374 375 376 377 378 layer = 2 keynum = 9 is_leaf = 1
380 381 382 383 384 385 386 387 388 layer = 2 keynum = 9 is_leaf = 1
390 391 392 393 394 395 396 397 398 layer = 2 keynum = 9 is_leaf = 1
400 401 402 403 404 405 406 407 408 layer = 2 keynum = 9 is_leaf = 1
410 411 412 413 414 415 416 417 418 layer = 2 keynum = 9 is_leaf = 1
420 421 422 423 424 425 426 427 428 layer = 2 keynum = 9 is_leaf = 1
430 431 432 433 434 435 436 437 438 layer = 2 keynum = 9 is_leaf = 1
440 441 442 443 444 445 446 447 448 layer = 2 keynum = 9 is_leaf = 1
450 451 452 453 454 455 456 457 458 layer = 1 keynum = 9 is_leaf = 0
469 479 489 499 509 609 619 629 639 layer = 2 keynum = 9 is_leaf = 1
460 461 462 463 464 465 466 467 468 layer = 2 keynum = 9 is_leaf = 1
470 471 472 473 474 475 476 477 478 layer = 2 keynum = 9 is_leaf = 1
480 481 482 483 484 485 486 487 488 layer = 2 keynum = 9 is_leaf = 1
490 491 492 493 494 495 496 497 498 layer = 2 keynum = 9 is_leaf = 1
500 501 502 503 504 505 506 507 508 layer = 2 keynum = 9 is_leaf = 1
600 601 602 603 604 605 606 607 608 layer = 2 keynum = 9 is_leaf = 1
610 611 612 613 614 615 616 617 618 layer = 2 keynum = 9 is_leaf = 1
620 621 622 623 624 625 626 627 628 layer = 2 keynum = 9 is_leaf = 1
630 631 632 633 634 635 636 637 638 layer = 2 keynum = 9 is_leaf = 1
640 641 642 643 644 645 646 647 648 layer = 1 keynum = 9 is_leaf = 0
659 669 679 689 699 709 719 729 739 layer = 2 keynum = 9 is_leaf = 1
650 651 652 653 654 655 656 657 658 layer = 2 keynum = 9 is_leaf = 1
660 661 662 663 664 665 666 667 668 layer = 2 keynum = 9 is_leaf = 1
670 671 672 673 674 675 676 677 678 layer = 2 keynum = 9 is_leaf = 1
680 681 682 683 684 685 686 687 688 layer = 2 keynum = 9 is_leaf = 1
690 691 692 693 694 695 696 697 698 layer = 2 keynum = 9 is_leaf = 1
700 701 702 703 704 705 706 707 708 layer = 2 keynum = 9 is_leaf = 1
710 711 712 713 714 715 716 717 718 layer = 2 keynum = 9 is_leaf = 1
720 721 722 723 724 725 726 727 728 layer = 2 keynum = 9 is_leaf = 1
730 731 732 733 734 735 736 737 738 layer = 2 keynum = 9 is_leaf = 1
740 741 742 743 744 745 746 747 748 layer = 1 keynum = 9 is_leaf = 0
759 769 779 789 799 809 819 829 839 layer = 2 keynum = 9 is_leaf = 1
750 751 752 753 754 755 756 757 758 layer = 2 keynum = 9 is_leaf = 1
760 761 762 763 764 765 766 767 768 layer = 2 keynum = 9 is_leaf = 1
770 771 772 773 774 775 776 777 778 layer = 2 keynum = 9 is_leaf = 1
780 781 782 783 784 785 786 787 788 layer = 2 keynum = 9 is_leaf = 1
790 791 792 793 794 795 796 797 798 layer = 2 keynum = 9 is_leaf = 1
800 801 802 803 804 805 806 807 808 layer = 2 keynum = 9 is_leaf = 1
810 811 812 813 814 815 816 817 818 layer = 2 keynum = 9 is_leaf = 1
820 821 822 823 824 825 826 827 828 layer = 2 keynum = 9 is_leaf = 1
830 831 832 833 834 835 836 837 838 layer = 2 keynum = 9 is_leaf = 1
840 841 842 843 844 845 846 847 848 layer = 1 keynum = 9 is_leaf = 0
859 869 879 889 899 909 919 929 939 layer = 2 keynum = 9 is_leaf = 1
850 851 852 853 854 855 856 857 858 layer = 2 keynum = 9 is_leaf = 1
860 861 862 863 864 865 866 867 868 layer = 2 keynum = 9 is_leaf = 1
870 871 872 873 874 875 876 877 878 layer = 2 keynum = 9 is_leaf = 1
880 881 882 883 884 885 886 887 888 layer = 2 keynum = 9 is_leaf = 1
890 891 892 893 894 895 896 897 898 layer = 2 keynum = 9 is_leaf = 1
900 901 902 903 904 905 906 907 908 layer = 2 keynum = 9 is_leaf = 1
910 911 912 913 914 915 916 917 918 layer = 2 keynum = 9 is_leaf = 1
920 921 922 923 924 925 926 927 928 layer = 2 keynum = 9 is_leaf = 1
930 931 932 933 934 935 936 937 938 layer = 2 keynum = 9 is_leaf = 1
940 941 942 943 944 945 946 947 948 layer = 1 keynum = 14 is_leaf = 0
959 969 979 989 999 1009 1019 1029 1039 1049 1059 1069 1079 1089 layer = 2 keynum = 9 is_leaf = 1
950 951 952 953 954 955 956 957 958 layer = 2 keynum = 9 is_leaf = 1
960 961 962 963 964 965 966 967 968 layer = 2 keynum = 9 is_leaf = 1
970 971 972 973 974 975 976 977 978 layer = 2 keynum = 9 is_leaf = 1
980 981 982 983 984 985 986 987 988 layer = 2 keynum = 9 is_leaf = 1
990 991 992 993 994 995 996 997 998 layer = 2 keynum = 9 is_leaf = 1
1000 1001 1002 1003 1004 1005 1006 1007 1008 layer = 2 keynum = 9 is_leaf = 1
1010 1011 1012 1013 1014 1015 1016 1017 1018 layer = 2 keynum = 9 is_leaf = 1
1020 1021 1022 1023 1024 1025 1026 1027 1028 layer = 2 keynum = 9 is_leaf = 1
1030 1031 1032 1033 1034 1035 1036 1037 1038 layer = 2 keynum = 9 is_leaf = 1
1040 1041 1042 1043 1044 1045 1046 1047 1048 layer = 2 keynum = 9 is_leaf = 1
1050 1051 1052 1053 1054 1055 1056 1057 1058 layer = 2 keynum = 9 is_leaf = 1
1060 1061 1062 1063 1064 1065 1066 1067 1068 layer = 2 keynum = 9 is_leaf = 1
1070 1071 1072 1073 1074 1075 1076 1077 1078 layer = 2 keynum = 9 is_leaf = 1
1080 1081 1082 1083 1084 1085 1086 1087 1088 layer = 2 keynum = 10 is_leaf = 1
1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 ---------------------------------
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0
the key 0 has been deleted
Cannot del key = 0---------------------------------
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 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099
---------------------------------
Keys in range [0, 20]:
Keys in range [1010, 1020]: (1010: 917) (1011: 918) (1012: 919) (1013: 920) (1014: 921) (1015: 922) (1016: 923) (1017: 924) (1018: 925) (1019: 926) (1029: 936) (1020: 927)
Keys in range [505, 515]: (505: 502) (506: 503) (507: 504) (508: 505) (509: 506) (609: 516)
Keys in range [300, 325]: (300: 297) (301: 298) (302: 299) (303: 300) (304: 301) (305: 302) (306: 303) (307: 304) (308: 305) (309: 306) (319: 316) (310: 307) (311: 308) (312: 309) (313: 310) (314: 311) (315: 312) (316: 313) (317: 314) (318: 315) (320: 317) (321: 318) (322: 319) (323: 320) (324: 321) (325: 322)
Keys in range [600, 660]: (600: 507) (601: 508) (602: 509) (603: 510) (604: 511) (605: 512) (606: 513) (607: 514) (608: 515) (609: 516) (619: 526) (610: 517) (611: 518) (612: 519) (613: 520) (614: 521) (615: 522) (616: 523) (617: 524) (618: 525) (620: 527) (621: 528) (622: 529) (623: 530) (624: 531) (625: 532) (626: 533) (627: 534) (628: 535) (629: 536) (639: 546) (630: 537) (631: 538) (632: 539) (633: 540) (634: 541) (635: 542) (636: 543) (637: 544) (638: 545) (640: 547) (641: 548) (642: 549) (643: 550) (644: 551) (645: 552) (646: 553) (647: 554) (648: 555) (649: 556) (749: 656) (650: 557) (651: 558) (652: 559) (653: 560) (654: 561) (655: 562) (656: 563) (657: 564) (658: 565) (659: 566) (660: 567) ---------------------------------
qiming@qiming:~/share/CTASK/data-structure$