skiplist实现
skiplist跳跃表,是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,来达到快速访问节点的目的,redis使用skiplist作为zsort的底层实现之一
结构很像树形结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| 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;
|