index.cpp
。これは、ルックアップをO(log N)として表現できることを意味します。 ここで、Nはドキュメントの数ですが、O(D)でもあります。 Dが木の深さである場合（木がある程度バランスが取れていると仮定）。各ノードには多くの子があるため、Dは通常非常に小さいです。
MongoDBのノード内の子の数は約8192です（ btree.h ）したがって、数10億のインデックス ドキュメントは、3つのレベルしかないツリーに収まる可能性があります。対数は（バイナリツリーのように）log_2ではなく、log_8192であり、非常にゆっくりと成長することが簡単にわかります。
このため、bツリーは通常、一定時間のルックアップと見なされます。O(1) 、実際には。
各ノードに多くの子を保持するもう1つの理由は、インデックスがディスクに保存されていることです。キャッシュパフォーマンスを改善し、ディスクシークを減らすために、1つのノードのディスクブロック内のすべてのスペースを利用しようとします。探しているものを見つけるために必要なノードはごくわずかであるため、Bツリーのディスクパフォーマンスは非常に優れています。