目次
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 搭載アプリ

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

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

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Windows 11 10.0.22000.100 のインストール時の 0x80242008 エラーの解決策 Windows 11 10.0.22000.100 のインストール時の 0x80242008 エラーの解決策 May 08, 2024 pm 03:50 PM

1. [スタート]メニューを起動し、[cmd]と入力し、[コマンドプロンプト]を右クリックし、[管理者として実行]を選択します。 2. 次のコマンドを順番に入力します (注意してコピーして貼り付けてください): SCconfigwuauservstart=auto、Enter キーを押す SCconfigbitsstart=auto、Enter キーを押す SCconfigcryptsvcstart=auto、Enter キーを押す SCconfigtrustedinstallerstart=auto、Enter キーを押す SCconfigwuauservtype=share、Enter キーを押す netstopwuauserv 、enter netstopcryptS を押す

PHP 開発におけるキャッシュ メカニズムとアプリケーションの実践 PHP 開発におけるキャッシュ メカニズムとアプリケーションの実践 May 09, 2024 pm 01:30 PM

PHP 開発では、キャッシュ メカニズムにより、頻繁にアクセスされるデータがメモリまたはディスクに一時的に保存され、データベース アクセスの数が削減され、パフォーマンスが向上します。キャッシュの種類には主にメモリ、ファイル、データベース キャッシュが含まれます。キャッシュは、組み込み関数またはサードパーティのライブラリ (cache_get() や Memcache など) を使用して PHP に実装できます。一般的な実用的なアプリケーションには、データベース クエリ結果をキャッシュしてクエリ パフォーマンスを最適化したり、ページ出力をキャッシュしてレンダリングを高速化したりすることが含まれます。キャッシュ メカニズムにより、Web サイトの応答速度が効果的に向上し、ユーザー エクスペリエンスが向上し、サーバーの負荷が軽減されます。

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 に設定し、システムを再起動してから、すべてを 0409 に変更します) この時点でシステムを再起動する必要があります。

Javaのデータ構造とアルゴリズム: 詳細な説明 Javaのデータ構造とアルゴリズム: 詳細な説明 May 08, 2024 pm 10:12 PM

データ構造とアルゴリズムは Java 開発の基礎です。この記事では、Java の主要なデータ構造 (配列、リンク リスト、ツリーなど) とアルゴリズム (並べ替え、検索、グラフ アルゴリズムなど) について詳しく説明します。これらの構造は、スコアを保存するための配列、買い物リストを管理するためのリンク リスト、再帰を実装するためのスタック、スレッドを同期するためのキュー、高速検索と認証のためのツリーとハッシュ テーブルの使用など、実際の例を通じて説明されています。これらの概念を理解すると、効率的で保守しやすい Java コードを作成できるようになります。

PHP データ構造: AVL ツリーのバランス、効率的で秩序あるデータ構造の維持 PHP データ構造: AVL ツリーのバランス、効率的で秩序あるデータ構造の維持 Jun 03, 2024 am 09:58 AM

AVL ツリーは、高速かつ効率的なデータ操作を保証するバランスのとれた二分探索ツリーです。バランスを達成するために、左回転と右回転の操作を実行し、バランスに反するサブツリーを調整します。 AVL ツリーは高さバランシングを利用して、ツリーの高さがノード数に対して常に小さくなるようにすることで、対数時間計算量 (O(logn)) の検索操作を実現し、大規模なデータ セットでもデータ構造の効率を維持します。

Win11でダウンロードしたアップデートファイルの探し方_Win11でダウンロードしたアップデートファイルの場所を共有する Win11でダウンロードしたアップデートファイルの探し方_Win11でダウンロードしたアップデートファイルの場所を共有する May 08, 2024 am 10:34 AM

1. まず、デスクトップ上の[このPC]アイコンをダブルクリックして開きます。 2. 次に、マウスの左ボタンをダブルクリックして [C ドライブ] に入ります。システム ファイルは通常、自動的に C ドライブに保存されます。 3. 次に、C ドライブで [windows] フォルダーを見つけ、ダブルクリックしてに入ります。 4. [windows]フォルダーに入ったら、[SoftwareDistribution]フォルダーを見つけます。 5. 入力後、win11 のダウンロード ファイルとアップデート ファイルがすべて含まれている [ダウンロード] フォルダーを見つけます。 6. これらのファイルを削除したい場合は、このフォルダー内で直接削除してください。

Nexo Exchangeはどこからですか? Nexo Exchangeはどこからですか? Mar 05, 2025 pm 05:09 PM

Nexo Exchange:Swiss Cryptocurrency Lending Platform詳細な分析Nexoは、暗号通貨貸付サービスを提供するプラットフォームであり、40を超える暗号資産、Fiat通貨、Stablecoinsの住宅ローンと融資をサポートしています。ヨーロッパとアメリカの市場を支配しており、プラットフォームの効率、セキュリティ、コンプライアンスの改善に取り組んでいます。多くの投資家は、Nexo Exchangeが登録されている場所を知りたいと思っています。答えはスイスです。 Nexoは2018年にSwiss Fintech Company Credissimoによって設立されました。 Nexo Exchangeの地理的位置と規制:Nexoは、有名な暗号通貨に優しい地域であるスイスのZugに本社を置いています。このプラットフォームは、さまざまな政府の監督と積極的に協力しており、米国金融犯罪法執行ネットワーク(FINCEN)およびカナダの財務に携わっています

Redis Exporter サービスを使用した Redis ドロップレットの監視 Redis Exporter サービスを使用した Redis ドロップレットの監視 Jan 06, 2025 am 10:19 AM

Redis データベースを効果的に監視することは、最適なパフォーマンスを維持し、潜在的なボトルネックを特定し、システム全体の信頼性を確保するために不可欠です。 Redis Exporter Service は、Prometheus を使用して Redis データベースを監視するように設計された堅牢なユーティリティです。 このチュートリアルでは、Redis Exporter Service の完全なセットアップと構成について説明し、監視ソリューションをシームレスに確立できるようにします。このチュートリアルに従うことで、Redis データベースのパフォーマンス メトリクスを効果的に監視するための完全に運用可能な監視セットアップを実現できます。

See all articles