redis跳跃表实现方式
作者:bin跳跃表是一链表的一个变种,通常普通的链表都是只有1个前驱,1个后继节点。
跳跃表可以除了原链表,他还增加了多层链表,每层都是一个链表
例如链表: 1 <-> 2 <-> 3 <-> 4 <-> 5
跳跃表除了:第一层(1 <-> 2 <-> 3 <-> 4 <-> 5),他还包含,第二层(1 <-> 3)、第三层(1<->5)
好处是,有序集合,他可以用2分法快速的查找元素,例如要找元素4,普通链表需要从1到4遍历,二跳跃表可以先比较1到3,发现比3大,即排除了一半的元素,提高了查找的效率。
一个跳跃表的图:
问题:
redis为什么不用红黑树,而要使用跳跃表呢?
1.范围查找的时候,跳跃表比红黑树操作更简单,比较次数更少
2.平衡树插入节点可能会引发树调整,操作更复杂,跳跃表只要修改相邻节点即可
3.内存占有更小,单节点引用指针跟少