Есть ли описания алгоритмов поиска в БД по не ключевому атрибуту?

Question

[Fuduin]

Подскажите пожалуйста, где можно почитать про алгоритмы поиска в БД как по ключу, так и по не ключевому атрибуту. При этом интересно как во втором случае используется Индекс. Есть подозрения, что в каждой СУБД эти алгоритмы разнятся, но сгодится любая информация.

Answer 1

[kazmiruk]

www.ozon.ru/context/detail/id/6573935 - крутая книжка по мускулю. Объясняется как и что ищется + много чего еще. По постгресу лучше официальной доки, к сожалению, ничего не нашел + существуют различные расширения о которых надо читать отдельно. По монге - хорошие бесплатные курсы у 10gen, которые объясняют как и что происходит внутри монги (https://education.mongodb.com/)

Comments

[Fuduin]

За книгу спасибо, буду читать.

[Fuduin]

Еще раз спасибо, книга супер, нашел все что хотел и даже больше)

[kazmiruk]

@Fuduin да, я прочитав книгу понял, что до этого про мускуль и базы данных не знал почти ничего ) Не за что.

Answer 2

[nekipelov]

Принцип везде один: если есть возможность использовать индекс, он используется, если же индекса нет или БД считает его использование не рациональным, осуществляется полное сканирование.

Алгоритмы, как и сами типы индексов бывают разными, в основном B-дерево, хеш таблица, иногда R-дерево (может и k-d дерево тоже встречается, я так сильно не углублялся).

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

Comments

[Fuduin]

Спасибо за ответ. Структуры данных используемые для построения Индекса, как и алгоритмы поиска по ним знаю. Кнута читал. Интересно, как СУБД решает когда использовать индекс а когда нет. В сторону документации уже смотрю. Я думал просто есть общие правила вроде, ищем не по ключу => индекс не используем)

Answer 3

[ArisChik]

Есть хорошая книга: Дэн Тоу - Настройка SQL для профессионалов. Примеры построены на Оракл, но объясняются все принципы.

И вот еще отличная книга по всем БД: use-the-index-luke.com

Answer 4

[ntkt]

То, как именно БД следует разложить запрос на элементарные операции доступа к данным, решает т.н. Optimizer. Есть он и у MySQL. Ключевые слова mysql cost based optimizer.

У каждой БД optimizer свой, алгоритмы частично описаны в документации, и у них бывают входные параметры, доступные пользователю, например, т.н. "хинты" (hints) -- указания вида "по этой таблице ты сходи по такому-то индексу, а в этой читай все данные, да обязательно подряд". Ключевые слова mysql hints

Answer 5

[B@rmaley.e><e]

Посоветую книгу Системы баз данных. Полный курс. В ней довольно подробно (и с примерами) описываются различные аспекты баз данных без привязки к конкретным системам.