La colonne Base de données MySQL d'aujourd'hui présente la comparaison entre l'index MySQL et l'index ElasticSearch.

Avant-propos

Je maintiens la fonction de recherche du produit pendant cette période, et à chaque fois que je le vois dans la console de gestionelasticsearch Je suis très curieux de savoir comment il parvient à une efficacité de requête aussi efficace.

C'est encore plus rapide que l'interrogation par clé primaire en utilisant MySQL sur ma machine locale.

J'ai recherché des informations pertinentes :

Il y a Il existe de nombreuses réponses à ce type de questions sur Internet, et la signification générale est la suivante :

ES est un moteur de recherche en texte intégral basé sur Lucene Il segmentera les données et les enregistrera. index. Il est bon pour gérer une grande quantité de données d'index, relativement MySQL n'est pas bon pour mettre à jour fréquemment les données et les requêtes associées.

n'est pas très approfondi et n'analyse pas les principes pertinents mais comme les index sont mentionnés à plusieurs reprises, comparons les différences entre les deux du point de vue des index ;

Index MySQL

Commençons par MySQL Tout le monde doit être familier avec le mot index. Il existe généralement dans certains scénarios de requête et est un cas typique d'échange d'espace contre du temps.

以下内容以 Innodb 引擎为例。复制代码

Copier après la connexion

Structures de données communes

Supposons que nous concevons l'index de MySQL nous-mêmes, quelles sont les options ?

Table de hachage

La première chose à laquelle nous devrions penser est la table de hachage, qui est une structure de données très courante et efficace pour les requêtes et l'écriture. La correspondance à Java est HashMap.

Cette structure de données ne devrait pas avoir besoin de trop d'introduction, son efficacité d'écriture est très élevéeO(1), par exemple, nous voulons interroger id=3 Lors de la saisie de données, vous devez effectuer une opération de hachage sur 3, puis trouver la position correspondante dans ce tableau.

Mais si nous voulons interroger des données d'intervalle comme 1≤id≤6, la table de hachage ne peut pas bien la satisfaire puisqu'elle n'est pas ordonnée, nous devons parcourir toutes les données pour savoir quelles données appartiennent à cet intervalle.

Tableau ordonné

L'efficacité des requêtes du tableau ordonné est également très élevée, lorsque nous voulons interroger les données de id=4 , les données ne peuvent être localisées efficacement que par recherche binaireO(logn).

En même temps, puisque les données sont également ordonnées, elles peuvent naturellement prendre en charge les requêtes par intervalles ; il semble donc que les tableaux ordonnés conviennent à une utilisation comme index

Bien sûr que non, c'est le cas ? un autre problème majeur ; Supposons que nous insérons des données id=2.5, toutes les données suivantes doivent être déplacées d'un bit en même temps, et cette efficacité d'écriture deviendra très faible.

Arbre binaire équilibré

Étant donné que l'efficacité d'écriture des tableaux ordonnés n'est pas élevée, jetons un coup d'œil à ceux avec une efficacité d'écriture élevée. Il est facile de penser à des arbres binaires ici, nous utilisons des arbres équilibrés ; arbres binaires comme exemple :

En raison des caractéristiques d'un arbre binaire équilibré :

Le nœud gauche est plus petit que le nœud parent et le nœud droit est plus grand que le nœud parent.

Donc, en supposant que nous voulons interroger les données de id=11, il suffit d'interroger 10—>12—>11 pour finalement trouver les données. La complexité temporelle est de O(logn). c'est aussi O(logn).

mais ne prend toujours pas très bien en charge la recherche par intervalles. Supposons que nous voulions interroger les données de 5≤id≤20, nous devons d'abord interroger le sous-arbre gauche de 10 nœuds, puis interroger le sous-arbre droit de 10 nœuds pour enfin. interroger toutes les données.

En conséquence, cette efficacité des requêtes n’est pas élevée.

Sauter la table

Sauter la table n'est peut-être pas aussi courant que la table de hachage, le tableau ordonné et l'arbre binaire mentionnés ci-dessus, mais en fait, le Redis dans sort set est utilisé. mise en œuvre des tableaux.

Nous présentons ici brièvement les avantages de la structure de données implémentée par les tables de sauts.

Nous savons tous que même interroger une liste chaînée ordonnée n'est pas efficace, car elle ne peut pas utiliser d'indices de tableau pour la recherche binaire, la complexité temporelle est o(n)

Mais. nous pouvons également optimiser intelligemment la liste chaînée pour implémenter une recherche binaire déguisée, comme indiqué ci-dessous :

Nous pouvons rechercher les données de niveau le plus bas Extraire le index primaire et index secondaire En fonction de la quantité de données, nous pouvons extraire des index de niveau N.

Lorsque nous interrogeons, nous pouvons utiliser l'index ici pour implémenter une recherche binaire déguisée.

En supposant que vous souhaitiez interroger les données de id=13, il vous suffit de parcourir les quatre nœuds de 1—>7—>10—>13 pour interroger les données. Lorsque le nombre est plus grand, l'amélioration de l'efficacité sera plus évidente.

Dans le même temps, la requête par intervalles est également prise en charge. Elle est similaire à l'interrogation d'un seul nœud tout à l'heure. Il vous suffit d'interroger le nœud de départ, puis de parcourir en arrière (La liste chaînée est ordonnée. ) vers le nœud cible. L'ensemble de la plage de données est interrogée.

En même temps, puisque nous ne stockerons pas de données réelles dans l'index, mais seulement un pointeur, l'espace occupé est négligeable par rapport à la liste chaînée en bas où les données sont stockées.

Optimisation de l'arbre binaire équilibré

Mais en fait, le MySQL dans Innodb n'utilise pas de table de saut, mais utilise une structure de données appelée B+ arbre.

Cette structure de données n'est pas comme l'arbre binaire dont les professeurs d'université parlent souvent comme structure de données de base, car ce type de structure de données est évolutif à partir de la structure de données de base basée sur des scénarios de demande dans des projets réels.

Par exemple, l'arbre B+ ici peut être considéré comme évoluant à partir d'un arbre binaire équilibré.

Nous venons de mentionner que l'efficacité des requêtes d'intervalle des arbres binaires n'est pas élevée. Cela peut être optimisé :

Dans le. arbre binaire d'origine Après optimisation basée sur : Tous les nœuds non-feuilles ne stockent pas de données, mais servent uniquement d'index pour les nœuds feuilles, et toutes les données sont stockées dans les nœuds feuilles.

De cette façon, les données de tous les nœuds feuilles sont stockées dans l'ordre et les requêtes par intervalles peuvent être bien prises en charge.

Il vous suffit d'abord d'interroger la position du nœud de départ, puis de parcourir en arrière dans les nœuds feuilles.

Lorsque la quantité de données est énorme, il est évident que le fichier d'index ne peut pas être stocké dans la mémoire. Bien qu'il soit rapide, il consomme beaucoup de ressources donc MySQL stockera directement le fichier d'index ; sur le disque.

Ceci est légèrement différent de l'index elasticsearch mentionné plus tard.

L'index étant stocké sur le disque, il faut réduire au maximum les IO sur le disque (l'efficacité des IO disque n'est pas du même ordre de grandeur que celle de la mémoire)

Comme le montre la figure ci-dessus, nous devons interroger une donnée nécessite au moins 4 fois IO. Évidemment, le nombre de fois IO est étroitement lié à la hauteur de l'arbre. , moins il y a de fois d’E/S et meilleures sont les performances.

Alors comment réduire la hauteur de l'arbre ?

On peut essayer de changer l'arbre binaire en arbre ternaire, pour que la hauteur de l'arbre baisse beaucoup, et le nombre de Les E/S lors de l'interrogation des données diminueront naturellement, tandis que l'efficacité des requêtes sera considérablement améliorée.

C'est en fait l'origine de l'arbre B+.

Quelques suggestions d'utilisation des index

En fait, grâce à la compréhension de B+树 dans l'image ci-dessus, vous pouvez également optimiser certains petits détails du travail quotidien par exemple, pourquoi ; il est préférable d'augmenter par ordre de ?

En supposant que les données de clé primaire que nous écrivons ne sont pas ordonnées, il est possible que l'identifiant des données écrites plus tard soit plus petit que celui écrit auparavant. De cette façon, il peut être nécessaire de déplacer les données déjà écrites. lors du maintien de l'index B+树 .

Si vous écrivez des données de manière incrémentielle, vous n'aurez pas cette considération. Il vous suffit de les écrire séquentiellement à chaque fois.

C'est pourquoi nous exigeons que la clé primaire de la base de données ait une tendance croissante autant que possible. Le moyen le plus raisonnable est d'auto-incrémenter la clé primaire sans tenir compte de la situation des tables fractionnées.

Dans l'ensemble, l'idée est similaire à celle d'une table de saut, mais des ajustements ont été apportés en fonction du scénario d'utilisation (par exemple, toutes les données sont stockées dans des nœuds feuilles).

ES Index

MySQL Maintenant que nous avons fini de discuter, voyons comment Elasticsearch utilise les index.

Forward index

utilise une structure de données appelée 倒排索引 en ES ; avant de parler formellement d'index inversé, parlons de son contraire 正排索引 .

À titre d'exemple, la façon dont nous pouvons interroger des objets spécifiques via doc_id est appelée en utilisant 正排索引. En fait, cela peut également être compris comme un. sorte de liste dispersée.

L'essence est de trouver de la valeur à travers la clé.

Par exemple, via doc_id=4, vous pouvez rapidement interroger les données name=jetty wang,age=20.

Index inversé

Alors si à mon tour je veux demander quelles données contiennent name dans li ? Comment interroger efficacement de cette manière ?

La simple utilisation de l'index direct mentionné ci-dessus n'a évidemment aucun effet. Nous ne pouvons parcourir toutes les données que dans l'ordre et déterminer si le nom contient li ;

Mais si on reconstruit une structure d'index :

Quand on veut interroger les données contenant name dans li , il vous suffit d'interroger les données contenues dans Posting List via cette structure d'index, puis d'interroger les données finales via le mappage. La structure de l'index

est en fait 倒排索引.

Dictionnaire de termes

Mais comment interroger efficacement li dans cette structure d'index Sur la base de notre expérience précédente, tant que nous organisons Term dans l'ordre, nous pouvons utiliser un arbre binaire ? La structure des données de l'arbre de recherche est interrogée sous o(logn).

Le processus de division d'un texte en Term indépendants est en fait ce que nous appelons souvent la segmentation des mots.

Et combiner tous les Term ensemble devient un Term Dictionary, qui peut également être appelé un dictionnaire de mots.

La segmentation des mots anglais est relativement simple. Il suffit de séparer le texte par des espaces et des signes de ponctuation pour diviser les mots. Le chinois est relativement compliqué, mais il existe également de nombreux outils open source pour la prendre en charge (. puisque ce n'est pas l'objet de cet article, la segmentation des mots (ceux qui sont intéressés peuvent effectuer une recherche par eux-mêmes).

Lorsque la quantité de notre texte est énorme, il y aura beaucoup de Term après la segmentation des mots. Si une telle structure de données d'index inversé est stockée en mémoire, elle ne suffira certainement pas. store, mais si c'est comme MySQL Le stocker sur disque n'est pas si efficace.

Index des termes

Nous pouvons donc choisir une méthode de compromis. Puisque l'intégralité de Term Dictionary ne peut pas être mise en mémoire, nous pouvons créer un index pour Term Dictionary et le mettre en mémoire au milieu.

De cette façon, Term Dictionary peut être interrogé efficacement, et enfin Term Dictionary peut être interrogé via Posting List.

sera également réduit plusieurs fois par rapport à MySQL en B+树. 磁盘IO

nous pouvons utiliser ce Term Index qui est ce que nous appelons souvent Trie树 pour stocker. 字典树

Pour plus d'informations sur les arbres de dictionnaires, veuillez consulter ici.

Si nous recherchons

commençant par j, la première étape consiste à interroger Term en mémoire quelle position dans le Le fichier de dictionnaire Term Index est le j commençant par Term (cette position peut être un pointeur de fichier ou une plage d'intervalles). Term Dictionary

Supprimez ensuite tous les

de cette plage d'emplacements. Puisqu'ils sont triés, vous pouvez localiser rapidement l'emplacement spécifique grâce à la recherche binaire de cette manière, vous pouvez interroger Term. Posting List

Enfin, les données cibles peuvent être récupérées à partir du fichier d'origine via les informations de localisation dans

. Posting List

Plus d'optimisations

Bien sûr,

a également effectué de nombreuses optimisations ciblées. Lorsque nous récupérons deux champs, nous pouvons utiliser ElasticSearch pour l'optimisation. bitmap

Par exemple, si nous devons maintenant interroger les données de

, alors nous devons utiliser ces deux champs pour obtenir les résultats respectifs name=li and age=18. Posting List

La méthode la plus simple consiste à parcourir les deux collections séparément et à supprimer les données en double, mais cela est évidemment inefficace.

À ce stade, nous pouvons utiliser la méthode bitmap pour stocker (également économiser de l'espace de stockage), et en même temps utiliser le calcul inné 位与 ** pour obtenir le résultat . **

[1, 3, 5] ⇒ 10101

[1, 2, 4, 5] ⇒ 11011

Le résultat peut être obtenu en additionnant deux tableaux binaires :

10001 ⇒ [1, 5]

résout finalement Posting List en [1, 5], ce qui est naturellement beaucoup plus efficace.

Il n'y a pas d'optimisation particulière pour les mêmes exigences de requête dans MySQL. Il filtre simplement d'abord les petites données, puis filtre le deuxième champ. Naturellement, l'efficacité n'est pas aussi élevée que ES.

Bien entendu, ES sera également compressé dans la dernière version de Posting List Pour les règles de compression spécifiques, vous pouvez consulter la documentation officielle, qui ne sera pas présentée en détail ici.

Résumé

Enfin résumons :

À travers le contenu ci-dessus, nous pouvons voir que peu importe comment Le produit est complexe. En fin de compte, ils sont tous composés de structures de données de base, mais ils seront optimisés spécifiquement pour différents scénarios d'application. Par conséquent, une fois que vous aurez une bonne base de structures de données et d'algorithmes, vous pourrez rapidement commencer à chercher. à une nouvelle technologie ou un nouveau middleware, et vous pouvez même connaître vous-même la direction de l'optimisation.

Enfin, je dessinerai une tarte. À l'avenir, j'essaierai de créer un moteur de recherche autonome basé sur l'idée de ES index inversé. Ce n'est qu'en l'écrivant moi-même que je pourrai l'approfondir. ma compréhension.