MongoDB sử dụng B-tree để lập chỉ mục, như có thể thấy trong mã nguồn của index.cpp
. Điều này có nghĩa là các tra cứu có thể được biểu thị dưới dạng O(log N) trong đó N là số tài liệu, nhưng nó cũng là O(D) nếu D là chiều sâu của cây (giả sử cây có phần cân bằng). D thường rất nhỏ vì mỗi nút sẽ có nhiều nút con.
Số lượng nút con trong MongoDB là khoảng 8192 ( btree.h ) vì vậy một chỉ mục có vài tỷ tài liệu có thể nằm gọn trong một cây chỉ có 3 cấp độ! Bạn dễ dàng nhận ra rằng logarit không phải là log_2 (như trong cây nhị phân) mà thay vào đó là log_8192, phát triển cực kỳ chậm.
Do đó, cây b thường được coi là tra cứu theo thời gian không đổi, O(1) , trong thực tế.
Một lý do tốt khác để giữ nhiều nút con trong mỗi nút là chỉ mục được lưu trữ trên đĩa. Bạn muốn cố gắng sử dụng tất cả không gian trong khối đĩa cho một nút để cải thiện hiệu suất bộ nhớ cache và giảm tìm kiếm đĩa. B-tree có hiệu suất đĩa rất tốt vì bạn chỉ cần truy cập vào rất ít nút để tìm thấy những gì bạn đang tìm kiếm.
