锐客网

  1. 首页 > 睿知 > it技术 > >

redis为啥用跳表不用b+树 redis实现跳表源码

睿知

导读：本文将介绍Redis中跳表的实现源码，主要涉及跳表的结构、插入、删除、查找等操作的实现过程 ， 并对跳表的优缺点进行分析和总结 。
1. 跳表的结构
Redis中跳表的结构体定义如下：
```
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
其中 ， zskiplistNode表示跳表的节点，包含元素值ele、分值score、后退指针backward和层级level；zskiplist表示跳表，包含头尾指针header、tail、长度length和层数level 。
2. 插入操作
插入操作是跳表中最复杂的操作之一，其实现过程如下：
(1) 首先确定新节点应该插入到哪一层，这个过程需要随机生成一个层数，具体代码如下：
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level }
其中，ZSKIPLIST_P是一个常量，用于控制随机生成层数的概率 。
(2) 创建新节点，并为其分配空间，具体代码如下：
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn = malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
(3) 从头结点开始查找插入位置 ， 具体代码如下：
zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
unsigned int rank[ZSKIPLIST_MAXLEVEL];
zskiplistNode *x = zsl->header;
for (int i = zsl->level-1; i >= 0; i--) {
rank[i] = (i == (zsl->level-1)) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
strcmp(x->level[i].forward->ele, ele) < 0))) {
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
其中，update数组保存每一层中需要更新的节点，rank数组保存每一层中需要更新的节点的排名 。
(4) 根据随机生成的层数，将新节点插入到跳表中，具体代码如下：
int level = zslRandomLevel();
if (level > zsl->level) {
for (int i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
zsl->level = level;
zskiplistNode *x = zslCreateNode(level, score, ele);
for (int i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
x->level[i].span = update[i]->level[i].span - (rank[0]-rank[i]);
update[i]->level[i].span = (rank[0]-rank[i])+1;
for (int i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
(5) 返回新节点，插入操作完成 。
3. 删除操作
删除操作是跳表中比较简单的操作之一，其实现过程如下：
(1) 查找需要删除的节点，具体代码如下：
x = x->level[0].forward;
if (!x || x->score != score || strcmp(x->ele, ele)) {
【redis为啥用跳表不用b+树 redis实现跳表源码】return

    推荐阅读


    上一篇：如何在战舰猎手中更换服务器？ 战舰猎手怎么改服务器

    下一篇：redis并发写入性能 redis并发号码占用