有书共读：《Redis设计与实现》第五章和第六章读书笔记
第5章：跳跃表
跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。其节点查找的平均复杂度为O(logN)，最坏复杂度为O(logN)。
Redis的跳跃表有redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中：
1）zskiplistNode结构用于表示跳跃节点；
2） zskiplist结构用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等；
3）每个跳跃表节点的层高都是1至32之间的随机数；
4）在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的；
5）跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
第6章：整数集合
整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
整数集合是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值。其底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
升级：每当需要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面。
升级整数集合并添加新元素共分为三步进行：
1）根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2）将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
3）将新元素添加到底层数组里面。
整数集合的升级操作的好处：1）提升整数集合的灵活性，2）尽可能地节约内存。
整数集合只支持升级操作，不支持降级操作。
#设计##读书笔记##笔记#
投递理想汽车等公司10个岗位 >