redis-数据结构-跳跃表+压缩列表

跳跃表

简化跳跃表逻辑，（跳跃的方式比较类似二分法，只是分的规则不完全取mid位置）

类似于有序的双向链表，但同时有多个双向链表，(这里以单链举例)比如链表1->2->3->4->5->6->7->8->9

• 1->5->9 记l1
• 1->3->5->7->9 记l2
• 1->2->3->4->5->6->7->8->9 记l3 遍历数据时，先遍历最上层数据，比如查找6，
• 遍历l1,发现9大于6，故在5节点位置同步下沉到l2的5
• 继续向前遍历l2, 5后边是7，7>6,继续下沉到l3的5
• 继续向前遍历l3,5后边是6，故找到6的位置

结构图

• backward是将跳跃表的不同节点逆序链接，可参考上图
• forward是将跳跃表的不同节点正序链接，图中未标注
• ele是sds，类似于有序集合的member
• score是分值，有序集合用来排序

压缩列表

压缩列表主要是为了节约内存而生

压缩列表优势

• 压缩列表类似于数组，不同的是压缩列表会根据存储的元素大小，压缩存储元素大小，且支持不同元素的大小可大小不一
• 有序集合在压缩列表的元素最大存储64字节或者数量超过128，超过则就需要切换底层结构为跳跃表
• 压缩列表适合元素数据占用小，且元素数量少
• 压缩列表支持正序和逆序遍历

结构图

压缩列表的结构如下：

压缩列表元素的结构定义如下:

这里只列出了主要的元素

• prevlen: 记录上一个元素的长度，可以逆序遍历时使用 p - prevrawlen为上一个元素地址
• encoding:记录当前元素类型+内容的长度
• content: 存储当前元素 故正序遍历下一个元素地址=p+prevlensize+encodingsize+contentsize