redis list底层数据结构

本文涉及的产品
云原生内存数据库 Tair,内存型 2GB
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Redis 版,经济版 1GB 1个月
简介: redis list数据结构 redis list数据结构底层采用压缩列表ziplist或linkedlist两种数据结构进行存储,首先以ziplist进行存储,在不满足ziplist的存储要求后转换为linkedlist列表。

redis list数据结构

 redis list数据结构底层采用压缩列表ziplist或linkedlist两种数据结构进行存储,首先以ziplist进行存储,在不满足ziplist的存储要求后转换为linkedlist列表。
当列表对象同时满足以下两个条件时,列表对象使用ziplist进行存储,否则用linkedlist存储。

  • 列表对象保存的所有字符串元素的长度小于64字节
  • 列表对象保存的元素数量小于512个。

redis list元素添加过程

 list的数据添加根据传入的变量个数一个个顺序添加,整个顺序如下:

  • 创建list对象并添加到db的数据结构当中
  • 针对每个待插入的元素添加到list当中
void pushGenericCommand(redisClient *c, int where) {

    int j, waiting = 0, pushed = 0;

    // 取出列表对象
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);

    // 如果列表对象不存在,那么可能有客户端在等待这个键的出现
    int may_have_waiting_clients = (lobj == NULL);

    if (lobj && lobj->type != REDIS_LIST) {
        addReply(c,shared.wrongtypeerr);
        return;
    }

    // 将列表状态设置为就绪
    if (may_have_waiting_clients) signalListAsReady(c,c->argv[1]);

    // 遍历所有输入值,并将它们添加到列表中
    for (j = 2; j < c->argc; j++) {

        // 编码值
        c->argv[j] = tryObjectEncoding(c->argv[j]);

        // 如果列表对象不存在,那么创建一个,并关联到数据库
        if (!lobj) {
            lobj = createZiplistObject();
            dbAdd(c->db,c->argv[1],lobj);
        }

        // 将值推入到列表
        listTypePush(lobj,c->argv[j],where);

        pushed++;
    }

    // 返回添加的节点数量
    addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));

    // 如果至少有一个元素被成功推入,那么执行以下代码
    if (pushed) {
        char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";

        // 发送键修改信号
        signalModifiedKey(c->db,c->argv[1]);

        // 发送事件通知
        notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
    }

    server.dirty += pushed;
}



 list的每个元素的插入过程中,我们会对是否需要进行转码作两个判断:

  • 对每个插入元素的长度进行判断是否进行ziplist->linkedlist的转码。
  • 对list总长度是否超过ziplist最大长度的判断。
/* 
 * 将给定元素添加到列表的表头或表尾。
 *
 * 参数 where 决定了新元素添加的位置:
 *
 *  - REDIS_HEAD 将新元素添加到表头
 *
 *  - REDIS_TAIL 将新元素添加到表尾
 *
 *
 * 调用者无须担心 value 的引用计数,因为这个函数会负责这方面的工作。
 */
void listTypePush(robj *subject, robj *value, int where) {

    // 是否需要转换编码?
    listTypeTryConversion(subject,value);

    // #define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512
    if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
        ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);

    // ZIPLIST
    if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
        int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
        // 取出对象的值,因为 ZIPLIST 只能保存字符串或整数
        value = getDecodedObject(value);
        subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
        decrRefCount(value);

    // 双端链表
    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
        if (where == REDIS_HEAD) {
            listAddNodeHead(subject->ptr,value);
        } else {
            listAddNodeTail(subject->ptr,value);
        }
        incrRefCount(value);

    // 未知编码
    } else {
        redisPanic("Unknown list encoding");
    }
}



 判断ziplist中单个元素的长度是否超过64的长度,如果超过了长度那么就需要转编码格式为linkedlist编码。

/* 
 * 对输入值 value 进行检查,看是否需要将 subject 从 ziplist 转换为双端链表,
 * 以便保存值 value 。
 *
 * 函数只对 REDIS_ENCODING_RAW 编码的 value 进行检查,
 * 因为整数编码的值不可能超长。
 */
void listTypeTryConversion(robj *subject, robj *value) {

    // 确保 subject 为 ZIPLIST 编码
    if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;

    if (sdsEncodedObject(value) &&
        // 看字符串是否过长,#define REDIS_LIST_MAX_ZIPLIST_VALUE 64
        sdslen(value->ptr) > server.list_max_ziplist_value)
            // 将编码转换为双端链表
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
}


redis ziplist数据结构

 ziplist又叫压缩列表,整体的数据格式如下,暂时可以临时看一看,后面会针对数据结构专门的文章来解释。

/* 
空白 ziplist 示例图

area        |<---- ziplist header ---->|<-- end -->|

size          4 bytes   4 bytes 2 bytes  1 byte
            +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
            |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
            +---------+--------+-------+-----------+
                                       ^
                                       |
                               ZIPLIST_ENTRY_HEAD
                                       &
address                        ZIPLIST_ENTRY_TAIL
                                       &
                               ZIPLIST_ENTRY_END

非空 ziplist 示例图

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL
*/
/*
 * 保存 ziplist 节点信息的结构
 */
typedef struct zlentry {

    // prevrawlen :前置节点的长度
    // prevrawlensize :编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;

    // len :当前节点值的长度
    // lensize :编码 len 所需的字节大小
    unsigned int lensize, len;

    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;

    // 当前节点值所使用的编码类型
    unsigned char encoding;

    // 指向当前节点的指针
    unsigned char *p;

}


redis linkedlist数据结构

 双向列表的格式是通用的数据结构,不用过多解释大家都能理解了。

/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

/*
 * 双端链表迭代器
 */
typedef struct listIter {

    // 当前迭代到的节点
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

/*
 * 双端链表结构
 */
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

    // 链表所包含的节点数量
    unsigned long len;

} list;
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
21天前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
36 1
|
21天前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
33 0
|
7天前
|
存储 缓存 Python
Python中的列表(List)和元组(Tuple)是两种重要的数据结构
【7月更文挑战第12天】Python中的列表(List)和元组(Tuple)是两种重要的数据结构
9 1
|
7天前
|
消息中间件 存储 NoSQL
Redis数据结构—跳跃表 skiplist 实现源码分析
Redis 是一个内存中的数据结构服务器,使用跳跃表(skiplist)来实现有序集合。跳跃表是一种概率型数据结构,支持平均 O(logN) 查找复杂度,它通过多层链表加速查找,同时保持有序性。节点高度随机生成,最大为 32 层,以平衡查找速度和空间效率。跳跃表在 Redis 中用于插入、删除和按范围查询元素,其内部节点包含对象、分值、后退指针和多个前向指针。Redis 源码中的 `t_zset.c` 文件包含了跳跃表的具体实现细节。
|
8天前
|
存储 NoSQL Redis
Redis数据结构—跳跃表 skiplist
Redis数据结构—跳跃表 skiplist
|
14天前
|
NoSQL Redis
Redis05数据结构介绍,数据结构介绍,官方网站中看到
Redis05数据结构介绍,数据结构介绍,官方网站中看到
|
消息中间件 NoSQL Redis
Redis---List数据类型操作
一、概述: 在Redis中,List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表一样,我们可以在其头部(left)和尾部(right)添加新的元素。在插入时,如果该键并不存在,Redis将为该键创建一个新的链表。与此相反,如果链表中所有的元素均被移除,那么该键也将会被从数据库中删除。List中可以包含的最大元素数量是4294967295。 从元素插入和删除的
1664 0
|
14天前
|
NoSQL Java Redis
软件开发常见流程之宝塔初始化安装环境配置,Lam前面不选,直接跳商城,在宝塔内点击软件商城,安Mysql5.7,安java项目管理器,安Ngnix最新版,安Redis
软件开发常见流程之宝塔初始化安装环境配置,Lam前面不选,直接跳商城,在宝塔内点击软件商城,安Mysql5.7,安java项目管理器,安Ngnix最新版,安Redis
|
16天前
|
存储 消息中间件 缓存
apt安装Redis 7
【7月更文挑战第2天】
|
21天前
|
存储 NoSQL 关系型数据库
Redis系列学习文章分享---第一篇(Redis快速入门之初始Redis--NoSql+安装redis+客户端+常用命令)
Redis系列学习文章分享---第一篇(Redis快速入门之初始Redis--NoSql+安装redis+客户端+常用命令)
51 1