假设有两个包含这些列的表
FirstName Id
Joe 3
Sarah 5
LastName Id
Smith 5
Rodriguez 3
并假设每个表中有 3000 个其他名称，如果加入Id. 还假装它Id不是主键，而只是一个没有索引或任何其他约束的常规整数列。
我假设在Id没有索引的情况下连接的性能是 O(n^2) 是否正确？MySQL 会在执行它之前自动为这个连接创建一个索引，认识到这会提高多少效率？我认为在大多数情况下，这将是一个明显的胜利，因为 O(n*log(n) + n) （排序然后遍历每个表）对于任何非平凡的 n 都会击败 O(n^2)。这个假设正确吗？