mongodbのドキュメントに基づく
このensureIndex()関数は、インデックスが存在しない場合にのみインデックスを作成します。
コレクションがキーでインデックス付けされると、指定されたキーに一致するクエリ式へのランダムアクセスが高速になります。インデックスがない場合、MongoDBは各ドキュメントを調べて、クエリで指定されたキーの値を確認する必要があります。
db.things.find({j:2}); // fast - uses index
db.things.find({x:3}); // slow - has to check all because 'x' isn't
これは、コードランタイムの1行目がbig_theta = 1であり、コードの2行目がであるという意味big_theta = nですか？
index.cppのソース コードに見られるように、MongoDB はインデックス作成に B ツリーを使用します。これは、ルックアップを次のように表すことができることを意味しますO(log N)。ここで、N はドキュメントの数ですが、O(D)D がツリーの深さである場合も同様です (ツリーがある程度バランスが取れていると仮定します)。各ノードには多くの子があるため、D は通常非常に小さいです。
MongoDB のノード内の子の数は約 8192 ( btree.h ) であるため、数十億のドキュメントを含むインデックスは 3 レベルのみのツリーに収まる可能性があります! 対数が log_2 (バイナリ ツリーのように) ではなく、非常にゆっくりと成長する log_8192 であることが容易にわかります。
このため、b ツリーは通常、実際には一定時間のルックアップと見なされO(1)ます。
各ノードに多くの子を保持するもう 1 つの理由は、インデックスがディスクに格納されていることです。1 つのノードのディスク ブロック内のすべての領域を利用して、キャッシュ パフォーマンスを改善し、ディスク シークを減らしたいと考えています。B ツリーは、探しているものを見つけるためにアクセスする必要があるノードが非常に少ないため、非常に優れたディスク パフォーマンスを備えています。
MongoインデックスはBツリーであるため、インデックス付きルックアップはO(log n)です。インデックス付けされていないルックアップはO(n)です。