La théorie des index mongodb :
Dans Cet article nous allons voir comment fonctionnent concrètement les index dans une base de donnée Mongodb. Nous allons donc aborder les thèmes suivants :
- Structure d’un disque
- Les index dans une BDD
- Les arbres binaires
- Les m-way tree
- Les B-tree
La structure d’un disque :
Un Disque de mémoire est composé de plusieurs de plateaux (chaque plateau est parcouru par une tête de lecture ou plus) eux-même découpés en pistes concentriques sous deux format -physique et logique- d’un côté sous forme de tranches appelées secteurs et d’un autre, sous forme de cylindres creux appelés cylindre ou track en anglais. l’intersection de ses deux types de coupures forme un bloc. Un bloc est un espace de mémoire contenant un certain nombre de octets(512 par exemple).
Pour pouvoir lire les données se trouvant dans un certain bloque on utilise le lecteur (en rouge). Pour se rendre à un stack on fait translater le lecteur et pour accéder à un secteur on fait tourner le disque.
Dans un bloc on va trouver 512 octets qui ont chacun une adresse qu’on appelle un offset. Par conséquent pour identifier un octets il faut les 3 coordonnées suivantes : un secteur, un track et un offset.
Le temps que prend l’extraction des données dépends de deux grandeurs importantes : le temps d’accès (en miliseconde pour un disque HDD) et le taux de transfert (en Mo/s).
Le but de l’étude des structures de données est de minimiser l’espace occupé par les programmes exécutés tout en réduisant le temps de traitement des données. C’est ce qu’on va voir par la suite !
Les index dans une base de données :
Une table d’une base de données (relationnelle ou pas) est stockée sous forme de linked list, prenons l’exemple suivant :
Prenons l’exemple suivant :
Supposons qu’on ai la taille suivante pour chacun des champs :
- id : 8 octets
- prénom : 50 octets
- pays : 50 octets
- département : 20 octets
On a donc un total de 128 octets pour chaque ligne. Sachant qu’un bloc fait 512 octets, chaque bloc pourrait stocker 4 lignes. Il nous faudrait donc 5 blocs pour stocker cette table de 20 lignes.
Donc pour effectuer une simple recherche d’un prénom dans la table, 5 blocs sont visités.
Voyons voir ce que cela donnerai avec un tableau d’index. Il s’agit d’une table avec champs en l’occurrence l’id ici et un pointeur vers la ligne correspondante à l’id :
Si on recalcule la taille à visiter nécessaire pour trouver un élément dans la table. Supposant qu’on ai les tailles suivantes :
- l’id : 8 octets
- pointeur : 20 octets
Donc un total de 28 octets par ligne, soit 560 octets pour 20 lignes. Pour un bloc de 512 octets, 2 blocs suffisent pour stocker tout le tableau des index.
Lorsque nous effectuons une recherche, le tableau des index est parcouru (2 blocs) ensuite une fois l’identifiant retrouvé le lecteur connait directement l’adresse du bloc où se trouve la ligne (1 bloc de recherché en plus). Ce qui fait en total 3 blocs parcourus à la place de 5 sans index. Ceci prend de l’importance en fonction du nombre de ligne dans la table.
Sparse index :
Supposons maintenant qu’on étant la table jusqu’à 10000 lignes, ce qui fait taille total pour l’index de 28 x 10000 = 280000. Ce qui correspond à 547 blocs. Dans ce cas une solution c’est de créer des index d’index. Il s’agit d’index qui réfèrent à une partie du tableau d’index. Ici on aura deux champs un avec un intervalle d’index et un autre avec un pointeur qui y réfère.
C’est plus simple avec une image :
Faisons le calcul de la taille à chercher pour trouver un élément dans chacun des cas suivants:
1- Table sans aucun index :
On a, la taille de chaque ligne est 128 octets, fois 10000 lignes, cela fait 1 280 000 octets . Ce qui correspond à 2500 blocs à visiter.
2- Table avec un simple index :
On a, la taille d’une ligne est 28 octets, fois 10 000 lignes, cela fait 280 000 octets soit 250 + 1 blocs à visiter.
3- table avec un sparse index :
On a, la taille d’une ligne est 28 octets, fois 10 lignes soit 280 octets. Une fois l’intervalle trouvé, on va chercher dans l’intervalle. Sachant que chaque intervalle contient 1000 lignes de 28 octets cela fait 28000 octets pour l’intervalle, soit un total de 28000 + 280 octets, soit 28280 équivalent à 53 blocs, +1 bloc de la table.
Si nous avons plus de ligne dans la table, par exemple 10 000 000 de lignes et que la taille du sparse index devient beaucoup trop grande, nous créons un sparse index d’un sparse index.
Les M-way trees :
Nous souhaitons que la mise en place d’index se fasse automatiquement. C’est à dire que dès qu’une table dépasse une certaine taille des index se mettent en place, voir des index d’index. Pour comprendre comment cela se fait automatiquement voyons voir une structure de données très connue appelée les m-way trees.
Nous connaissons tous les arbres binaires qui permettent de parcourir et ordonner des données facilement. Le but est simple, on a un noeud, on ajoute une valeur, si cette dernière est supérieur à la valeur du noeud elle passe à droite, sinon à gauche. Quand on parcours un arbre binaire cela peut aller très vite vu que les donnés sont divisés en deux à chaque fois. tandis que si on parcours une liste chaînée cela nécessite de parcourir toute la liste.
Les m-way trees sont une généralisation des arbres binaires. Un arbre binaire à 1 clé est deux enfants, c’est donc un 2-way tree. le m indique le nombre d’enfants et le nombre de clés est toujours égale à m-1.
Voici un exemple de 3-way trees avec 3 enfants et 2 clés.
Si la valeur entrée est inférieur à 10 elle passe à gauche, si elle est entre 10 et 44 elle passe au milieu sinon elle passe à droite.
La structure d’un noeud d’une 3-way tree ressemble à ceci :
Le noeud d’une m-way tree est constitué de m-1 clés (en vert) et de m pointeurs vers des enfants.
Les m-way trees pour les index :
On pourrait tout à fait envisager d’utiliser les m-way trees pour les index, en ajoutant des pointeur vers les lignes/ index / intervalle d’index au noeud. Comme ceci :
La partie en rouge est un pointeur vers un intervalle d’index de 0 à 400 et la deuxième de 400 à 1000. Le problème des m-way trees c’est qu’il n’y aucune condition d’instanciation ce qui fait que ça peut créer un arbre non équilibré.
Les B trees :
Les B trees est une structure de données basé sur les M-way trees mais en y ajoutant quelques propriétés :
- Chaque Noeud doit être au moins à moitié rempli sauf pour le premier noeud.
- Le premier noeud doit avoir au minimum deux enfants.
- Toutes les couches doivent avoir le même degré.
- La création de l’arbre se fait du bas vers le haut.
Voici comment un B tree est créé pour les valeurs suivante : 5,10,15,20,30,35,40,3,13,16
Conclusion :
En conclusion nous avons vu dans cet article l’utilité des index en calculant la taille des blocs à visiter pour répondre à une requête. Nous avons aussi vu les différents types d’index utilisant toutes sortes de structures de données.
