从另一个 table 引用的 table 获取数据的时间复杂度是多少？

Question

const image_schema = () => {
  const common_fields = {
    user_id: {
      type: mongoose.Schema.Types.ObjectId,
      ref: "user",
      required: true,
    },
    file_name: {
      type: String,
      required: true,
    },
  };
  return new mongoose.Schema(common_fields, {
    collection: `image`,
    timestamps: true,
  });
};

以上是 image 集合的 mongoDB 架构。

每当我需要获取此 table 中的行子集时，我还需要从 user table 中获取相应的 user 信息，即被 user_id 列引用。

从 user table 中获取附加列的时间复杂度是多少？

如果 user 集合中的这些额外列包含在 image 集合中，从而破坏规范化，速度性能会不会显着提高？

Answer 1

What is the time complexity of fetching the additional columns from the user table?

好吧，对于每张图片，无论您是使用 $lookup 还是在初始获取后的代码中获取它，都需要执行额外的读取操作。

所以这种方法有明显的性能开销（但是在“现实生活”中这种差异通常是可以忽略的），话虽如此，我个人在大多数情况下仍然更喜欢“规范化”方法。

这两种方法之间存在权衡，如果您的用户从未更新过，图像收集的额外存储使用量是一个 none 问题，那么也许您可以从打破“规范化”中获益。这实际上取决于您的产品使用情况。

在实际决定之前需要考虑很多因素，我认为（数据的）规模和实际性能需要成为前 2 个因素

Answer 2

从技术上讲，嵌入式文档的 O(1) 与 query[ 中引用文档的 O(n) =38=] 时间在 mongodb 端，但也有数据 transfer 和 mongoose hydration - 全部两种情况都是 O(n)。本质上它是相同的 O(n)，但梯度稍差。请阅读下面的详细信息。

请注意 mongoose（撰写本文时为 v6）不使用 $lookup 但 "more powerful alternative called populate()" 因为它是 mongoose，大部分时间花在客户端将 bson 解组为 json，然后将 json 合成 Mongoose 模型。

Mongoose 批量获取refs，默认5000个文档，所以如果查询不到5000张图片，需要多查询一次才能获取所有被引用的用户。尽管从技术上讲它是 O(n) 绝对值非常小 - 如果用户适合工作集，则查询数据服务器端是毫秒级的问题。您可能会花费更多时间将数据从 mongo 传输到客户端。

将 bson 转换为 json 需要更多时间。它是 O(n)，在这种情况下，n 是字段数 x 对象数。这是 mongo nodejs 驱动程序的一部分，您在这里唯一可以改进的是仅投影必填字段。

最昂贵的部分是将 json 转换为 Mongoose。复杂度仍然是 O(n)，但它非常耗时，甚至有 lean 选项可以跳过此步骤，return 普通 json 以获得更高的性能。所以使用：

.populate({ path: 'user_id', select: <only required user's info> , options: { lean: true} })

将使开销可以忽略不计。请记住，用户的字段将是只读的。

数据修改比时间复杂度更重要。虽然非规范化可能会显着提高查询速度，但它会打开一个完整的数据同步蠕虫罐——如果您更改用户 table 中的“相应用户信息”，它不会自动反映在存储在中的用户信息中“图像”集合。

因此，如果您对数据进行非规范化，则需要考虑的事项很少：

您将需要更改用户更新逻辑以更新所有相关集合中的信息

您可能需要将其包装在多文档事务中以确保数据完整性

您将需要从应用程序外部监控更改，例如使用 mongosh
手动更改

从另一个 table 引用的 table 获取数据的时间复杂度是多少？

What is the time complexity of fetching data from a table that is referenced in another table?

sql

database

mongodb

nosql

relational-database