MongoDB menggunakan B-tree untuk pengindeksan, seperti yang dapat dilihat di kode sumber untuk index.cpp
. Ini berarti bahwa pencarian dapat dinyatakan sebagai O(log N) di mana N adalah jumlah dokumen, tetapi juga O(D) jika D adalah kedalaman pohon (dengan asumsi pohon agak seimbang). D biasanya sangat kecil karena setiap node akan memiliki banyak anak.
Jumlah anak dalam sebuah simpul di MongoDB adalah sekitar 8192 (btree.h ) jadi indeks dengan beberapa miliar dokumen mungkin muat di pohon dengan hanya 3 level! Anda dengan mudah menyadari bahwa logaritma bukanlah log_2 (seperti pada pohon biner) melainkan log_8192, yang tumbuh sangat lambat.
Karena itu, b-tree biasanya dianggap sebagai pencarian waktu-konstan, O(1) , dalam praktiknya.
Alasan bagus lainnya untuk menyimpan banyak anak di setiap node adalah bahwa indeks disimpan di disk. Anda ingin mencoba memanfaatkan semua ruang di blok disk untuk satu node guna meningkatkan kinerja cache dan mengurangi pencarian disk. B-tree memiliki kinerja disk yang sangat baik karena Anda hanya perlu mengunjungi sedikit node untuk menemukan apa yang Anda cari.
