基于 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
big_theta = 1，而第二行代码的运行时间为big_theta = n？MongoDB使用B树进行索引，可以在index.cpp的源代码中看到。这意味着查询可以表示为O(log N)，其中N是文档的数量，但如果D是树的深度（假设树有一定的平衡性），则其也为 O(D)。D通常非常小，因为每个节点都会有很多子节点。
MongoDB中每个节点的子节点数量约为8192 (btree.h)，因此拥有几十亿文档的索引可能只需要3层的树！您很容易意识到对数不是log_2（如二叉树），而是log_8192，其增长非常缓慢。
因此，B树通常被视为实践中的常数时间查找，即O(1)。
在每个节点中保留许多子节点的另一个好处是，索引存储在磁盘上。您想尝试利用磁盘块中的所有空间来提高缓存性能并减少磁盘寻道。B树具有非常好的磁盘性能，因为您只需要访问非常少的节点即可找到您要查找的内容。
O(log n)。未索引的查找的时间复杂度为O(n)。B-树的时间复杂度是O(log N)，Emil Vikström的答案O(1)是错误的。即使在他的“动机”（或假设）下，也是错误的：他忘记了搜索每个节点的8192个子节点所需的时间。换句话说，如果K是节点大小，D是树的深度，则时间复杂度可以重新表示为O(D) + O(log K)（相当于O(log N)），如果子节点以BST或类似的对数结构组织。