关于MongoDB索引与非索引字段查询时间复杂度的技术问询

时间复杂度 #

没错，当通过非索引字段查询时，MongoDB会执行全集合扫描，时间复杂度就是O(n)——这里的n是集合中的文档总数。

实现方式 #

MongoDB的全集合扫描逻辑很直接：

• 遍历集合里的每一条文档，逐个检查是否符合查询条件
• 对于默认的WiredTiger存储引擎，集合数据以磁盘文件的形式存储，扫描时会按顺序读取磁盘上的文档数据，加载到内存后进行条件匹配
• 如果集合数据能完全放进内存（比如小数据集），扫描速度会快不少；但如果数据量远超内存容量，会频繁触发磁盘IO，速度会大幅下降

耗时情况 #

耗时没有固定数值，完全取决于几个核心因素：

• 文档总量：集合里的文档越多，扫描耗时肯定越长
• 单文档大小：大文档的读取和匹配开销远高于小文档
• 硬件性能：磁盘读写速度（SSD比HDD快很多）、内存大小（能缓存更多数据就减少IO）、CPU算力（处理条件匹配的速度）都直接影响耗时
• 查询复杂度：比如带正则、聚合表达式的条件，比简单的等值匹配要更耗时

举个实际场景的例子：100万条小字段文档的集合，全扫描可能几秒就能完成；但千万级的大文档集合，全扫描可能要几分钟甚至更久。

小优化提示 #

虽然全扫描是O(n)，但你可以通过一些操作减少开销：

• 查询时只指定需要返回的字段（投影），避免读取整个文档，减少IO和内存占用
• 如果这类查询频繁出现，最好还是给对应字段建立索引，直接把查询复杂度降到O(log n)，这才是最根本的优化方式

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