Уявіть, що ви коли-небудь відвідали сайт, який миттєво знає про вас все — незважаючи на те, що він обробляє мільйони користувачів. Ви могли подумати: Вау! Комп'ютери дійсно швидкі, чи не так? Вони переглядають мільйони записів за лічені секунди, щоб знайти мої дані — або ж… чи насправді так?
Зараз ми розглянемо одну з хитрощів, які дозволяють усе це виглядати так легко. Спойлер: вони не переглядають усі записи.
Для початку уявімо, що ви відкриваєте книгу і шукаєте, скажімо, четвертий розділ. Ви не переглядали кожну сторінку, щоб знайти “Розділ 4”, правда? Ви, ймовірно, перевірили зміст і дізналися, що “Розділ 4” знаходиться на сторінці 132.
Бази даних — або точніше, системи управління базами даних (DBMS) — працюють за схожим принципом.
Як це виглядає в світі баз даних?
Припустимо, ми маємо таблицю з іменами. Найкращий спосіб її організувати — це впорядкувати за алфавітом, але ми не знаємо, як імена будуть представлені в таблиці, тому створюємо іншу таблицю — “Таблицю індексів”. Подумайте про це як про зміст бази даних. У таблиці з іменами все впорядковано за алфавітним порядком, а також є посилання на оригінальні дані. Коли ми відсортовуємо дані, можемо використовувати бінарний пошук для знаходження потрібних даних — так само, як ми стрибаємо на потрібну сторінку в книзі.
Рис. 1: Бінарний пошук
Як видно з діаграми, якщо мені потрібно отримати дані, я спочатку звертаюся до індексу. Дані та індекс зберігаються на носії, але “Адреса” не зберігається; це лише для прикладу, щоб показати, де на диску зберігаються імена (як номер сторінки).
Припустимо, я шукаю “Chloe”. Я починаю з середини індексної таблиці, на ім'я Lucas. Chloe йде перед Lucas, тому я переходжу до середини першої половини таблиці, до імені Ethan. Chloe менше за Ethan, тому я переходжу до першої половини залишкової таблиці і знаходжу Chloe. Потім я бачу, що вона знаходиться на сторінці 3, слот H, і одразу потрапляю до потрібного місця.
Цей метод називається плоским індексом.
Чи можемо ми зробити це краще?
Ось кілька проблем з методом плоского індексу:
- Індекс — це один великий блок даних, який зберігається на диску. У наведеному прикладі таблиця мала малий розмір, але якщо б це була велика таблиця, операція стала б дуже дорогою.
- Вони працюють повільніше через необхідність кількаразових операцій вводу/виводу, що вимагає багато часу на зчитування з диска.
- Якщо потрібно вставити дані в середині таблиці, то переміщення всіх елементів після цього створить велику обчислювальну навантаження.
- Збільшення операцій вводу/виводу, оскільки весь індекс завантажується в пам'ять при кожному зчитуванні, а при великих наборах даних пам'ять може бути недостатньо.
Тепер, зустрічайте індекси дерев.
Вони використовують ту ж стратегію "розділяй і володарюй", але набагато ефективніше. Цього разу ми маємо 27 імен замість 9, а наш індекс виглядає так:
Рис. 2: Індекс дерева
Як ви можете побачити, індекс розділений на сторінки, а не зберігається в одному великому блоці. Є:
- Внутрішні вузли (P1 до P4): Це сторінки, що містять значення разом із посиланням на інші внутрішні або листяні вузли.
- Листяні вузли (P5 до P13): Це сторінки, що містять значення разом із посиланнями на дані.
Кожна сторінка містить 3 ключі та посилання.
Давайте подивимося, як це працює. Припустимо, ми шукаємо “Chloe” серед 27 імен.
- Починаємо з кореневого вузла P1. Порівнюємо Chloe з Henry. Chloe йде перед Henry, тому ми йдемо до попереднього вузла, який веде до P2.
- Порівнюємо Chloe з Elijah. Chloe йде перед Elijah, тому йдемо до попереднього вузла, що веде до P5.
- Chloe більша за Caleb, тому ми йдемо до наступного слоту, що веде нас до оригінальних даних на сторінці 16, слот C.
Ми зробили 3 стрибки, як і в попередньому прикладі, але тепер ми працюємо з більшим набором даних, і видно, що цей метод працює значно швидше. До того ж, тепер, коли індекс розділений на сторінки, ми завантажуємо лише одну сторінку в пам'ять, що зменшує навантаження на пам'ять.
Вставки тепер також дешевші, але ми не будемо обговорювати це тут.
Зверніть увагу, що цей набір даних досить малий. У реальних випадках ми можемо мати сторінки порядку 100, і кожна з цих сторінок має 133 нащадки. Тому на 3 рівнях глибини ми працюємо з 133³ = 2,352,637 вузлами. Для кожного рішення, яке ви приймаєте, ви виключаєте 133³ — 1 варіанти, що значно зменшує кількість записів, з якими працюєте.
Оцініть елегантність цього алгоритму, особливо враховуючи велику кількість записів. І найкраща частина? Все відбувається так легко. Часова складність цього алгоритму — O(log n).
Тепер уявімо, що я хочу отримати діапазон значень — скажімо, всі імена між A та H. В нашій поточній конфігурації нам доведеться кілька разів пройти через дерево, що неефективно. Щоб виправити це, ми з'єднуємо листяні вузли послідовно. Тепер, коли ми знаходимо перший лист, ми просто слідуємо за ланцюгом.
Хочу більше ключів…
Ми можемо створювати індекси на кількох стовпцях — це називається складеними ключами. Чому використовувати таку стратегію?
Приклад: припустимо, я хочу знайти одного студента в школі; спершу я знаходжу клас, до якого він належить, а потім знаходжу студента в цьому класі.
Аналогічно, ми можемо зробити те саме з індексами, але треба враховувати пріоритетність стовпців. Який з них має більший пріоритет: клас чи ім’я студента? Тут ми сортуємо спершу за класом, а якщо знайдемо студентів з однаковим класом, то сортуємо їх за іменем.
Це працює добре, якщо ви спочатку шукаєте перший стовпець, а потім другий. Але якщо ви ставите фільтр тільки на другий стовпець, це буде неефективно, оскільки значення другого стовпця будуть розкидані по всьому диску.
Навіщо додавати посилання до листя? Давайте додамо дані прямо туди!
Цей метод називається кластеризованим індексом. Замість того, щоб листяні вузли містили посилання на дані, ми додаємо дані прямо до листяних вузлів.
Це робить процес більш ефективним. Замість того, щоб шукати посилання, ми маємо дані прямо там. Також ми економимо місце на диску, оскільки не потрібно постійно переміщувати диск.
Однак, є один недолік: можна створити лише один такий індекс, оскільки це потребує перестановки самих даних.
Ось і все!
Алгоритм, описаний вище, називається алгоритмом B+ дерева, і це стандартна структура індексації в популярних базах даних, таких як PostgreSQL та MySQL.
Якщо вам здається, що цей алгоритм швидкий, чекайте, поки ви дізнаєтеся про хеш-індекси. Вони мають часову складність O(1).
Але важливо розуміти, що немає єдиного універсального рішення для пришвидшення бази даних; часто вам доводиться робити компроміси. Які операції ви виконуватимете на базі даних: запис чи читання? Які стовпці ви запитуєте? Ви використовуєте базу для аналітики чи транзакцій? Відповіді на ці питання допоможуть обрати правильний підхід.
На цьому все.
Перекладено з: Access Your Data Quickly: A Peek into Tree Index