ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
### 2.4.1 跳跃表的结构 跳跃表由 `server.h/zskiplist` 和 `server.h/zskiplistNode` 定义: ```c // 跳跃表结点 typedef struct zskiplistNode { sds ele; // 成员对象 double score; // 结点按照各自的分值从小到大排序 struct zskiplistNode *backward; // 后退指针,用于从表尾向头遍历 struct zskiplistLevel { // 层 struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度 } level[]; } zskiplistNode; // 跳跃表 typedef struct zskiplist { struct zskiplistNode *header, *tail; // 表头表尾结点 unsigned long length; // 结点长度 int level; // 最大层数 } zskiplist; ``` - 层:level数组包含多个元素,每个元素包含指向其他结点的指针 - 理论上层的数量越多,访问其他结点的速度越快 - 每次创建一个新结点时,程序都根据幂次定律(越大的数出现的概率越小)随机生成一个介于1到32的数作为level数组的大小 - 前进指针:用于从头到尾遍历 - 跨度:记录两个结点之间的距离,用于计算排位(rank) - 跨度越大,相距越远 - 指向NULL的所有前进指针跨度都是0 - 后退指针:用于从后向前遍历 - 分值和成员: - 表中所有结点都按照分值(score)进行从小到大的排序 - 成员对象(ele)是一个SDS类型,必须唯一