Как устроены индексы в реляционных базах данных?

А, индексы в базах данных! Ну это ж классика, блядь, вечная тема, как Герасим с Муму, только в мире данных. Сидишь ты такой, запрос пишешь, а он выполняется, сука, как черепаха в сиропе — овердохуища времени ждёшь. А всё потому, что индексов нет, блядь!

Представь себе библиотеку, ёпта, не просто полки с книгами, а полный пиздец, бардак, где все тома свалены в кучу. И ты ищешь «Войну и мир», а она, сука, где-то в самом низу, под «Камасутрой» и сборником анекдотов про Штирлица. Вот так и таблица без индекса — чтобы найти строчку, системе приходится, блядь, всю таблицу целиком перелопатить, от первой до последней записи. Это называется full table scan, и это, простите, полный пиздец по производительности.

А теперь представь, что у нас есть умный библиотекарь — это и есть индекс, сука! Чаще всего это такая штука, называется B-дерево (или его разновидность B+дерево). Выглядит оно, конечно, не как ёлка, а как этакая иерархическая пирамидка из данных.

Допустим, ищем мы пользователя с email vasya@pupkin.ru. Без индекса СУБД бы сказала: «Ну, блядь, ладно...» и пошла бы честно, строчка за строчкой, все миллионы записей просматривать. А с индексом она такая: «Ага, email'ы у меня отсортированы в этом самом B-дереве!». И начинает с корня: «vasya@pupkin.ru? Так, это явно где-то после m но до z. Иду в эту ветку!» «Там опять выбор: после t но до x. Иду дальше!» И так, за несколько шагов, она, хитрая жопа, приходит прямиком к листовой страничке, где и лежит ссылка на ту самую, ебучую, строчку в основной таблице. Всё! Нашла! Скорость — O(log n), что в переводе на русский означает «охуенно быстро».

Но не всё так радужно, ёпта! Индекс — это не магия, а палка о двух концах, блядь.

Плюсы, их все знают:

• Искать быстро. WHERE email = '...' — просто песня.
• Сортировать быстро. ORDER BY last_name — если есть индекс по last_name, то данные уже почти отсортированы в листьях дерева.
• Соединять таблицы. JOIN по индексированному полю — просто объедение, а не адская мука.

А теперь, внимание, подвох! Минусы, про которые все забывают:

• Место жрёт, сука! Это же отдельная структура данных. Представь, что к каждой книге ты пишешь ещё и карточку в каталог. Места нужно больше. Иногда — намного больше.
• Запись тормозит, блядь! Это главная цена! Каждый раз, когда ты вставляешь новую запись (INSERT), обновляешь (UPDATE) или, не дай бог, удаляешь (DELETE) — этой ебучей индексной структуре нужно перестраиваться, чтобы сохранить порядок. Представь, что в наш идеальный алфавитный каталог нужно вписать новую книжку про «Анну Каренину». Придётся, блядь, сдвигать все карточки после буквы «А». На больших таблицах это может превратить быструю вставку в настоящую пытку.

Вот тебе живой пример на SQL:

-- Допустим, у нас таблица users, и все орут на медленные поиски по почте.
-- Делаем так:
CREATE INDEX idx_email ON users(email);

-- Теперь этот запрос полетит:
SELECT * FROM users WHERE email = 'boss@company.com'; -- Фьють! И готово!

-- А можно сделать составной индекс, это вообще мощь:
CREATE INDEX idx_name_dep ON users(last_name, department_id);

-- Этот запрос будет использовать его на ура:
SELECT * FROM users WHERE last_name = 'Иванов' AND department_id = 5;
-- Потому что идёт сначала по фамилии, а потом внутри уже по отделу.

-- А ВОТ ЭТОТ — ХУЙ!
SELECT * FROM users WHERE department_id = 5;
-- Почему? Да потому что в нашем индексе `(last_name, department_id)` данные сначала упорядочены по фамилии, а потом уже по отделу.
-- Искать только по отделу — всё равно что искать в телефонной книге всех, кто живёт на определённой улице. Придётся просмотреть ВСЁ, блядь. Полный скан.

Так когда же это чудо создавать?

• Когда столбец постоянно мелькает в WHERE и JOIN. Почувствовал боль — ставь индекс.
• На первичных и уникальных ключах — они создаются автоматом, за тебя уже всё решили.
• На полях, по которым часто сортируешь (ORDER BY).

А когда НЕ НАДО, даже если очень хочется?

• На табличке, в которую только и делают, что пишут, пишут и пишут. Индексы её просто убьют.
• На столбцах с ебануто низкой селективностью. Что это? Ну, например, поле пол со значениями «М» и «Ж». Какой смысл, блядь? Индекс отсеет максимум половину данных, а full scan всё равно почти неизбежен. Тратить ресурсы на такой индекс — это как прибивать тапок к полу: вроде и зафиксировал, но ходить неудобно.
• Если неправильно составил составной индекс (как в примере выше). Порядок столбцов — это святое, ёпта!

Короче, индексы — это как специи в блюде: без них — пресно и долго, а если переборщить — есть невозможно, всё разъёбет. Нужно чувство меры и понимание, что ты вообще готовишь.