目录
intset 结构体
intset 搜索
intset 插入
首页 数据库 mysql教程 深入剖析 redis 数据结构 intset

深入剖析 redis 数据结构 intset

Jun 07, 2016 pm 04:37 PM
redis 剖析 数据结构 深入

intset 和 dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,会使用前者;否则使用后者。 特别的 ,当遇到添加数据为字符串,即不能表示为整数时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。 本片展开的是 ints

intset 和 dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,会使用前者;否则使用后者。特别的,当遇到添加数据为字符串,即不能表示为整数时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。

本片展开的是 intset,dict 的文章可以参看之前写的《深入剖析 redis 数据结构 dict》。

intset 结构体

intset 底层本质是一个有序的、不重复的、整型的数组,支持不同类型整数。

typedef struct intset {
    // 每个整数的类型
    uint32_t encoding;
    // intset 长度
    uint32_t length;
    // 整数数组
    int8_t contents[];
} intset;
登录后复制

encoding 能下面的三个值:分别是 16,32 和 64位整数:

/* Note that these encodings are ordered, so:
* INTSET_ENC_INT16 
<h3 id="intset-搜索">intset 搜索</h3>
<p>intset 是有序的整数数组,可以用二分搜索查找。</p>
<pre class="brush:php;toolbar:false">static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;
    /* The value can never be found when the set is empty */
    // 集合为空
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        // value 比最大元素还大
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        // value 比最小元素还小
        } else if (value = min) {
        mid = (min+max)/2;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value 
<h3 id="intset-插入">intset 插入</h3>
<p>intset 实现中比较远有意思的是插入算法部分。</p>
<pre class="brush:php;toolbar:false">/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;
    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if  intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    // 正常,分配内存,插入
    } else {
        // intset 内部不允许重复
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        // realloc
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 迁移内存,腾出空间给新的数据。intsetMoveTail() 完成内存迁移工作
        if (pos length)) intsetMoveTail(is,pos,pos+1);
    }
    // 在腾出的空间中设置新的数据
    _intsetSet(is,pos,value);
    // 更新 intset size
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
// 升级整数类型,譬如从 short->int。当插入数据的内存占用比原有数据大
// 的时候,会被调用
/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    // value0 尾插
    int prepend = value encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    // 逆向处理,防止数据被覆盖,一般的插入排序步骤
    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    // valuelength),value);
    // 更新 set size
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
登录后复制

捣乱 2014-7-3

http://daoluan.net

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Windows11安装10.0.22000.100跳出0x80242008错误解决办法 Windows11安装10.0.22000.100跳出0x80242008错误解决办法 May 08, 2024 pm 03:50 PM

1、启动【开始】菜单,输入【cmd】,右键点击【命令提示符】,选择以【管理员身份】运行。2、依次输入下面命令(可小心复制贴上):SCconfigwuauservstart=auto,按回车SCconfigbitsstart=auto,按回车SCconfigcryptsvcstart=auto,按回车SCconfigtrustedinstallerstart=auto,按回车SCconfigwuauservtype=share,按回车netstopwuauserv,按回车netstopcryptS

Golang API缓存策略与优化 Golang API缓存策略与优化 May 07, 2024 pm 02:12 PM

GolangAPI中的缓存策略可提升性能和减轻服务器负载,常用策略有:LRU、LFU、FIFO和TTL。优化技巧包括:选择合适的缓存存储、分级缓存、失效管理以及进行监控和调整。实操案例中,使用LRU缓存优化从数据库获取用户信息的API,可从缓存中快速检索数据,否则从数据库中获取后再更新缓存。

PHP开发中的缓存机制与应用实战 PHP开发中的缓存机制与应用实战 May 09, 2024 pm 01:30 PM

在PHP开发中,缓存机制通过将经常访问的数据临时存储在内存或磁盘中来提升性能,从而减少数据库访问次数。缓存类型主要包括内存、文件和数据库缓存。PHP中可以使用内置函数或第三方库实现缓存,如cache_get()和Memcache。常见的实战应用包括缓存数据库查询结果以优化查询性能,以及缓存页面输出以加快渲染速度。缓存机制有效改善网站响应速度,提升用户体验并降低服务器负载。

Win11英文21996怎么升级到简体中文22000_Win11英文21996升级到简体中文22000的方法 Win11英文21996怎么升级到简体中文22000_Win11英文21996升级到简体中文22000的方法 May 08, 2024 pm 05:10 PM

首先你需要将系统语言设置为简体中文显示并重启。当然,之前已经改为简体中文显示语言的直接跳过这一步即可。下面开始操作注册表,regedit.exe,左侧导航栏或上方地址栏直接定位到HKEY_LOCAL_MACHINESYSTEMCurrentControlSetControlNlsLanguage,然后将其中的InstallLanguage键值、Default键值全部修改为0804(如果想改为英文的en-us,需要先将系统显示语言设置为en-us,重启系统再全部修改为0409)进行到这里必须重启系

Java数据结构与算法:深入详解 Java数据结构与算法:深入详解 May 08, 2024 pm 10:12 PM

数据结构和算法是Java开发的基础,本文深入探讨Java中的关键数据结构(如数组、链表、树等)和算法(如排序、搜索、图算法等)。这些结构通过实战案例进行说明,包括使用数组存储分数、使用链表管理购物清单、使用栈实现递归、使用队列同步线程以及使用树和哈希表进行快速搜索和身份验证等。理解这些概念可以编写高效且可维护的Java代码。

Win11下载的更新文件怎么找_Win11下载的更新文件位置分享 Win11下载的更新文件怎么找_Win11下载的更新文件位置分享 May 08, 2024 am 10:34 AM

1、首先双击打开桌面上的【此电脑】图标。2、接着双击鼠标左键进入【c盘】,系统文件一般都会自动存放在c盘。3、然后再c盘中找到【windows】文件夹,同样双击进入。4、进入【windows】文件夹后,找到其中的【SoftwareDistribution】文件夹。5、进入之后再找到【download】文件夹,里面存放的就是所有的win11下载更新文件了。6、如果我们想要删除这些文件的话,直接在这个文件夹中将他们删除就可以了。

PHP数据结构:AVL树的平衡之道,维持高效有序的数据结构 PHP数据结构:AVL树的平衡之道,维持高效有序的数据结构 Jun 03, 2024 am 09:58 AM

AVL树是一种平衡二叉搜索树,确保快速高效的数据操作。为了实现平衡,它执行左旋和右旋操作,调整违反平衡的子树。AVL树利用高度平衡,确保树的高度相对于节点数始终较小,从而实现对数时间复杂度(O(logn))的查找操作,即使在大型数据集上也能保持数据结构的效率。

Nexo交易所是哪个国家的?在哪里?Nexo交易所全面介绍 Nexo交易所是哪个国家的?在哪里?Nexo交易所全面介绍 Mar 05, 2025 pm 05:09 PM

Nexo交易所:瑞士加密货币借贷平台深度解析Nexo是一个提供加密货币借贷服务的平台,支持超过40种加密资产、法币和稳定币的抵押和借贷。它在欧洲和美国市场占据主导地位,并致力于提升平台的效率、安全性和合规性。许多投资者都想知道Nexo交易所的注册地,答案是:瑞士。Nexo由瑞士金融科技公司Credissimo于2018年创立。Nexo交易所的地理位置及监管:Nexo总部位于瑞士楚格,这是一个知名的加密货币友好型地区。平台积极配合各国政府监管,已在美国金融犯罪执法网络(FinCEN)、加拿大金融

See all articles