MongoDB中按_id执行findOne和updateOne的时间复杂度是多少？

• 时间复杂度：按_id执行findOne()或updateOne()的平均时间复杂度为O(log n)，但实际场景里（比如百万级数据量），因为MongoDB默认给_id创建了唯一B树索引，而B树的高度通常很低——百万级数据的B树高度一般只有2-3层，所以实际执行速度极快，几乎能做到"即时完成"。

• 和HashMap机制的差异：这和HashMap的O(1)平均复杂度机制不一样。HashMap靠哈希函数直接定位桶的位置，而MongoDB的_id索引是基于B树实现的：

  • B树通过分层索引定位数据，虽然平均复杂度是O(log n)，但能保证最坏情况下的性能稳定，不会出现哈希碰撞导致的O(n)性能退化；
  • HashMap的性能依赖哈希函数的好坏，如果出现大量哈希碰撞，最坏复杂度会掉到O(n)，这是B树不会遇到的问题。

• 百万级集合的实际表现：在有100万条记录的集合里执行db.collection.findOne({"_id": id})或db.collection.updateOne({"_id": id}, {$set : {field: data}})，操作确实能在毫秒级完成，因为B树的查找路径很短，不需要遍历大量数据。

内容的提问来源于stack exchange，提问作者Rongeegee