GoSuda

Bitmap dynamique

By snowmerak
views ...

Qu'est-ce qu'un Bitmap ?

Ici, le bitmap est un type d'index. Si vous êtes venu en pensant aux graphiques, vous pouvez revenir en arrière.

Concept de base

Un bitmap est une forme de technique d'indexation de base de données. Il représente les valeurs d'une colonne spécifique sous la forme d'un tableau ou d'un vecteur de bits, où chaque bit indique la présence ou l'absence d'une valeur spécifique pour cette colonne. Par conséquent, la forme la plus élémentaire consiste à attribuer un index de bits à chaque ligne et à représenter la présence par 0 et l'absence par 1.

Par exemple, supposons que nous ayons une table avec une colonne de genre. Supposons que cette table contienne 5 lignes 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

À quoi cela sert-il réellement ?

Chacun pensera que cela ne sert pas seulement à 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 lignes. Et supposons que nous exécutons la requête suivante.

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

Cette requête recherche les lignes où les colonnes active et sex sont toutes deux à TRUE. L'opération bitwise AND pourrait alors être utilisée pour trouver rapidement les lignes satisfaisant la condition où les deux colonnes sont à TRUE.

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

Alors, en effectuant une opération bitwise AND sur les deux index bitmap, nous pouvons rapidement trouver les lignes où les deux colonnes sont à TRUE. Puisqu'il s'agit d'une simple opération bitwise, les résultats peuvent être obtenus beaucoup plus rapidement que par d'autres types de balayage d'index.

Compromis

Les index bitmap peuvent être très efficaces, mais ils présentent 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 faibles cardinalités (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.

L'utilisation d'un index bitmap sur une colonne à cardinalité élevée peut nécessiter beaucoup d'espace de stockage, car un bitmap distinct doit être créé pour chaque valeur unique. Par exemple, si une colonne contient 1 000 000 de valeurs uniques, 1 000 000 de bitmaps devraient être créés, ce qui peut être très inefficace.

Donc nous

Nous pouvons utiliser un Roaring Bitmap comme alternative aux bitmaps à cardinalité élevée. Le Roaring Bitmap possède diverses caractéristiques, mais sa philosophie et sa caractéristique fondamentales les plus importantes sont de « maximiser à la fois le taux de compression et la vitesse d'opération en sélectionnant dynamiquement la méthode de stockage la plus appropriée en fonction de la densité des données ».

Concept de base du Roaring Bitmap

Indexation à deux niveaux

Pour stocker un entier, le Roaring Bitmap passe d'abord par les deux étapes suivantes. On parle d'indexation à deux niveaux, mais on peut simplement le 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. Cela devient l'index du tableau externe d'un tableau bidimensionnel d'une longueur totale de 65536. Ce tableau stocke l'adresse du conteneur qui sera décrit ci-dessous.
  • Extraction des 16 bits inférieurs : Les 16 bits inférieurs de l'entier sont extraits et utilisés comme position au sein du conteneur.

Conteneur

Ce conteneur correspond 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 qu'il contient. Le Roaring Bitmap prend en charge les 3 types de conteneurs suivants.

  • 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 simplement implémenté comme un tableau d'entiers triés. Les éléments peuvent être trouvés par recherche binaire.
  • 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 si l'entier à cette position existe.
  • 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 contient toutes les valeurs ? Cela signifie simplement qu'il contient tout du début à la fin, donc il suffit de stocker un seul (0, 65536).

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

Fonctionnalités de Roaring Bitmap

Fonctions de base

Le Roaring Bitmap fournit les fonctions de base suivantes.

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

Opérations sur les ensembles

Le Roaring Bitmap prend également en charge les opérations sur les ensembles 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 un seul des deux bitmaps.

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 utilisé pour exploiter facilement le 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)     // Initialise avec 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialise 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	// Comme les opérations bitmap modifient l'original, utilisez une copie.
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 fonctions principales qui n'apparaissent pas dans l'exemple de code ci-dessus sont les suivantes :

  • Contains(x uint32) bool : Vérifie si une valeur spécifique existe 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 de bytes.
  • FromBytes(data []byte) error : Restaure le bitmap à partir d'un slice de bytes.
  • Clone() *Bitmap : Crée une copie du bitmap.
  • Clear() : Initialise le bitmap.
  • NextValue(x uint32) int64 : Renvoie l'élément suivant supérieur ou égal à x.
  • PreviousValue(x uint32) int64 : Renvoie l'élément précédent inférieur à x.
  • Maximum() uint32 : Renvoie le plus grand élément du bitmap.
  • Minimum() uint32 : Renvoie le plus petit élément du bitmap.

De telles fonctionnalités existent. Pour plus de détails, veuillez consulter la documentation officielle.

À noter que le package roaring inclut des packages qui prennent en charge uint64 en plus de uint32. Ils fournissent une interface presque identique, ce qui permet de les remplacer directement.

 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)     // Initialise avec 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialise 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	// Comme les opérations bitmap modifient l'original, utilisez une copie.
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 langage Go, l'utilisation du package github.com/RoaringBitmap/roaring permet d'exploiter facilement toutes les fonctionnalités du Roaring Bitmap. 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 journaux et les calculs statistiques pour une gestion efficace des données.

Le Roaring Bitmap offre des performances élevées, en particulier avec de grands ensembles de données, et peut être utilisé de manière bénéfique dans diverses applications. Combiné à la syntaxe concise et efficace du langage Go, le Roaring Bitmap offre un outil puissant aux développeurs. On s'attend à ce que le développement du Roaring Bitmap se poursuive, apportant davantage de fonctionnalités et d'optimisations.

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