mongodb - 在 MongoDB 中如何使用索引进行排序？

Question

我想知道在 MongoDB 中使用索引进行排序实际上是如何工作的。有couple articles在 MongoDB 文档中，但它们实际上并没有描述排序如何进行或时间复杂度。到目前为止，对 SO 和互联网的搜索总体上还没有发现任何相关内容。

假设集合中有一个文档，find() 子句匹配 b 个文档，返回的文档数量有限制，a >> b >> c，并且 c 是一些适当大的数字，使得返回的集合无法容纳内存 - 例如，假设有 1M 个文档。

在操作开始时，存在需要排序的 b 个文档和一个大小为 a 的排序树索引，用于对文档进行排序的特征。

我能想象:

a) 按顺序遍历索引，对于每个ObjectID 遍历b 个文档的列表。返回匹配项，直到达到 c。这将是 O(ab)。

B) 同 A)，但首先在 b 文档中构建 ObjectID 的哈希集。这是 O(a)，但需要 O(b) 内存。

我试图考虑基于遍历 b 文档集的排序，但似乎无法想出比 O(b log b) 更快的任何东西，这并不比没有索引的排序好。

我假设(但也许我错了)每种排序都不需要索引扫描，那么排序实际上是如何工作的？

更新:

凯文的回答和提供的链接缩小了问题的范围，但我想确认/澄清几点:

据我了解，如果您想避免内存中排序，则不能对查询和排序使用不同的索引。当我阅读 this page看起来好像你可以(或者至少，它没有指定一种或另一种方式)，但这似乎是不正确的。本质上，对文档进行排序是因为它们在查询期间按照索引的顺序进行查找，因此按照索引的顺序返回。对？

查询复合索引时，排序索引必须是复合索引中的第一个索引，查询是等式的索引除外。如果不是，则在内存中执行排序。对？

排序如何与 $in 一起使用或 $or查询？例如，假设查询是
{a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

... a 上有一个复合索引和 b以该顺序。如果排序在 a 上，排序将如何工作或 b ? $or更复杂，因为据我所知， $or查询本质上分为多个单独的查询。是 $or查询总是内存中排序，至少用于合并单独查询的结果？

Answer 1

MongoDB 中的索引存储在 B 树结构中，其中每个索引条目指向磁盘上的特定位置。使用 B 树结构也意味着 MongoDB 索引按排序顺序存储，始终按顺序遍历，并且 MongoDB 通过索引按排序顺序获取一系列文档的成本很低。

更新 :B-tree 结构对于 MMAPv1 存储引擎是正确的，但 WiredTiger 存储引擎的实现略有不同(自 MongoDB 3.2 起默认)。基本思想保持不变，以排序顺序遍历索引的成本很低。

一个 SORT查询中的阶段(即内存中排序)限制为 32MB 的内存使用。如果 SORT 查询将失败阶段超过此限制。这个限制可以通过利用索引的排序特性来回避，这样 MongoDB 就可以返回一个带有 sort() 的查询。参数而不执行内存中的排序。

让我们假设查询的形状是:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort(...)

带收藏 a有一个索引:

    db.a.createIndex({b:1,c:1})

当 sort() 出现时，有两种可能的情况。阶段在查询中指定:

1. MongoDB 不能使用索引的排序特性，必须在内存中执行 SORT舞台 .

如果查询不能使用“索引前缀”，这就是结果。例如:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({c:1})

在上面的查询中，索引 {b:1,c:1}可用于:

匹配具有 b 的文档{b:{$gt:100}} 大于 100查询的一部分。

但是，不能保证返回的文档按 c 排序。 .

因此，MongoDB别无选择，只能执行内存中排序。 explain()此查询的输出将具有 SORT阶段。此 SORT stage 将被限制为 32MB 的内存使用。

2、MongoDB可以利用索引的排序性质 .

这是查询使用的结果:

匹配索引顺序的排序键，以及

指定与索引相同的顺序(即索引 {b:1,c:1} 可用于 sort({b:1,c:1}) 或 sort({b:-1,c:-1}) 但不能用于 sort({b:1,c:-1}) )

例如:

    db.a.find({b:{$gt:100}, c:{$gt:200}}).sort({b:1})

在上面的查询中，索引 {b:1,c:1}可用于:

匹配具有 b 的文档{b:{$gt:100}} 大于 100查询的一部分。

在这种情况下，MongoDB 可以保证返回的文档按照 b 进行排序。 .

explain()上述查询的输出将 不是 有一个 SORT阶段。另外， explain()带有和不带有 sort() 的查询输出是相同的。本质上，我们得到了 sort()免费。

理解这个主题的一个有值(value)的资源是 Optimizing MongoDB Compound Indexes .请注意，这篇博文写于 2012 年。虽然一些术语可能已经过时，但文章的技术性仍然相关。

后续问题更新

MongoDB 使用 only one index for most queries .例如，为了避免内存中 SORT查询阶段

db.a.find({a:1}).sort({b:1})

索引必须同时涵盖 a和 b同时字段；例如复合索引，例如 {a:1,b:1}是必须的。您不能有两个单独的索引 {a:1}和 {b:1} ，并期待 {a:1}用于相等部分的索引，以及 {b:1}用于排序部分的索引。在这种情况下，MongoDB 将选择两个索引之一。

因此，对结果进行排序是正确的，因为它们是按照索引的顺序查找和返回的。

为了避免使用复合索引进行内存中排序，索引的第一部分必须满足查询的相等部分，第二部分必须满足查询的排序部分(如 ( 1) 以上)。

如果您有这样的查询:

db.a.find({}).sort({a:1})

指数{a:1,b:1}可用于排序部分(因为您基本上要返回整个集合)。如果您的查询如下所示:

db.a.find({a:1}).sort({b:1})

同指数{a:1,b:1}也可用于查询的两个部分。还:

db.a.find({a:1,b:1})

也可以使用相同的索引 {a:1,b:1}
注意这里的模式:find()其次是 sort()参数遵循索引顺序{a:1,b:1} .因此复合索引必须按 排序相等 -> 排序 .

关于不同类型排序的更新

如果文档之间的字段具有不同的类型(例如，如果 a 在一个文档中是字符串，在其他文档中是数字，在另一个文档中是 bool 值)，排序如何进行？

答案是 MongoDB BSON type comparison order .解释一下手册页，顺序是:

MinKey(内部类型)

空

数字(整数、长整数、 double 数、小数)

符号、字符串

对象

数组

BinData

对象 ID

bool

日期

时间戳

正则表达式

MaxKey(内部类型)

所以从上面使用升序的例子来看，包含数字的文档将首先出现，然后是字符串，然后是 bool 值。