MongoDB索引的复杂性

Question

我真的很喜欢MongoDB，我在工作和家中都使用它，而且还没有遇到过性能，复杂性或限制问题。但我一直在考虑索引，我有一个问题，我没有找到适当的答案。

SQL数据库的大规模问题之一是查询的相对复杂性。具体来说，MySQL对大多数索引使用b-树，查询需要O（log（n）），优于线性，但仍然意味着事物需要的时间越长，数据越多。

noSQL数据库的一个很大吸引力就是消除或减轻了这种扩展问题，而通常依赖于具有O（1）查找时间的哈希样式索引，所以拥有更多数据不会减慢您的应用程序。这是我的问题的地方：

根据官方的MongoDB文档，all indexes in Mongo use b-trees。尽管Mongo does in fact have a hashed index，据我可以告诉这些仍然存储在B树，与_id字段上的索引一样。在Mongo的文档中，我甚至找不到任何关于固定时间的任何事情！

所以我的问题是：事实上，所有索引（包括_id和散列）在Mongo中存储在B树？这是否意味着查询密钥（甚至通过_id）实际上需要O（log（n））时间？

附录：作为一个需要注意的问题，如果Mongo文档通过示例查询提供了一些复杂性公式，我会很棒。我最喜欢的例子是Redis documentation。其他：This is related。但是我有关于散列索引和（更重要的）_id索引的附加特定问题。

Answer 1

如果您查看mongodb中的索引代码（here），您可以很容易地看到它使用btree进行索引。所以算法的顺序是O（logN），但是对数函数的基数不是2，它是8192它是代码here

因此，对于一百万条记录，我们只有两个级别（假设树是平衡的）和它可以快速找到记录。总的来说，顺序是对数的，但是由于对数函数的基数非常大，它的增长速度很慢。