Алгоритм для rdbms, выберите оператор

Question

Привет, не знаю, если это правильное место, чтобы задать этот вопрос, я уже изучил диссертацию и сейчас нахожусь в алгоритме. Моя диссертация - это приложение, которое отправляет сообщения, используя которые контакты будут запрашиваться из БД. Итак, мой вопрос, что такое алгоритм поиска контактов из БД? линейный поиск ??

Answer 1

Если поле contacts проиндексировано в вашей базе данных, оно будет использовать поиск B-Tree, поиск по хешу или поиск FULLTEXT (который является комбинацией некоторых более простых алгоритмов) в зависимости от типа индекса и структура поискового запроса.

Если контакты не проиндексированы или структура поискового запроса не позволяет использовать индекс, то да, будет использоваться линейный поиск.

Answer 2

Индекс не обязательно должен быть первичным, он может быть индексом для любого поля. Как сказал Quassnoi, вы можете указать структуру данных под индексом. Mysql предполагает, что это B-дерево по умолчанию. Таким образом, время поиска узла будет O (logn), если дерево сбалансировано, то есть B-дерево.

Если поле контакта не проиндексировано, БД будет линейно сканировать каждую запись и находить строку, пока не найдет ее. Это наихудший случай за O (n) время.