【网络编程】在 KV 存储服务中引入红黑树：从协议解析到增删改查实现

做网络编程时服务端经常要维护一批键值对数据。最基础的做法是数组顺序查找但当数据越来越多时查找、删除、修改都会越来越慢。这个时候引入红黑树的意义就出来了把键值对存到一棵自平衡二叉搜索树里让查找、插入、删除都尽量保持稳定效率。这套实现里服务端一边负责接收文本命令一边把命令转成底层数据结构操作。比如客户端发来RSET Teacher Charon RGET Teacher RMOD Teacher King RDEL Teacher REXIST Teacher服务端会先拆协议再分发命令最后调用红黑树接口完成对应操作。整个链路已经在代码里打通了。一、为什么这里要用红黑树而不是继续用数组先看这套服务里红黑树节点长什么样// 红黑树节点除了 key、value还要保存颜色、父节点、左右孩子 typedef struct _rbtree_node { unsigned char color; // 节点颜色红 or 黑 struct _rbtree_node *right; // 右孩子 struct _rbtree_node *left; // 左孩子 struct _rbtree_node *parent; // 父节点 KEY_TYPE key; // 键这里是字符串 void *value; // 值 } rbtree_node; // 红黑树本体根节点 哨兵 nil 节点 typedef struct _rbtree { rbtree_node *root; rbtree_node *nil; } rbtree;这里最关键的点有两个key和value不是简单局部变量而是节点长期持有的数据。树里多了一个nil哨兵节点用来统一处理空孩子和边界情况。也就是说这里不是做“临时查一下”而是做一个长期存储在服务端内存里的有序 KV 容器。开启红黑树功能、定义字符串键类型、定义节点结构和树结构这些配置在头文件里都已经给出来了。可以把这一步理解成网络服务收的是字符串命令红黑树存的是字符串键值对。二、先别急着看树先看命令是怎么走进来的红黑树能不能用起来不在于“旋转函数写没写”而在于网络层有没有把请求正确交到它手里。1先把客户端命令切开// 把 RSET Teacher Charon 这种字符串按空格拆分 int kvs_split_token(char *msg, char *tokens[]) { if (msg NULL || tokens NULL) return -1; int idx 0; char *token strtok(msg, ); while (token ! NULL) { tokens[idx] token; // 依次保存命令、key、value token strtok(NULL, ); } return idx; // 返回拆出来的 token 个数 }这一步的作用很直接原来网络层收到的是一整串文本拆完以后就变成tokens[0]命令字tokens[1]keytokens[2]value这正是后面协议分发的入口。对应实现里协议先切词再把切出来的结果传给过滤函数。2再把命令分发到红黑树接口// 协议分发识别命令然后调用对应的红黑树操作 int kvs_filter_protocol(char **tokens, int count, char *response) { if (tokens[0] NULL || count 0 || response NULL) return -1; int cmd KVS_CMD_START; for (cmd KVS_CMD_START; cmd KVS_CMD_COUNT; cmd) { if (strcmp(tokens[0], command[cmd]) 0) { break; // 找到匹配命令 } } char *key tokens[1]; char *value tokens[2]; int ret 0; int length 0; switch (cmd) { case KVS_CMD_RSET: ret kvs_rbtree_set(global_rbtree, key, value); length (ret 0) ? sprintf(response, OK\r\n) : sprintf(response, ERROR\r\n); break; case KVS_CMD_RGET: { char *result kvs_rbtree_get(global_rbtree, key); length (result NULL) ? sprintf(response, NO EXIST\r\n) : sprintf(response, %s\r\n, result); break; } case KVS_CMD_RDEL: ret kvs_rbtree_del(global_rbtree, key); length (ret 0) ? sprintf(response, OK\r\n) : sprintf(response, NO EXIST\r\n); break; case KVS_CMD_RMOD: ret kvs_rbtree_mod(global_rbtree, key, value); length (ret 0) ? sprintf(response, OK\r\n) : sprintf(response, NO EXIST\r\n); break; case KVS_CMD_REXIST: ret kvs_rbtree_exist(global_rbtree, key); length (ret 0) ? sprintf(response, EXIST\r\n) : sprintf(response, NO EXIST\r\n); break; } return length; }这一步最能体现“网络编程 数据结构”的结合点上层收到的是文本协议中间层负责识别命令下层真正干活的是红黑树接口这样一来协议层和存储层就分开了。即使以后把红黑树换成哈希表只要命令接口不变整体服务框架仍然能复用。这个分发思路在当前实现里已经完整体现出来了。三、红黑树版本的增删改查到底怎么落地真正看懂“红黑树做了什么”最好的方式不是只看概念而是直接看接口层。1插入把 key 和 value 都拷贝进节点再插入树// RSET 的底层实现创建节点把 key-value 放进红黑树 int kvs_rbtree_set(kvs_rbtree_t *inst, char *key, char *value) { if (!inst || !key || !value) return -1; // 先创建一个新节点 rbtree_node *node (rbtree_node*)kvs_malloc(sizeof(rbtree_node)); // 为 key 单独申请空间并复制内容 node-key kvs_malloc(strlen(key) 1); if (!node-key) return -2; memset(node-key, 0, strlen(key) 1); strcpy(node-key, key); // 为 value 单独申请空间并复制内容 node-value kvs_malloc(strlen(value) 1); if (!node-value) return -2; memset(node-value, 0, strlen(value) 1); strcpy(node-value, value); // 插入红黑树 rbtree_insert(inst, node); return 0; }这段代码有一个很重要的细节不是简单地node-key key而是重新申请内存再把字符串复制进去。这样做的作用是让节点真正拥有自己的数据不依赖外部缓冲区。当前实现里的RSET就是按这个思路写的。2查找沿着“左小右大”的路径一直走// 红黑树查找本质上还是二叉搜索树查找 rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) { rbtree_node *node T-root; while (node ! T-nil) { if (strcmp(key, node-key) 0) { node node-left; // 比当前节点小去左子树 } else if (strcmp(key, node-key) 0) { node node-right; // 比当前节点大去右子树 } else { return node; // 找到了 } } return T-nil; // 没找到返回哨兵节点 }这段代码非常适合在文章里解释“为什么红黑树首先是一棵搜索树”。平衡是红黑树的特点但查找规则本质上和二叉搜索树一致还是按 key 大小决定往左还是往右。当前实现里用的是字符串 key所以比较方法是strcmp。3修改先查再只换 value// RMOD 的底层实现找到节点后只修改 value int kvs_rbtree_mod(kvs_rbtree_t *inst, char *key, char *value) { if (!inst || !key || !value) return -1; rbtree_node *node rbtree_search(inst, key); if (node inst-nil) return 1; // 没找到 // 旧值先释放 kvs_free(node-value); // 再给新值开空间 node-value kvs_malloc(strlen(value) 1); if (!node-value) return -2; memset(node-value, 0, strlen(value) 1); strcpy(node-value, value); return 0; }这里没有改树结构只改节点内部的value。也就是说RMOD做的事情不是“删掉节点重建”而是“找到已有节点把内容更新掉”。这个思路在 KV 服务里特别自然因为 key 没变树的位置就不需要变。4删除真正难的不是删而是删完以后还要修复平衡// 红黑树删除入口先按搜索树规则删除再视情况做修复 rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) { rbtree_node *y T-nil; rbtree_node *x T-nil; // y 是真正要被删掉的节点 if ((z-left T-nil) || (z-right T-nil)) { y z; } else { y rbtree_successor(T, z); // 两个孩子都在就找后继 } // x 是接替 y 位置的节点 if (y-left ! T-nil) { x y-left; } else if (y-right ! T-nil) { x y-right; } x-parent y-parent; if (y-parent T-nil) { T-root x; } else if (y y-parent-left) { y-parent-left x; } else { y-parent-right x; } // 如果删掉的是黑节点还要修复红黑树性质 if (y-color BLACK) { rbtree_delete_fixup(T, x); } return y; }这段很适合拿来说明红黑树比普通搜索树多做的一步就是删除后修复平衡。delete不是结束delete_fixup才是保证这棵树还能继续稳定工作的关键。当前实现里删除修复通过兄弟节点、颜色判断、左右旋组合完成。四、测试代码验证一套数据结构接进网络服务之后最怕的是“本地函数能跑协议联调用不了”。所以测试代码做的事情很简单直接模拟客户端发命令看服务端返回对不对。// 红黑树版本的测试顺序插入、查询、修改、再查、判断存在、删除、再次查询 void rbtree_testcase(int connfd){ testcase(connfd, RSET Teacher Charon, OK\r\n, RSET-Teacher); testcase(connfd, RGET Teacher, Charon\r\n, RGET-Teacher); testcase(connfd, RMOD Teacher King, OK\r\n, RMOD-Teacher); testcase(connfd, RGET Teacher, King\r\n, RGET-Teacher); testcase(connfd, REXIST Teacher King, EXIST\r\n, REXIST-Teacher); testcase(connfd, RDEL Teacher, OK\r\n, RDEL-Teacher); testcase(connfd, RGET Teacher, NO EXIST\r\n, RGET-Teacher); testcase(connfd, RMOD Teacher Charon, NO EXIST\r\n, RMOD-Teacher); testcase(connfd, REXIST Teacher, NO EXIST\r\n, REXIST-Teacher); }这 9 步其实正好把红黑树版本 KV 服务的核心链路全覆盖了能不能插进去能不能查出来改完值以后查出来的是不是新值删掉以后是不是确实不存在了这类测试的价值不只是“看 PASS”更重要的是验证协议层、网络层、红黑树层到底有没有真正连起来。现有测试程序就是按照这个顺序发请求、收响应、逐项校验的。结语把红黑树放进网络编程项目里真正练到的不是某一个孤立知识点而是一条完整链路文本命令怎么拆命令怎么分发红黑树怎么保存键值对查找、修改、删除怎么映射到网络响应所以这件事的重点不是“实现了一棵树”而是实现了一个能接收网络请求、并用红黑树完成增删改查的小型 KV 服务。命令枚举、协议拆分、红黑树节点定义、RSET/RGET/RDEL/RMOD/REXIST 分发、测试验证这些部分在工程里已经形成了一条清晰流程。0voice · GitHub