大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说Redis学习笔记（四） 跳跃表与整数集合[通俗易懂],希望您对编程的造诣更进一步.
（一）跳跃表
跳跃表是一种有序的数据结构，它通过每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表作为有序集合键的底层实现。
Redis中的两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。
Redis的跳跃表由zskiplistNode 与 zskiplist 两个结构定义。其中zskiplistNode 结构用于标识跳跃表节点，zskiplist结构用于保存跳跃表节点的相关信息（表头、表尾节点、节点数量等）。
zskiplistNode
typedef struct zskiplistNode{ //层 struct zskiplistLevel{ struct zskiplistNode *forward;//前进指针 unsigned int span;//跨度 } level[]; //后退指针 struct zskiplistNode *backward; //分值 double score; //成员对象 robj *obj; }
代码100分
层中包含多个元素，每个元素是指向其他节点的指针，通过这些层可以加快访问其他节点的速度，层越多，访问其他节点的速度越快。没增加一个跳跃节点，程序根据幂次定律（越大的数出现概率越小）生成1-32之间的值作为层高。
1、每层都有一个指向表尾方向的前进指针，作为表头向表尾方向访问节点。
2、层中的跨度用于记录两个节点之间的距离。
3、后退指针则只能一次跨1个节点进行访问。
4、跳跃表的排序是按照所有节点的分值来排序的。
5、节点中的对象则是保存了一个SDS的字符串。
6、同一个跳跃表的对象必须唯一，但分值可以重复。（相同分数，成员小的靠前排）。
跳跃表zskiplist
代码100分typedef struct zskiplist{ struct skiplistNode *header,*tail;//表头节点与表尾节点 unsigned long length;//表中节点的数量 int level;//表中层数最大的节点的层数(表头不计算在内) } zskiplist;
（二）整数集合
整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现，并且保证集合中不会出现重复元素。
intset
typedef struct intset{ uint32_t encoding;//编码方式 uint32_t length;//集合包含的元素数量。 int8_t contents[];//保存元素的数组 } intset;
contents数组是这个数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项的数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。
升级
当我们要将一个新元素添加到整数集合里面时，并且新元素类型比整数集合现有的所有元素类型都长时，整数集合需要先进性升级，然后才能将新的元素添加到整数集合中。
1、根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2、将底层数组现有的所有元素都转换为与新元素相同的类型，并将类型转换后的元素放置到正确位置上，而且在放置元素过程中，需要继续维持底层数组的有序性质不变。
3、将新元素添加到底层数组里面。
4、修改整数集合encoding属性。
因为每次向整数集合添加新元素都有可能引起升级，而每次升级都需要将底层数组中已有的所有元素进行类型转换，所以向整数集合中添加新元素的时间复杂度为O(N);
—- end —-
每天学一点，总会有收获。
说明：尊重作者知识产权，文中内容参考《Redis设计与实现》，仅在此做学习与大家分享。
![Redis学习笔记（四） 跳跃表与整数集合[通俗易懂]](https://www.yht7.com/upload/image/20200513/404258-20200512234136830-356484428.png "Redis学习笔记（四） 跳跃表与整数集合[通俗易懂]插图2")
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/8479.html
