bou*_*ppo 3 algorithm indexing runtime mongodb
基于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是文档的数量,但是O(D)如果D是树的深度(假设树稍微平衡)也是如此.D通常很小,因为每个节点都会有很多孩子.
MongoDB中节点中的子节点数约为8192(btree.h),因此具有几十亿个文档的索引可能只适用于只有3个级别的树!您很容易意识到对数不是log_2(如在二叉树中),而是log_8192,它变得非常缓慢.
因此O(1),在实践中,b树通常被视为恒定时间查找.
在每个节点中保留许多子节点的另一个好理由是索引存储在磁盘上.您希望尝试将磁盘块中的所有空间用于一个节点,以提高缓存性能并减少磁盘搜索.B树具有非常好的磁盘性能,因为您只需访问很少的节点即可找到您要查找的内容.