regex - 在 mongoDB 中搜索索引数据的复杂度（Big-O）是多少？

Question

这是一个设计问题。你能告诉我我是否正在索引关键字，如下所示。

obj = {
    name: "Apollo",
    text: "Some text about Apollo moon landings",
    tags: [ "moon", "apollo", "spaceflight" ]
}

确保这样的索引。

db.articles.ensureIndex( { tags: 1 } );

和频繁查询如下。

db.articles.findOne( { tags: "apollo" } ).name

如果我插入了 n 个此类文档，请给我此类查询的性能。

是 O(1) 吗？

在这些数据上搜索正则表达式的性能是什么？

score 3 · Accepted Answer

这是一个 B 树索引，就像在几乎所有数据库中一样，因此它具有 O(log n) 查找时间。

正则表达式搜索听起来像是需要进行全表扫描或全索引扫描，两者都是 O(n)。如果表达式是前缀锚定的，它只需要扫描一个范围，但我想这仍然算作 O(n)。

score 2 · Accepted Answer

正如 Thilo 所提到的，MongoDB 索引是作为“B-Tree”索引实现的，从根本上说，MongoDB 中的索引在操作上类似于其他数据库系统中的索引。此处对 MongoDB 中的索引有一个很好的概述。

我建议阅读有关索引策略和索引操作的信息，以帮助您的实施、管理和设计。

为了帮助分析查询的性能并查看它们在做什么，您可以将 explain() 运算符附加到查询中。请参阅此处以获取更多信息explain()以及如何解释其输出。

MongoDB 将PCRE用于正则表达式。用法记录在这里。除了 PCRE 库中的限制之外，没有大小限制。与所有正则表达式一样，请记住构造不良的正则表达式的后果:)

2 回答 2