有趣的算法（二）——跳跃表的分析

有趣的算法（二）——跳跃表的分析

（原创内容，转载请注明来源，谢谢）

一、概述

最近在学习redis，其中说到当使用redis的sorted set类型时，如果数据量大，redis内部会使用跳跃表结合散列表的方式对数据进行存储。其中散列表主要用在存储score，即hash的方式——键值对。而由于sorted set的值按照score有序排序，因此跳跃表用于存储score和内容的对应关系。

二、理想跳跃表的存储

跳跃表是一种改进的链表，理想的跳跃表如下图：

从图中可以看到，跳跃表通过增加存储，来达到查询时的类二分法。理想跳跃表，第一层的数字是从小到大排序，第二层存储了第一层每两个中的一个，第三层存第二层每两个中的一个，以此类推，最后一层存储2个。另外，除了第一层，其余每一层每一个元素都指向下一层中和本元素值相同的元素。

这样做的好处在于，查询的时候可以从最高层开始查找，从小到大，当匹配到小于目标值的最大值时，进入下一层进行查找，以此类推，直到找到结果或确定结果不存在。

三、redis中sorted set的值存储

类似跳跃表，但是为了方便逆向排序，对每个元素加入了指向前一个元素的指针。另外根据sorted set特性，允许跳跃表中的元素值相同。

四、类理想跳跃表

理想跳跃表对于查找来说实现完全的二分法，速度最快。但是，当元素插入、删除时，如果仍使用理想跳跃表，维护起来极其复杂。因此，通常采用类理想跳跃表，即非理想情况下的最优，而又最利于元素的插入和删除。

观察理想跳跃表，发现高层元素的个数总是下一层元素的一半。现采用概率的方式，第一层所有新增的数据全部加入，第二层开始，当第一层元素插入后的，其的前后都没有对应的第二层的元素指向，则在第二层直接加入；如果前后都有，则不加入；如果前后有一个指向，则用随机的方式，如果随机出值，就在第二层进行增加，否则不增加。高层类推。

此方法在数据量小的时候，偏差较大，而当数据量非常大的时候，由于总是0.5的几率插入，因此概率上是一个接近完美的跳跃表。

因此，数据量小的时候，不适合使用跳跃表，因为n很小的时候，O(1)和O(n)差距不大。当数据量大的时候，由于类理想跳跃表又接近于理想跳跃表，则可以很好的使用。

——written by linhxx 2017.08.07