GoSuda

Bitmap animée

By snowmerak
views ...

Qu'est-ce qu'un Bitmap ?

Ici, un bitmap est un type d'index. Si vous pensiez aux graphiques, vous pouvez revenir en arrière.

Concept de base

Le bitmap est une forme de technique d'indexation dans les bases de données. Il représente les valeurs d'une colonne spécifique sous la forme d'un tableau de bits ou d'un élément ou d'une forme d'un vecteur, où chaque bit indique la présence ou l'absence d'une valeur spécifique dans cette colonne. Ainsi, la forme la plus élémentaire consiste à attribuer un index de bit à chaque row et à représenter la présence ou l'absence par 0 et 1.

Par exemple, considérons une table avec une colonne de genre. Supposons que cette table contienne 5 rows et que les valeurs de la colonne de genre soient les suivantes :

  1. Homme
  2. Femme
  3. Homme
  4. Femme
  5. Autre

Dans ce cas, l'index bitmap pour la colonne de genre peut être représenté comme suit :

  • Homme : 10100
  • Femme : 01010
  • Autre : 00001

Où est-il réellement utilisé ?

Ainsi, tout le monde pensera que ce n'est pas simplement pour représenter cela. Pour utiliser correctement l'index bitmap, considérons le cas suivant.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Supposons que cette table contienne 1 000 000 de rows. Et supposons que nous exécutons la requête suivante.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Cette requête recherche les rows où les colonnes active et sex sont toutes deux TRUE. Il serait alors possible d'utiliser l'opération bitwise AND pour trouver rapidement les rows qui satisfont la condition où les deux colonnes sont TRUE.

  • Supposons que l'index bitmap pour la colonne active soit 1100110011... (tableau de 1 000 000 bits) pré-indexé, et
  • Supposons que l'index bitmap pour la colonne sex soit 1010101010... (tableau de 1 000 000 bits) pré-indexé.

Ensuite, en effectuant une opération bitwise AND sur les deux index bitmap, nous pouvons trouver rapidement les rows où les deux colonnes sont TRUE. Comme il s'agit d'une simple opération bitwise, les résultats peuvent être obtenus beaucoup plus rapidement que les autres balayages d'index.

Compromis

Les index bitmap peuvent être très efficaces, mais ils comportent quelques compromis. Bien qu'il existe de nombreux autres inconvénients, nous n'en aborderons qu'un seul pour l'instant.

Les index bitmap sont plus adaptés aux cardinalités faibles (c'est-à-dire lorsque le nombre de valeurs possibles dans une colonne est faible). L'utilisation d'un index bitmap sur une colonne à cardinalité élevée peut entraîner un bitmap très volumineux.

Si un index bitmap est utilisé sur une colonne à cardinalité élevée, un bitmap distinct doit être créé pour chaque valeur unique, ce qui peut nécessiter un espace de stockage important. Par exemple, si une colonne contient 1 000 000 de valeurs uniques, il serait nécessaire de créer 1 000 000 de bitmaps, ce qui peut être très inefficace.

Et donc nous

Pour remplacer les bitmaps résultant d'une cardinalité élevée, nous pouvons utiliser ce que l'on appelle le Roaring Bitmap. Le Roaring Bitmap présente diverses caractéristiques, mais sa philosophie et sa caractéristique fondamentales les plus importantes sont de sélectionner dynamiquement le mode de stockage le plus approprié en fonction de la densité des données, maximisant ainsi à la fois le taux de compression et la vitesse de traitement.

Concepts de base du Roaring Bitmap

Indexation en 2 étapes

Pour stocker un entier, le Roaring Bitmap passe d'abord par les deux étapes suivantes. Bien qu'il s'agisse d'une indexation en 2 étapes, il suffit de la considérer comme un tableau bidimensionnel.

  • Extraction des 16 bits supérieurs : Les 16 bits supérieurs de l'entier sont extraits et utilisés comme index. Il s'agit de l'index du tableau externe parmi un tableau bidimensionnel d'une longueur totale de 65536. Ce tableau stocke l'adresse du conteneur qui sera décrit plus loin.
  • Extraction des 16 bits inférieurs : Les 16 bits inférieurs de l'entier sont extraits et utilisés comme position dans le conteneur.

Conteneurs

Ces conteneurs correspondent au tableau interne du tableau bidimensionnel, comme nous l'avons comparé précédemment. Cependant, contrairement aux 16 bits supérieurs, la structure interne de ce conteneur varie en fonction de la quantité de données internes. Le Roaring Bitmap prend en charge les 3 types de conteneurs suivants.

  • Conteneur de tableau (Array Container) : Ce conteneur est utilisé lorsque peu de données sont stockées à l'intérieur. Plus précisément, il est utilisé pour stocker 4096 éléments ou moins. Ce conteneur est implémenté simplement comme un tableau d'entiers triés. Les éléments peuvent être trouvés par recherche binaire.
  • Conteneur de bitmap (Bitmap Container) : Ce conteneur est utilisé lorsque de nombreuses données sont stockées à l'intérieur. Plus précisément, il est utilisé pour stocker plus de 4096 éléments. Ce conteneur est implémenté comme un bitmap de 65536 bits (8192 octets). Chaque bit indique la présence ou l'absence de l'entier à cette position.
  • Conteneur d'exécution (Run Container) : Ce conteneur est utilisé pour stocker des plages d'entiers consécutifs. Par exemple, il est efficace pour stocker des entiers consécutifs tels que 1, 2, 3, 4, 5. Ce conteneur est implémenté comme une liste de paires (valeur de début, longueur). S'il y en a beaucoup ? Cela signifie simplement qu'il y en a du début à la fin, donc il suffit de stocker (0, 65536).

Cette approche permet au Roaring Bitmap d'utiliser la mémoire de manière très efficace et d'offrir des performances optimales pour diverses densités de données.

Fonctionnalités du Roaring Bitmap

Fonctionnalités de base

Le Roaring Bitmap offre les fonctionnalités de base suivantes.

  • Insertion : Ajoute un nouvel entier au bitmap. Au cours de ce processus, un conteneur approprié peut être sélectionné ou un conteneur peut être converti si nécessaire.
  • Suppression : Supprime un entier existant du bitmap. Au cours de ce processus, un traitement approprié est effectué en fonction de l'état du conteneur.
  • Recherche : Vérifie si un entier spécifique est présent dans le bitmap. Ce processus est effectué très rapidement.

Opérations d'ensemble

Le Roaring Bitmap prend également en charge les opérations d'ensemble suivantes.

  • Union : Crée un nouveau bitmap contenant tous les éléments des deux bitmaps.
  • Intersection : Crée un nouveau bitmap contenant uniquement les éléments présents dans les deux bitmaps.
  • Différence symétrique : Crée un nouveau bitmap contenant les éléments présents dans l'un des deux bitmaps seulement.

Ces opérations sont optimisées en fonction du type de conteneur du bitmap et sont effectuées très rapidement.

En langage Go

En langage Go, le package github.com/RoaringBitmap/roaring peut être facilement utilisé pour tirer parti du Roaring Bitmap. Ce package fournit toutes les fonctionnalités du Roaring Bitmap et est optimisé pour les caractéristiques du langage Go.

Installation

1go get github.com/RoaringBitmap/roaring/v2

Exemple d'utilisation

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Initialisé avec 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialisé avec 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Ajoute 5
14	b2.Add(10) // Ajoute 10
15
16	b2.Remove(12) // Supprime 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Les opérations bitmap modifient l'original, il faut donc utiliser un clone
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Les fonctionnalités principales non présentées dans l'exemple de code ci-dessus sont :

  • Contains(x uint32) bool : Vérifie si une valeur spécifique est présente dans le bitmap.
  • GetCardinality() uint64 : Renvoie le nombre d'éléments contenus dans le bitmap.
  • Rank(x uint32) uint64 : Renvoie le nombre d'éléments inférieurs ou égaux à une valeur spécifique.
  • ToBytes() ([]byte, error) : Sérialise le bitmap en un slice d'octets.
  • FromBytes(data []byte) error : Restaure le bitmap à partir d'un slice d'octets.
  • Clone() *Bitmap : Crée une copie du bitmap.
  • Clear() : Initialise le bitmap.
  • NextValue(x uint32) int64 : Renvoie la valeur suivante supérieure ou égale à x.
  • PreviousValue(x uint32) int64 : Renvoie la valeur précédente inférieure ou égale à x.
  • Maximum() uint32 : Renvoie l'élément le plus grand du bitmap.
  • Minimum() uint32 : Renvoie l'élément le plus petit du bitmap.

Ces fonctionnalités sont disponibles. Pour plus de détails, veuillez consulter la documentation officielle.

À noter que le package roaring inclut des packages prenant en charge uint64 en plus de uint32. Ils offrent des interfaces presque identiques et peuvent être utilisés de manière interchangeable.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Initialisé avec 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialisé avec 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Ajoute 5
14	b2.Add(10) // Ajoute 10
15
16	b2.Remove(12) // Supprime 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Les opérations bitmap modifient l'original, il faut donc utiliser un clone
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Conclusion

Le Roaring Bitmap est un outil puissant pour stocker et manipuler efficacement des ensembles d'entiers à cardinalité élevée. En utilisant le package github.com/RoaringBitmap/roaring en langage Go, toutes les fonctionnalités du Roaring Bitmap peuvent être facilement exploitées. Ce package maximise l'utilisation de la mémoire et les performances grâce à divers types de conteneurs et des opérations optimisées. Le Roaring Bitmap peut être utilisé dans divers domaines tels que l'indexation de bases de données, l'analyse de logs et les calculs statistiques pour réaliser un traitement efficace des données.

Le Roaring Bitmap est particulièrement performant sur de grands ensembles de données et peut être utile dans diverses applications. Associé à la syntaxe concise et efficace du langage Go, le Roaring Bitmap offre un outil puissant aux développeurs. On s'attend à ce que le Roaring Bitmap continue d'évoluer avec davantage de fonctionnalités et d'optimisations à l'avenir.

Pourquoi ai-je fait cela ? Pour l'indexation par tag et les opérations d'union rapides dans les bases de données de séries temporelles.