有趣的算法(二)——跳跃表的分析
(原创内容,转载请注明来源,谢谢)
一、概述
最近在学习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