mysql - 聚集索引在SQL查询上的性能

Question

假设您有两个表:

Student(id, class) // 100 rows
Course(id, course) // 100 rows

最初假设两个表上都没有索引。现在假设我们有一个查询:-

select id, course 
from Student join course 
on student.id = Course.id and student.id = 20

由于没有任何索引，所以需要遍历两个表中的所有行。

Time complexity - O(100 x 100)

现在我们更新了表，Student.id 是主键。将在其上创建聚集索引，现在总体复杂度为

Time complexity - O(log 100) // Nested loop join

你认为我的假设正确吗？有人可以帮助我吗？

嵌套循环连接算法在这里:

Answer 1

join course 
on student.id = Course.id

正确位于 O(MN) (最坏情况)，其中 M和N分别是第一个和第二个表中的行数，因为它是 equi-join (加入 = 条件)它将第一行与第二行的每一行进行比较。

但是，你还有第二个条件。自 SQL有很多性能增强算法，很可能是student.id = 20将首先进行评估。那么你首先会 M (假设与 Students 表的行数呈线性)搜索 student.id = 20 。那么，如果student.id = 20只是常数，假设 m，你会得到 m * N 。

总而言之，O(M + (m * N)) 。

这里现在取决于 m 。如果m那么在渐近分析中是常数 O(M + N) = O(2M) ，自 M=N你最终得到 O(M) = O(N)或线性。否则，如果 m位于Omega(1) ，那么它将是 O(M + M * N)或者如您所假设的 O(MN) .

然后关于PRIMARY KEY将/可以创建聚集索引。现在未来查询的时间复杂度将如您所说的 O(log K) ，其中 K 是新表中的行(可以是 != 100)。

现在为什么log K ？因为关系数据库的索引结构为B-trees 。然后在 WC 你会得到O(log K)在树的高度。

更准确地说

因为在 B 树上你有最大。 2d children和按键数量s之间d - 1 < s < 2d 。 d称为树的阶数、度数或分支因子。

希望对你有帮助!