MongoDB utilizza B-tree per l'indicizzazione, come si può vedere nel codice sorgente di index.cpp
. Ciò significa che le ricerche possono essere espresse come O(log N) dove N è il numero di documenti, ma è anche O(D) se D è la profondità dell'albero (supponendo che l'albero sia in qualche modo equilibrato). D è solitamente molto piccolo perché ogni nodo avrà molti figli.
Il numero di figli in un nodo in MongoDB è di circa 8192 (btree.h ) quindi un indice con pochi miliardi i documenti possono stare in un albero con solo 3 livelli! Ti rendi facilmente conto che il logaritmo non è log_2 (come negli alberi binari) ma invece log_8192, che cresce molto lentamente.
Per questo motivo, i b-tree sono generalmente considerati come ricerca a tempo costante, O(1) , in pratica.
Un altro buon motivo per mantenere molti figli in ogni nodo è che l'indice è archiviato su disco. Si desidera provare a utilizzare tutto lo spazio in un blocco del disco per un nodo per migliorare le prestazioni della cache e ridurre le ricerche del disco. I B-tree hanno prestazioni del disco molto buone perché devi solo visitare pochissimi nodi per trovare quello che stai cercando.
