Implementing indexes in POSTGRESQL
This article explores the process of designing and implementing a new index access method in the PostgreSQL database management system, using a suffix tree–based index as a case study. Suffix trees provide optimal theoretical search complexity; however, classical descriptions of this data structure...
Saved in:
| Date: | 2026 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
PROBLEMS IN PROGRAMMING
2026
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/888 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| _version_ | 1863673987387621376 |
|---|---|
| author | Zvazhii, D.V. Gorokhovsky, S.S. |
| author_facet | Zvazhii, D.V. Gorokhovsky, S.S. |
| author_sort | Zvazhii, D.V. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-04-27T07:39:08Z |
| description | This article explores the process of designing and implementing a new index access method in the PostgreSQL database management system, using a suffix tree–based index as a case study. Suffix trees provide optimal theoretical search complexity; however, classical descriptions of this data structure assume unlimited memory, arbitrary pointer manipulation, and single-threaded access — conditions that PostgreSQL does not provide. The paper systematically examines the key architectural subsystems of PostgreSQL that directly affect index design: the "one process per connection" multi-process model, page-based storage organization with a fixed 8 KB block size, and the two-level memory management system based on the shared buffer pool and hierarchical memory contexts. Using a concrete implementation as an example, the paper analyzes the key design decisions a developer faces when building a new index: the strategy for mapping logical tree nodes onto physical pages, the organization of intra-page storage for variable-length edges with separation into identification and payload components, the design of the page special area for navigational metadata and suffix links, and mechanisms for page type identification. Particular attention is given to open implementation challenges — edge label compression, parallelism limitations of Ukkonen’s algorithm, and the feasibility of supporting index-only scans. It is shown that implementing a new index structure in a DBMS of PostgreSQL’s caliber is not merely a matter of adapting an algorithm to a specific programming interface, but also of aligning it with the internal invariants, protocols, and subsystem interaction logic that define the permissible space of architectural decisions.Problems in programming 2026; 1: 14-24 |
| first_indexed | 2026-04-24T01:00:15Z |
| format | Article |
| fulltext |
Бази даних
14
© Д.В Зважій, C.C Гороховський, 2026
ISSN 1727-4907. Проблеми програмування. 2026. №1
УДК: 004.658:004.65 https://doi.org/10.15407/pp2026.01.014
Д.В. Зважій , С.С. Гороховський
ВПРОВАДЖЕННЯ ІНДЕКСІВ У POSTGRESQL
У статті досліджено процес проєктування та реалізації нового індексного методу доступу в системі
управління базами даних PostgreSQL на прикладі індексу на основі суфіксного дерева. Суфіксні дерева
забезпечують оптимальну теоретичну складність пошуку, однак класичні описи цієї структури даних
припускають необмежену пам’ять, довільні маніпуляції з вказівниками та однопотоковий доступ —
умови, які PostgreSQL не забезпечує. У роботі послідовно розглянуто ключові архітектурні підсистеми
PostgreSQL, що безпосередньо впливають на проєктування індексних структур: багатопроцесну модель
«один процес на з’єднання», сторінкову організацію зберігання даних із фіксованим розміром блоку 8
КБ, а також дворівневу систему керування пам’яттю на основі спільного пулу буферів та ієрархічних
контекстів пам’яті. На прикладі конкретної реалізації проаналізовано ключові проєктні рішення, з якими
стикається розробник нового індексу: вибір стратегії відображення логічних вузлів дерева на фізичні
сторінки, організацію внутрішньосторінкового зберігання ребер змінної довжини з розділенням на іден-
тифікаційну та змістову частини, проєктування спеціальної області сторінки для навігаційних метаданих
і суфіксних посилань, а також механізми ідентифікації типів сторінок. Окрему увагу приділено відкри-
тим проблемам реалізації — стисненню міток ребер, обмеженням паралелізму алгоритму Укконена та
можливостям підтримки index-only scan.Показано,що впровадження нової індексної структури в системі
управління базами даних рівня PostgreSQL є не лише задачею адаптації алгоритму до конкретного про-
грамного інтерфейсу, а й узгодженням його з внутрішніми інваріантами, протоколами та логікою
взаємодії підсистем, які визначають допустимий простір архітектурних рішень.
Ключові слова: PostgreSQL, індекси, методи доступу, структури даних, керування пам’яттю, узагальнені
суфіксні дерева, архітектура баз даних
D. Zvazhii , S. Gorokhovsky
IMPLEMENTING INDEXES IN POSTGRESQL
This article explores the process of designing and implementing a new index access method in the PostgreSQL
database management system, using a suffix tree–based index as a case study. Suffix trees provide optimal
theoretical search complexity; however, classical descriptions of this data structure assume unlimited memory,
arbitrary pointer manipulation, and single-threaded access — conditions that PostgreSQL does not provide. The
paper systematically examines the key architectural subsystems of PostgreSQL that directly affect index design:
the "one process per connection" multi-process model, page-based storage organization with a fixed 8 KB block
size, and the two-level memory management system based on the shared buffer pool and hierarchical memory
contexts. Using a concrete implementation as an example, the paper analyzes the key design decisions a
developer faces when building a new index: the strategy for mapping logical tree nodes onto physical pages, the
organization of intra-page storage for variable-length edges with separation into identification and payload
components, the design of the page special area for navigational metadata and suffix links, and mechanisms for
page type identification. Particular attention is given to open implementation challenges — edge label
compression, parallelism limitations of Ukkonen’s algorithm, and the feasibility of supporting index-only scans.
It is shown that implementing a new index structure in a DBMS of PostgreSQL’s caliber is not merely a matter
of adapting an algorithm to a specific programming interface, but also of aligning it with the internal invariants,
protocols, and subsystem interaction logic that define the permissible space of architectural decisions.
Keywords: PostgreSQL, indexes, data structures, memory management, generalized suffix trees, database -
architecture
Вступ
У сфері систем управління базами
даних (СУБД) ефективність доступу до
даних є визначальним чинником, що
впливає на масштабованість системи та
рівень затримок. Із переходом обсягів да-
них від гігабайтного до петабайтного мас-
штабу обчислювальні витрати, пов’язані з
операціями доступу, трансформуються з
другорядного аспекту на критичне місце
архітектури. Базовим механізмом доступу
https://pp.isofts.kiev.ua
CC BY 4.0
Бази даних
15
до даних у системі PostgreSQL є
послідовне сканування (Sequential Scan),
яке характеризується часовою складністю
𝑂𝑂(𝑛𝑛) , де 𝑛𝑛 — це потужність множини,
або таблиці. Попри прийнятність
лінійного підходу для малих обсягів да-
них, у середовищах із високою пропуск-
ною здатністю така складність на прак-
тиці може виявитися неефективною.
У цих умовах індексні структури
стають важливим елементом архітектури
СУБД. PostgreSQL вирізняється серед ба-
гатьох інших СУБД не лише тим, що має
відкритий вихідний код, а також завдяки
наявності високорозширюваної індексної
інфраструктури. Окрім традиційних B-
дерев [1], PostgreSQL низку альтернатив-
них методів доступу, — зокрема, Hash [2],
GiST [3], SP-GiST [4][5], GIN [6] і BRIN
[7] — кожен з яких орієнтований на
обробку специфічних типів даних і семан-
тик запитів. Що більш суттєво, Post-
greSQL надає розробникам можливість
визначати власні методи доступу до ін-
дексів, відкриваючи простір для експери-
ментування з новими структурами даних і
адаптації підходів індексування до пред-
метно-орієнтованих задач. Така розши-
рюваність робить PostgreSQL не лише
промисловою системою керування ба-
зами даних, а й ефективною платформою
для проведення наукових досліджень. По-
при високу гнучкість, розроблення нового
типу індексу для PostgreSQL залишається
складним і нетривіальним завданням. Ре-
алізація такого індексу потребує глибо-
кого розуміння внутрішнього програм-
ного інтерфейсу PostgreSQL, моделі кон-
курентного доступу, механізмів ке-
рування буферами, журналювання попе-
реднього запису (write-ahead logging,
WAL), а також особливостей взаємодії з
планувальником запитів. Рішення, що
ухвалюються на рівні індексу, зокрема,
щодо організації сторінок, стратегій
розбиття або гарантування узгодженості,
мають далекосяжні наслідки для корект-
ності, продуктивності та підтримуваності
всієї системи. Як наслідок, багато потен-
ційно цінних індексних концепцій зали-
шаються недостатньо дослідженими або
реалізуються поза межами СУБД, зо-
крема, в прикладних пошукових рушіях
чи зовнішніх системах зберігання даних.
У попередній статті [8] основну
увагу було зосереджено на адаптації спе-
цифікації Access Methods API (програм-
ного інтерфейсу методів доступу) [9], яку
PostgreSQL надає для імплементації ін-
дексу на базі суфіксного дерева.
Натомість у цій статті процес розроб-
лення індексів для PostgreSQL розгля-
дається як із концептуальної, так і з прак-
тичної перспективи. Замість зосере-
дження винятково на використанні наяв-
них типів індексів аналізується, яким чи-
ном у межах розширюваного програм-
ного інтерфейсу методів доступу Post-
greSQL (Access Methods API) можна
проєктувати та реалізовувати нові ін-
дексні структури. Окрему увагу при-
ділено аналізу ключових особливостей
архітектури PostgreSQL [10] та їхнього
впливу на проєктування індексів. Як
практичний приклад розглянуто розробку
індексу на базі суфіксного дерева [11].
Аналіз останніх досліджень та
публікацій
Як уже було зазначено вище, Post-
greSQL надає чітко визначений інтерфейс
для створення власних методів доступу до
індексів і постачається з шістьома вбудо-
ваними типами індексів. Розширюваність
цієї системи спирається на дві фундамен-
тальні концепції. Геллерстайн, Нотон і
Пфеффер [12] запропонували узагальнене
дерево пошуку (GiST), яке об’єднує ви-
сотно збалансовані індекси, зокрема, B+-
дерева та R-дерева, у межах єдиного роз-
ширюваного програмного інтерфейсу.
Проте GiST не здатне репрезентувати за
своєю природою незбалансовані струк-
тури, зокрема, префіксні дерева (trie) або
суфіксні дерева. Валід і Ільяс [4] запропо-
нували для цього SP-GiST — фреймворк
для просторово-роздільних незбалансова-
них дерев (trie, k-d-дерева, квадродерева).
Елтабах, Елтаррас і Ареф [13] реалізували
SP-GiST у PostgreSQL і продемон-
стрували суттєве зростання продуктив-
ності, зокрема, представивши реалізацію
суфіксного дерева для пошуку підрядків.
Бази даних
16
Попри підтримку незбалансованих
структур, SP-GiST має критичне обме-
ження: кожен запис листка відповідає
рівно одному ключу та одному іденти-
фікатору кортежу (TID). Для суфіксних
структур це створює проблему, оскільки
один рядок 𝑠𝑠 довжини 𝑙𝑙 породжує 𝑙𝑙
суфіксів, які мають посилатися на той
самий TID (tuple identifier). Обмеження
«один ключ — один TID» унеможливлює
повноцінну емуляцію поведінки суфікс-
ного дерева або суфіксного масиву в
межах SP-GiST. Нещодавно Шьоманc,
Ареф, Зіманьї та Сакр [14] запропонували
MGiST і MSP-GiST — розширення GiST і
SP-GiST із підтримкою множинних за-
писів, що дозволяють декомпозувати
один об’єкт бази даних на кілька індекс-
них записів за допомогою користуваць-
кого методу ExtractValue. Хоча ці підходи
розроблялися для індексування
траєкторій і визнають проблему обме-
ження «один запис на кортеж», їх досі не
застосовано до суфіксних структур.
Що ж до стуктур даних, які
зберігають суфікси: суфіксні дерева (Вай-
нер [15], Маккрейт [16], Укконен [17]) і
суфіксні масиви (Манбер і Майєрс [18]) -
то вони давно є ґрунтовно дослідженими.
Проте практичні реалізації цих структур у
межах СУБД залишаються вкрай
рідкісними. Сюй, Чен, Хуан, Ху та Нонг
[19] запропонували SAES — систему, що
замінює інвертований індекс Elasticsearch
індексом на основі суфіксного масиву для
повнотекстового пошуку в гетерогенних
даних; це одна з небагатьох спроб інте-
грувати суфіксне індексування в наявну
пошукову інфраструктуру.
Таким чином, існує очевидна про-
галина: попри значну кількість алго-
ритмічних розробок, лише небагато
структур реалізовано як вбудовані методи
доступу до індексів у СУБД, а суфіксні
дерева та масиви практично відсутні в
промислових рушіях баз даних. Запропо-
нована робота спрямована на заповнення
цієї прогалини шляхом реалізації суфікс-
ного індексу як власного методу доступу
PostgreSQL та документування проєктних
рішень, зумовлених її архітектурними об-
меженнями (фіксований розмір сторінки
8 КБ, менеджер буферів, вимоги WAL),
які алгоритмічна література здебільшого
залишає поза увагою.
Реалізація індексу на базі
суфіксного дерева
Задача пошуку підрядків —
знаходження всіх рядків, у яких тексто-
вий стовпець містить заданий шаблон, є
поширеною в базах даних. Стандартні B-
деревні індекси ефективно прискорюють
префіксні запити (наприклад, LIKE
’pattern%’), однак не допомагають у
випадку ведучих байдужих символів
(LIKE ’%pattern%’), що змушує систему
виконувати послідовне сканування ко-
лонки. Суфіксні дерева забезпечують по-
шук за шаблоном за час 𝑂𝑂(𝑚𝑚 + 𝑘𝑘) [20], де
𝑚𝑚 — довжина шаблону, незалежно від
розміру тексту, а 𝑘𝑘 - кількість можливих
повторів шаблону. Це робить суфіксні де-
рева теоретично привабливими для цієї
задачі. Втім, класичні описи суфіксних
дерев у підручниках припускають необ-
межену пам’ять, довільні маніпуляції з
вказівниками та однопотоковий доступ.
PostgreSQL не надає жодної з цих переду-
мов. Натомість він оперує сторінками
фіксованого розміру, спільним пулом бу-
ферів із суворими протоколами pinning,
обов’язковим журналюванням попе-
реднього запису (WAL) і конкурентним
доступом з боку кількох бекендів. Інте-
грація суфіксного дерева в таке середо-
вище вимагає ухвалення проєктних
рішень, які теоретична література зазви-
чай не розглядає. Цей розділ зосередже-
ний на деталях реалізації індексу на базі
суфіксного дерева. Спочатку окреслено
архітектурні обмеження PostgreSQL,
після чого розглядаються важливі
проєктні рішення з якими зіштовхується
розробник під час реалізації. Для конкре-
тизації наводяться приклади із конкретної
реалізації індексу на базі суфіксного де-
рева [11].
PostgreSQL зберігає всі дані у
сторінках фіксованого розміру — зазви-
чай 8192 байти (8 КБ), який задається на
етапі компіляції параметром BLCKSZ. Це
обмеження є всеосяжним: у його межах
працюють кожна індексна сторінка,
Бази даних
17
сторінка heap і записи журналу WAL. Для
суфіксного дерева це одразу породжує
низку питань. Вузол із великою кількістю
вихідних ребер може не вміститися в одну
сторінку. Мітка ребра може мати довільну
довжину. Розмір сторінки не підлягає
зміні — реалізації мають проєктуватися з
урахуванням цього обмеження. Фактично
доступний для даних простір сторінки є
меншим за BLCKSZ. Кожна сторінка
містить 24-байтовий заголовок
(PageHeaderData) і також зазвичай ре-
зервує певний простір наприкінці
сторінки для типоспецифічних метаданих
(так звана special area). Для сторінки роз-
міром 8 КБ приблизно 8140 байтів до-
ступні для безпосереднього вмісту, а у
випадку використання значної спеціаль-
ної області — навіть менше. Кожна
сторінка PostgreSQL має стандартну
внутрішню структуру. Заголовок
сторінки містить вказівники (pd_lower,
pd_upper), які окреслюють межі між зайня-
тою та вільною частинами сторінки. Ме-
тоди доступу можуть зарезервувати
спеціальну область (special area) напри-
кінці сторінки для типоспецифічних мета-
даних.
Розмір спеціальної області
фіксується під час ініціалізації сторінки.
Саме тут методи доступу зазвичай
зберігають навігаційні вказівники (на
батьківські та сусідні сторінки), прапорці
типу сторінки та ідентифікаційні мар-
кери. Проєктування цієї структури є од-
ним із ключових ранніх рішень, оскільки
її розмір і вміст безпосередньо впливають
як на доступний простір для даних, так і
на можливості еволюції індексної струк-
тури.
Менеджер буферів PostgreSQL
опосередковує весь доступ до сторінок.
Сторінки ніколи не зчитуються безпосе-
редньо з диска; натомість бекенд-процеси
запитують буфери за чітко визначеним
протоколом:
- Читання: ReadBuffer(relation,
blockno) — фіксує (pin) сторінку в
пулі буферів.
- Блокування: LockBuffer(buffer,
mode) — захоплює спільне або
виключне блокування.
- Доступ: BufferGetPage(buffer) — по-
вертає вказівник на сторінку.
- Модифікація: Mark-
BufferDirty(buffer) — сигналізує, що
сторінку було змінено.
- Звільнення: UnlockRelease-
Buffer(buffer) — знімає блокування.
Утримання буфера в стані pinned запобігає
витісненню сторінки з пулу, а утримання
блокування перешкоджає конкурентним
модифікаціям або забезпечує стабільність
читання. Критично важливим наслідком є
унеможливлення збереження сирих
вказівників на сторінках між операціями з
буферами: після звільнення буфера будь-
який вказівник на його вміст стає
недійсним. Для алгоритмів обходу дерев,
які концептуально “спускаються” шляхом
від кореня до листка, це означає необ-
хідність вибору між двома підходами: або
одночасно утримувати кілька буферів у
стані pinned (що підвищує ризик взаємних
блокувань), або повторно зчитувати
сторінки після їхнього звільнення. Оби-
два варіанти накладають суттєві обме-
ження на проєктування структур даних і
алгоритмів навігації в межах індексів
PostgreSQL.
Розподілювач пам’яті PostgreSQL
(palloc) працює в межах контекстів пам’яті
— ієрархічних арен, які можна скидати
або знищувати масово. Код методів до-
ступу зазвичай виконується в контекстах
відповідного кортежу (per-tuple contexts),
що скидаються після оброблення кожного
кортежу.
Із цього випливає важливе правило: не
можна зберігати вказівники на пам’ять,
виділену через palloc, за межами оброб-
PageInit(page, BLCKSZ,
sizeof(MyOpaqueData));
opaque = (MyOpaque) PageGetSpe-
cialPointer(page);
Лістинг 1: Ініціалізація спеціальної
частини сторінки
Бази даних
18
лення окремого кортежу. Будь-які до-
поміжні структури даних мають або роз-
міщуватися в контексті з довшим часом
життя, або відновлюватися заново для
кожного кортежу.
PostgreSQL гарантує надійність
збереження даних за допомогою жур-
налювання попереднього запису (write-
ahead logging, WAL): усі зміни мають
бути зафіксовані в журналі до того, як мо-
дифікована сторінка буде записана на
диск. Для методів доступу це має два
ключові прояви:
- Критичні секції. Модифікації, які
повинні бути атомарними,
обгортаються в START_CRIT_SEC-
TION() / END_CRIT_SECTION().
Усередині критичної секції будь-
яка помилка призводить до PANIC
(перезапуску бази даних), а не до
подовження неузгодженого стану
системи.
- WAL-записи. Складні методи до-
ступу генерують власні типи
WAL-записів. Простіші реалізації
можуть покладатися на повні зоб-
раження сторінок (full-page im-
ages) під час початкової побудови
індексу, уникаючи детального
журналювання кожної окремої
зміни.
Для інкрементних вставок коректне жур-
налювання WAL вимагає проєктування
форматів записів і реалізації процедур по-
вторного відтворення (redo), що є склад-
ним і трудомістким завданням.
PostgreSQL визначає методи до-
ступу до індексів за допомогою структури
IndexAmRoutine [8], яка задає підтримувані
можливості та набір зворотних викликів
(callbacks), показаний на лістингу 3. Ін-
терфейс також декларує можливості ме-
тоду доступу: чи може індекс забезпечу-
вати унікальність, чи підтримує багато-
стовпцеві ключі, чи здатен повертати кор-
тежі у впорядкованому вигляді тощо. Для
суфіксного дерева, орієнтованого на по-
шук підрядків, більшість із цих можливо-
стей відсутня: індекс не забезпечує
унікальність, не підтримує впорядку-
вання результатів і працює лише з одним
текстовим стовпцем.
Під час проєктування індексу ви-
никає необхідність зберігання різних
структур, тому індекс може містити
сторінки різних типів — сторінки метада-
них, вузли дерева, сторінки переповнення
для великих записів, а також сторінки для
відстеження вільного простору. Під час
читання сторінки реалізація методу до-
ступу повинна однозначно визначити її
тип. Крім того, діагностичні інструменти
на кшталт pg_filedump отримують істотну
користь від можливості ідентифікувати
тип індексної сторінки без знання при-
кладного контексту. Для розв’язання цієї
задачі застосовуються різні підходи:
oldCtx = MemoryCon-
textSwitchTo(buildState->tmpMem-
Ctx);
MemoryContextSwitchTo(oldCtx);
MemoryContextReset(buildState-
>tmpMemCtx); PageGetSpe-
cialPointer(page);
Лістинг 2: Приклад зміни контексту під
час індексації кортежу
amroutine->ambuild =
stree_build;
amroutine->ambuildempty =
stree_empty;
amroutine->aminsert = stree_in-
sert;
amroutine->ambeginscan =
stree_beginscan;
amroutine->amgettuple =
stree_gettuple;
amroutine->amendscan =
stree_endscan;
Лістинг 3: Ключові функції зворотнього
виклику методу доступу
Бази даних
19
- фіксовані номери блоків — окремі
номери блоків мають фіксоване
призначення (наприклад, мета-
сторінка в блоці 0);
- використання відведених кон-
стант, записаних у визначене
місце сторінки;
- збереження міток типу сторінки у
спеціальній області сторінки
(special area).
Схема з фіксованими номерами блоків
може спрацювати, якщо є можливість по-
передньо зарезерувати під них пам’ять,
але непридатна для сторінок, які будуть
виділені динамічно під час вставок.
Числа-константи забезпечують надійну
ідентифікацію, проте споживають простір
і потребують координації, щоб уникнути
колізій між різними методами доступу. У
практиці PostgreSQL зазвичай поєднують
компактні мітки типу сторінки з фіксова-
ним ідентифікатором методу доступу,
розміщеним у спеціальній області
сторінки (наприклад, streePageId =
0xCDEE). Такий підхід дає змогу ро-
зрізняти типи сторінок як усередині ін-
дексу, так і між різними індексними
структурами, забезпечуючи зручність під
час налагодження та валідації сторінок
під час обходу — за незначної додаткової
вартості простору, оскільки спеціальна
область зазвичай уже містить навігаційні
метадані.
Якщо говорити про стуктури, які повинен
зберігати індекс, то можна виділити такі
складові дерева як вузли, ребра та іденти-
фікатори кортежів (TID - tuple identifier),
які буде повертати індекс. Ці типи даних
суттєво відрізняються за розмірами, шаб-
лонами доступу та характером зростання,
що створює нетривіальну задачу відобра-
ження їх на сторінки фіксованого розміру
PostgreSQL так, щоб забезпечити ефек-
тивну побудову індексу та швидкий по-
шук. Розміри вузлів суфіксного дерева
можуть істотно варіюватися. Вузол по-
близу кореня може мати вихідні ребра для
сотень різних символів, тоді як вузол гли-
боко в дереві часто має лише одне ребро.
Це породжує питання відображення: як
співвіднести логічні вузли дерева для
зберігання на фізичних сторінках. Можна
виділити три основні підходи:
- Один вузол на сторінку: кожен ву-
зол дерева займає рівно одну
сторінку розміром 8 КБ, а номер
блоку (BlockNumber) слугує його
ідентифікатором — без потреби в
додатковій адресації.
- Кілька вузлів на сторінці: дрібні
вузли пакуються разом для змен-
шення втрат простору. Це вимагає
внутрішньосторінкової адресації
(номер блоку + зсув) і ускладнює
логіку росту вузлів.
- Вузли, що розтягуються на кілька
сторінок: великі вузли можуть
мати сторінки-продовження, що
дозволяє підтримувати довільні
розміри, але додає складності під
час обходу й синхронізації.
Модель “один вузол — одна сторінка”
природно узгоджується з менеджером бу-
ферів PostgreSQL. Закріплення (pinning)
вузла означає фіксацію рівно одного бу-
фера, а його звільнення— звільнення того
самого буфера. Відсутні часткові блоку-
вання вузла, міжсторінкова узгодженість і
складна адресна арифметика. Основний
недолік цього підходу — неефективне ви-
користання простору: листковий вузол з
#define STREE_META
(1<<0)
#define STREE_ROOT
(1<<1)
#define STREE_INTERNAL_NODE
(1<<2)
#define STREE_DATA_PAGE
(1<<3)
typedef struct STreeNodePage-
OpaqueData {
uint16 flags;
/* ... інші поля ... */
} STreeNodePageOpaqueData;
Лістинг 4: Приклад використання міток
сторінки
Бази даних
20
одним ребром і мінімальними метада-
ними може займати лише близько 100
байтів із 8 КБ, що означає до 98% втрат.
Для дерева з мільйонами дрібних вузлів
це може становити значні накладні вит-
рати. Водночас суфіксні дерева мають ко-
рисну властивість: кількість внутрішніх
вузлів обмежена сумарною довжиною ін-
дексованих рядків. Дерево, що індексує N
символів, містить не більше ніж N
внутрішніх вузлів. Отже, просторові
накладні витрати, хоч і відчутні, зроста-
ють лінійно — 𝑂𝑂(𝑛𝑛) сторінок — і не є не-
контрольованими. З огляду на це, для по-
чаткової реалізації підхід “один вузол на
сторінку” пропонує переконливий баланс
між простотою та коректністю. У власній
реалізації [11] був використаний розши-
рений варіант, який дозволяє вузлу розро-
статися на нову сторінку, якщо було вико-
ристано увесь вільний простір. Оп-
тимізації на кшталт пакування дрібних
вузлів доцільно відкласти до наступної
ітерації — коли стане зрозуміло, що саме
використання простору, а не складність
алгоритмів, є головним вузьким місцем.
Вузол суфіксного дерева також
зберігає набір вихідних ребер, кожне з
яких складається з мітки змінної довжини
та вказівника на цільовий вузол. У про-
цесі побудови суфіксного дерева алго-
ритм Укконена [17] багаторазово виконує
три базові операції над ребрами:
- пошук ребра, що починається з за-
даного символу;
- вставка нового ребра з певною
міткою та призначенням;
- поділ наявного ребра, коли його
мітка скорочується на позиції 𝑘𝑘 та
перенаправляється до нового
внутрішнього вузла.
Дизайн сторінки індексу має ефективно
підтримувати всі ці операції, оскільки
кожна з них по-різному модифікує вміст
сторінки, а обсяг змін безпосередньо
впливає на розміри WAL-записів і ча-
стоту позначення буферів як “брудних”.
Найчастішою операцією є пошук: на кож-
ному кроці оброблення вхідного рядка ал-
горитм перевіряє, чи існує ребро з
відповідним початковим символом. Це
вимагає організації ребер у формі, зручній
для пошуку — наприклад, шляхом
зберігання у відсортованому вигляді з
можливістю бінарного пошуку або за до-
помогою хешування. Вставка додає нові
дані до сторінки: якщо ребра зберігаються
компактно й упорядковано, вставка по-
требує зсуву всіх наступних елементів. У
схемах з апендиксним додаванням ко-
рисних даних і окремим індексом вставка
самих даних має амортизовану складність
𝑂𝑂(1), а підтримка впорядкування — 𝑂𝑂(𝑛𝑛)
за кількістю ребер. Ключовою операцією,
яка впливає на дизайн структури
сторінки, є операція поділу ребра. Під час
розщеплення ребра 𝑒𝑒 на позиції 𝑘𝑘 його
мітка, наприклад, ABCDEF, перетво-
рюється на префікс AB, створюється но-
вий внутрішній вузол із ребром CDEF, а
призначення початкового ребра
змінюється на цей новий вузол.
Вирішальним є питання: чи можна скоро-
тити мітку на місці, не переміщуючи
байти в пам’яті, адже переміщення даних
істотно збільшує обсяг модифікацій
сторінки та відповідне WAL-
журналювання. Ефективним розв’язан-
ням цієї проблеми є відокремлення струк-
тури ребра, необхідної для пошуку
(наприклад, першого символу), від його
корисного навантаження — повної мітки
та вказівника призначення.
Це дозволяє організувати сторінку, яка
зростатиме у два напрямки (Рис.1):
typedef struct EdgeId {
pg_wchar firstChar;
uint16 payloadOffset;
uint16 payloadLength;
} EdgeId;
typedef struct EdgePayload {
BlockNumber destination;
uint16 labelLength;
char label[];
} EdgePayload;
Лістинг 5: Представлення ребра
Бази даних
21
- масив ідентифікаторів ребер зрос-
тає від заголовка сторінки,
зберігаючи впорядкованість за
першим символом;
- корисні дані ребер додаються
апендиксом з боку спеціальної об-
ласті сторінки, тобто у протилеж-
ному напрямку.
За такої організації вставка нового ребра з
початковим символом 𝑐𝑐 виконується че-
рез бінарний пошук позиції, зсув еле-
ментів масиву ідентифікаторів, запис но-
вого ідентифікатора та додавання ко-
рисних даних у верхній частині вільного
простору.
Архітектура сторінки, що дозволяє
рости в обидва напрямки, розв’язує за-
дачу зберігання ребер, однак вузол
суфіксного дерева містить значно більше,
ніж лише ребра. Під час побудови та ви-
користання дерева алгоритм повинен пе-
реміщатися між вузлами різними шля-
хами:
- переходити за суфіксними поси-
ланнями під час побудови за Укко-
неном,
- підніматися до батьківських
вузлів у певних сценаріях віднов-
лення або перевірки коректности,
- ітеруватися по сторінках даних під
час збирання ідентифікаторів кор-
тежів (TID).
PostgreSQL резервує наприкінці кожної
сторінки простір для даних, специфічних
для методу доступу, — до якого зверта-
ються через PageGetSpecialPointer(). Для
вузлів суфіксного дерева ця спеціальна
область містить як навігаційні вказівники,
так і ідентифікаційну інформацію про тип
сторінки. Зокрема, тут зберігаються:
- parentNode - забезпечує
можливість руху вгору по ієрархії.
Хоча алгоритм Укконена
здебільшого виконує обхід дерева
від кореня до листків, у деяких
ситуаціях, наприклад, під час
відновлення або перевірки
цілісності структури, потрібен
підйом до батьківського вузла.
Явне зберігання посилання на
батька дозволяє уникнути
підтримки окремого стеку обходу.
- suffixLink - ключове поле для до-
сягнення лінійної складності O(n)
під час побудови дерева за алго-
ритмом Укконена [17]. Після ство-
рення або відвідування
внутрішнього вузла, що відповідає
суфіксу 𝑆𝑆[𝑖𝑖. . 𝑗𝑗], це посилання вка-
зує на вузол для 𝑆𝑆[𝑖𝑖 + 1. . 𝑗𝑗]. Такий
перехід між спорідненими суфік-
сами виконується за сталий час.
Без механізму суфіксних посилань
складність побудови зростала б до
𝑂𝑂(𝑛𝑛²).
- itemPointersStart - вказує на першу
сторінку в ланцюжку сторінок, що
зберігають TID. Вузол, який
відповідає поширеному підрядку,
може відповідати тисячам рядків у
heap; ідентифікатори кортежів не
зберігаються у вузлі разом із
ребрами, а виносяться в окремі
пов’язані сторінки, щоб не
перевантажувати основну
структуру вузла.Рис. 1. Дизайн сторінки, яка зберігає ребра
Бази даних
22
- prevSiblingNode та nextSiblingNode
- формують двобічно зв’язаний
список сторінок переповнення для
TID та ребер. Коли сторінка даних
заповнюється, виділяється нова й
приєднується до ланцюжка через
ці вказівники.
- streePageId - число-константа
(наприклад, 0xCDEE), що одно-
значно ідентифікує сторінку як
сторінку суфіксного дерева. Це
дозволяє при відлагодженні
розпізнавати тип сторінки без по-
треби інтерпретувати її
внутрішню структуру.
- flags - містить прапорці, що визна-
чають роль сторінки: коренева,
внутрішня, сторінка даних (TID).
Це дає змогу застосовувати
спеціалізовану логіку під час об-
ходу та оброблення індексу.
Попри отримане рішення 11, низка
проєктних аспектів залишається склад-
ною й потребує додаткового осмислення.
Однією з найбільш проблемних зон є
взаємодія з механізмом VACUUM і
оброблення видалень. Коли рядок у heap
видаляється, його TID необхідно вилу-
чити з усіх вузлів індексу, де він
зберігається. Це означає або повне ска-
нування структури індексу, або
підтримку зворотних посилань від TID до
відповідних вузлів. Обидва підходи ма-
ють суттєві недоліки: перший пов’язаний
із високими обчислювальними витрат-
ами, другий — ускладнює структуру ін-
дексу та збільшує накладні витрати на
зберігання й супровід додаткових метада-
них. Іншим складним напрямом є стис-
нення. Мітки ребер у суфіксному дереві
часто мають спільні префікси, оскільки
вони є суфіксами тих самих або подібних
рядків. Теоретично можливо застосо-
вувати словникове стиснення або схеми
на основі посилань для зменшення обсягу
зберігання. Однак такі оптимізації
ускладнюють логіку вставки, розщеп-
лення ребер і журналювання змін у WAL,
що своєю чергою, збільшує складність ре-
алізації та підвищує ризик помилок. Пи-
тання паралелізму також є нетривіаль-
ним. Хоча PostgreSQL підтримує пара-
лельну побудову індексів, класичний ал-
горитм Укконена по суті є послідовним—
через залежності, пов’язані з підтримкою
суфіксних посилань. Це обмежує мож-
ливість прямого використання механізмів
паралельного виконання. Альтернативні
підходи, зокрема, алгоритми паралельної
побудови суфіксних масивів, потенційно
могли б забезпечити кращу масштабо-
ваність, однак потребують докорінно ін-
шої організації індексної структури.
Нарешті, слід враховувати обмеження ме-
ханізму index-only scan. У PostgreSQL цей
режим дає змогу уникати звернень до
heap, якщо індекс містить усі необхідні
для запиту стовпці. У випадку суфіксного
дерева, яке індексує лише текстовий стов-
пець, повернення самого тексту без звер-
нення до heap вимагало б зберігання його
в самому індексі, що ускладнює завдання
зменшення обсягу структури.
Висновки
Реалізація суфіксного дерева як ін-
дексної структури в PostgreSQL передба-
чає інтеграцію теоретично елегантної мо-
делі в складну, багаторівневу архітектуру
промислової СУБД. У цьому процесі
кожне проєктне рішення, пов’язане з
необхідністю балансувати між просторо-
вою ефективністю, часовими характери-
стиками операцій, складністю реалізації
typedef struct STreeNodePage-
OpaqueData {
BlockNumber parentNode;
BlockNumber suffixLink;
BlockNumber
BlockNumber prevSiblingNode;
BlockNumber nextSiblingNode;
uint16 streePageId;
uint16 flags;
} STreeNodePageOpaqueData;
Лістинг 6: Структура спеціального
простору сторінки
Бази даних
23
та вимогами до транзакційної надійності
й відновлення після збоїв.
Проаналізовані питання — іденти-
фікація сторінок, організація внутрішньої
архітектури сторінки, відображення
логічних вузлів на фізичні сторінки,
зберігання міток, розміщення TID,
взаємодія з буферним менеджером репре-
зентують лише частину спектру рішень,
які необхідно ухвалити. Повноцінна ре-
алізація неминуче потребує десятків до-
даткових виборів на більш дрібному рівні,
кожен з яких впливає на загальну по-
ведінку системи.
Водночас кожна система рівня
складності сучасної СУБД фактично фор-
мує власний внутрішній програмний кар-
кас— набір інтерфейсів, інваріантів і про-
токолів взаємодії, які визначають, як саме
окремі компоненти можуть співпрацю-
вати. Цей каркас не є нейтральним: він за-
дає допустимі способи розширення, об-
межує архітектурні рішення та формує ха-
рактер компромісів, які доводиться прий-
мати розробникові. Тому впровадження
нової індексної структури — це не лише
адаптація алгоритму до конкретного про-
грамного інтерфейсу, а й узгодження його
з глибинною логікою взаємодії підсистем.
Література
1. Comer D. Ubiquitous B-Tree. ACM Comput.
Surv. 11. 1979. Vol. 11., no.2. P.121–37.
URL:
https://doi.org/10.1145/356770.356776.
(date of access: 08.05.2025)
2. Hash Indexes. PostgreSQL Documentation.
URL: https://www.post-
gresql.org/docs/17/hash-index.html.
(date of access: 08.05.2025)
3. GiST Indexes. PostgreSQL Documentation.
URL: https://www.post-
gresql.org/docs/17/gist.html.
(date of access: 08.05.2025)
4. Walid A.G., Ilyas I. F. SP-GiST: An Exten-
sible Database Index for Supporting Space
Partitioning Trees. Journal of Intelligent In-
formation Systems. 2001. Vol. 11., no.2.
P.215–40. URL:
https://doi.org/10.1023/A:1012809914301.
(date of access: 25.01.2026)
5. SP-GiST Indexes. PostgreSQL Documenta-
tion. URL: https://www.post-
gresql.org/docs/17/spgist.html.
(date of access: 08.05.2025)
6. GIN Indexes. PostgreSQL Documentation.
URL: https://www.post-
gresql.org/docs/17/gin.html.
(date of access: 08.05.2025)
7. BRIN Indexes. PostgreSQL Documentation.
URL: https://www.post-
gresql.org/docs/17/brin.html.
(date of access: 08.05.2025)
8. Зважій Д. Особливості Індексації у Post-
greSQL. Наукові Записки НаУКМА.
Комп’ютерні Науки. 2025.№. 8.С. 113–17.
DOI: 10.18523/2617-3808.2025.8.113-117.
(дата звернення: 25.01.2026)
9. Basic API Structure for Indexes. PostgreSQL
Documentation. URL: https://www.post-
gresql.org/docs/17/index-api.html.
(date of access: 08.05.2025)
10. Stonebraker M., Rowe L. A. The design of
POSTGRES. SIGMOD. 1986. Vol. 15., no. 2
P. 340—355. DOI: 10.1145/16856.16888.
URL:
https://dl.acm.org/doi/10.1145/16856.16888.
(дата зверн. 25.01.2026)
11. Suffix Tree Based AM Index Method Source
Code. URL:
https://github.com/Uaman/postgres/tree/feat
ure-string-search-am.
(date of access: 10.02.2026)
12. Hellerstein J. M., Naughton J. F., Pfeffer A.
Generalized Search Trees for Database Sys-
tems. Encyclopedia of Database Systems
Morgan Kaufmann Publishers Inc. 1998.
P.1-3. URL: https://doi.org/10.1007/978-1-
4899-7993-3_743-2
(date of access: 15.02.2026)
13. Eltabakh M., Ramy E., Walid A. Space-Par-
titioning Trees in PostgreSQL: Realization
and Performance. 2006. URL:
https://doi.org/10.1109/ICDE.2006.146.
(date of access: 08.05.2025)
14. Schoemans M., Walid G. A., Zimányi E.,
Sakr M. Multi-Entry Generalized Search
Trees for Indexing Trajectories. Proceedings
of the 32nd ACM International Conference
on Advances in Geographic Information Sys-
tems. 2024. P.21–31. URL:
https://doi.org/10.1145/3678717.3691320.
(date of access: 15.02.2026)
15. Weiner P. Linear Pattern Matching Algo-
rithm. 1973. URL:
https://doi.org/10.1109/SWAT.1973.13.
(date of access: 10.02.2026)
Бази даних
24
16. McCreight E. M. A Space-Economical Suffix
Tree Construction Algorithm. J. ACM . 1976.
Vol.23., no.2. P.262–72. URL:
https://doi.org/10.1145/321941.321946.
(date of access: 15.02.2026)
17. Ukkonen E.. On-Line Construction of Suffix
Trees. Algorithmica. 1995. Vol.14., no.3
P.249–60. URL:
https://doi.org/10.1007/BF01206331.
(date of access: 10.02.2026)
18. Manber U., Gene M. Suffix Arrays: A New
Method for on-Line String Searches. SIAM
Journal on Computing. 1993. Vol. 22., no. 5:
P.935–48. URL:
https://doi.org/10.1137/0222058.
(date of access: 15.02.2026)
19. Xu W., Haoyu C., Yidong H., Xuedong H.,
Ge N. Full-Text Search Engine with Suffix
Index for Massive Heterogeneous Data. In-
formation Systems. 2022. URL:
https://doi.org/10.1016/j.is.2021.101893.
(date of access: 10.02.2026)
20. Gusfield D. Algorithms on Strings, Trees,
and Sequences: Computer Science and Com-
putational Biology. Cambridge University
Press. 1997. URL:
https://doi.org/10.1017/CBO9780511574931.
(date of access: 08.05.2025)
Дата першого надходження до видання:
17.02.2026
Внутрішня рецензія отримана: 25.02.2026
Зовнішня рецензія отримана: 25.02.2026
Дата прийняття статті до друку: 19.03.2026
Дата публікації: 16.04.2026
Про авторів:
Зважій Дмитро Володимирович,
аспірант,
старший викладач кафедри мережних
технологій факультету інформатики,
Zvazhii Dmytro,
Post-graduate student, senior tutor
https://orcid.org/0000-0003-1705-3590
E-mail: d.zvazhii@ukma.edu.ua
Гороховський Семен Самуїлович,
кандидат фізико-математичних наук,
доцент кафедри інформатики факультету
інформатики,
Gorokhovsky Semen,
Ph.D (physical and mathematical sciences),
associate professor
E-mail: gor@ukma.edu.ua
Місце роботи авторів:
Національний університет
«Києво-Могилянська академія»,
04655, Україна, Київ,
вул. Григорія Сковороди 2,
National University
“Kyiv–Mohyla Academy”,
faculty of informatics
E-mail: fin@ukma.edu.ua
|
| id | pp_isofts_kiev_ua-article-888 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-04-28T01:00:15Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/08/98a3d2b36f5684852b61ff036e83a508.pdf |
| spelling | pp_isofts_kiev_ua-article-8882026-04-27T07:39:08Z Implementing indexes in POSTGRESQL Впровадження індексів у POSTGRESQL Zvazhii, D.V. Gorokhovsky, S.S. PostgreSQL; indexes; data structures; memory management; generalized suffix trees; database architecture UDC 004.658:004.65 PostgreSQL; індекси; методи доступу; структури даних; керування пам’яттю; узагальнені суфіксні дерева; архітектура баз даних УДК: 004.658:004.65 This article explores the process of designing and implementing a new index access method in the PostgreSQL database management system, using a suffix tree–based index as a case study. Suffix trees provide optimal theoretical search complexity; however, classical descriptions of this data structure assume unlimited memory, arbitrary pointer manipulation, and single-threaded access — conditions that PostgreSQL does not provide. The paper systematically examines the key architectural subsystems of PostgreSQL that directly affect index design: the "one process per connection" multi-process model, page-based storage organization with a fixed 8 KB block size, and the two-level memory management system based on the shared buffer pool and hierarchical memory contexts. Using a concrete implementation as an example, the paper analyzes the key design decisions a developer faces when building a new index: the strategy for mapping logical tree nodes onto physical pages, the organization of intra-page storage for variable-length edges with separation into identification and payload components, the design of the page special area for navigational metadata and suffix links, and mechanisms for page type identification. Particular attention is given to open implementation challenges — edge label compression, parallelism limitations of Ukkonen’s algorithm, and the feasibility of supporting index-only scans. It is shown that implementing a new index structure in a DBMS of PostgreSQL’s caliber is not merely a matter of adapting an algorithm to a specific programming interface, but also of aligning it with the internal invariants, protocols, and subsystem interaction logic that define the permissible space of architectural decisions.Problems in programming 2026; 1: 14-24 У статті досліджено процес проєктування та реалізації нового індексного методу доступу в системі управління базами даних PostgreSQL на прикладі індексу на основі суфіксного дерева. Суфіксні дерева забезпечують оптимальну теоретичну складність пошуку, однак класичні описи цієї структури даних припускають необмежену пам’ять, довільні маніпуляції з вказівниками та однопотоковий доступ — умови, які PostgreSQL не забезпечує. У роботі послідовно розглянуто ключові архітектурні підсистеми PostgreSQL, що безпосередньо впливають на проєктування індексних структур: багатопроцесну модель «один процес на з’єднання», сторінкову організацію зберігання даних із фіксованим розміром блоку 8 КБ, а також дворівневу систему керування пам’яттю на основі спільного пулу буферів та ієрархічних контекстів пам’яті. На прикладі конкретної реалізації проаналізовано ключові проєктні рішення, з якими стикається розробник нового індексу: вибір стратегії відображення логічних вузлів дерева на фізичні сторінки, організацію внутрішньосторінкового зберігання ребер змінної довжини з розділенням на іден тифікаційну та змістову частини, проєктування спеціальної області сторінки для навігаційних метаданих і суфіксних посилань, а також механізми ідентифікації типів сторінок. Окрему увагу приділено відкри тим проблемам реалізації — стисненню міток ребер, обмеженням паралелізму алгоритму Укконена та можливостям підтримки index-onlyscan. Показано,що впровадження нової індексної структури в системі управління базами даних рівня PostgreSQL є не лише задачею адаптації алгоритму до конкретного програмного інтерфейсу, а й узгодженням його з внутрішніми інваріантами, протоколами та логікою взаємодії підсистем, які визначають допустимий простір архітектурних рішень.Problems in programming 2026; 1: 14-24 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-04-23 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/888 PROBLEMS IN PROGRAMMING; No 1 (2026); 14-24 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2026); 14-24 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2026); 14-24 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/888/941 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | PostgreSQL indexes data structures memory management generalized suffix trees database architecture UDC 004.658:004.65 Zvazhii, D.V. Gorokhovsky, S.S. Implementing indexes in POSTGRESQL |
| title | Implementing indexes in POSTGRESQL |
| title_alt | Впровадження індексів у POSTGRESQL |
| title_full | Implementing indexes in POSTGRESQL |
| title_fullStr | Implementing indexes in POSTGRESQL |
| title_full_unstemmed | Implementing indexes in POSTGRESQL |
| title_short | Implementing indexes in POSTGRESQL |
| title_sort | implementing indexes in postgresql |
| topic | PostgreSQL indexes data structures memory management generalized suffix trees database architecture UDC 004.658:004.65 |
| topic_facet | PostgreSQL indexes data structures memory management generalized suffix trees database architecture UDC 004.658:004.65 PostgreSQL індекси методи доступу структури даних керування пам’яттю узагальнені суфіксні дерева архітектура баз даних УДК: 004.658:004.65 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/888 |
| work_keys_str_mv | AT zvazhiidv implementingindexesinpostgresql AT gorokhovskyss implementingindexesinpostgresql AT zvazhiidv vprovadžennâíndeksívupostgresql AT gorokhovskyss vprovadžennâíndeksívupostgresql |