検索

深入剖析 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 までご連絡ください。
MySQLのライセンスは、他のデータベースシステムと比較してどうですか?MySQLのライセンスは、他のデータベースシステムと比較してどうですか?Apr 25, 2025 am 12:26 AM

MySQLはGPLライセンスを使用します。 1)GPLライセンスにより、MySQLの無料使用、変更、分布が可能になりますが、変更された分布はGPLに準拠する必要があります。 2)商業ライセンスは、公的な変更を回避でき、機密性を必要とする商用アプリケーションに適しています。

MyisamよりもInnodbを選びますか?MyisamよりもInnodbを選びますか?Apr 25, 2025 am 12:22 AM

Myisamの代わりにInnoDBを選択する場合の状況には、次のものが含まれます。1)トランザクションサポート、2)高い並行性環境、3)高いデータの一貫性。逆に、Myisamを選択する際の状況には、1)主に操作を読む、2)トランザクションサポートは必要ありません。 INNODBは、eコマースプラットフォームなどの高いデータの一貫性とトランザクション処理を必要とするアプリケーションに適していますが、Myisamはブログシステムなどの読み取り集約型およびトランザクションのないアプリケーションに適しています。

MySQLの外国キーの目的を説明してください。MySQLの外国キーの目的を説明してください。Apr 25, 2025 am 12:17 AM

MySQLでは、外部キーの機能は、テーブル間の関係を確立し、データの一貫性と整合性を確保することです。外部キーは、参照整合性チェックとカスケード操作を通じてデータの有効性を維持します。パフォーマンスの最適化に注意し、それらを使用するときに一般的なエラーを避けてください。

MySQLのインデックスのさまざまなタイプは何ですか?MySQLのインデックスのさまざまなタイプは何ですか?Apr 25, 2025 am 12:12 AM

MySQLには、B-Treeインデックス、ハッシュインデックス、フルテキストインデックス、空間インデックスの4つのメインインデックスタイプがあります。 1.B-Treeインデックスは、範囲クエリ、ソート、グループ化に適しており、従業員テーブルの名前列の作成に適しています。 2。HASHインデックスは、同等のクエリに適しており、メモリストレージエンジンのHASH_TABLEテーブルのID列の作成に適しています。 3。フルテキストインデックスは、記事テーブルのコンテンツ列の作成に適したテキスト検索に使用されます。 4.空間インデックスは、地理空間クエリに使用され、場所テーブルのGEOM列での作成に適しています。

MySQLでインデックスをどのように作成しますか?MySQLでインデックスをどのように作成しますか?Apr 25, 2025 am 12:06 AM

tocreateanindexinmysql、usethecreateindexstatement.1)forasinglecolumn、 "createdexidx_lastnameonemployees(lastname);" 2)foracompositeindexを使用して、 "createindexidx_nameonemployees(lastname、firstname);" 3); "3)、" 3)を使用します

MySQLはSQLiteとどのように違いますか?MySQLはSQLiteとどのように違いますか?Apr 24, 2025 am 12:12 AM

MySQLとSQLiteの主な違いは、設計コンセプトと使用法のシナリオです。1。MySQLは、大規模なアプリケーションとエンタープライズレベルのソリューションに適しており、高性能と高い並行性をサポートしています。 2。SQLiteは、モバイルアプリケーションとデスクトップソフトウェアに適しており、軽量で埋め込みやすいです。

MySQLのインデックスとは何ですか?また、パフォーマンスをどのように改善しますか?MySQLのインデックスとは何ですか?また、パフォーマンスをどのように改善しますか?Apr 24, 2025 am 12:09 AM

MySQLのインデックスは、データの取得をスピードアップするために使用されるデータベーステーブル内の1つ以上の列の順序付けられた構造です。 1)インデックスは、スキャンされたデータの量を減らすことにより、クエリ速度を改善します。 2)B-Tree Indexは、バランスの取れたツリー構造を使用します。これは、範囲クエリとソートに適しています。 3)CreateIndexステートメントを使用して、createIndexidx_customer_idonorders(customer_id)などのインデックスを作成します。 4)Composite Indexesは、createIndexIDX_CUSTOMER_ORDERONORDERS(Customer_Id、Order_date)などのマルチコラムクエリを最適化できます。 5)説明を使用してクエリ計画を分析し、回避します

データの一貫性を確保するために、MySQLでトランザクションを使用する方法を説明します。データの一貫性を確保するために、MySQLでトランザクションを使用する方法を説明します。Apr 24, 2025 am 12:09 AM

MySQLでトランザクションを使用すると、データの一貫性が保証されます。 1)StartTransactionを介してトランザクションを開始し、SQL操作を実行して、コミットまたはロールバックで送信します。 2)SavePointを使用してSave Pointを設定して、部分的なロールバックを許可します。 3)パフォーマンスの最適化の提案には、トランザクション時間の短縮、大規模なクエリの回避、分離レベルの使用が合理的に含まれます。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

PhpStorm Mac バージョン

PhpStorm Mac バージョン

最新(2018.2.1)のプロフェッショナル向けPHP統合開発ツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。