为啥 redis 使用跳表(skiplist)而不是使用 red-black？1
需积分: 0 33 浏览量
2022-08-08
22:49:44
上传
评论
收藏 24KB DOCX 举报
为啥 redis 使用跳表(skiplist)而不是使用 red-black？
当数据元素个数少于某值，redis 会使用 l 跳表来存储元素，而不使用 hash。
如果把跳表换成红黑树，redis 的性能会有多大的变化？
Hak Ego
题主的问题没有说清楚，有些概念混淆。
1. “当数据元素个数少于某值，redis 会使用 l 跳表来存储元素，而不使用 hash。” 这里应该是
ziplist 而不是跳表。ziplist 的使用属于 redis 具体实现上，针对较少元素时用时间换空间的一种
优化方法。
2. redis 使用跳表的地方是在 ZSET(sorted list)里，zset 是 redis 支持的一类数据结构，属于 redis
对外接口的一部分。请查阅 Z*系列的命令。
如果题主是想问跳表和红黑树的话，就不要提节省内存的 ziplist。这两个是不同 level 上的概念。
于康，买飞机找我~~
amazingjxq、十三、陈乐群 等人赞同
1 skiplist 的复杂度和红黑树一样，而且实现起来更简单。
2 在并发环境下 skiplist 有另外一个优势，红黑树在插入和删除的时候可能需要做一些 rebalance
的操作，这样的操作可能会涉及到整个树的其他部分，而 skiplist 的操作显然更加局部性一些，
锁需要盯住的节点更少，因此在这样的情况下性能好一些。
具体可以参考 Herb Sutter 写的 Choose Concurrency-Friendly Data Structures.
另外这篇论文里有更详细的说明和对比，page50~53：
http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf
囧 原来和一楼答案差不多。
dccmx，搞技术的
空成、freeNik、Witkey Fan 等人赞同
redis 使用跳表(ziplist)?
首先，跳表是 skiplist？不是 ziplist。ziplist 在 redis 中是一个非常省内存的链表（代价是性能略
低），所以在 hash 元素的个数很少（比如只有几十个），那么用这个结构来存储则可以在性能
损失很小的情况下节约很多内存（redis 是内存数据库啊，能省还是要省的）。好这个问题清楚
了。
至于这个问题：请问，有人用 C 实现过红黑树么？实在看不懂。
养生的控制人
- 粉丝: 17
- 资源: 333
评论0