Компьютеры используют индексы, чтобы помочь им найти что-то. Google использует их для своей поисковой системы. Windows использует его при поиске файлов. И они играют важную роль в базах данных.
Но как они работают? Представьте, что вам нужно найти книгу на книжной полке. Вы просматриваете корешки книг, пока не найдете то, что ищете. Но что, если шипы не помечены?
Теперь, чтобы что-то найти, нужно вытащить каждую книгу и посмотреть на ее обложку. Чтобы что-то найти, потребуется много времени. Как мы можем ускорить эту задачу? Мы могли бы расположить книги в алфавитном порядке, тогда бы мы примерно знали, где находится книга, которую мы ищем.
Если книги отсортированы, мы можем использовать бинарный поиск. Это работает следующим образом: посмотрите на книгу в самой середине, и это скажет нам, в какой половине находится книга. Затем мы повторяем этот процесс, глядя на книгу в середине правильной половины. Каждый раз, когда мы смотрим на книгу, количество книг, которые могли бы быть нашей книгой, сокращается вдвое.
Допустим, у нас есть 100 книг. После просмотра книги в середине осталось 50 книг, которые могли бы быть нашей книгой. После просмотра средней книги снова есть 25, затем 12, 6, 3, 1. Нам нужно всего лишь просмотреть 6 книг, чтобы найти ту, которую мы хотим. Это довольно хорошо, но с указателем можно просмотреть только одну книгу.
Чтобы индекс работал, нам нужно присвоить нашим книгам адрес. Итак, на книжной полке под каждой книгой мы добавим номер (предположим, что все книги одинаковой ширины). Эти числа будут начинаться с 0 и увеличиваться. Если кому-то нужна книга 50, это легко, мы просто берем книгу по этому адресу. Конечно, зачем кому-то просить книгу 50? Не будут, они попросят Алису в Стране Чудес. Ну по какому адресу? Мы не знаем. Нам нужен способ сопоставить названия книг с адресами книг.
Давайте поместим Пятьдесят оттенков серого по адресу 50. Теперь, когда нам нужно найти эту книгу, мы точно знаем, где она. Но не все книги так просты, и эта система должна работать для всех книг. К счастью, умные люди уже решили эту проблему. С помощью хеш-функции мы можем сопоставить любое название книги с хешем. Типичный хэш будет намного больше адресов в нашей книге, но мы можем решить эту проблему с помощью хеш-таблицы.
Хэш-таблица упрощает нам это сопоставление. Все, что нам нужно сделать, это дать ему набор пар ключ-значение.
Нравится
Моби Дик: 0
Том Сойер: 1
…
Алиса в стране чудес: 100
И это создаст сопоставление между ними для нас. Теперь мы можем найти любую книгу на полке, просто взглянув на одну книгу! Но есть и компромисс: создание хэш-таблицы ускоряет поиск книг, но требует места на компьютере.
Когда вы помечаете столбец в базе данных как индекс (или первичный ключ), база данных создает индекс (хеш-таблицу), который сопоставляет данные в этом столбце с адресом, где хранится эта строка.
Для поиска в Google им нужно знать не только обо всех страницах в Интернете, но и обо всех словах на этих страницах. Google создает индекс, который сопоставляет слова (понятия) с веб-страницами. Вот как быстро работает Google.
Выполните поиск кошек, и Google очень быстро найдет все страницы, связанные с кошками, используя уже вычисленное сопоставление. Настоящая магия Google заключается в сортировке результатов.
Индексы делают компьютеры намного быстрее в поиске вещей.
