Почему добавление индекса в поле базы данных ускоряет поиск по этому полю?

Question

Я новичок в базах данных и читаю, что добавление индекса в поле, которое нужно искать, может значительно ускорить поиск. Я понимаю эту реальность, но мне любопытно, как она на самом деле работает. Я немного искал эту тему, но не нашел ничего хорошего, лаконичного, а не технического ответа на то, как это работает.

Я читал аналогию с тем, что он как индекс в конце книги, но в случае поля данных уникальных элементов (таких как адреса электронной почты в пользовательской базе данных), используя обратную аналогии книги обеспечит такое же линейное время поиска, как и неиндексированное знакомство.

Что здесь происходит, чтобы ускорить поиск времени? Я немного читал о поиске с использованием B+-Trees, но описания были слишком сложными. То, что я ищу, - это обзор на высоком уровне того, что происходит, что-то, что помогает моему концептуальному пониманию этого, а не технические детали.

Answer 1

Хорошо, после того, как немного исследований и дискуссий, вот что я узнал:

Концептуально индекс представляет собой отсортированный копию поля данных она является индексация, где каждое значение индекса указывает на это оригинал (несортированные) ряд. Поскольку база данных знает, как сортируются значения, она может применять более сложные алгоритмы поиска, чем просто поиск значения от начала до конца. binary search algorithm - простой пример алгоритма поиска отсортированных списков и уменьшает максимальное время поиска от O (n) до O (log n).

В качестве побочного примечания: Достаточный алгоритм сортировки обычно принимает O (n log n), что означает (как мы все, вероятно, слышали раньше), вы должны помещать индексы только в поля, которые вы будете часто искать , так как добавить индекс (который включает сортировку) немного дороже, чем несколько раз выполнить полный поиск. Например, в большой базе данных из более чем 1 000 000 записей она находится в диапазоне 20x дороже сортировки, чем поиск один раз.

Редактировать: См. @Jarod Elliott's answer для более глубокого изучения эффективности поиска, особенно в отношении чтения с дисковых операций.

Answer 2

Чтобы продолжить повторение аналогии с книгой, если страницы были , чтобы этот элемент был бы таким же временем поиска, как и без индексации, да.

Однако, если ваша книга была списком рецензий, отобранных автором, но вы знали только ISBN. ISBN уникален, да, но вам все равно придется сканировать каждый обзор, чтобы найти тот, который вы ищете.

Теперь добавьте указатель в конце книги, отсортированный по ISBN. Бум, быстрое время поиска. Это аналогично индексу базы данных, переходя от индексного ключа (ISBN) к фактической строке данных (в этом случае номер страницы вашей книги).

Answer 3

Расширяя эффективность алгоритма поиска, ключевой областью в производительности базы данных является то, как быстро можно получить доступ к данным. В общем, чтение данных с диска происходит намного медленнее, чем чтение данных из памяти.

Чтобы проиллюстрировать точку, предположим, что все хранится на диске. Если вам нужно искать по каждой строке данных в таблице, которая ищет определенные значения в поле, вам все равно нужно прочитать всю строку данных с диска, чтобы убедиться, что она соответствует - это обычно называется «сканирование таблицы» ».

Если ваша таблица составляет 100 МБ, это 100 МБ, вы должны читать с диска.

Если вы индексируете столбец, который хотите выполнить поиск, в упрощенном виде индекс сохранит каждое уникальное значение данных и ссылку на точное местоположение соответствующей полной строки данных. Этот индекс может теперь составлять только 10 МБ по сравнению с 100 МБ для всей таблицы.

Чтение 10 МБ данных с диска (и, возможно, немного больше, чтобы прочитать данные полной строки для каждого соответствия) примерно в 10 раз быстрее, чем чтение 100 МБ.

Различные базы данных будут хранить индексы или данные в памяти различными способами, чтобы сделать эти вещи намного быстрее. Однако, если ваш набор данных большой и не помещается в память, тогда скорость диска может иметь огромное влияние, и индексирование может показать огромную прибыль. В памяти все еще может быть большой прирост производительности (среди других показателей эффективности).

В общем, поэтому вы можете не заметить ощутимой разницы при индексировании небольшого набора данных, который легко вписывается в память.

Основные сведения будут различаться между системами, и на самом деле это будет намного сложнее, но я всегда находил, что чтение диска по сравнению с памятью читает легко понятный способ объяснить это.