Redis为何这么快——数据存储角度

ZSet有序集合对象底层实现可以是ziplist（压缩列表）或者skiplist（跳跃表）。

当一个有序集合的元素数量比较多或者成员是比较长的字符串时，Redis就使用skiplist（跳跃表）作为ZSet对象的底层实现。

typedef struct zskiplist {  
 // 表头节点和表尾节点  
 struct zskiplistNode *header, *tail;  
 // 表中节点的数量  
 unsigned long length;  
 // 表中层数最大的节点的层数  
 int level;  
 } zskiplist;  
typedef struct zskiplistNode {  
 // 成员对象  
 robj *obj;  
 // 分值  
 double score;  
 // 后退指针  
 struct zskiplistNode *backward;  
 // 层  
 struct zskiplistLevel {  
 // 前进指针  
 struct zskiplistNode *forward;  
 // 跨度---前进指针所指向节点与当前节点的距离  
 unsigned int span;  
 } level[];  
} zskiplistNode; 

zadd---zslinsert---平均O(logN), 最坏O(N)

zrem---zsldelete---平均O(logN), 最坏O(N)

zrank--zslGetRank---平均O(logN), 最坏O(N)

skiplist的查找时间复杂度是LogN，可以和平衡二叉树相当，但实现起来又比它简单。跳跃表(skiplist)是一种有序数据结构，它通过在某个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

【编辑推荐】

1. 如何使用Redis构建轻量级微服务
2. 如何使用Redis做MySQL的缓存
3. Redis如何分析慢查询操作？
4. 读完这篇文章，就基本搞定了Redis数据库
5. Redis常见的几种使用方式解决方案总结

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!