探索数据结构之美——有序集合的内部机制

admin管理员组

文章数量:1440022

写在文章开头

在现代软件开发中，高效的数据结构和算法设计对于构建高性能系统至关重要。有序集合（Sorted Set）作为一种常用的数据结构，在许多应用场景中发挥着重要作用，例如缓存、索引、排名等。本文将深入探讨有序集合的内部机制，分析其源代码，并揭示其实现细节。

注意，本着对核心数据结构的剖析，本文有序集合的所有指令操作都是以字典+跳表这两个编码展开讨论，对于压缩列表的实现细节就不会涉及。

Hi，我是 sharkChili ，是个不断在硬核技术上作死的技术人，是 CSDN的博客专家 ，也是开源项目 Java Guide 的维护者之一，熟悉 Java 也会一点 Go ，偶尔也会在 C源码 边缘徘徊。写过很多有意思的技术博客，也还在研究并输出技术的路上，希望我的文章对你有帮助，非常欢迎你关注我的公众号： 写代码的SharkChili 。

同时也非常欢迎你star我的开源项目mini-redis:https://github/shark-ctrl/mini-redis

因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。

详解有序集合核心指令实现

跳表相关导读

本文着重于讲解有序集合内部核心实现，会涉及大量跳表的知识点，需要了解的读者建议阅读一下笔者下面这篇关于跳表设计与实现的文章：

高效索引的秘密：redis跳表设计与实现
:https://mp.weixin.qq/s/7iMwsunZC_UyBBrLTvx8OA

元素添加指令zadd

有序集合添加指令就是zadd，它支持添加一个或者多个指令，对应的操作示例如下，可以看到操作成功之后就会返回添加的元素数：

redis> ZADD myzset 1 "one"
(integer) 1
redis> ZADD myzset 1 "uno"
(integer) 1
redis> ZADD myzset 2 "two" 3 "three"
(integer) 2

对应的指令函数源码的实现是zaddCommand，该函数大体按照如下步骤进行：

1. 检查元素是否能被2整除来校验参数个数是否正确。
2. 检查有序集合的key是否存在且类型确实是有序集合。
3. 逐个遍历元素及其score查看该元素是否存在，如果不存在则先插入操有序集合底层的跳表中来维护元素之间的先后顺序。确保这步操作成功后再将元素指针添加到有序集合的字典中，保证单元素检索的效率。
4. 如果元素已存在，则会将该元素从跳表中删除，保证关于这个元素的索引都清理干净后在进行插入，以保证跳表的正确性，因为元素已经在有序集合字典中存在了，所以更新操作就不会操作字典了。

对应我们也给出操作的源码细节，读者可以参照笔者的上述的讲解了解一下源码的细节：

//调用zaddGenericCommand并传入0，意为告知zaddGenericCommand要返回本次操作的添加数(不包括更新)
void zaddCommand(redisClient *c) {
   
    zaddGenericCommand(c,0);
}

/* This generic command implements both ZADD and ZINCRBY. */
void zaddGenericCommand(redisClient *c, int incr) {
   
	//.......
    //拿到有序集合里面element和score有几对
    int j, elements = (c->argc-2)/2;
    int added = 0, updated = 0;
    //检查参数是否是基数个，如果是则报错
    if (c->argc % 2) {
   
        addReply(c,shared.syntaxerr);
        return;
    }

    //创建score数组
    scores = zmalloc(sizeof(double)*elements);
    //遍历score转为double类型，将转换后的结果存到scores数组中,后续元素的score都依次按照顺序从数组中获取
    for (j = 0; j < elements; j++) {
   
        if (getDoubleFromObjectOrReply(c,c->argv[2+j*2],&scores[j],NULL)
            != REDIS_OK) goto cleanup;
    }

 
    //查看这个有序集合是否在redis中存在
    zobj = lookupKeyWrite(c->db,key);
    //如果不存在则进行初始化,然后添加到redis数据库中
    if (zobj == NULL) {
   
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[3]->ptr))
        {
   
        	//创建有序集合对象
            zobj = createZsetObject();
        } else {
   
         	//......
        }
        //添加到内存数据库中
        dbAdd(c->db,key,zobj);
    } 
    //遍历传入的每一个元素
    for (j = 0; j < elements; j++) {
   
        //拿到元素的score
        score = scores[j];

        if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
   
           //......
        } else if (

本文标签： 数据结构之美机制