Table des matières
intset 结构体
intset 搜索
intset 插入
Maison base de données tutoriel mysql 深入剖析 redis 数据结构 intset

深入剖析 redis 数据结构 intset

Jun 07, 2016 pm 04:37 PM
redis 剖析 数据结构 aller en profondeur

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;
Copier après la connexion

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;
}
Copier après la connexion

捣乱 2014-7-3

http://daoluan.net

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Meilleurs paramètres graphiques
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Comment réparer l'audio si vous n'entendez personne
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Comment déverrouiller tout dans Myrise
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Comment construire le mode Cluster Redis Comment construire le mode Cluster Redis Apr 10, 2025 pm 10:15 PM

Le mode Redis Cluster déploie les instances Redis sur plusieurs serveurs grâce à la rupture, à l'amélioration de l'évolutivité et de la disponibilité. Les étapes de construction sont les suivantes: Créez des instances de redis étranges avec différents ports; Créer 3 instances Sentinel, Moniteur Redis Instances et basculement; Configurer les fichiers de configuration Sentinel, ajouter des informations d'instance Redis de surveillance et des paramètres de basculement; Configurer les fichiers de configuration d'instance Redis, activer le mode de cluster et spécifier le chemin du fichier d'informations de cluster; Créer un fichier nœuds.conf, contenant des informations de chaque instance redis; Démarrez le cluster, exécutez la commande CREATE pour créer un cluster et spécifiez le nombre de répliques; Connectez-vous au cluster pour exécuter la commande d'informations de cluster pour vérifier l'état du cluster; faire

Comment la clé est-elle unique pour Redis Query Comment la clé est-elle unique pour Redis Query Apr 10, 2025 pm 07:03 PM

Redis utilise cinq stratégies pour assurer le caractère unique des clés: 1. Séparation des espaces de noms; 2. Structure de données de hachage; 3. Définir la structure des données; 4. Caractères spéciaux des touches de chaîne; 5. Vérification du script LUA. Le choix de stratégies spécifiques dépend de l'organisation des données, des performances et des exigences d'évolutivité.

Comment implémenter le redis sous-jacent Comment implémenter le redis sous-jacent Apr 10, 2025 pm 07:21 PM

Redis utilise des tables de hachage pour stocker les données et prend en charge les structures de données telles que les chaînes, les listes, les tables de hachage, les collections et les collections ordonnées. Redis persiste les données via des instantanés (RDB) et ajoutez les mécanismes d'écriture uniquement (AOF). Redis utilise la réplication maître-esclave pour améliorer la disponibilité des données. Redis utilise une boucle d'événement unique pour gérer les connexions et les commandes pour assurer l'atomicité et la cohérence des données. Redis définit le temps d'expiration de la clé et utilise le mécanisme de suppression paresseux pour supprimer la clé d'expiration.

Comment le cluster redis est-il implémenté Comment le cluster redis est-il implémenté Apr 10, 2025 pm 05:27 PM

Le cluster Redis est un modèle de déploiement distribué qui permet une expansion horizontale des instances Redis, et est implémentée via la communication inter-nœuds, l'espace clé de la division des emplacements de hachage, l'élection du nœud, la réplication maître-esclave et la redirection de commande: communication inter-nœuds: la communication du réseau virtuel est réalisée via le bus de cluster. Slot de hachage: divise l'espace clé en emplacements de hachage pour déterminer le nœud responsable de la clé. Élection du nœud: au moins trois nœuds maîtres sont nécessaires et un seul nœud maître actif est assuré par le mécanisme électoral. Réplication maître-esclave: le nœud maître est responsable de la rédaction de demandes, et le nœud esclave est responsable des demandes de lecture et de la réplication des données. Redirection de commande: le client se connecte au nœud responsable de la clé et le nœud redirige les demandes incorrectes. Dépannage: détection des défauts, marquer la ligne et re

Comment afficher le numéro de version de redis Comment afficher le numéro de version de redis Apr 10, 2025 pm 05:57 PM

Pour afficher le numéro de version redis, vous pouvez utiliser les trois méthodes suivantes: (1) Entrez la commande Info, (2) Démarrez le serveur avec l'option - Version et (3) afficher le fichier de configuration.

Comment afficher toutes les clés dans Redis Comment afficher toutes les clés dans Redis Apr 10, 2025 pm 07:15 PM

Pour afficher toutes les touches dans Redis, il existe trois façons: utilisez la commande Keys pour retourner toutes les clés qui correspondent au modèle spécifié; Utilisez la commande SCAN pour itérer les touches et renvoyez un ensemble de clés; Utilisez la commande info pour obtenir le nombre total de clés.

Comment utiliser redis zset Comment utiliser redis zset Apr 10, 2025 pm 07:27 PM

Les ensembles commandés par Redis (ZSETS) sont utilisés pour stocker des éléments commandés et trier par des scores associés. Les étapes à utiliser ZSET incluent: 1. Créer un ZSET; 2. Ajouter un membre; 3. Obtenez un score de membre; 4. Obtenez un classement; 5. Obtenez un membre dans la gamme de classement; 6. Supprimer un membre; 7. Obtenez le nombre d'éléments; 8. Obtenez le nombre de membres dans la plage de score.

Comment utiliser la ligne de commande redis Comment utiliser la ligne de commande redis Apr 10, 2025 pm 10:18 PM

Utilisez l'outil de ligne de commande redis (Redis-CLI) pour gérer et utiliser Redis via les étapes suivantes: Connectez-vous au serveur, spécifiez l'adresse et le port. Envoyez des commandes au serveur à l'aide du nom et des paramètres de commande. Utilisez la commande d'aide pour afficher les informations d'aide pour une commande spécifique. Utilisez la commande QUIT pour quitter l'outil de ligne de commande.

See all articles