深入剖析 redis 数据结构 intset
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
原文地址:深入剖析 redis 数据结构 intset, 感谢原作者分享。
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前
By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
擊敗分裂小說需要多長時間?
3 週前
By DDD
R.E.P.O.保存文件位置:在哪里以及如何保護它?
3 週前
By DDD

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

Windows11安裝10.0.22000.100跳出0x80242008錯誤解決方法

Win11英文21996怎麼升級到簡體中文22000_Win11英文21996升級到簡體中文22000的方法
