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