MongoDB utilise B-tree pour l'indexation, comme on peut le voir dans le code source de index.cpp
. Cela signifie que les recherches peuvent être exprimées sous la forme O(log N) où N est le nombre de documents, mais c'est aussi O(D) si D est la profondeur de l'arbre (en supposant que l'arbre est quelque peu équilibré). D est généralement très petit car chaque nœud aura de nombreux enfants.
Le nombre d'enfants dans un nœud dans MongoDB est d'environ 8192 (btree.h ) donc un index avec quelques milliards les documents peuvent tenir dans un arbre avec seulement 3 niveaux ! Vous réalisez facilement que le logarithme n'est pas log_2 (comme dans les arbres binaires) mais plutôt log_8192, qui croît extrêmement lentement.
Pour cette raison, les b-trees sont généralement considérés comme une recherche en temps constant, O(1) , en pratique.
Une autre bonne raison de conserver de nombreux enfants dans chaque nœud est que l'index est stocké sur le disque. Vous souhaitez essayer d'utiliser tout l'espace d'un bloc de disque pour un nœud afin d'améliorer les performances du cache et de réduire les recherches de disque. Les arbres B ont de très bonnes performances de disque car il suffit de visiter très peu de nœuds pour trouver ce que vous cherchez.
