MongoDB używa B-drzewa do indeksowania, jak widać w kodzie źródłowym indeks.cpp
. Oznacza to, że wyszukiwania mogą być wyrażone jako O(log N) gdzie N to liczba dokumentów, ale jest to również O(D) jeśli D jest głębokością drzewa (zakładając, że drzewo jest nieco zrównoważone). D jest zwykle bardzo małe, ponieważ każdy węzeł będzie miał wiele dzieci.
Liczba dzieci w węźle w MongoDB wynosi około 8192 (btree.h ), czyli indeks z kilkoma miliardami dokumenty mogą zmieścić się na drzewie z zaledwie 3 poziomami! Łatwo zdasz sobie sprawę, że logarytm to nie log_2 (jak w drzewach binarnych), ale log_8192, który rośnie bardzo wolno.
Z tego powodu b-drzewa są zwykle traktowane jako wyszukiwanie w czasie stałym, O(1) w praktyce.
Innym dobrym powodem trzymania wielu dzieci w każdym węźle jest to, że indeks jest przechowywany na dysku. Chcesz spróbować wykorzystać całą przestrzeń w bloku dysku dla jednego węzła, aby poprawić wydajność pamięci podręcznej i zmniejszyć liczbę wyszukiwań dysku. B-drzewa mają bardzo dobrą wydajność dysku, ponieważ wystarczy odwiedzić bardzo niewiele węzłów, aby znaleźć to, czego szukasz.
