1.Zset

redis的中的Zset底层是一个跳表，Skip list是一个“概率型”的数据结构，可以在很多应用场景中替代平衡树。Skip list算法与平衡树相比，有相似的渐进期望时间边界，但是它更简单，更快，使用更少的空间。

Skip list是一个分层结构多级链表，最下层是原始的链表，每个层级都是下一个层级的“高速跑道”。 假设：zset中存X个节点 跳表的高度： h = logX; 跳表的每一层中放着数据索引： 第一级索引个数为：X/2；
第二级索引个数为：X/4；
···
第h级索引个数为：X/2^h； 某个i层的元素，出现在i+1层的概率p是固定的，例如常取p=1/2或p=1/4；
平均来讲，每个元素出现在1/(1-p)个链表中；
最高的元素，例如head通常采用Int.MIN_VALUE作为的最小值，会出现在每一层链表中； 跳表特性： 查询 和 增加 删除的算法难度都是logN。其实是二分法的一种实现。跳表在插入和删除的时候，要注意。 　　插入时：跳表通过“随机函数”来维护前面的“高效性”，具体的操作是：往跳表中插入数据a时，通过随机函数生成一个随机数h，a插入单链表的同时，在第1级到第h级中也同时插入索引a。随机函数不是乱选的，要能保证索引的大小及跳表的平衡性，防止它退化成单链表的窘境。跳表的实现有点复杂，所以在此不再赘述。 　　删除时：删除时，不仅仅要删除单链表，而且还要删除索引。

 

 

 

产考链接:

https://www.jianshu.com/p/60d2561b821c

https://www.jianshu.com/p/60d2561b821c

https://blog.csdn.net/u011489043/article/details/78769428