Як індекси пришвидшують пошук?

Індекс - це окрема структура даних (зазвичай дерево чи хеш-структура), у якій БД зберігає відсортовані посилання на рядки таблиці. Завдяки цьому пошук іде не по всій таблиці, а по значно меншому й зручному для обходу набору даних.

Простими словами:

#1. Без індексу

База переглядає рядки один за одним (full scan), порівнює значення в потрібному стовпці й шукає збіг. Якщо даних багато - це довго, тому що кожен рядок доводиться читати.

#2. З індексом

В індексі значення вже відсортовані, і БД шукає по них, як у телефонній книзі - швидким алгоритмом (наприклад, бінарним пошуком по B-дереву). Вона одразу знаходить потрібний діапазон і лише потім звертається до конкретних рядків таблиці.

#3. Що пришвидшує

• Пошук за WHERE column = X
• Пошук за діапазоном BETWEEN, >, <
• JOIN за проіндексованими стовпцями
• ORDER BY і GROUP BY - якщо індекс покриває колонку

#4. Ціна пришвидшення

• Індекс займає місце на диску
• Вставки/оновлення стають трохи повільнішими (індекс теж потрібно оновлювати)

Отже: індекс дозволяє не читати всю таблицю, а швидко знаходити потрібні рядки за відсортованою структурою, тому операції пошуку виконуються значно швидше.