我在存储什么
我正在尝试存储一个 URL 列表，而不是其他任何东西。我的目标是有一个列入黑名单的 URL 列表，我可以在需要时添加到这个列表中，如果可能的话，我想以 O(1) 时间复杂度从列表中读取。
我已经阅读了一些答案 here有人建议，如果确实需要，创建一个只有一列的表可能是一个很好的设计。
我是如何存储的
当然，只有一列意味着只存储主键。在这种情况下，将生成 URL 的 MD5 散列值并将其作为主键插入到数据库中。该列表可能非常大(数十万)，但不太可能发生碰撞，因此它们目前并不重要。所以想象一下它们不会发生。
如果重要的话，我正在使用 MySQL。
我的问题
- 向该数据库添加新 URL 的时间复杂度是多少？
- 检查 URL 是否存在的时间复杂度是多少？
此外，由于我是 SQL 的新手，因此非常感谢任何用于表创建、插入和更新的示例查询。
最佳答案
在 SQL 中读取时间复杂度为 O(1) 的内容的唯一方法是使用哈希索引——当哈希填满时，即使这样做也需要更长的时间。
也就是说，您可以在 documentation 中了解哈希索引.
也就是说，我怀疑您是否真的需要一个。 B 树索引适用于大多数用途，并且 O( log(n) ) 在数据库中的数据量上并不明显。但是，您的问题指定了 O(1) 而不是“足够快”，因此请了解散列和基于散列的索引。
关于mysql - 在只有一列(主键)的 SQL 表中选择/插入的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61666130/