SQL 查询上聚集索引的性能

Question

假设您有两个 table：

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

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

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

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

Time complexity - O(100 x 100)

现在我们更新了table并且Student.id是一个主键。将在其上创建聚簇索引，现在整体复杂度为

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

你觉得我的假设正确吗？谁能帮帮我？

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

Answer 1

join course 
on student.id = Course.id

在 O(MN) 中是正确的（最坏情况），其中 M 和 N 分别是第一行和第二行 table 中的行数，因为是一个 equi-join（在 = 条件下加入）它比较第一行和第二行的每一行。

不过，你还有第二个条件。由于 SQL 有许多提高性能的算法，因此很可能首先评估 student.id = 20。那么你首先要M（假设学生的行数呈线性table）来搜索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创建一个聚簇索引will/can。现在，未来查询的时间复杂度将如您所说 O(log K)，其中 K 是新 table 中的行（可以是 != 100）。

现在为什么要 log K？因为关系数据库将索引结构化为 B-trees。然后在 WC 中，树的高度为 O(log K)。

更准确地说

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

希望对您有所帮助！

SQL 查询上聚集索引的性能

Performance of clustered index on SQL Query

mysql

sql

indexing

time-complexity

clustered-index