MongoDB verwendet B-Tree für die Indizierung, wie im Quellcode für index.cpp
. Das bedeutet, dass Suchvorgänge als O(log N) ausgedrückt werden können wobei N die Anzahl der Dokumente ist, aber auch O(D) wenn D die Tiefe des Baums ist (unter der Annahme, dass der Baum einigermaßen ausgeglichen ist). D ist normalerweise sehr klein, weil jeder Knoten viele Kinder haben wird.
Die Anzahl der Kinder in einem Knoten in MongoDB beträgt etwa 8192 (btree.h ) also ein Index mit ein paar Milliarden Dokumente können in einen Baum mit nur 3 Ebenen passen! Sie erkennen leicht, dass der Logarithmus nicht log_2 (wie in Binärbäumen) ist, sondern log_8192, der extrem langsam wächst.
Aus diesem Grund werden B-Bäume normalerweise als Lookup in konstanter Zeit betrachtet, O(1) , in der Praxis.
Ein weiterer guter Grund, viele Kinder in jedem Knoten zu behalten, ist, dass der Index auf der Festplatte gespeichert wird. Sie möchten versuchen, den gesamten Speicherplatz in einem Festplattenblock für einen Knoten zu nutzen, um die Cache-Leistung zu verbessern und Festplattensuchen zu reduzieren. B-Bäume haben eine sehr gute Festplattenleistung, da Sie nur sehr wenige Knoten besuchen müssen, um zu finden, wonach Sie suchen.
