-
无序集合
redis通常使用字典结构保存集合数据,字典健存储集合元素,字典值为空。如果一个集合全为整数,使用字典就有点浪费了,redis使用intset保存。
- 插入元素到intset中
- 获取插入元素编码,如果插入元素编码级别高于intset编码,intset的编码则需要升级
- 通过二分查找插入元素是否为重复插入,是,则插入失败,否,则赋值
- 为intset重新分配内存空间(分配插入元素所需空间),若插入位置存在后驱节点,后驱节点全部后移
- 更新intset的len值
- intset升级编码
- 设置新的编码,然后分配新的内存空间
- 将intset的元素移动到新位置
- 然后插入新的元素
redis不会降级intset编码!
- 插入元素到intset中
-
有序集合
当数据都是有序的时候,则使用数组和链表进行存储。redis中的skiplist既能通过二分查找元素,又能快速插入数据。
-
skiplist
skiplist是一个多层级链表结构。
-
skiplist查找元素
- 当查找元素的时候需要从最高层进行查找。
- 如果存在后驱节点并且后驱节点小于目标值,则沿forward继续寻找。
- 如果节点等于目标值则返回,否则降一级查找。
2. skiplist插入元素
- 查找每层插入位置的前驱节点
- 随机生成新节点的层数
- 新节点的层数比其他节点大的时候,skiplist需要添加新的层数
- 因为头层数需要大于等于其他节点的层数,所以要在头节点添加新的层,头节点新增的层为skiplist的长度。
- 因为skiplist的头节点预先就分配好了最大层内存,所以不用再分配内存
- 创建节点,遍历各层,插入新节点并更新前后节点的属性。
- 如果存在一个节点的层数比新节点的层数大,则其前驱节点的要加1
- 设置新节点的backward值,更新skiplist.length属性
-
有序集合通过ziplist和skiplist存储元素,所以它有两种编码OBJ_ENCODING_ZIPLIST和OBJ_ENCODING_SKIPLIST。
只有 有序集合元素数量小于或等于配置中的server.zset_max_ziplist_entries和有序集合元素长度小于或等于配置中的server.zset_max_ziplist_value时才使用ziplist存储有序集合。
-