![](https://csdnimg.cn/release/download_crawler_static/86388281/bg1.jpg)
为啥 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 实现过红黑树么?实在看不懂。