Redis ZSet 底层skiplist是如何设计与实现的

跳表是空间换时间, 这是毋庸置疑的

skiplist 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

为什么说 skiplist 是二分查找的链表

• 首先看一下链表的结构

链表一般和数组作比较, 链表插入和删除的时间复杂度是O(1), 为什么说是O(1)呢, 因为链表在内存中是不连续的, 插入只对两个元素又影响, 但是链表也有痛处, 就是链表不能随机访问, 因为他的内存不连续(没有扩容的问题)所以必须有向前后元素位置的指针, 会消耗更多的内存. 数据出入和删除的时间复杂度是O(n), 为什么? 因为数据在内存中是一块连续的空间(扩容的时候也是找到1.5倍的空间把之前的复制过去), 所以插入和删除元素会影响后面的元素, 集体往后移位或者往前移位, 数据也有他的优势, 虽然数据查询的时间复杂度也是O(n), 但是数据可以通过索引来随机访问.

• skiplist 是如何实现二分查找的链表

刚才说了链表的查找时间复杂度是O(n), 如果可以二分查找, 时间复杂度直接降为O(log n), skiplist 是这样解决的, 在链表的基础上增加了几层索引(redis 默认是32层), 这是链表就变成这样了

这样就变成了二分查找了, 这时候问题来了, 如何插入和删除一个节点, 是不是要rebalance?

• skiplist 是如何解决rebalance

skiplist不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数, 现在结构就成这样了

• skiplist 是如何删除一个节点或者插入一个节点的呢

其实和链表的插入是一样的, 只不过skiplist 的前驱有很多个, 也是先修改前驱节点的后驱节点的前驱, 在修改前驱节点的后驱, 如果新增的节点的level比较高, 那么整体skiplist的level也要增高

删除也一样, 如果删除的节点level比较高, 那么有可能会降低整体的level

具体源码参照这篇文章 http://cmsblogs.com/?p=4430