查找作为对象的字段的属性值的时间复杂度是多少?

Question

而不是:

{
A: [user_id_1, user_id_2, etc.]
}

我想创建这个模式:

{
A: {
user_id_1: true,
user_id_2: true,
etc...
}
}

原因是为了查找user_id_x在A中是否为$，如果它是一个数组，时间复杂度为O(N)。

然而，据我所知，找到一个键值对的时间复杂度是O(1)或O(logN)。

如果我选择MongoDB的模式设计，它会有上面描述的性能改进吗?

Answer 1

是的，如果您选择的模式设计中字段的属性是一个对象，那么查找特定user_id的时间复杂度将是O(1)或O(logN)，如您所提到的。这是因为MongoDB使用哈希表数据结构来存储对象，这允许使用键值对进行常量时间查找。相对于搜索数组的O(N)时间复杂度，这是一个显著的改进。但是，只有当键的数量相对较少时，才能看到这种性能改进。