Redis跳表使用的不足之处（redis用跳表缺点）

Redis跳表使用的不足之处

Redis是现代的高性能内存数据库，已经成为了广受欢迎的数据库解决方案之一。它能够提供高效的数据读写，支持复制和持久化，而且还提供了超过100个命令，支持不同类型的数据结构。其中，Redis跳表作为一种快速检索的数据结构，也被广泛应用于Redis中。不过，Redis跳表还存在一些不足之处，本文将分析并讨论其问题所在。

Redis跳表的结构与算法简介

跳表是一种可以替代平衡树的数据结构。由William Pugh于1990年发明，是一种用来在有序链表中进行快速查找的数据结构。Redis跳表用于有序集合的实现，它采用了类似于平衡树的算法，在一定情况下可以提供更高效的性能。

跳表中的元素是有序排列的，每个元素都有一个指向后面元素的指针，而且每个元素还有一定的概率指向多个后继节点。这样就可以在查找元素的时候，跨越多个元素，实现快速查找。

Redis跳表的优缺点

Redis跳表具有以下优点：

1. Redis跳表能够提供最坏情况下O(logN)的时间复杂度，用于实现高效的排序查找；

2. Redis跳表非常容易实现，而且也不需要进行动态平衡操作，相比于红黑树等平衡树，其代码实现要简单不少；

3. Redis跳表较为灵活，能够适应一定的数据规模变化，不需要像平衡树那样频繁进行平衡操作。

然而Redis跳表也存在一些问题：

1. 针对数据分布特点差异较大的有序集合，Redis跳表的性能并不比平衡树更优；

2. 跳表的高效依赖于节点分布的随机性和跳表的层数，在实际使用中并非总是稳定和可预测。

结论

Redis跳表是一种简单而高效的数据结构，被广泛地应用于Redis服务中。然而在一定的情况下，它仍然存在不足之处，需要根据具体的数据分布特点进行选择。

代码示例：

以下是一个简单的Redis跳表实现，方便读者理解：

struct skipList {
  struct skiplistNode *header, *tl;
  unsigned long length;
  int level;
};
 
struct skiplistNode {
  robj *obj;
  double score;
  struct skiplistNode *backward;
  struct skiplistLevel {
    struct skiplistNode *forward;
    unsigned int span;
  } level[];
};
 
skiplistNode *slCreateNode(int level, double score, robj *obj) {
  skiplistNode *sn = zmalloc(sizeof(*sn)+level*sizeof(struct skiplistLevel));
  sn->score = score;
  sn->obj = obj;
  return sn;
}
 
skiplist *slCreate(void) {
  int j;
  skiplist *sl;
 
  sl = zmalloc(sizeof(*sl));
  sl->level = 1;
  sl->length = 0;
  sl->header = slCreateNode(SKIPLIST_MAXLEVEL,0,NULL);
  for (j = 0; j 
    sl->header->level[j].forward = NULL;
    sl->header->level[j].span = 0;
  }
  sl->header->backward = NULL;
  sl->tl = NULL;
  return sl;
}
 
static unsigned int zslRandomLevel(void) {
  unsigned int level = 1;
  while ((random()&0xFFFF) 
      level += 1;
  return (level
}
 
int slInsert(skiplist *sl, double score, robj *obj) {
  skiplistNode *update[SKIPLIST_MAXLEVEL], *x;
  unsigned int rank[SKIPLIST_MAXLEVEL];
  int i, level;
 
  assert(!isnan(score));
  x = sl->header;
  for (i = sl->level-1; i >= 0; i--) {
    /* store rank that is crossed to reach the insert position */
    rank[i] = i == (sl->level-1) ? 0 : rank[i+1];
    while (x->level[i].forward &&
           (x->level[i].forward->score 
            (x->level[i].forward->score == score &&
             compareStringObjects(x->level[i].forward->obj,obj) 
      rank[i] += x->level[i].span;
      x = x->level[i].forward;
    }
    update[i] = x;
  }
  /* we assume the element is not already inside, since we allow duplicated
   * scores, and the re-insertion of score and redis object should never
   * happen since the caller of slInsert() should test in the hash table
   * if the element is already inside or not. */
  level = zslRandomLevel();
  if (level > sl->level) {
    for (i = sl->level; i 
        rank[i] = 0;
        update[i] = sl->header;
        update[i]->level[i].span = sl->length;
    }
    sl->level = level;
  }
  x = slCreateNode(level,score,obj);
  for (i = 0; i 
    x->level[i].forward = update[i]->level[i].forward;
    update[i]->level[i].forward = x;
 
    /* update span covered by update[i] as x is inserted here */
    x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
    update[i]->level[i].span = (rank[0] - rank[i]) + 1;
  }
  for (i = level; i level; i++) {
    update[i]->level[i].span++;
  }
  x->backward = (update[0] == sl->header) ? NULL : update[0];
  if (x->level[0].forward)
    x->level[0].forward->backward = x;
  else
    sl->tl = x;
  sl->length++;
  return 1;
}
 
void slFreeNode(skiplistNode *node) {
  decrRefCount(node->obj);
  zfree(node);
}
 
void slFree(skiplist *sl) {
  skiplistNode *node = sl->header->level[0].forward, *next;
 
  zfree(sl->header);
  while(node) {
    next = node->level[0].forward;
    slFreeNode(node);
    node = next;
  }
  zfree(sl);
}