【c_c++项目】手把手带你实现一个内存型数据库（kv存储） 历史版本:
上次修改时间:
插入测试\\n\");\n }else{\n printf(\"FAIL---->插入测试\\n\");\n }\n // rbtree_display(T);\n\n printf(\"-------------------红黑树前驱节点测试------------------\\n\");\n int pass_flag = 1;\n if(rbtree_precursor_node(T, rbtree_search(T, KeyArray_sort[0])) != T->nil_node){\n printf(\"search first key %d\'s precursor error! get %d, expected nil_node\\n\", len_max, rbtree_precursor_node(T, rbtree_search(T, KeyArray_sort[0]))->key);\n pass_flag = 0;\n }\n for(i = 1; ikey != KeyArray_sort[i-1]){\n printf(\"search key %d error! get %d, expected %d\\n\", KeyArray_sort[i], precursor->key, KeyArray_sort[i-1]);\n pass_flag = 0;\n }\n }\n if(pass_flag){\n printf(\"PASS---->前驱节点测试\\n\");\n }else{\n printf(\"FAIL---->前驱节点测试\\n\");\n }\n\n printf(\"-------------------红黑树后继节点测试------------------\\n\");\n pass_flag = 1;\n if(rbtree_successor_node(T, rbtree_search(T, KeyArray_sort[len_max-1])) != T->nil_node){\n printf(\"search last key %d\'s successor error! get %d, expected nil_node\\n\",\\\n KeyArray_sort[len_max-1],\\\n rbtree_successor_node(T, rbtree_search(T, KeyArray_sort[len_max-1]))->key);\n pass_flag = 0;\n }\n for(i = 0; ikey != KeyArray_sort[i+1]){\n printf(\"search key %d error! get %d, expected %d\\n\", KeyArray_sort[i], successor->key, KeyArray_sort[i+1]);\n pass_flag = 0;\n }\n }\n if(pass_flag){\n printf(\"PASS---->后继节点测试\\n\");\n }else{\n printf(\"FAIL---->后继节点测试\\n\");\n }\n\n printf(\"-------------------红黑树删除测试------------------\\n\");\n // 依次删除所有元素\n for(i=0; i删除测试%d\\n\", i+1);\n break;\n }else{\n printf(\"PASS---->删除测试%d\\n\", i+1);\n }\n }\n\n printf(\"-------------------红黑树打印测试------------------\\n\");\n // 先插入数据1~18，再删除16/17/18，即可得到4层的满二叉树\n for(i = 0; i < len_max; i++){\n rbtree_insert(T, KeyArray[i], NULL);\n }\n for(i=0; i<3; i++){\n rbtree_delete(T, rbtree_search(T, KeyArray_sort[len_max-i-1]));\n if(!rbtree_check_effective(T)){\n printf(\"FAIL---->删除测试%d\\n\", KeyArray_sort[len_max-i-1]);\n break;\n }else{\n printf(\"PASS---->删除测试%d\\n\", KeyArray_sort[len_max-i-1]);\n }\n }\n // 打印看看结果\n rbtree_display(T);\n // 清空红黑树\n for(i=0; ikey != i+1){\n printf(\"continue_search error!\\n\");\n return 0;\n }\n }\n gettimeofday(&tv_end, NULL);\n time_ms = TIME_SUB_MS(tv_end, tv_begin);\n qps = (float)continue_test_len / (float)time_ms * 1000;\n printf(\"total SEARCHs:%d time_used:%d(ms) qps:%.2f(SEARCHs/sec)\\n\", continue_test_len, time_ms, qps);\n\n printf(\"---------------红黑树连续删除性能测试---------------\\n\");\n gettimeofday(&tv_begin, NULL);\n for(i = 0; i < continue_test_len; i++){\n rbtree_delete(T, rbtree_search(T, i+1));\n }\n gettimeofday(&tv_end, NULL);\n time_ms = TIME_SUB_MS(tv_end, tv_begin);\n qps = (float)continue_test_len / (float)time_ms * 1000;\n printf(\"total DELETEs:%d time_used:%d(ms) qps:%.2f(DELETEs/sec)\\n\", continue_test_len, time_ms, qps);\n#endif\n\n printf(\"--------------------------------------------------\\n\");\n rbtree_free(T); // 别忘了释放内存\n free(KeyArray_sort);\n return 0;\n}\n#endif\n```\n\n **测试代码输出结果** \n\n\n\n```\nlyl@ubuntu:~/Desktop/kv-store/code_init$ gcc -o main rbtree_int.c \nlyl@ubuntu:~/Desktop/kv-store/code_init$ ./main\n-------------------红黑树插入测试------------------\n测试数组长度: 18\nRAND_MAX: 2147483647\nPASS---->插入测试\n-------------------红黑树前驱节点测试------------------\nPASS---->前驱节点测试\n-------------------红黑树后继节点测试------------------\nPASS---->后继节点测试\n-------------------红黑树删除测试------------------\nPASS---->删除测试1\nPASS---->删除测试2\nPASS---->删除测试3\nPASS---->删除测试4\nPASS---->删除测试5\nPASS---->删除测试6\nPASS---->删除测试7\nPASS---->删除测试8\nPASS---->删除测试9\nPASS---->删除测试10\nPASS---->删除测试11\nPASS---->删除测试12\nPASS---->删除测试13\nPASS---->删除测试14\nPASS---->删除测试15\nPASS---->删除测试16\nPASS---->删除测试17\nPASS---->删除测试18\n-------------------红黑树打印测试------------------\nPASS---->删除测试18\nPASS---->删除测试17\nPASS---->删除测试16\n | 8 | \n |BLACK| \n / \\ \n | 4 | | 12 | \n | RED | | RED | \n / \\ / \\ \n | 2 | | 6 | | 10 | | 14 | \n |BLACK| |BLACK| |BLACK| |BLACK| \n / \\ / \\ / \\ / \\ \n| 1 || 3 || 5 || 7 || 9 || 11 || 13 || 15 |\n|BLACK||BLACK||BLACK||BLACK||BLACK||BLACK||BLACK||BLACK|\nThere is NO key=16 in rbtree!\nThere is NO key=17 in rbtree!\nThere is NO key=18 in rbtree!\n---------------红黑树连续插入性能测试---------------\ntotal INSERTs:1000000 time_used:295(ms) qps:3389830.50(INSERTs/sec)\n---------------红黑树连续查找性能测试---------------\ntotal SEARCHs:1000000 time_used:118(ms) qps:8474576.00(SEARCHs/sec)\n---------------红黑树连续删除性能测试---------------\ntotal DELETEs:1000000 time_used:95(ms) qps:10526315.00(DELETEs/sec)\n--------------------------------------------------\n```\n\n编程感想：\n\n### 2.4 btree的实现\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/79f3df47-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n一般来说，B树也是一个自平衡的二叉搜索树。但与红黑树不同的是，B树的节点可以存储多个元素，m mm阶B树的单个节点，最多有 m − 1 m-1m−1 个元素、m mm 个子节点。并且B树只有孩子节点、没有父节点（没有向上的指针）。也就是说，对于插入/删除操作，红黑树可以先从上往下寻找插入位置，再从下往上进行调整；而B树要先从上往下调整完（“分裂、合并/借位”），最后在叶子节点进行插入/删除，而没有从下往上的过程。即进行插入/删除时，B树从上往下只走一次。下面给出一个 m mm阶B树应该满足的条件（判断一棵B树是否有效的依据）：\n\n同样的，B树的查找操作只需要从根节点不断比较即可，而B树的插入/删除逻辑如下：\n\n **B树插入** ：从上往下寻找要插入的叶子节点，过程中要下去的孩子若是满节点，则进行“分裂”。\n\n **B树删除** ：从上往下寻找要删除元素的所在节点，过程中看情况进行“合并/借位”。若所在节点不是叶子节点，就将其换到叶子节点中。最后在叶子节点删除元素。\n\n\n\n```\n// 遍历到叶子节点\nwhile(不是叶子节点){\n // 1. 确定下一节点和其兄弟节点\n if(当前节点有要删除的元素) 哪边少哪边就是下一节点，当前元素对应的另一边就是兄弟节点。\n else(当前节点没有要删除的元素) 确定好要去的下一节点后，左右两边谁多谁是兄弟节点。\n // 2. 看是否需要调整\n if(下一节点元素少){\n if(孩子的兄弟节点元素多) 借位，进入下一节点。\n else(孩子的兄弟节点元素少) 合并，进入合并后的节点。\n }else if(下一节点元素多 && 当前节点有要删除元素){\n if(下一节点是删除元素的左节点) 删除元素和其前驱元素换位，进入下一节点。\n else(下一节点是删除元素的右节点) 删除元素和其后继元素换位，进入下一节点。\n }else{\n 直接进入下一节点。\n }\n}\n// 然后在叶子节点删除元素\n```\n\n注：判断孩子节点的元素少的条件是 元素数量≤ ceil m/2 -1，判断元素多的条件是 元素数量≥ ceil m/2。\n\n根据上述原理，我使用C语言实现了B树完整的 **增删查** 操作，并增加了 **检验有效性** 、 **打印B树** 的代码，以及 **测试代码(终端显示进度条)** 。同样为了加快开发速度，预设“键值对”的类型为、，后续将B树添加进“kv存储协议”中时会进一步修改：\n\n **btree_int.c** -共989行\n\n\n\n```\n#include\n#include\n#include\n#include\n\n// 编译指令：gcc -o main 1-1btree.c\n// 本代码实现M阶B树，存储int型key，未定义value。\n\n#define BTREE_DEBUG 1 // 是否运行测试代码\n\ntypedef struct _btree_node{\n int *keys;\n void *values;\n struct _btree_node **children;\n int num; // 当前节点的实际元素数量\n int leaf; // 当前节点是否为叶子节点\n}btree_node;\n\ntypedef struct _btree{\n int m; // m阶B树\n struct _btree_node *root_node;\n}btree;\n\n\n/*\n下面是所有的函数声明，排列顺序与源代码调用相同，最外层的函数放在最下面。\n*/\n/*----初始化分配内存----*/\n// 创建单个节点，leaf表示是否为叶子节点\nbtree_node *btree_node_create(btree *T, int leaf);\n// 初始化m阶B树：分配内存，最后记得销毁B树btree_destroy()\nbtree *btree_init(int m);\n\n/*----释放内存----*/\n// 删除单个节点\nvoid btree_node_destroy(btree_node *cur);\n// 递归删除给定节点作为根节点的子树\nvoid btree_node_destroy_recurse(btree_node *cur);\n// 删除所有节点，释放btree内存\nbtree *btree_destroy(btree *T);\n\n/*----插入操作----*/\n// 根节点分裂\nbtree_node* btree_root_split(btree *T);\n// 索引为idx的孩子节点分裂\nbtree_node* btree_child_split(btree *T, btree_node* cur, int idx);\n// btree插入元素：先分裂，再插入，必然在叶子节点插入\nvoid btree_insert_key(btree *T, int key);\n\n/*----删除操作----*/\n// 借位：将cur节点的idx_key元素下放到idx_dest孩子\nbtree_node *btree_borrow(btree_node *cur, int idx_key, int idx_dest);\n// 合并：将cur节点的idx元素向下合并\nbtree_node *btree_merge(btree *T, btree_node *cur, int idx);\n// 找出当前节点索引为idx_key的元素的前驱节点\nbtree_node* btree_precursor_node(btree *T, btree_node *cur, int idx_key);\n// 找出当前节点索引为idx_key的元素的后继节点\nbtree_node* btree_successor_node(btree *T, btree_node *cur, int idx_key);\n// btree删除元素：先合并/借位，再删除，必然在叶子节点删除\nvoid btree_delete_key(btree *T, int key);\n\n/*----查找操作----*/\n// 查找key\nbtree_node* btree_search_key(btree *T, int key);\n\n/*----打印信息----*/\n// 打印当前节点信息\nvoid btree_node_print(btree_node *cur);\n// 先序遍历给定节点为根节点的子树(递归)\nvoid btree_traversal_node(btree *T, btree_node *cur);\n// btree遍历\nvoid btree_traversal(btree *T);\n\n/*----检查有效性----*/\n// 获取B树的高度\nint btree_depth(btree *T);\n// 检查给定节点的有效性\n// 键值：根节点至少有一个key，其余节点至少有ceil(m/2)-1个key\n// 分支：所有节点数目子树为当前节点元素数量+1\nbool btree_node_check_effective(btree *T, btree_node *cur);\n// 遍历所有路径检查m阶B树的有效性\n// 平衡性：所有叶节点都在同一层（所有路径高度相等）\n// 有序性：所有元素升序排序\n// 键值：根节点至少有一个key，其余节点至少有ceil(m/2)-1个key\n// 分支：所有节点数目子树为当前节点元素数量+1\nbool btree_check_effective(btree *T);\n\n/*-----------------------------下面为函数定义-------------------------------*/\n// 创建单个节点，leaf表示是否为叶子节点\nbtree_node *btree_node_create(btree *T, int leaf){\n btree_node *new = (btree_node*)malloc(sizeof(btree_node));\n if(new == NULL){\n printf(\"btree node malloc failed!\\n\");\n return NULL;\n }\n new->keys = (int*)calloc(T->m-1, sizeof(int));\n new->values = (void*)calloc(T->m-1, sizeof(void));\n new->children = (btree_node **)calloc(T->m, sizeof(btree_node*));\n new->num = 0;\n new->leaf = leaf;\n return new;\n}\n\n// 删除单个节点\nvoid btree_node_destroy(btree_node *cur){\n free(cur->keys);\n free(cur->values);\n free(cur->children);\n free(cur);\n}\n\n// 初始化m阶B树：分配内存，最后记得销毁B树btree_destroy()\nbtree *btree_init(int m){\n btree *T = (btree*)malloc(sizeof(btree));\n if(T == NULL){\n // 只有内存不够时才会分配失败\n printf(\"rbtree malloc failed!\\n\");\n return NULL;\n }\n T->m = m;\n T->root_node = NULL;\n}\n\n// 递归删除给定节点作为根节点的子树\nvoid btree_node_destroy_recurse(btree_node *cur){\n int i = 0;\n if(cur->leaf == 1){\n btree_node_destroy(cur);\n }else{\n for(i=0; inum+1; i++){\n btree_node_destroy_recurse(cur->children[i]);\n }\n }\n}\n\n// 释放btree内存\nbtree *btree_destroy(btree *T){\n // 删除所有节点\n if(T->root_node != NULL){\n btree_node_destroy_recurse(T->root_node);\n }\n // 删除btree\n free(T);\n}\n\n\n// 根节点分裂\nbtree_node* btree_root_split(btree *T){\n // 创建兄弟节点\n btree_node *brother = btree_node_create(T, T->root_node->leaf);\n int i = 0;\n for(i=0; i<((T->m-1)>>1); i++){\n brother->keys[i] = T->root_node->keys[i+(T->m>>1)];\n T->root_node->keys[i+(T->m>>1)] = 0;\n brother->children[i] = T->root_node->children[i+(T->m>>1)];\n T->root_node->children[i+(T->m>>1)] = NULL;\n brother->num++;\n T->root_node->num--;\n }\n // 还需要复制最后一个指针\n brother->children[brother->num] = T->root_node->children[T->m-1];\n T->root_node->children[T->m-1] = NULL;\n \n // 创建新的根节点\n btree_node *new_root = btree_node_create(T, 0);\n new_root->keys[0] = T->root_node->keys[T->root_node->num-1];\n T->root_node->keys[T->root_node->num-1] = 0;\n T->root_node->num--;\n new_root->num = 1;\n new_root->children[0] = T->root_node;\n new_root->children[1] = brother;\n T->root_node = new_root;\n\n return T->root_node;\n}\n\n// 索引为idx的孩子节点分裂\nbtree_node* btree_child_split(btree *T, btree_node* cur, int idx){\n // 创建孩子的兄弟节点\n btree_node *full_child = cur->children[idx];\n btree_node *new_child = btree_node_create(T, cur->children[idx]->leaf);\n int i = 0;\n for(i=0; i<((T->m-1)>>1); i++){\n new_child->keys[i] = full_child->keys[i+(T->m>>1)];\n full_child->keys[i+(T->m>>1)] = 0;\n new_child->children[i] = full_child->children[i+(T->m>>1)];\n full_child->children[i+(T->m>>1)] = NULL;\n new_child->num++;\n full_child->num--;\n }\n new_child->children[new_child->num] = full_child->children[T->m-1];\n full_child->children[T->m-1] = NULL;\n\n // 把孩子的元素拿上来\n // 调整自己的key和children\n for(i=cur->num; i>idx; i--){\n cur->keys[i] = cur->keys[i-1];\n cur->children[i+1] = cur->children[i];\n }\n cur->children[idx+1] = new_child;\n cur->keys[idx] = full_child->keys[full_child->num-1];\n full_child->keys[full_child->num-1] = 0;\n cur->num++;\n full_child->num--;\n\n return cur;\n}\n\n\n// btree插入元素：先分裂，再插入，必然在叶子节点插入\nvoid btree_insert_key(btree *T, int key){\n btree_node *cur = T->root_node;\n if(key <= 0){\n // printf(\"illegal insert: key=%d!\\n\", key);\n }else if(cur == NULL){\n btree_node *new = btree_node_create(T, 1);\n new->keys[0] = key;\n new->num = 1;\n T->root_node = new;\n }else{\n // 函数整体逻辑：从根节点逐步找到元素要插入的叶子节点，先分裂、再添加\n // 先查看根节点是否需要分裂\n if(cur->num == T->m-1){\n cur = btree_root_split(T);\n }\n\n // 从根节点开始寻找要插入的叶子节点\n while(cur->leaf == 0){\n // 找到下一个要比较的孩子节点\n int next_idx = 0; // 要进入的孩子节点的索引\n int i = 0;\n for(i=0; inum; i++){\n if(key == cur->keys[i]){\n // printf(\"insert failed! already has key=%d!\\n\", key);\n return;\n }else if(key < cur->keys[i]){\n next_idx = i;\n break;\n }else if(i == cur->num-1){\n next_idx = cur->num;\n }\n }\n // 查看孩子是否需要分裂，不需要就进入\n if(cur->children[next_idx]->num == T->m-1){\n cur = btree_child_split(T, cur, next_idx);\n }else{\n cur = cur->children[next_idx];\n }\n }\n\n // 将新元素插入到叶子节点中\n int i = 0;\n int pos = 0; // 要插入的位置\n for(i=0; inum; i++){\n if(key == cur->keys[i]){\n // printf(\"insert failed! already has key=%d!\\n\", key);\n return;\n }else if(key < cur->keys[i]){\n pos = i;\n break;\n }else if(i == cur->num-1){\n pos = cur->num;\n }\n }\n // 插入元素\n if(pos == cur->num){\n cur->keys[cur->num] = key;\n }else{\n for(i=cur->num; i>pos; i--){\n cur->keys[i] = cur->keys[i-1];\n }\n cur->keys[pos] = key;\n }\n cur->num++;\n }\n}\n\n// 借位：将cur节点的idx_key元素下放到idx_dest孩子\nbtree_node *btree_borrow(btree_node *cur, int idx_key, int idx_dest){\n int idx_sour = (idx_key == idx_dest) ? idx_dest+1 : idx_key;\n btree_node *node_dest = cur->children[idx_dest]; // 目的节点\n btree_node *node_sour = cur->children[idx_sour]; // 源节点\n if(idx_key == idx_dest){\n // 自己下去作为目的节点的最后一个元素\n node_dest->keys[node_dest->num] = cur->keys[idx_key];\n node_dest->children[node_dest->num+1] = node_sour->children[0];\n node_dest->num++;\n // 把源节点的第一个元素请上来\n cur->keys[idx_key] = node_sour->keys[0];\n for(int i=0; inum-1; i++){\n node_sour->keys[i] = node_sour->keys[i+1];\n node_sour->children[i] = node_sour->children[i+1];\n }\n node_sour->children[node_sour->num-1] = node_sour->children[node_sour->num];\n node_sour->children[node_sour->num] = NULL;\n node_sour->keys[node_sour->num-1] = 0;\n node_sour->num--;\n }else{\n // 自己下去作为目的节点的第一个元素\n node_dest->children[node_dest->num+1] = node_dest->children[node_dest->num];\n for(int i=node_dest->num; i>0; i--){\n node_dest->keys[i] = node_dest->keys[i-1];\n node_dest->children[i] = node_dest->children[i-1];\n }\n node_dest->keys[0] = cur->keys[idx_key];\n node_dest->children[0] = node_sour->children[node_sour->num];\n node_dest->num++;\n // 把源节点的最后一个元素请上来\n cur->keys[idx_key] = node_sour->keys[node_sour->num-1];\n node_sour->keys[node_sour->num-1] = 0;\n node_sour->children[node_sour->num] = NULL;\n node_sour->num--;\n }\n return node_dest;\n}\n\n// 合并：将cur节点的idx元素向下合并\nbtree_node *btree_merge(btree *T, btree_node *cur, int idx){\n btree_node *left = cur->children[idx];\n btree_node *right = cur->children[idx+1];\n // 自己下去左孩子，调整当前节点\n left->keys[left->num] = cur->keys[idx];\n left->num++;\n for(int i=idx; inum-1; i++){\n cur->keys[i] = cur->keys[i+1];\n cur->children[i+1] = cur->children[i+2];\n }\n cur->keys[cur->num-1] = 0;\n cur->children[cur->num] = NULL;\n cur->num--;\n // 右孩子复制到左孩子\n for(int i=0; inum; i++){\n left->keys[left->num] = right->keys[i];\n left->children[left->num] = right->children[i];\n left->num++;\n }\n left->children[left->num] = right->children[right->num];\n // 删除右孩子\n btree_node_destroy(right);\n // 更新根节点\n if(T->root_node == cur){\n btree_node_destroy(cur);\n T->root_node = left;\n }\n return left;\n}\n\n// 找出当前节点索引为idx_key的元素的前驱节点\nbtree_node* btree_precursor_node(btree *T, btree_node *cur, int idx_key){\n if(cur->leaf == 0){\n cur = cur->children[idx_key];\n while(cur->leaf == 0){\n cur = cur->children[cur->num];\n }\n }\n return cur;\n}\n\n// 找出当前节点索引为idx_key的元素的后继节点\nbtree_node* btree_successor_node(btree *T, btree_node *cur, int idx_key){\n if(cur->leaf == 0){\n cur = cur->children[idx_key+1];\n while(cur->leaf == 0){\n cur = cur->children[0];\n }\n }\n return cur;\n}\n\n\n// btree删除元素：先合并/借位，再删除，必然在叶子节点删除\nvoid btree_delete_key(btree *T, int key){\n if(T->root_node!=NULL && key>0){\n btree_node *cur = T->root_node;\n // 在去往叶子节点的过程中不断调整(合并/借位)\n while(cur->leaf == 0){\n // 看看要去哪个孩子\n int idx_next = 0; //下一个要去的孩子节点索引\n int idx_bro = 0;\n int idx_key = 0;\n if(key < cur->keys[0]){\n idx_next = 0;\n idx_bro = 1;\n }else if(key > cur->keys[cur->num-1]){\n idx_next = cur->num;\n idx_bro = cur->num-1;\n }else{\n for(int i=0; inum; i++){\n if(key == cur->keys[i]){\n // 哪边少去哪边\n if(cur->children[i]->num <= cur->children[i+1]->num){\n idx_next = i;\n idx_bro = i+1;\n }else{\n idx_next = i+1;\n idx_bro = i;\n }\n break;\n }else if((inum-1) && (key > cur->keys[i]) && (key < cur->keys[i+1])){\n idx_next = i + 1;\n // 谁多谁是兄弟\n if(cur->children[i]->num > cur->children[i+2]->num){\n idx_bro = i;\n }else{\n idx_bro = i+2;\n }\n break;\n }\n }\n }\n idx_key = (idx_next < idx_bro) ? idx_next : idx_bro;\n // 依据孩子节点的元素数量进行调整\n if(cur->children[idx_next]->num <= ((T->m>>1)-1)){\n // 借位：下一孩子的元素少，下一孩子的兄弟节点的元素多\n if(cur->children[idx_bro]->num >= (T->m>>1)){\n cur = btree_borrow(cur, idx_key, idx_next);\n }\n // 合并：两个孩子都不多\n else{\n cur = btree_merge(T, cur, idx_key);\n }\n }else if(cur->keys[idx_key] == key){\n // 若当前元素就是要删除的节点，那一定要送下去\n // 但是不能借位,而是将前驱元素搬上来\n btree_node* pre;\n int tmp;\n if(idx_key == idx_next){\n // 找到前驱节点\n pre = btree_precursor_node(T, cur, idx_key);\n // 交换 当前元素 和 前驱节点的最后一个元素\n tmp = pre->keys[pre->num-1];\n pre->keys[pre->num-1] = cur->keys[idx_key];\n cur->keys[idx_key] = tmp;\n }else{\n // 找到后继节点\n pre = btree_successor_node(T, cur, idx_key);\n // 交换 当前元素 和 后继节点的第一个元素\n tmp = pre->keys[0];\n pre->keys[0] = cur->keys[idx_key];\n cur->keys[idx_key] = tmp;\n }\n cur = cur->children[idx_next];\n // cur = btree_borrow(cur, idx_key, idx_next);\n }else{\n cur = cur->children[idx_next];\n }\n }\n // 叶子节点删除元素\n for(int i=0; inum; i++){\n if(cur->keys[i] == key){\n if(cur->num == 1){\n // 若B树只剩最后一个元素\n btree_node_destroy(cur);\n T->root_node = NULL;\n }else{\n if(i != cur->num-1){\n for(int j=i; j<(cur->num-1); j++){\n cur->keys[j] = cur->keys[j+1];\n }\n }\n cur->keys[cur->num-1] = 0;\n cur->num--;\n }\n }\n // else if(i == cur->num-1){\n // printf(\"there is no key=%d\\n\", key);\n // }\n }\n }\n}\n\n// 打印当前节点信息\nvoid btree_node_print(btree_node *cur){\n if(cur == NULL){\n printf(\"NULL\\n\");\n }else{\n printf(\"leaf:%d, num:%d, key:|\", cur->leaf, cur->num);\n for(int i=0; inum; i++){\n printf(\"%d|\", cur->keys[i]);\n }\n printf(\"\\n\");\n }\n}\n\n// 先序遍历给定节点为根节点的子树(递归)\nvoid btree_traversal_node(btree *T, btree_node *cur){\n // 打印当前节点信息\n btree_node_print(cur);\n\n // 依次打印所有子节点信息\n if(cur->leaf == 0){\n int i = 0;\n for(i=0; inum+1; i++){\n btree_traversal_node(T, cur->children[i]);\n }\n }\n}\n\n// btree遍历\nvoid btree_traversal(btree *T){\n if(T->root_node != NULL){\n btree_traversal_node(T, T->root_node);\n }else{\n // printf(\"btree_traversal(): There is no key in B-tree!\\n\");\n }\n}\n\n// 查找key\nbtree_node* btree_search_key(btree *T, int key){\n if(key > 0){\n btree_node *cur = T->root_node;\n // 先寻找是否为非叶子节点\n while(cur->leaf == 0){\n if(key < cur->keys[0]){\n cur = cur->children[0];\n }else if(key > cur->keys[cur->num-1]){\n cur = cur->children[cur->num];\n }else{\n for(int i=0; inum; i++){\n if(cur->keys[i] == key){\n return cur;\n }else if((inum-1) && (key > cur->keys[i]) && (key < cur->keys[i+1])){\n cur = cur->children[i+1];\n }\n }\n }\n }\n // 在寻找是否为叶子节点\n if(cur->leaf == 1){\n for(int i=0; inum; i++){\n if(cur->keys[i] == key){\n return cur;\n }\n }\n }\n }\n // 都没找到返回NULL\n return NULL;\n}\n\n// 获取B树的高度\nint btree_depth(btree *T){\n int depth = 0;\n btree_node *cur = T->root_node;\n while(cur != NULL){\n depth++;\n cur = cur->children[0];\n }\n return depth;\n}\n\n// 检查给定节点的有效性\n// 键值：根节点至少有一个key，其余节点至少有ceil(m/2)-1个key\n// 分支：所有节点数目子树为当前节点元素数量+1\nbool btree_node_check_effective(btree *T, btree_node *cur){\n bool eff_flag = true;\n // 统计键值和子节点数量\n int num_kvs = 0, num_child = 0;\n int i = 0;\n while(cur->keys[i] != 0){\n // 判断元素是否递增\n if(i>=1 && (cur->keys[i] <= cur->keys[i-1])){\n printf(\"ERROR! the following node DOT sorted!\\n\");\n btree_node_print(cur);\n eff_flag = false;\n break;\n }\n // 统计数量\n num_kvs++;\n i++;\n }\n i = 0;\n while(cur->children[i] != NULL){\n // 子节点和当前节点的有序性\n if(ikeys[i] <= cur->children[i]->keys[cur->children[i]->num]){\n printf(\"ERROR! the follwing node\'s child[%d] has bigger key=%d than %d\\n\", i, cur->children[i]->keys[cur->children[i]->num], cur->keys[i]);\n printf(\"follwing node--\");\n btree_node_print(cur);\n printf(\" error child--\");\n btree_node_print(cur->children[i]);\n eff_flag = false;\n }else if(cur->keys[i] >= cur->children[i+1]->keys[0]){\n printf(\"ERROR! the follwing node\'s child[%d] has smaller key=%d than %d\\n\", i+1, cur->children[i+1]->keys[0], cur->keys[i]);\n printf(\"follwing node--\");\n btree_node_print(cur);\n printf(\" error child--\");\n btree_node_print(cur->children[i+1]);\n eff_flag = false;\n }\n }\n // 统计数量\n num_child++;\n i++;\n }\n // 判断元素数量是否合理\n if(cur->num >= T->m){\n printf(\"ERROR! the follwing node has too much keys:%d(at most %d)\\n\", cur->num, T->m-1);\n btree_node_print(cur);\n eff_flag = false;\n }\n if((cur != T->root_node) && (num_kvs<((T->m>>1)-1))){\n printf(\"ERROR! the follwing node has too few keys:%d(at least %d)\\n\", num_kvs, (T->m>>1)-1);\n btree_node_print(cur);\n eff_flag = false;\n }\n if(num_kvs != cur->num){\n printf(\"ERROR! the follwing node has %d keys but num=%d\\n\", num_kvs, cur->num);\n btree_node_print(cur);\n eff_flag = false;\n }\n if((cur->leaf == 0) && (num_child != cur->num+1)){\n printf(\"ERROR! the follwing node has %d keys but %d child(except keys+1=child)\\n\", num_kvs, num_child);\n btree_node_print(cur);\n eff_flag = false;\n }\n return eff_flag;\n}\n\n// 遍历所有路径检查m阶B树的有效性\n// 平衡性：所有叶节点都在同一层（所有路径高度相等）\n// 有序性：所有元素升序排序\n// 键值：根节点至少有一个key，其余节点至少有ceil(m/2)-1个key\n// 分支：所有节点数目子树为当前节点元素数量+1\nbool btree_check_effective(btree *T){\n bool effe_flag = true;\n int depth = btree_depth(T);\n if(depth == 0){\n // printf(\"btree_check_effective(): There is no key in B-tree!\\n\");\n }else if(depth == 1){\n // 只有一个根节点\n effe_flag = btree_node_check_effective(T, T->root_node);\n }else{\n // 最大的可能路径数量\n int max_path = 1;\n int depth_ = depth-1;\n while(depth_ != 0){\n max_path *= T->m;\n depth_--;\n }\n // 遍历所有路径(每个路径对应一个叶子节点)\n btree_node *cur = T->root_node;\n int i_path = 0;\n for(i_path=0; i_pathroot_node;\n while(cur != NULL){\n // 当前节点的有效性\n effe_flag = btree_node_check_effective(T, cur);\n if(!effe_flag) break;\n // 更新高度\n i_height++;\n // 更新下一节点\n if(cur->children[dir%T->m]==NULL && !cur->leaf){\n i_effe = 0;\n break;\n }\n cur = cur->children[dir%T->m];\n dir /= T->m;\n }\n // if(btree_node_check_effective(T, cur))\n\n // 判断本路径节点数（高度）\n if(i_height != depth && i_effe){\n printf(\"ERROR! not all leaves in the same layer! the leftest path\'s height=%d, while the %dst path\'s height=%d.\\n\",\n depth, i_path, i_height);\n effe_flag = false;\n }\n if(!effe_flag) break;\n }\n \n }\n return effe_flag;\n}\n\n\n/*-----------------------------下面为测试代码-------------------------------*/\n#if BTREE_DEBUG\n#include // 使用随机数\n#include // 计算qps中获取时间\n#define TIME_SUB_MS(tv1, tv2) ((tv1.tv_sec - tv2.tv_sec) * 1000 + (tv1.tv_usec - tv2.tv_usec) / 1000)\n#define ENABLE_QPS 1 // 是否开启qps性能测试\n#define continue_test_len 10000000 // 连续测试的长度\n// 冒泡排序\nvoid bubble_sort(int arr[], int len) {\n int i, j, temp;\n for (i = 0; i < len - 1; i++)\n for (j = 0; j < len - 1 - i; j++)\n if (arr[j] > arr[j + 1]) {\n temp = arr[j];\n arr[j] = arr[j + 1];\n arr[j + 1] = temp;\n }\n}\n// 打印当前数组\nvoid print_int_array(int* KeyArray, int len_array){\n printf(\"测试数组为KeyArray[%d] = {\", len_array);\n for(int i=0; i0){\n btree_insert_key(T_old, KeyArray[i-1]);\n }\n btree_insert_key(T, KeyArray[i]);\n // 方便打印调试\n // if(i==65){\n // printf(\"Before insert the %2d\'s key=%d:\\n\", i+1, KeyArray[i]);\n // btree_traversal(T_old);\n // printf(\"After insert the %2d\'s key=%d:\\n\", i+1, KeyArray[i]);\n // btree_traversal(T);\n // }\n if(btree_check_effective(T)==false){\n printf(\"after insert KeyArray[%d]=%d error!\\n\", i, KeyArray[i]);\n pass_flag = false;\n break;\n }\n }\n if(pass_flag){\n if(detail_flag) printf(\"PASS---->插入测试%d/%d\\n\", i_test+1, max_test);\n btree_insert_key(T_old, KeyArray[len_array]);\n }else{\n if(detail_flag) printf(\"FAIL---->插入测试%d/%d\\n\", i_test+1, max_test);\n // printf(\"Before insert:\\n\");\n // btree_traversal(T_old);\n // printf(\"After insert:\\n\");\n // btree_traversal(T);\n\n btree_destroy(T_old);\n btree_destroy(T);\n break;\n }\n if(detail_flag){\n btree_traversal(T);\n printf(\"\\n\");\n }\n \n if(detail_flag){\n printf(\"-------------------B树查找测试------------------\\n\");\n }\n /*-------------------B树查找测试------------------*/\n btree_node* sear = NULL;\n for(int i=0; i 0){\n sear = btree_search_key(T, KeyArray[i]);\n pass_flag = false;\n if(sear != NULL){\n for(int j=0; jnum; j++){\n if(sear->keys[j] == KeyArray[i]){\n pass_flag = true;\n break;\n }\n }\n }\n if(detail_flag){\n printf(\"search KeyArray[%d]=%d ----> \", i, KeyArray[i]);\n btree_node_print(sear);\n }\n }\n if(pass_flag == false){\n print_int_array(KeyArray, len_array); // 打印当前数组\n printf(\"following node DOT has KeyArray[%d]=%d!\\n\", i, KeyArray[i]);\n btree_node_print(sear);\n pass_flag = false;\n break;\n }\n }\n if(pass_flag){\n if(detail_flag) printf(\"PASS---->查找测试%d/%d\\n\", i_test+1, max_test);\n }else{\n printf(\"FAIL---->查找测试%d/%d\\n\", i_test+1, max_test);\n break;\n }\n\n if(detail_flag){\n printf(\"-------------------B树删除测试------------------\\n\");\n }\n /*-------------------B树删除测试------------------*/\n for(int i=0; i0){\n btree_delete_key(T_old, KeyArray[i-1]);\n }\n btree_delete_key(T, KeyArray[i]);\n if(detail_flag){\n printf(\"delete KeyArray[%d]=%d:\\n\", i, KeyArray[i]);\n btree_traversal(T);\n } \n if(btree_check_effective(T) == false){\n print_int_array(KeyArray, len_array); // 打印当前数组\n printf(\"after delete KeyArray[%d]=%d error!\\n\", i, KeyArray[i]);\n pass_flag = false;\n break;\n }\n }\n if(pass_flag){\n if(detail_flag) printf(\"PASS---->删除测试%d/%d\\n\", i_test+1, max_test);\n }else{\n printf(\"FAIL---->删除测试%d/%d\\n\", i_test+1, max_test);\n // printf(\"Before delete:\\n\");\n // btree_traversal(T_old);\n // printf(\"After delete:\\n\");\n // btree_traversal(T);\n\n btree_destroy(T_old);\n btree_destroy(T);\n break;\n }\n\n\n if(detail_flag){\n printf(\"--------------------------------------------------\\n\");\n }\n\n btree_destroy(T_old);\n btree_destroy(T);\n\n // 整点进度条看看\n if(pass_flag){\n // printf(\"PASS----> WHOLE TEST %d/%d!\\r\", i_test+1, max_test);\n int bar_process; // 编译器初始化为0\n bool already_print_txt; // 编译器初始化为false\n bool already_print_bar; // 编译器初始化为false\n const int len_bar = 20; // 完整进度条的长度\n // 打印进度条前面的说明\n if(!already_print_txt){\n printf(\"PASS TEST PROCESS: \");\n fflush(stdout);\n }\n already_print_txt = true;\n // 打印进度条\n if(len_bar*(i_test+1)/max_test > bar_process){\n // 光标往前回退\n if(already_print_bar){\n printf(\"\\033[4D\"); // ANSI转义序列\n }\n // 画出进度条\n for(int i=0; i<(len_bar*(i_test+1)/max_test - bar_process); i++){\n printf(\"█\");\n fflush(stdout);\n }\n // 显示进度范围\n printf(\" %d%%\", 100*(i_test+1)/max_test);\n fflush(stdout);\n already_print_bar = true;\n bar_process = len_bar*(i_test+1)/max_test;\n if(i_test+1 == max_test) printf(\"\\n\");\n }\n }\n }\n // 只是为了最后一行判断用\n if(pass_flag){\n // printf(\"\\r\\033[K\"); // 清除本行\n printf(\"PASS----> ALL %d TEST!\\n\", max_test);\n }\n printf(\"--------------------------------------------------\\n\");\n\n\n printf(\"---------------------性能测试---------------------\\n\");\n btree* bT = btree_init(16); // 初始化16阶B树\n // 定义时间结构体\n struct timeval tv_begin;\n struct timeval tv_end;\n // 插入性能测试\n gettimeofday(&tv_begin, NULL);\n for(int i=0; inum; idx++){\n if(node->keys[idx] == i+1){\n break;\n }\n }\n if(idx == node->num){\n printf(\"continue_search error!\\n\");\n return 0;\n }\n }\n gettimeofday(&tv_end, NULL);\n time_ms = TIME_SUB_MS(tv_end, tv_begin);\n qps = (float)continue_test_len / (float)time_ms * 1000;\n printf(\"total SEARCHs:%d time_used:%d(ms) qps:%.2f(SEARCHs/sec)\\n\", continue_test_len, time_ms, qps);\n // // 删除性能测试\n // gettimeofday(&tv_begin, NULL);\n // for(int i=0; i ALL 100 TEST!\n--------------------------------------------------\n---------------------性能测试---------------------\ntotal INSERTs:10000000 time_used:2379(ms) qps:4203447.00(INSERTs/sec)\ntotal SEARCHs:10000000 time_used:1007(ms) qps:9930486.00(SEARCHs/sec)\ntotal DELETEs:10000000 time_used:18(ms) qps:555555584.00(DELETEs/sec)\n--------------------------------------------------\n```\n\n未解决bug：测试代码的最后如果多加上一个“删除性能测试”，就不显示进度条了？很奇怪\n\n### 2.5 hash的实现\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/7eb89728-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n终于度过了本项目所有最难的部分，下面的内容都比较简单。链式哈希的增删查操作简洁明了。链式哈希首先会声明一个固定长度的哈希表（如1024），若需要 **插入新元素时** ，首先计算哈希值作为索引，若有冲突则直接在当前位置使用“ **头插法** ”即可。注意以下几点：\n\n就不单独写型的代码并测试了，可以直接参考\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“hash.h”、“hash.c”。\n\n### 2.6 dhash的实现\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/83fbf813-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n显然上述hash有个很大问题，就是“哈希表的大小”是固定的。如果声明哈希表大小为1024，却要插入10w个元素，那每个所有都会对应一个很长的链表，最坏的情况下和直接遍历一遍没什么区别！这显然失去了哈希的意义，于是在上面的基础上，我们使用“空间换时间”，自动增加/缩减哈希表的大小，也就是“动态哈希表”dhash：\n\n同样，不单独写型的代码测试了，可以直接参考\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“dhash.h”、“dhash.c”。\n\n### 2.7 skiplist的实现\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/88b0e1ed-6029-11f0-b5f6-00e05a680215.png\")
\n\n跳表本质上是一个有序链表。红黑树每次比较都能排除一半的节点，这启发我们，要是每次都能找到链表最中间的节点，不就可以实现O ( log N )的查找时间复杂度了嘛。于是如上图所示，我们不妨规定跳表的每个节点都有一组指针，跳表还有一个额外的空节点作为“跳表头”，那么每次都从顶层依次底层进行“跳”，就可以实现“ **每次比较都能排除剩下一半的节点** ”。但是还有个大问题，那就是上述理想跳表需要插入/删除一个元素时，元素的调整会非常麻烦，甚至还需要遍历整个链表来调整所有节点的指向！\n\n所以在实际应用中，不会直接使用上述理想跳表的结构。而是在每次插入一个新元素时， **按照一定概率计算其高度** 。统计学证明，当存放元素足够多的时候，该实际跳表性能无限趋近于理想跳表。\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/8d83f978-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n同样，代码直接见\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“skiplist.h”、“skiplist.c”。\n\n### 2.8 kv存储协议的实现\n\n如“1.2节-项目预期及基本架构”给出的“服务端程序架构”。现在我们实现了网络收发功能（网络层）、所有存储引擎的增删查改操作（引擎层），还差最后一个“kv存储协议”（协议层）就可以实现完整的服务端程序。“kv存储协议”的主要功能有：\n\n值得注意的是，“引擎层”的接口函数应该统一封装命名，并在各存储引擎中实现，“引擎层”的头文件中也只有这些接口函数暴露给“协议层”。这样保证了“协议层”和“引擎层”的隔离性，即使后续“引擎层”代码需要进行修改，也不会干扰到接口函数的调用、无需修改协议层。整个“服务端”的“网络层”、“协议层”、“引擎层”的函数调用关系如下：\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/91f4de11-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n同样，代码直接见\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“kvstore.h”、“kvstore.c”。\n\n## 3. 性能测试\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/96e3683f-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n上述我们将“服务端”的代码实现完毕，并且可以使用“网络连接助手”进行正常的收发数据。如上图所示，依次发送5条指令后都得到预期的回复。但是我们要想测试客户端的极限性能，显然需要写一个“客户端”测试程序。该测试程序目标如下：\n\n如下图所示，开启两个Ubuntu虚拟机，分别运行“服务端”、“客户端”程序，得到如下的测试数据：\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/9b6086da-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n ![](\"https://www.testingcloud.club/sapi/api/image_download/9fda18bc-6029-11f0-b5f6-00e05a680215.jpeg\")
\n\n **结果分析** ：\n\n## 4. 项目总结及改进思路\n\nC/C++适合做服务器，但不适合做业务。因为可能会因为一行代码有问题，导致整个进程退出。虽然也能做，但维护成本高，并且对工程师要求高。比如“腾讯课堂”中课程、图片、价格等参数很适合用C语言做“kv存储”，但是显示网页等业务功能使用Jc语言更加合适。所以 **VUE框架(Java)等适合做前端业务；C/C++适合做基础架构、高性能组件、中间件** 。比如在量化交易中，底层的高频组件、低延迟组件适合用C/C++，上层的交易业务、交易策略没必要C/C++。\n\n C/C++适合做服务器，但不适合做业务。因为可能会因为一行代码有问题，导致整个进程退出。虽然也能做，但维护成本高，并且对工程师要求高。比如“腾讯课堂”中课程、图片、价格等参数很适合用C语言做“kv存储”，但是显示网页等业务功能使用Jc语言更加合适。所以VUE框架(Java)等适合做前端业务；C/C++适合做基础架构、高性能组件、中间件。比如在量化交易中，底层的高频组件、低延迟组件适合用C/C++，上层的交易业务、交易策略没必要C/C++。\n\n **下面是对本项目的一些 改进思路：** \n\n **编程感想：** \n\n1.字符串拷贝：C语言中，使用strncpy、snprintf拷贝字符串时，注意目的字符串不能只是声明为char*，而是需要malloc/calloc分配内存才可以。另外也不要忘了释放内存free。\n\n2.天坑：解析指令时层层传递的是epoll的读缓冲rbuffer，然后使用strtok/strtok_r进行分割指令并存储在char* tokens[]中，注意这个char* tokens[]的元素指向的就是读缓冲本身！！！而snprintf是逐字符进行拷贝的，也就是说，此时使用snprintf将tokens的内容再写回读缓冲就会导致读缓冲错乱。如果不额外分配内存很难解决该问题。所以建议不要使用snprintf拷贝自己的格式化字符串。\n\n3.良好的内存管理习惯：free()之前先判断是否为NULL，free()之后一定要指向NULL。\n\n4.层层传递初始化：\n\n【可行方法1】如果最顶层需要创建实例对象（不如全局变量），那就需要传地址给最底层，且最底层无需再重新为这个对象malloc空间（因为最顶层已经创建对象了），只需要malloc好这个实例对象的所有指针即可，或者先定义成NULL后期插入时再分配。\n\n【可行方法2】若最顶层无需创建全局的实例对象，那么也可以不传参数给最底层，最底层直接创建一个对象指针，并malloc/NULL这个对象指针的所有参数，最后直接返回这个对象指针就行。\n\n【不可行方法】顶层创建了全局的实例对象，然后传地址给最底层，最底层重新malloc一个新的对象指针，初始化这个对象指针的所有参数，最后让传递下来的地址指向这个指针。最后在顶层就会发现所有参数都没初始化，都是空！\n\n【关键点】：对谁进行malloc非常重要，一定要对顶层传下来的结构体指针的元素直接malloc，而不是malloc一个新的结构体，在赋值给这个结构体指针。\n\n5.关于strcmp()：在使用strcmp()时一定要先判断不为空，才能使用。这是因为strcmp()的底层使用while(*des++==*src**)，所以若比较的双方有一方为空，就会直接报错。\n\n6.注意项目的include关系，是在编译指令中指定的。当然也可以将“kv_store.c”中的case语句封装到各自的数据结构中，然后以动态库的方式进行编译。\n\n链接：\n\n[基于C语言实现内存型数据库(kv存储)](https://blog.csdn.net/weixin_46258766/article/details/136228729)\n\n
\n\n[https://zhuanlan.zhihu.com/p/700085445](https://zhuanlan.zhihu.com/p/700085445)
\n -->
\n\n一般来说，B树也是一个自平衡的二叉搜索树。但与红黑树不同的是，B树的节点可以存储多个元素，m mm阶B树的单个节点，最多有 m − 1 m-1m−1 个元素、m mm 个子节点。并且B树只有孩子节点、没有父节点（没有向上的指针）。也就是说，对于插入/删除操作，红黑树可以先从上往下寻找插入位置，再从下往上进行调整；而B树要先从上往下调整完（“分裂、合并/借位”），最后在叶子节点进行插入/删除，而没有从下往上的过程。即进行插入/删除时，B树从上往下只走一次。下面给出一个 m mm阶B树应该满足的条件（判断一棵B树是否有效的依据）：\n\n同样的，B树的查找操作只需要从根节点不断比较即可，而B树的插入/删除逻辑如下：\n\n **B树插入** ：从上往下寻找要插入的叶子节点，过程中要下去的孩子若是满节点，则进行“分裂”。\n\n **B树删除** ：从上往下寻找要删除元素的所在节点，过程中看情况进行“合并/借位”。若所在节点不是叶子节点，就将其换到叶子节点中。最后在叶子节点删除元素。\n\n\n\n```\n// 遍历到叶子节点\nwhile(不是叶子节点){\n // 1. 确定下一节点和其兄弟节点\n if(当前节点有要删除的元素) 哪边少哪边就是下一节点，当前元素对应的另一边就是兄弟节点。\n else(当前节点没有要删除的元素) 确定好要去的下一节点后，左右两边谁多谁是兄弟节点。\n // 2. 看是否需要调整\n if(下一节点元素少){\n if(孩子的兄弟节点元素多) 借位，进入下一节点。\n else(孩子的兄弟节点元素少) 合并，进入合并后的节点。\n }else if(下一节点元素多 && 当前节点有要删除元素){\n if(下一节点是删除元素的左节点) 删除元素和其前驱元素换位，进入下一节点。\n else(下一节点是删除元素的右节点) 删除元素和其后继元素换位，进入下一节点。\n }else{\n 直接进入下一节点。\n }\n}\n// 然后在叶子节点删除元素\n```\n\n注：判断孩子节点的元素少的条件是 元素数量≤ ceil m/2 -1，判断元素多的条件是 元素数量≥ ceil m/2。\n\n根据上述原理，我使用C语言实现了B树完整的 **增删查** 操作，并增加了 **检验有效性** 、 **打印B树** 的代码，以及 **测试代码(终端显示进度条)** 。同样为了加快开发速度，预设“键值对”的类型为、，后续将B树添加进“kv存储协议”中时会进一步修改：\n\n **btree_int.c** -共989行\n\n\n\n```\n#include \n\n终于度过了本项目所有最难的部分，下面的内容都比较简单。链式哈希的增删查操作简洁明了。链式哈希首先会声明一个固定长度的哈希表（如1024），若需要 **插入新元素时** ，首先计算哈希值作为索引，若有冲突则直接在当前位置使用“ **头插法** ”即可。注意以下几点：\n\n就不单独写型的代码并测试了，可以直接参考\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“hash.h”、“hash.c”。\n\n### 2.6 dhash的实现\n\n \n\n显然上述hash有个很大问题，就是“哈希表的大小”是固定的。如果声明哈希表大小为1024，却要插入10w个元素，那每个所有都会对应一个很长的链表，最坏的情况下和直接遍历一遍没什么区别！这显然失去了哈希的意义，于是在上面的基础上，我们使用“空间换时间”，自动增加/缩减哈希表的大小，也就是“动态哈希表”dhash：\n\n同样，不单独写型的代码测试了，可以直接参考\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“dhash.h”、“dhash.c”。\n\n### 2.7 skiplist的实现\n\n \n\n跳表本质上是一个有序链表。红黑树每次比较都能排除一半的节点，这启发我们，要是每次都能找到链表最中间的节点，不就可以实现O ( log N )的查找时间复杂度了嘛。于是如上图所示，我们不妨规定跳表的每个节点都有一组指针，跳表还有一个额外的空节点作为“跳表头”，那么每次都从顶层依次底层进行“跳”，就可以实现“ **每次比较都能排除剩下一半的节点** ”。但是还有个大问题，那就是上述理想跳表需要插入/删除一个元素时，元素的调整会非常麻烦，甚至还需要遍历整个链表来调整所有节点的指向！\n\n所以在实际应用中，不会直接使用上述理想跳表的结构。而是在每次插入一个新元素时， **按照一定概率计算其高度** 。统计学证明，当存放元素足够多的时候，该实际跳表性能无限趋近于理想跳表。\n\n \n\n同样，代码直接见\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“skiplist.h”、“skiplist.c”。\n\n### 2.8 kv存储协议的实现\n\n如“1.2节-项目预期及基本架构”给出的“服务端程序架构”。现在我们实现了网络收发功能（网络层）、所有存储引擎的增删查改操作（引擎层），还差最后一个“kv存储协议”（协议层）就可以实现完整的服务端程序。“kv存储协议”的主要功能有：\n\n值得注意的是，“引擎层”的接口函数应该统一封装命名，并在各存储引擎中实现，“引擎层”的头文件中也只有这些接口函数暴露给“协议层”。这样保证了“协议层”和“引擎层”的隔离性，即使后续“引擎层”代码需要进行修改，也不会干扰到接口函数的调用、无需修改协议层。整个“服务端”的“网络层”、“协议层”、“引擎层”的函数调用关系如下：\n\n \n\n同样，代码直接见\n\n[项目源码](https://github.com/jjejdhhd/kv-store/tree/main/kv-store-v1)中的“kvstore.h”、“kvstore.c”。\n\n## 3. 性能测试\n\n \n\n上述我们将“服务端”的代码实现完毕，并且可以使用“网络连接助手”进行正常的收发数据。如上图所示，依次发送5条指令后都得到预期的回复。但是我们要想测试客户端的极限性能，显然需要写一个“客户端”测试程序。该测试程序目标如下：\n\n如下图所示，开启两个Ubuntu虚拟机，分别运行“服务端”、“客户端”程序，得到如下的测试数据：\n\n \n\n \n\n **结果分析** ：\n\n## 4. 项目总结及改进思路\n\nC/C++适合做服务器，但不适合做业务。因为可能会因为一行代码有问题，导致整个进程退出。虽然也能做，但维护成本高，并且对工程师要求高。比如“腾讯课堂”中课程、图片、价格等参数很适合用C语言做“kv存储”，但是显示网页等业务功能使用Jc语言更加合适。所以 **VUE框架(Java)等适合做前端业务；C/C++适合做基础架构、高性能组件、中间件** 。比如在量化交易中，底层的高频组件、低延迟组件适合用C/C++，上层的交易业务、交易策略没必要C/C++。\n\n C/C++适合做服务器，但不适合做业务。因为可能会因为一行代码有问题，导致整个进程退出。虽然也能做，但维护成本高，并且对工程师要求高。比如“腾讯课堂”中课程、图片、价格等参数很适合用C语言做“kv存储”，但是显示网页等业务功能使用Jc语言更加合适。所以VUE框架(Java)等适合做前端业务；C/C++适合做基础架构、高性能组件、中间件。比如在量化交易中，底层的高频组件、低延迟组件适合用C/C++，上层的交易业务、交易策略没必要C/C++。\n\n **下面是对本项目的一些 改进思路：** \n\n **编程感想：** \n\n1.字符串拷贝：C语言中，使用strncpy、snprintf拷贝字符串时，注意目的字符串不能只是声明为char*，而是需要malloc/calloc分配内存才可以。另外也不要忘了释放内存free。\n\n2.天坑：解析指令时层层传递的是epoll的读缓冲rbuffer，然后使用strtok/strtok_r进行分割指令并存储在char* tokens[]中，注意这个char* tokens[]的元素指向的就是读缓冲本身！！！而snprintf是逐字符进行拷贝的，也就是说，此时使用snprintf将tokens的内容再写回读缓冲就会导致读缓冲错乱。如果不额外分配内存很难解决该问题。所以建议不要使用snprintf拷贝自己的格式化字符串。\n\n3.良好的内存管理习惯：free()之前先判断是否为NULL，free()之后一定要指向NULL。\n\n4.层层传递初始化：\n\n【可行方法1】如果最顶层需要创建实例对象（不如全局变量），那就需要传地址给最底层，且最底层无需再重新为这个对象malloc空间（因为最顶层已经创建对象了），只需要malloc好这个实例对象的所有指针即可，或者先定义成NULL后期插入时再分配。\n\n【可行方法2】若最顶层无需创建全局的实例对象，那么也可以不传参数给最底层，最底层直接创建一个对象指针，并malloc/NULL这个对象指针的所有参数，最后直接返回这个对象指针就行。\n\n【不可行方法】顶层创建了全局的实例对象，然后传地址给最底层，最底层重新malloc一个新的对象指针，初始化这个对象指针的所有参数，最后让传递下来的地址指向这个指针。最后在顶层就会发现所有参数都没初始化，都是空！\n\n【关键点】：对谁进行malloc非常重要，一定要对顶层传下来的结构体指针的元素直接malloc，而不是malloc一个新的结构体，在赋值给这个结构体指针。\n\n5.关于strcmp()：在使用strcmp()时一定要先判断不为空，才能使用。这是因为strcmp()的底层使用while(*des++==*src**)，所以若比较的双方有一方为空，就会直接报错。\n\n6.注意项目的include关系，是在编译指令中指定的。当然也可以将“kv_store.c”中的case语句封装到各自的数据结构中，然后以动态库的方式进行编译。\n\n链接：\n\n[基于C语言实现内存型数据库(kv存储)](https://blog.csdn.net/weixin_46258766/article/details/136228729)\n\n\n\n[https://zhuanlan.zhihu.com/p/700085445](https://zhuanlan.zhihu.com/p/700085445)
\n -->
0条评�?
发表评论
全部评论
关于博主
an actually real engineer
通信工程专业毕业,7年开发经验
技术栈:
精通c/c++
精通golang
熟悉常见的脚本,js,lua,python,php
熟悉电路基础,嵌入式,单片机
耕耘领域:
服务端开发
嵌入式开发
>gin接口代码CURD生成工具
sql ddl to struct and markdown,将sql表自动化生成代码内对应的结构体和markdown表格格式,节省宝贵的时间。
输入ddl:
输出代码:
qt .ui文件转css文件
duilib xml 自动生成绑定控件代码
协议调试器
基于lua虚拟机的的协议调试器软件 支持的协议有:
串口
tcp客户端/服务端
udp 组播/udp节点
tcp websocket 客户端/服务端
软件界面
使用例子: 通过脚本来获得接收到的数据并写入文件和展示在界面上
下载地址和源码
webrtc easy demo
webrtc c++ native 库 demo 实现功能:
基于QT
webrtc摄像头/桌面捕获功能
opengl渲染/多播放窗格管理
janus meeting room
下载地址和源码
wifi,蓝牙 - 无线开关
实现功能:
通过wifi/蓝牙实现远程开关电器或者其他电子设备
电路原理图:
实物图:
深度学习验证工具
虚拟示波器
硬件实物图:
实现原理
基本性能
采集频率: 取决于外部adc模块和ebaz4205矿板的以太网接口速率,最高可以达到100M/8 约为12.5MPS
上位机实现功能: 采集,显示波形,存储wave文件。
参数可运行时配置
上位机:
显示缓冲区大小可调
刷新率可调节
触发显示刷新可调节
又一个modbus调试工具
最近混迹物联网企业,发现目前缺少一个简易可用的modbus调试工具,本软件旨在为开发者提供一个简单modbus测试工具。 主打一个代码简单易修改。 特点:
1. 基于QT5
2. 基于libmodbus
3. 三方库完全跨平台,linux/windows。
开源plutosdr 板卡
1. 完全开源
2. 提高固件定制服务
3. 硬件售价450 手焊产量有线
测试数据
内部DDS回环测试
接收测试
外部发送500MHZ FM波形
matlab测试
2TRX版本
大部分plutosdr应用场景都是讲plutosdr板卡作为射频收发器来使用。 实际上plutosdr板卡本身运行linux 操作系统。是具有一定脱机运算的能力。 对于一些微型频谱检测,简单射频信号收发等应用完全可以将应用层直接实现在板卡上 相较于通过网卡或者USB口传输具有更稳定,带宽更高等优点。 本开源板卡由于了SD卡启动,较原版pluto支持了自定义启动应用的功能。 提供了应用层开发SDK(编译器，buildroot文件系统)。 通过usb连接电脑,经过RNDIS驱动可以近似为通过网卡连接 (支持固件的开发定制)。
二次开发例子
``` all: arm-linux-gnueabihf-gcc -mfloat-abi=hard --sysroot=/root/v0.32_2trx/buildroot/output/staging -std=gnu99 -g -o pluto_stream ad9361-iiostream.c -lpthread -liio -lm -Wall -Wextra -lrt clean: rm pluto_stream
版面分析即分析出图片内的具体文件元素,如文档标题,文档内容,文档页码等,本工具基于cnstd模型