Fonctionnement des index B-tree de MongoDB

Sans index, MongoDB doit parcourir chaque document d’une collection pour répondre à une requête — cette opération s’appelle un parcours de collection (COLLSCAN). Dans une collection contenant des millions de documents, un COLLSCAN peut prendre plusieurs secondes, voire plusieurs minutes. Un index est une structure de données distincte et ordonnée qui permet à MongoDB d’accéder directement aux documents correspondants en quelques microsecondes.

MongoDB utilise un arbre B (arbre équilibré) pour stocker les entrées d’index. Un arbre B est organisé sous forme de hiérarchie de nœuds : un nœud racine au sommet, des nœuds internes au milieu et des nœuds feuilles à la base. Chaque nœud contient plusieurs paires clé-valeur et des pointeurs vers les nœuds enfants. L’arbre reste équilibré — tous les nœuds feuilles se trouvent à la même profondeur — de sorte que les recherches nécessitent toujours le même nombre d’étapes, quelle que soit la valeur recherchée.

Lorsque vous créez un index sur un champ comme age, MongoDB construit un arbre B dont chaque entrée de nœud feuille contient la valeur du champ indexé associée à un pointeur (le RecordId) vers le document réel sur le disque. Les entrées sont triées par ordre croissant ou décroissant selon la définition de l’index. Comme l’arbre est trié, MongoDB peut répondre aux recherches par égalité, aux requêtes par intervalle et aux opérations de tri à partir de la même structure.

Chaque requête passe par le planificateur de requêtes de MongoDB, qui évalue les index disponibles et choisit le plan d’exécution le plus efficace. Lorsque le planificateur trouve un index approprié, il utilise une étape IXSCAN (parcours d’index) au lieu d’un COLLSCAN. Un IXSCAN parcourt l’arbre B depuis la racine jusqu’aux nœuds feuilles correspondants, puis récupère uniquement les documents pertinents sur le disque à l’aide de leurs pointeurs RecordId.

Un index en arbre B prend en charge trois types de schémas d’accès : les recherches par égalité (trouver la clé exacte), les parcours d’intervalle (parcourir les nœuds feuilles contigus entre deux limites) et les opérations de tri (l’arbre étant déjà ordonné, aucun tri en mémoire n’est nécessaire). Cette triple capacité rend un index bien placé beaucoup plus utile qu’il n’y paraît au premier abord.

Lorsque vous créez un index avec 1, les entrées sont stockées dans l’ordre croissant ; avec -1, elles sont stockées dans l’ordre décroissant. Pour un index sur un seul champ, le sens importe peu, car MongoDB peut parcourir l’arbre B dans les deux directions. Le sens devient essentiel pour les index composés, lorsque la combinaison des sens doit correspondre à l’ordre de tri utilisé par vos requêtes.

MongoDB essaie de conserver l’ensemble de travail des index dans la RAM (le cache WiredTiger). Lorsqu’un index tient entièrement en mémoire, les recherches sont pratiquement des opérations d’E/S gratuites. Lorsqu’un index est trop volumineux pour la RAM, MongoDB doit charger ses nœuds depuis le disque par pagination, ce qui provoque des pics de latence. C’est pourquoi vous devez conserver des index compacts : n’indexez que les champs sur lesquels vous effectuez réellement des requêtes et utilisez une projection pour éviter de renvoyer des données inutilisées.

Une requête couverte est une requête dont tous les champs du filtre et de la projection sont présents dans l’index. MongoDB peut répondre à une telle requête en utilisant uniquement l’arbre B de l’index : il n’a jamais besoin de récupérer le document réel sur le disque. Les requêtes couvertes sont extrêmement rapides et méritent d’être prévues pour vos chemins de lecture les plus sollicités.

Chaque collection MongoDB possède automatiquement un index unique en arbre B sur _id. Cet index par défaut explique pourquoi les recherches sur _id sont toujours rapides, même dans des collections gigantesques. Vous ne pouvez pas supprimer l’index _id. Tous les autres index sont facultatifs et doivent être créés explicitement par le développeur ou le DBA.

Les index accélèrent les lectures, mais ralentissent les écritures. Chaque insertion, mise à jour ou suppression doit mettre à jour non seulement le document sur le disque, mais aussi chaque arbre B qui indexe un champ de ce document. Une collection contenant 10 index entraîne 10 écritures supplémentaires dans des arbres B pour chaque insertion. Ce compromis signifie que vous ne devez créer que des index correspondant à de véritables schémas de requêtes : les index inutilisés continuent de faire payer un coût d’écriture sans apporter de bénéfice.

Lorsque vous indexez un champ qui contient un tableau, MongoDB crée un index multiclé — il insère une entrée d’arbre B pour chaque élément du tableau. Cela permet à des requêtes comme { tags: 'mongodb' } d’utiliser l’index, même si tags est un tableau. MongoDB détecte automatiquement les champs de type tableau et active l’indicateur multiclé ; vous n’avez rien de particulier à faire lors de la création de l’index.

Dans cette leçon, vous avez appris que MongoDB utilise des structures en arbre B dont les entrées feuilles triées pointent vers les RecordIds des documents, que le planificateur de requêtes choisit IXSCAN plutôt que COLLSCAN lorsqu’un index approprié existe et que les index accélèrent les lectures, mais ajoutent un coût aux écritures. Nous allons maintenant étudier la création d’index sur un seul champ et d’index composés.