研究Redis中跳表的遍历方法（redis跳表如何遍历）

Redis是一款开源的基于内存key /value数据库。跳表是Redis中用于储存有序数据的数据结构，由网上查询跳表是一种只在两端以O（logN）时间复杂度插入，删除，取得有序数据的数据结构。在Redis中，跳表主要用于实现有序集合功能，在有序集合钟添加新的元素和删除已存在的元素时，跳表的操作几乎可以实现O（logN）的时间复杂度，在时间复杂度上性能远高于普通的哈希表。那么跳表有哪些特点？该怎么去遍历跳表？

跳表与普通的链表类似，它从头结点和尾结点开始，在头结点和尾结点之间，以比较稳定的层级来连接其他节点，每一层的节点的指向性为一侧连接，也就是每一层的节点只能指向较低层级的节点，利用这种结构，实现查找的时间复杂度达到O（logN），遍历是比较重要的操作，下面介绍一下如何遍历跳表：

（1）从头结点开始，按照向右的方向，依次遍历；

（2）当到达有效结点时，访问这个结点；

（3）然后再次访问该结点，下行搜索它的元素所在的低层级；

（4）当这个低层级搜索完毕，将再次向右移动；

（5）循环这个步骤，直到跳表的末端元素。

以下是基于有序集合实现的跳表遍历的代码：

zsl_list* zsl_getNext(zsl_list* node) {
 if (node->level[0].forward == NULL) {
  return NULL;
 }

 //如果node节点有下一个节点，从底层开始迭代节点
 int i = 0;
 while (i level[i].span &&
   node->level[i].forward == NULL) {
  i++;
 }
 return node->level[i].forward;
}
// 遍历跳表
int zsl_traversal(zsl_list *zslHead) {
 int nodeLevel; 
 zsl_list *node;
 node = zslHead->level->forward;  // 获取首元结点

 while (node != NULL) {
  nodeLevel = node->level;

  int i;
  for (i = nodeLevel-1; i >= 0; --i) {
   printf("node.value = %d rank = %d, span =%d\n", 
   node->score, node->rank, node->level[i].span);  
  }
  node = node->level[0].forward;
 } 
 return 1;
}