Що таке B tree індекс

B-TREE та HASH індекси

Привіт. Цікавить що таке B-TREE, HASH індекси? Як вони впливають прискорення вибірки? Який їхній синтаксис?

2 відповіді 2

B-tree він же balanced tree індекс, це індекс згрупований за листям збалансованого дерева. Застосовується для великих індексів, це індекс індексів. Ну скажемо індекси з величиною від 1 до 10 зберігаються в одній гілці, від 11 до 20 в іншій і т.д., коли надходить запит на індекс з номером 35, йдемо до 3-ї гілки і знаходимо там 5-й елемент. Загалом якось так. Докладніше тут

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

B-Tree індекс дає швидкість вибірки порядку log(N), hash дає лінійну. У реальному житті hash та B-Tree застосовуються спільно, тобто для обчислення значень B-Tree індексу все одно застосовуються хеші.

> B-tree він же binary tree індекс Це не так. B - balanced - тут означає збалансоване, тобто кожен лист дерева має однакову кількість предків. В результаті доступ до будь-яких даних за допомогою такого індексу здійснюється за однакову кількість кроків.

@ Barmaley а чому hash дає лінійну швидкість? Я просто по душі вважав, що там має бути O(1), якщо колізії не враховувати.

B ДЕРЕВО у структурі даних: пошук, вставка, видалення Operaприклад

Б Дерево являє собою структуру даних, що самобалансується, засновану на певному наборі правил для пошуку, вставки та видалення даних більш швидким і ефективним способом використання пам'яті.Для цього при створенні B-дерева дотримуються наступних правил.

B-дерево – це особливий вид дерева у структурі даних. У 1972 році цей метод був вперше представлений МакКрайтом, і Байєр назвав його "Дерево пошуку зі збалансованою висотою m-way". Це допомагає вам зберігати дані відсортованими та дозволяє виконувати різні операції, такі як вставка, пошук та видалення за менший час.

Правила для B-дерева

Ось важливі правила створення B_Tree.

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

m = 4 max keys: 4 - 1 = 3

m = 4 min keys: 4/2-1 = 1

Навіщо використовувати B-дерево

Ось причини використання B-Tree

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

Історія B-Дерева

Дані зберігаються на диску блоками, ці дані, коли вони вміщуються в основну пам'ять (або ОЗУ), називаються структурою даних.
У разі великих даних пошук одного запису на диску потребує читання всього диска; це збільшує споживання часу та основної пам'яті через високу частоту доступу до диска та розмір даних.
Щоб подолати цю проблему, створюються індексні таблиці, у яких зберігаються посилання записи з урахуванням блоків, де вони перебувають. Це радикально знижує споживання часу та пам'яті.
Оскільки ми маємо величезні дані, ми можемо створювати багаторівневі індексні таблиці.
Багаторівневий індекс можна створити за допомогою B-дерева для сортування даних, що самобалансується.

Пошук Operaвиробництво

Операція пошуку - найпростіша операція в B-дереві.

Застосовується наступний алгоритм:

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

Вставити Operaвиробництво

Оскільки B-дерево є деревом, що самобалансується, ви не можете примусово вставити ключ у будь-який вузол.

Застосовується наступний алгоритм:

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

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

У наведеному вище прикладі:

Знайдіть відповідну позицію у вузлі ключа.
Вставте ключ у цільовий вузол та перевірте наявність правил.
Чи має вузол після вставки більш ніж мінімальна кількість ключів, що дорівнює 1? В даному випадку так і є. Перевірте таке правило.
Чи має вузол після вставки кількість ключів, що перевищує максимальну, що дорівнює 3? У цьому випадку ні, не так.Це означає, що B-дерево не порушує жодних правил і вставку завершено.

У наведеному вище прикладі:

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

У наведеному вище прикладі:

Вузол має менше максимальної кількості ключів
1 вставлена поруч із 3, але правило зростання порушено
Щоб це виправити, ключі відсортовані

Аналогічно, 13 та 2 можна легко вставити у вузол, оскільки вони відповідають правилу меншої кількості ключів для вузлів.

У наведеному вище прикладі:

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

Аналогічно, на основі наведених вище правил і випадків, інші значення можна легко вставити в B-дерево.

Видалити Operaвиробництво

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

Застосовується наступний алгоритм:

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

Якщо цільовий ключ знаходиться в кінцевому вузлі

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

Якщо цільовий ключ знаходиться у внутрішньому вузлі

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

Якщо цільовий ключ знаходиться у кореневому вузлі

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

Тепер розберемося з операцією видалення на прикладі.

На діаграмі вище показані різні випадки операції видалення у B-дереві. Це B-дерево має порядок 5, що означає, що мінімальна кількість дочірніх вузлів, яка може мати будь-який вузол, дорівнює 3, а максимальна кількість дочірніх вузлів, яка може мати будь-який вузол, дорівнює 5. Беручи до уваги, що мінімальна та максимальна кількість ключів будь-якого вузла може мати 2 та 4 відповідно.

У наведеному вище прикладі:

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

У наведеному вище прикладі:

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

Наступна діаграма пояснює, як видалити цей ключ:

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

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

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

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

СТАТТІ ЗА ТЕМОЮ

Дивіться процедуру видалення такого ключа:

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

Видалити OperaПсевдокод

private int removeBiggestElement() < if (root has no child) remove and return the last element else < answer = subset[childCount-1].removeBiggestElement() if (subset[childCount-1].dataCount < MINIMUM) fixShort (childCount- 1) return answer >>

Результат:

Найбільший елемент видаляється з B-дерева.

Разом

B Tree — це структура даних, що самобалансується, для кращого пошуку, вставки та видалення даних з диска.
B Дерево регулюється такою мірою
B Ключі та вузли дерева розташовані в порядку зростання.
Операція пошуку в B-дереві є найпростішою, вона завжди починається з кореня і перевіряє, чи більше або менше цільової ключ значення вузла.
Операція вставки B-дерева досить докладна: спочатку знаходить відповідну позицію вставки для цільового ключа, вставляє її, оцінює достовірність B-дерева для різних випадків, а потім реструктурує вузли B-дерева.
Операція видалення B-дерева спочатку шукає цільовий ключ, який потрібно видалити, видаляє його, оцінює достовірність на основі кількох випадків, таких як мінімальний та максимальний ключі цільового вузла, однорівневих вузлів та батька.

Ви могли б:

SQL-Ex blog

Введення в B-Tree та хеш-індекси в PostgreSQL

У цій статті вивчаються реалізація B-Tree (B означає збалансоване) та структури даних хеш-індексу в PostgreSQL. У міру зростання популярності PostgreSQL як система баз даних з відкритими кодами для розробників і як мета для перенесення робочого навантаження Oracle, розуміння роботи індексів у PostgreSQL винятково важливе для розробників та адміністраторів баз даних. PostgreSQL має кілька інших типів індексів, таких як індекси GIN, індекси GiST та індекси BRIN. У цій статті я не розглядатиму їх, оскільки вони специфічні для пошуку в тексті, географічних та інших складних типів даних. І хоча використання індексу B-Tree покриває приблизно 90% випадків використання, хеш-індекси та їх концепція також важливі для розуміння.

Таблиці PostgreSQL

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

Сторінки даних та індексів

Кожна таблиця та індекс у PostgreSQL складається з масиву сторінок. Сторінка є структурою даних, яка призначена для зберігання записів таблиці чи індексів індексу. Сторінка бази даних PostgreSQL зазвичай має розмір 8Кб, але його можна змінити при компіляції сервера. Оскільки таблиця немає порядку в PostgreSQL, при вставці рядка в таблицю вона потрапляє на першу сторінку, на яку може поміститися. Для цього PostgreSQL відстежує заповнення кожної сторінки за допомогою структури даних, відомої як карта вільного простору (Free Space Map – FSM). Структура FSM містить по одному байти на сторінку, і цей байт показує, наскільки заповнена сторінка. Якщо на жодній сторінці таблиці немає достатньо місця для збереження запису даних, до таблиці додається нова сторінка, на яку і міститься запис.

Вторинні індекси

Кожен індекс PostgreSQL є вторинним індексом - структурою даних, що зберігається окремо від табличної структури купи і містить покажчик деякого типу на таблицю купи. Два типи індексів, на яких я зупинюся сьогодні – це індекс B-Tree та хеш-індекс. Індекс B-Tree є найбільш загальною використовуваною індексною структурою, яка дозволяє виконувати швидкий пошук та сортування даних за мінімальних витрат на зберігання індексу. Хеш-індекси є одностовпцевими індексами, що зберігають 4-байтові результати застосування алгоритму хешування до ключа індексу. Хеш-значення зіставляється із сегментом, у якому зберігається покажчик на рядок у таблиці купи. Я поясню переваги та недоліки хеш-індексу трохи пізніше.

Створимо тестову таблицю для демонстраційних прикладів. Як GUI я використовуватиму DBeaver Community Edition - блискучий інтерфейс для розробки та адміністрування міріадів екземплярів різних баз даних. Для бази даних PostgreSQL я використовуватиму Azure Database for PostgreSQL Flexible Server. Azure спрощує розкручування сервера баз даних PostgreSQL, тому я можу запускати свої демонстрації, а потім швидко демонтувати екземпляр із мінімальними витратами.

Перший крок – це створення тестової бази даних:

create database sqlskills;

Потім скористаємось навичкам SQL і створимо таблицю з ім'ям numbers:

create table numbers (numbercol int, charcol varchar (100));

Я буду використовувати функцію PostgreSQL generate_series для швидкого створення списку з 5000 чисел і випадкових рядкових значень для вставки в таблицю numbers.Зауважте, що я генерую випадкове число у пропозиції ORDER BY для вставки даних у таблицю у випадковому порядку.

insert into numbers (numbercol, charcol)  
select generate_series, left(md5 (random()::text),100)  
від generate_series (1,5000)  
order by random();

Тепер, коли я виконаю запит SELECT до цієї таблиці, дані повертаються у випадковому порядку:

Щоб показати команду CLUSTER у дії, я маю спочатку створити індекс B-Tree на таблиці за допомогою команди CREATE INDEX. Індекс може бути вказаний як ASC або DESC, при цьому ASC приймається за умовчанням. Цей індекс B-Tree упорядкований по стовпцю numbercol таблиці numbers:

create index idx_numbers_numbercol on numbers (numbercol);

І тепер виконання команди CLUSTER, в яку передається ім'я індексу, фізично впорядковує вміст таблиці:

cluster numbers using idx_numbers_numbercol;

Тепер виконання простого SELECT без ORDER BY виводить дані з таблиці в тому самому порядку, який використаний у щойно створеному індексі:

Індекси B-Tree

Індекс у попередньому прикладі є індексом B-Tree (B означає збалансоване). Індекси B-Tree є найбільш загальними та переважними структурами серед реляційних систем управління базами даних (RDBMS – РСУБД). Індекс B-Tree має 2 цілі. Перша та основна мета – забезпечити швидкий та ефективний пошук записів замість виконання послідовного сканування таблиці. Друга допоміжна мета - уможливити швидке сортування даних. Для досягнення обох цих цілей індекс B-Tree зберігає дані, які він містить, у відсортованому порядку та має дерево пошуку.

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

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

select numbercol  
from numbers n  
де numbercol = 2500;

При переміщенні цього індексу B-Tree для знаходження значення 2500 першої опитується коренева сторінка. Коренева сторінка містить першу підказку на карті для пошуку потрібного значення. Значення 2500 більше, ніж значення 2001, тому коренева сторінка направляє пошук на праву сторінку нелистового (проміжного) рівня структури B-Tree, як показано нижче.

На нелистових рівнях індексу B-Tree знаходяться "індексні сторінки", що містять покажчики або на наступний рівень нелистового індексу в дереві, або на листовий рівень індексу. На нелистових рівнях індексні сторінки являють собою двозв'язкові списки, які підтримують логічний порядок в індексі. Для нашого пошуку значення 2500 знаходиться між 2001 та 3001, тому наступною сторінкою для переходу є листова сторінка, що містить 2001 – 3000, як показано нижче.

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

Для наведеного вище запиту ядру PostgreSQL необхідно перевірити лише три сторінки, щоб повернути затребувані дані. Ми можемо легко перевірити це за допомогою команди EXPLAIN. У PostgreSQL команда EXPLAIN використовується для виведення плану виконання оператора SQL. Занурення в деталі, що стосуються команди EXPLAIN, виходять за межі цієї статті; однак я покажу вам, як отримати план виконання для оператора та використовувати опцію BUFFERS, щоб побачити, як багато загальних буферів (сторінок даних у пам'яті) було задіяно для цього оператора.

Для перегляду плану виконання я надрукую ключове слово EXPLAIN перед оператором, план якого хочу отримати, як показано нижче:

explain (analyze, buffers)  
select numbercol  
from numbers n  
де numbercol = 2500;

Після EXPLAIN ключове слово ANALYZE каже PostgreSQL виконати оператора і включити кількість загальних буферів, задіяних для повернення даних. PostgreSQL має велику область виділеної пам'яті, щоб зберігати дані та індексні сторінки для запитів. Сторінки даних повинні витягуватися з диска в цей пул пам'яті, що розділяється, перш ніж дані повертаються кінцевому користувачеві. Зазвичай, що менше загальних буферів задіяно повернення даних користувачу, то швидше запит.

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

Хеш-індекси

Хеш-індекс реалізує варіацію структури даних хеш-таблиці, при якій функція хешування використовує значення ключа індексу, створюючи 4-байтове ціле знакове знакове значення (32 біта), що представляє значення ключа, і зберігає хешоване значення в так званому відрі (bucket), поряд з покажчиком те місце, де знаходиться запис у таблиці купи (по набір кортежів). До PostgreSQL версії 10 хеш-індекси не дуже добре працювали за високо конкурентного навантаження і не підтримували протокол журналізації WAL, це означає, що вони часто будуть пошкоджені у разі відновлення після збою. Однак, оскільки були здійснені поліпшення хеш-індексів, вони безпечні для використання, і в ряді випадків мають перевагу в порівнянні з індексами B-Tree.

Перш ніж я покажу демонстраційний код для створення хеш-індексу, давайте спочатку розглянемо логіку застосування хеш-індексу (це не фактична реалізація — просто логічний погляд). Для цього припустимо, що є поле FirstName, де зберігаються текстові значення. У PostgreSQL є функція hashtext, яка набуває рядкового значення та повертає детерміністичне ціле значення для цього рядка. У цьому випадку моє ім'я відображається на 403,565,329. Стосовно роботи хеш-індексування мисліть шекстекст як першу частину алгоритму хешування.

select hashtext ('Paul') as hashvalue;

Другою частиною алгоритму хешування є відображення виведення хеш-функції на бакет. Структура бакета відображає значення хеш-коду на фактичні рядки таблиці. Бакети реалізовані як сторінки даних у PostgreSQL і, залежно від розміру таблиці, вони можуть відображати кілька різних хеш-значень на той самий бакет - звичайний сценарій, відомий як колізія.Якщо колізії заповнюють сторінку бакета повністю, то виділяється сторінка переповнення для зберігання додаткових хеш-значень і розташування таблиці для хешованого значення рядка. У цьому прикладі я використовую функцію PostgreSQL mod для виведення за модулем 10 (значення залишку від 0 до 9) хеш-значення мого імені:

select mod (hashtext ('Paul'), 10) як bucketpointer;

Це хеш значення відображається на бакет 9.

Погляньмо на створення хеш-індексу. Я знову використовуватиму схему таблиці, яку я створював для індексів B-Tree.

drop table numbers;  
create table numbers (numbercol int, charcol varchar(100));  
insert into numbers (numbercol, charcol)  
select generate_series, left (md5 (random()::text),100)  
від generate_series (1,5000)  
order by random();

Щоб створити хеш-індекс, я маю використовувати пропозицію "using" в операторі CREATE INDEX для вказівки, що індекс є хеш-індексом, а потім вказати в дужках ключовий стовпець. Мені не потрібно раніше включати пропозицію using при створенні індексів B-Tree, т.к. індекс B-Tree є індексом за промовчанням для синтаксису CREATE INDEX.

create index idxhash_numbers_numbercol on numbers using hash (numbercol);

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

explain (analyze)  
select *  
from numbers n  
де numbercol = 2500;

Обмеження хеш-індексів

У попередньому прикладі було показано, як створити хеш-індекс для знаходження єдиного запису таблиці, використовуючи порівняння з унікальним значенням у пропозиції WHERE запиту.Мені довелося використати простий приклад через обмеженість хеш-індексів у випадках їх використання. Хеш-індекси підтримують лише порівняння на рівність під час пошуку. Це обумовлено застосовуваною структурою даних - алгоритм хешування працює з ключем індексу, виробляючи та зберігаючи єдине 4-байтове ціле значення. Щоразу, коли виконується пошук, той самий алгоритм хешування повинен знову застосовуватися до знаку, що розшукується для отримання покажчика на рядок з бакета в цій структурі даних. Тому структура даних не має порядку. Єдиним способом знаходження діапазону значень є читання всієї таблиці виявлення цих значень, при цьому хеш-індекс не буде використовуватися взагалі. Хеш-індекси в PostgreSQL підтримуються тільки для ключа з єдиного стовпця, тому наявність багатостовцевого індексу як хеш-індекс - не варіант. Крім того, хеш-індекси не мають змоги накладати обмеження унікальності.

Переваги хеш-індексу в порівнянні з індексами B-Tree

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

Іншою перевагою хеш-індексів над індексами B-Tree є розмір ключа. Оскільки індекси B-Tree зберігають фактичні значення ключа в структурі індексу, індекс може сильно розроститися. Індекси B-Tree мають обмеження на довжину ключа, який вони зберігають.Хеш-індекси, у свою чергу, не зберігають фактичні значення ключа, а лише 4-байтові значення хешування ключа зі знаком.

І останньою перевагою хеш-індексів над індексами B-Tree полягає в тому, що на розмір хеш-індексу не впливає, наскільки селективним є значення ключа індексу.

Використання B-tree та хеш-індексів

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