Производительность кластерного индекса по SQL Query

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 

Считаете ли вы, что мое предположение верно? Может ли кто-нибудь мне помочь?

вложенного цикл Algo здесь:

Answer 1

join course 
on student.id = Course.id 

правильно в O(MN) (в худшем случае), где M и N являются числом строк в первой и второй таблице, соответственно, так как это equi-join (Присоединитесь к состоянию =), он сравнивает каждую строку с первой и второй.

Однако у вас также есть второе условие. Поскольку SQL имеет множество алгоритмов повышения производительности, очень вероятно, что сначала будет оценен student.id = 20. Затем вы должны были бы сначала M (предположим, что линейное число строк таблицы студентов) для поиска 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 называется порядком, степенью или коэффициентом ветвления дерева.

Надеюсь, это поможет!