algorithm

B-Tree实现

依照CLRS讲解实现了一个B-Tree，包括create & insert & search & delete操作，实现上使用迭代完成，没有使用递归。
CODE: link.

B-Tree节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define T           85
#define BNODE_KEY_SIZE  (2*T-1)
#define BNODE_CHILDREN_SIZE (2*T)

struct BTreeNode {
    size_t count;
    bool is_leaf;

    size_t keys[BNODE_KEY_SIZE];
    size_t values[BNODE_KEY_SIZE];
    size_t children[BNODE_CHILDREN_SIZE];

    BTreeNode() : count(0), is_leaf(true) {}
};

字段具体含义不解释。每个BTreeNode对一个磁盘页，实现了一组sim_XXX()函数模拟磁盘数据载入写出过程，通常用户持有一个size_t类型的node id，使用sim_get_node(size_t node_id)函数载入对应的磁盘数据，并返回对应的内存地址，修改或访问完以后使用sim_release_node()释放并“写回磁盘”。目前这组函数里做的只是size_t和BTreeNode*类型间的转换，可以额外增加写cache、reference_count代码，模拟实际开销。

b_tree_insert() 实现可以检测重复key，如果重复则只是更新对应的value值。
该函数实现有一点需要注意：当关键字k插入到x节点时，对应的插入子树为ci[x]，如果n[ci[x]]==2t-1，则需要拆分子树ci[x]，拆分后k & keyi[x]的相对关系会变化，需要重新对比k & keyi[x] & keyi+1[x]三者间的关系：确定k是否重复，需要递归处理拆分出来的ci[x] & ci+1[x]中的哪一个，对应在实现代码的 line: 153-178。
这部分还可以不检测，split-child以后下次递归或循环还在当前节点处理而不下降，代码会清爽一些。

b_tree_delete() 实现复杂一些。按照CLRS描述，对于递归处理的下一节点x有：n[x]>=t，因此x有可能会跟左兄弟或有兄弟合并，合并后n[parent[x]]会减一，如果parent[x]是根节点，则意味着合并后x再无兄弟节点，x成为新的根节点。这种情况在2c) & 3b)里会出现，需要注意处理。

剩下的可以直接看代码，有问题可以留言。