跳跃表是如何实现的?原理?
跳跃表是如何实现的?原理?
跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其它节点的指针,从而达到快速访问节点的目的。
为什么使用跳跃表?
首先,因为 zset 要支持随机的插入和删除,所以它 不宜使用数组来实现,关于排序问题,我们也很容易就想到 红黑树/ 平衡树 这样的树形结构,为什么 Redis 不使用这样一些结构呢?
- 性能考虑: 在高并发的情况下,树形结构需要执行一些类似于 rebalance 这样的可能涉及整棵树的操作,相对来说跳跃表的变化只涉及局部;
- 实现考虑: 在复杂度与红黑树相同的情况下,跳跃表实现起来更简单,看起来也更加直观;
基于以上的一些考虑,Redis 基于 William Pugh 的论文做出一些改进后采用了 跳跃表 这样的结构。
本质是解决查找问题。
跳跃表是怎么实现的?
跳跃表的节点里有这些元素:
- 层 跳跃表节点的level数组可以包含多个元素,每个元素都包含一个指向其它节点的指针,程序可以通过这些层来加快访问其它节点的速度,一般来说,层的数量月多,访问其它节点的速度就越快。
每次创建一个新的跳跃表节点的时候,程序都根据幂次定律,随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”
- 前进指针 每个层都有一个指向表尾的前进指针(level[i].forward属性),用于从表头向表尾方向访问节点。
- 跨度 层的跨度用于记录两个节点之间的距离。跨度是用来计算排位(rank)的:在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排位。
例如查找,分值为3.0、成员对象为o3的节点时,沿途经历的层:查找的过程只经过了一个层,并且层的跨度为3,所以目标节点在跳跃表中的排位为3。
- 分值和成员 节点的分值(score属性)是一个double类型的浮点数,跳跃表中所有的节点都按分值从小到大来排序。
节点的成员对象(obj属性)是一个指针,它指向一个字符串对象,而字符串对象则保存这一个SDS值。