SQL-Ex blog

Однією з найважливіших концепцій, яку потрібно розуміти новачкові у світі баз даних SQL, є індексування. Індекси відіграють вирішальну роль у покращенні продуктивності запитів до бази даних та є основою для ефективного проектування бази даних. У цій статті ми розглянемо найбільш загальні типи індексів SQL, покажемо приклади, випадки використання та вникнемо в їхню алгоритмічну складність, щоб допомогти початківцям зрозуміти цю життєво важливу тему.

Що таке індекс?

SQL індекс схожий на ретельно організовану книгу посилань, яка допомагає швидко знаходити інформацію в таблиці бази даних без необхідності читати її всю поспіль. Без індексів для запитів до бази даних часто знадобилося б сканування всієї таблиці, що робить їх повільними та неефективними при великих наборах даних.

Робота індексів полягає у створенні окремої структури даних, в якій зберігається підмножина стовпців таблиці та посилання на фактичні дані. Така організація дозволяє баз даних SQL знаходити конкретні значення значно швидше.

Загальні типи індексів SQL

Давайте розглянемо найбільш загальні типи індексів, які мають знати початківці.

1. Одностовпцевий індекс

Одностовпцевий індекс є найпростішим і найчастіше використовуваним типом індексу. Він будується на єдиному стовпці таблиці, що робить його ефективним для запитів, які виконують фільтрацію або сортування за цим стовпцем.

Приклад:

CREATE INDEX idx_customer_id 
ON customers (customer_id);

• Випадок використання: Якщо ви часто використовуєте пошук замовників за їх унікальним ВД, то одностовпцевий індекс на стовпці customer_id може значно покращити продуктивність запиту.
  
• Алгоритмічна складність: пошук в одностовпцевому індексі зазвичай становить O(log N), де N - число рядків у таблиці.

2. Складовий індекс

Складовий індекс, також званий многостолбцовым, включає індексування разом кількох стовпців. Це корисно, коли запити використовують фільтрацію або сортування комбінації цих стовпців.

приклад

CREATE INDEX idx_last_name_first_name 
ON employees (last_name, first_name)

• Випадок використання: У базі даних співробітників пошук на ім'я та прізвище може отримати перевагу від складеного індексу за цими двома стовпцями.
  
• Алгоритмічна складність: Пошук по складовому індекси також оцінюється як O(log N) індексований стовпець, але сумарна складність залежить від селективності кожного стовпця.

3. Унікальний індекс

Унікальний індекс забезпечує унікальність значень в стовпці (стовпцях), що індексується, гарантуючи відсутність дублікатів записів.

Приклад:

CREATE UNIQUE INDEX idx_unique_email 
ON users (email);

• Випадок використання: Для гарантії унікальності адрес електронної пошти в таблиці users можна створити унікальний індекс на стовпці email.
  
• Алгоритмічна складність: Для пошуку в унікальному індексі зазвичай становить O(log N), подібно до одностовпцевого індексу.

4. Повнотекстовий індекс

Повнотекстовий індекс призначений для ефективного пошуку великих текстових стовпців, таких як статті, публікації в блогах або коментарі. Вони дозволяють виконувати пошук за ключовими словами.

Приклад:

CREATE FULLTEXT INDEX idx_fulltext_content 
ON articles (content);

• Випадок використання: У системах керування контентом повнотекстовий індекс на контентному стовпчику дозволяє ефективно шукати ключові слова.
  
• Алгоритмічна складність: Складність повнотекстового пошуку залежить від алгоритму індексування тексту, але часто дорівнює O(log N) або краще.

Bitmap-індекс

Bitmap-індекс ефективний для стовпців з низькою кардинальністю, що означає невелику кількість різних значень. Він використовує бітові карти для представлення наявності чи відсутності рядків, які відповідають конкретному значенню.

Приклад:

CREATE BITMAP INDEX idx_bitmap_gender 
ON employees (gender);

• Випадок використання: Якщо у вас є стовпець типу "підлога" з обмеженою кількістю значень (наприклад, "чоловічий", "жіночий"), bitmap-індекс може виявитися ефективним для фільтрації по підлозі.
  
• Алгоритмічна складність: Bitmap-індекси забезпечують пошук за постійний час (O(1)), роблячи їх дуже швидкими для запитів певного типу.

Висновок

У базах даних SQL індекси є важливим інструментом покращення продуктивності запитів та оптимізації операцій бази даних. Розуміння індексів різних типів та випадків їх використання є фундаментальним у проектуванні ефективних систем баз даних. Індексування є вирішальним навичкою, чи працюєте ви з одностовпцевими індексами для типових запитів або складними складовими індексами для нетривіального пошуку. Крім того, знання алгоритмічної складності допоможе вам прийняти обґрунтоване рішення під час проектування схеми бази даних та вибору правильних індексів для ваших конкретних випадків використання.

Зворотні посилання

Немає зворотних посилань

Коментарі

Показувати коментарі Як список | Деревоподібною структурою

Автор не дозволив коментувати цей запис

Індекси у реляційній базі даних

Один із найпростіших способів підвищити загальну продуктивність бази даних, а якщо конкретніше, продуктивність запитів, це використовувати індекси баз даних. Але тут головне – вибрати правильний тип індексу. Кожен індекс в SQL має власні переваги, і тому важливо знати, коли і який індекс використовувати. Тут ми розглянемо найпоширеніші індекси з найпопулярніших реляційних СУБД (СУБД – система управління базами даних) та з'ясуємо, коли їх потрібно використовувати.

Що таке індекси бази даних?

Індекс бази даних – це додаткова структура даних, що створюється поруч із даними у таблиці. Ви визначаєте індекс для таблиці та стовпця (або набору стовпців). Таким чином, ви створюєте нову структуру пошуку даних, яка безпосередньо пов'язана з цією таблицею і набором стовпців.

У цій статті ми докладно розпишемо, що таке індекс, як його можна створити, які типи індексів і коли їх потрібно використовувати.

Навіщо потрібні індекси?

Індекси баз даних прискорюють процес отримання даних, і тим самим підвищують продуктивність запитів. Це і є головним завданням таких індексів. Все це відбувається за рахунок того, що для зберігання b-дерева та покажчиків на фактичні дані виділяється додаткова пам'ять.

Індекси використовуються для того, щоб при кожному запиті рядка з таблиці база даних не мала необхідності переглядати всі рядки. Загалом індекси забезпечують досить ефективний спосіб звернення до впорядкованих записів.

Як створити індекс?

У різних РСУБД різний синтаксис створення індексу.Крім цього, різні механізми СУБД використовують при цьому різні параметри. Це ми з вами зможемо побачити трохи згодом. І все ж існує загальний синтаксис створення найпримітивнішого індексу, який підходить для всіх механізмів СУБД. Нижче наведено синтаксичну структуру, за допомогою якої можна створити в таблиці найпримітивніший індекс.

CREATE INDEX index_name ON table_name (column_name_1, column_name_2, …)

А зараз давайте скористаємося цією структурою, щоби створити індекс для реальної таблиці. Припустимо, ми маємо таблицю Customer (див. нижче), і ми хочемо створити індекс для того, щоб прискорити процес пошуку на ім'я клієнта.

CREATE INDEX IX_CustomerName ON Customer (FirstName, LastName)

Після запуску цього коду ми отримаємо індекс для таблиці Customer під назвою IX_CustomerName . За рахунок цього індексу пошук даних у стовпцях FirstName та LastName буде проходити набагато швидше.

Індекс, який створюється, як то кажуть, за кадром, ще називають некластеризованим індексом або індексом бінарного пошуку. За допомогою цього індексу ми можемо виконувати оптимізовані запити для сценаріїв, де є такі запити, як:

SELECT FirstName, LastName, Email FROM Customer WHERE FirstName = 'Mark' and LastName = 'Thompson'

Як показує досвід, щоразу, коли ми хочемо оптимізувати запит, ми дивимося на стовпці, які використовуються для вибірки даних, і перевіряємо, чи є у нас для них індекс. У випадку, якщо стовпці у реченні SELECT аналогічні стовпцям у пропозиціях для вибірки даних, у нас з'являється оптимізований план дій, і, відповідно, пошук відбувається швидше.

Але це не те, що нам потрібне.Індексування – це набагато більше, ніж ці правила.

Які бувають індекси SQL?

Якщо ми вже розібралися, як створювати індекс, тепер давайте обговоримо основні типи індексів реляційних баз даних, за допомогою яких ви зможете оптимізувати свої запити. Для деяких із них потрібний певний механізм СУБД, тому ми вкажемо, де їх можна використовувати.

Всі індекси зберігають покажчики на рядки даних у структурі даних під назвою дерево пошуку. Ця структура оптимізована для пошуку, і вона є головною опорою для індексу. З її допомогою ми можемо виконувати щось на кшталт пошуку у двійковому дереві пошуку, але в нашому випадку все трохи складніше.

Є багато різних індексів. У кожного їх своя внутрішня структура даних, а, відповідно, і призначення. Далі ми розглянемо їх докладніше, а тут поки коротко обговоримо їхні назви.

• З погляду характеристик атрибуту:
• Первинний індекс
• Кластеризований індекс
• Вторинний індекс
• З точки зору кількості посилань на файл даних:
• Щільний індекс
• Розріджений індекс
• Нестандартні індекси для дуже специфічних сценаріїв:
• Бітовий індекс
• Реверсивний індекс
• Хеш-індекс
• Відфільтрований індекс
• Індекс за функцією
• Просторовий індекс

Давайте для прикладу скористаємося тією самою таблицею Customer, що ми використовували раніше. Щоб зрозуміти, як виглядають вибіркові дані, давайте напишемо простий запит SELECT і повернемо з таблиці всі дані.

Кластеризований індекс

Кластеризований (або кластеризуючий) індекс – це один із найпоширеніших індексів, які можна використовувати у всіх сучасних повнофункціональних СУБД. Цей індекс визначає порядок, в якому дані зберігаються на сторінці (фізично) та таблиці (неявно).

Давайте подивимося на приклад.Припустимо, що перші два рядки знаходяться на сторінці №1, третій та четвертий рядки – на сторінці №2, а останній п'ятий рядок – на сторінці №3 (див. нижче).

Завдання кластеризованого індексу – фізично зберігати рядки у порядку зростання чи спадання, беручи в якості основи стовпець, який було обрано. Цей індекс потрібний для того, щоб зберігати саме відсортовані дані. Це значно спрощує пошук одного чи кількох значень у якомусь діапазоні. Щоправда, кластеризований індекс може допомогти нам лише в тому випадку, якщо ми шукаємо значення в якомусь діапазоні, а не серед усіх даних.

Припустимо, що список клієнтів на нашій інформаційній панелі завжди відображається за абеткою. Так от, ми хочемо, щоб наші дані зберігалися в нашій базі даних у відсортованому порядку за іменами та прізвищами. І для того, щоб створити кластеризований індекс, ми пишемо наступний запит:

CREATE CLUSTERED INDEX CI_FirstName_LastName ON Customer (FirstName ASC, LastName ASC);

Цей запит позначається на попередньому, за допомогою якого ми повернули всі дані. Коли ми створили кластеризований індекс із сортуванням за зростанням на ім'я та прізвище, то ми фізично переупорядкували дані на сторінках. Якщо ми з вами поглянемо на наші сторінки, то побачимо, що тепер вони виглядають інакше:

Як ми бачимо, тепер дані відсортовані на ім'я, а потім на прізвище. Це може суттєво спростити нам життя та покращити продуктивність, оскільки, якщо ми зробимо запит на сортування рядків за алфавітом, нічого не станеться, оскільки рядки і так зберігаються у відсортованому порядку. Таким чином, ми можемо уникнути сортування в самому запиті.

Якщо ми захочемо отримати дані про перших 10 клієнтів з точки зору алфавітного порядку, то база даних не шукатиме їх по всій таблиці. Вона просто поверне сторінки з першими 10 записами, оскільки вони вже відсортовані.

Бітовий індекс

Битовий індекс - це ще один різновид індексів. На момент написання статті його можна було використовувати тільки в Oracle. не така вже й велика.

Повернімося до нашого прикладу і спробуємо застосувати цей бітовий індекс. Уявіть, що в нашій таблиці Customer насправді не 5, а більше 10 мільйонів рядків. статі з прізвищем Watson.

Ми можемо написати запит приблизно так:

SELECT FirstName, LastName, Email FROM Customer WHERE Gender = 2 AND LastNamr = "Watson";

Битовий індекс ідеально підходить для цієї ситуації, тому що в порівнянні з 10 мільйонами записів рядків, які відповідають якійсь певній підлозі, набагато менше.

CREATE BIMAP INDEX BMP_Gender ON Customer (Gender)

А тепер ми вибираємо «Kate Watson» та її адресу електронної пошти (див. нижче), а також решту відповідних рядків з 10 мільйонів у цій таблиці.

бітовий індекс може виявитися ще більш потужним, якщо ви створите його в пропозиції JOIN .

CREATE BITMAP INDEX BMP_Gender_Sales ON Customer (Gender) FROM Customer, Sales WHERE Customer.ID = Sales.Customer_ID;

Щоразу, коли ви надсилаєте запит на об'єднання цих двох таблиць і їх фільтрації по підлозі, ви будете дуже близькі до максимальної продуктивності запиту.

Реверсивний індекс

Реверсивний індекс багато в чому нагадує звичайний індекс. Але він не створює двійкове дерево пошуку для того, щоб прискорити пошук даних у порядку зростання, цей індекс оптимізовано для пошуку даних у порядку зменшення. Синтаксична конструкція для створення реверсивного індексу дуже схожа на синтаксичну конструкцію звичайного індексу некластеризованого. Різниця лише в тому, що ми повинні вказати, що дані повинні бути у зворотному порядку.

Припустимо, що ми хочемо оптимізувати запит, за допомогою якого хочемо дізнатися імена клієнтів, які розмістили 3 останні замовлення. Створимо індекс:

CREATE INDEX IX_LastOrder_Customer ON Customer (LastOrder DESC);

Найважливіше слово у цій конструкції – це DESC. Воно повідомляє механізм СУБД, що необхідно створити саме реверсивний індекс. Таким чином, щоразу, коли ми будемо запитувати дані про три останні замовлення з таблиці Customer, ми будемо отримувати найкращу продуктивність запиту.

Яку структуру даних використовує індекс?

Як ми вже згадували, індекси створюються поряд з іншими структурами даних для оптимізації пошукових операцій. Але що це за структури даних?

Збалансоване дерево

Найпоширеніші індекси для того, щоб прискорити запити використовують, так би мовити, за кадром збалансоване дерево. Більшість механізмів СУБД використовують або збалансоване дерево, або його різновид, наприклад b-дерево. Нижче показано, як виглядає структура звичайного збалансованого дерева.

Верхній вузол – це кореневий, проте інші, які розташовані нижче, - це або дочірні, або кінцеві вузли. Пошук рядка починається з кореневого вузла. Ми порівнюємо потрібне значення зі значенням у поточному вузлі, більше воно чи менше. Залежно від результату цього порівняння ми зрозуміємо, в який бік нам треба йти, ліворуч чи праворуч. Якщо ми подивимося приклад вище, то побачимо, що це значення менше 8 ведуть нас вліво, а значення більше 8 – вправо, тощо.

Хеш використовується хеш-індексами. Це структура даних, яка забезпечує один із найшвидших пошуків. За допомогою хеша індекси можуть дуже швидко знаходити дані, що зберігаються у таблиці.

Основна ідея хеш полягає в наступному: замість того, щоб перебирати всі ключі пошуку за допомогою індексів або шукати їх по всій таблиці, ми застосовуємо до нього хеш-функцію. Цей ключ пошуку перетворюється на хеш-значення, яке визначає відповідно так зване «відро». Давайте подивимося на приклад нижче. У ньому ми застосовуємо хеш-функцію до ключа пошуку «Mike», після чого воно ставить у відповідність певне відро.

Кожне таке відро в масиві цебер містить однакову кількість записів. Не має значення, скільки в стовпці різних значень, кожен рядок зіставляється з окремим відром. Після чого вибирається відповідний рядок і повертається із цього відра.

Реалізація індексів за допомогою механізмів РСУБД

Як ви вже могли зрозуміти, у реляційній базі даних є кілька типів індексів. І кожен механізм СУБД має свої власні реалізації цих індексів. Давайте пройдемося найпопулярнішими механізмами СУБД, перерахуємо індекси, які в них є і обговоримо, коли їх краще використовувати.

Індекси у PostgreSQL

У PostgreSQL перелік індексів досить великий.Кожен із них підходить для конкретних сценаріїв:

• Найпоширеніший індекс - індекс В-дерева. Він буде корисним у ситуаціях, коли вам потрібно порівнювати діапазони в стовпцях, які можна сортувати.
• Хеш-індекс зберігає 32-бітовий хеш-код, який є похідним від значень індексованих стовпців. Він буде корисним у тих випадках, коли вам потрібно проводити прості порівняння.
• GiST - це не один якийсь індекс, а скоріше логічна структура, в якій можуть бути реалізовані кілька різних стратегій індексування. Найчастіше ця структура використовується в сценаріях, в рамках яких вам потрібно знайти найближчого сусіда в геометричних типах даних.
• SP-GiST, як і GiST, реалізує декілька стратегій індексування. У його основі лежать різні структури даних, такі як дерева квадрантів, k-мірні та базисні дерева. Цей індекс використовується у тих самих сценаріях, що й GiST.
• GIN також називають "інвертованим індексом". Він використовується у сценаріях, у яких дані є масивом. Інвертований індекс містить окремий запис кожного компонента масиву.
• BRIN розшифровується як "Block Range INdex", що перекладається як "блочно-діапазонний індекс". Він використовується для зберігання короткого опису значень на послідовних сторінках фізичних даних усередині таблиці. Найкраще він підходить для ситуацій, коли значення рядків перегукуються з фізичним порядком сторінок даних.

Індекси в Oracle

У Oracle список індексів трохи менший. Але при цьому вони вважаються більш продуманими з точки зору застосування.

• В-дерево – це стандартний індекс. Він також є й у інших механізмах СУБД.В-дерево найкраще підходить для представлення первинних ключів та стовпців, які мають величезну кількість різних значень щодо загальної кількості рядків.
• Побутовий індекс потрібен для зворотних сценаріїв. Наприклад, його можна використовувати в сценаріях, де кількість різних значень у стовпці не така велика щодо загальної кількості рядків.
• Індекс за функцією – це індекс, у межах якого значення, що зберігається у дереві пошуку, визначається функцією. Таким чином, він забезпечує відмінну продуктивність запитів, в яких є пропозиції WHERE з функціями всередині.

Індекси в SQL Server

SQL Server не так багато індексів, але при цьому у них дуже багато функціональних можливостей.

• Кластеризований індекс потрібен не лише для того, щоб механізм СУБД міг здійснити пошук у запиті. Він фізично реорганізовує рядки на сторінках даних так, щоб вони були відсортовані або за зростанням або за зменшенням.
• Некластеризований індекс - це еквівалент В-дерева, яке є в інших механізмах СУБД. В основному він добре підходить для ситуацій, коли потрібно перебрати дані з безліччю різних значень.
• Відфільтровані індекси створюються для певних груп даних. Вони використовуються для того, щоб оптимізувати пошук асиметричних даних із заданими критеріями. Наприклад, ми хочемо знайти в стовпці число 55. Але воно є лише в кількох рядках (щодо загальної кількості рядків у таблиці). Тоді можна створити відфільтрований індекс за принципом кластеризованого, просто додатково вказавши умову WHERE column = 55 .

Індекси у MySQL

MySQL також має кілька індексів, за допомогою яких можна підвищити продуктивність запитів.

• Індекс первинного ключа – це унікальний індекс, за допомогою якого можна швидко та ефективно звертатися до унікальних значень. Також йому вигідною є оптимізація NOT NULL , оскільки він може бути значення NULL . Він завжди використовується для визначення первинного ключа і створюється автоматично, коли ви вказуєте ключові слова PRIMARY KEY .
• Однозначний індекс багато в чому схожий на індекс первинного ключа. Але він більш гнучкий у тому сенсі, що дозволяє багаторазово зберігати значення NULL . Він використовується для того, щоб забезпечити додаткову унікальність у тому випадку, коли первинний ключ вже було створено.

Розширіть свій інструментарій за допомогою індексів баз даних

Якщо ви дійшли аж до сюди, то вам сподобалося читати про індекси баз даних! Я сподіваюся, що ця інформація була для вас корисною і ви змогли знайти тут для себе щось нове. Якщо раптом ваші запити гальмують, то за допомогою ваших знань про те, які є індекси в різних механізмах СУБД, ви зможете підвищити продуктивність запитів.

Іноді може бути так, що звичайного дерева буде недостатньо, або він може не відповідати схемі та/або даним. Тому мати уявлення про те, які ще є типи індексів у реляційній базі даних, це все одно, що мати швейцарський армійський ніж у своїй ящику з інструментами.

Що таке індекси бази даних (початківців)?

Багато хто чув про те, що індекси в базах даних – це дуже корисна штука. Але одна справа чути, а інша уявляти собі їх пристрій хоча б на базовому рівні. Тому в рамках цієї статті для початківців, я розгляну це питання, застосовуючи прості та зрозумілі кожному вирази та аналогії з життя.

Що таке індекс бази даних і навіщо він потрібний?

Щоб зрозуміти навіщо потрібні індекси в базі даних і що він є, зараз розглянемо простий приклад.

Уявіть, що у вас є поличка для книг. При цьому спочатку ця поличка з книгами пуста. Книги вам то приносять, то забирають, то роблять у них якісь коригування (наприклад, мемуари або, можливо, чернетки) тощо.

Так як поличка маленька, то ви якось не особливо замислювалися про будь-яку систему класифікації, а просто вставляєте книги в будь-які порожні місця.

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

Тепер уявіть собі, що йдеться не про одну поличку, а про величезне приміщення, де знаходяться тисячі книг.

Тут ви і починаєте замислюватися про те, що непогано б запровадити якусь систему класифікації, наприклад, за назвою книги. Звичайно, повністю сортувати всі ці тисячі книг в алфавітному порядку ви не збираєтеся, плюс з цим виникла б купа інших питань (як додати книгу до вже заповненої полиці та інших).

Тому ви робите простіше, ви берете каталог, де можна додавати листочки. При цьому кожну сторінку виділяєте лише під одну назву книги, а самі сторінки маєте в каталозі в порядку зростання назв. Зміст цих сторінок дуже простий — ви записуєте в якомусь стелажі, на якій полиці і якою є книга. Якщо книжок кілька, то рядків у цій сторінці стає кілька.

Таким чином, щоб знайти одну або всі потрібні книги за назвою, вам достатньо відкрити цей каталог і швидко прогорнути до потрібної сторінки, а потім пройти по всіх вказаних стелажах. При цьому для спрощення, ви також можете перші літери назв так само індексувати. Тобто додаєте наклейку на кожну першу сторінку із зазначеною літерою (таким чином можете відразу перейти, наприклад, до літери «Р», не перегортаючи всі назви до неї).

Звичайно, для підтримки такої системи потрібен додатковий час, але все ж таки він істотно менший, ніж спроба знайти наосліп книгу з тисячі (пара хвилин проти декількох годин і більше).

Так ось, у цьому прикладі, якщо переносити це до бази даних:

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

Пошук книги - це sql-запити отримання даних. При цьому важливо зазначити, що самі собою вони не змінюються. Тобто як потрібно було знайти «Термодинаміку», так і залишилося потрібним знайти «Термодинаміку». Інша річ, як ви це здійснюватимете — прочісуючи тисячі книг або відкривши каталог.

Каталог - це і є спрощений варіант індексу в базі даних. Тобто індекс це набір додаткових даних, записаних у зручному вигляді, який дозволяє суттєво швидше здійснювати пошук, хоч і потребує додаткових зусиль для підтримання його актуальності.

Ім'я книги (сторінка) – це ключ в індексі. Те унікальне значення, яке може посилатися як на один запис, так і на кілька. Навіть якщо записів для кожного значення буде кілька, це все одно швидше, ніж повний перебір всіх даних.

Якщо підсумовувати, можна побачити, що наявність індексу може бути дуже вигідним. Наприклад, для однієї домашньої полички з десятком книг — індекс загалом не дуже потрібен, а от коли мова заходить про більші обсяги, то індекс буде дуже корисним.

Також можна помітити, що додавання індексу не вимагає того, щоб самі sql-запити були переписані, оскільки останні є лише виразом спрощеною мовою для бази даних. Якщо продовжити аналогію, це як попросити когось знайти вам «Флора і фауна». При цьому яким чином і скільки цей хтось шукатиме книгу, вирішуватиме сама ця людина. У даному прикладі «знайти книгу» — це SQL-запит, а цей «хтось» це база даних.

Які індекси бувають?

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

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

Як бачите, дуже схоже на перевернуте звичайне зелене дерево, у якого гілки ростуть не вгору, а вниз.

Максимальна кількість дочірніх вузлів, Як імовірно вже здогадалися по картинці, це кількість дочірніх вузлів, більше якого в одного вузла не може бути.

Тепер поясню, звідки береться логарифм.Справа в тому, що дерево зазвичай заповнюється за певними правилами. Наприклад, якщо у вузла максимально може бути всього два дочірні вузли (так зване бінарне дерево), то зазвичай лівий дочірній вузол має значення менше поточного, а праве більше значення. Тому якщо вам потрібно знайти, наприклад, число 30 у дереві з малюнка трохи вище, то вам знадобиться лише 4 порівняння (40 – 25 – 32 – 30). Саме через цю особливість пошуку і береться логарифм (оскільки кожне порівняння скорочує кількість елементів, що перевіряються, в два рази). При цьому зазвичай значення логарифму округляють у більшу сторону.

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

Як бачите, щоб знайти запис з ключем «3» знадобиться 4 порівняння (40 — 25 — 10 — 3), хоча всього записів 5.

Практично у всіх базах даних, існує розподіл унікальності:

Унікальний індекс — це такий індекс, у якого всі значення трапляються лише один раз. Проводячи аналогію, коли кожна книга є тільки в одному примірнику і ніколи назви книг не збігаються.

Неунікальний індекс - Це такий індекс, у якого значення можуть повторюватися. Проводячи аналогію, існують книги з тими самими назвами, але різними авторами, або ж просто зустрічаються копії.

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

Також варто знати, що індекси діляться за кількістю полів, що входять до них:

Звичайні індекси - Складаються з одного поля. Тут, мабуть, усе зрозуміло. Типовий каталог сторінок.

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

Трохи докладніше про складові індекси. Розглянемо аналогію із тими ж книжками. До цього індекс будувався лише за назвою. Тепер уявімо, що книги з однаковими назвами часто зустрічаються. У такій ситуації легко може вийде, що сторінка каталогу складатиметься з координат сотень книг (десятки авторів і в кожного по десять копій). Бігати їх усіх перевіряти — так само багато часу. Тому замість того, щоб сторінка просто перераховувала все місцезнаходження книг, можна зробити так, щоб сторінки з іменами книг вказували на додаткові каталоги, де аналогічно проіндексовані автори.

Трохи спрощуючи пошук буде виглядати приблизно так.

1. Спочатку ви шукайте в каталозі з іменами необхідну сторінку під назвою.

2. Потім у цій сторінці дивіться, де є відповідний каталог з авторами.

3. Берете цей каталог і вже в ньому знаходите сторінку, де вказано розташування всіх книг з цим автором і назвою.

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

Існують і інші моменти, але найчастіше достатньо знати хоча б ці базові знання.