Implementing indexes in POSTGRESQL

• Дата: 2026
• Автори: Zvazhii, D.V., Gorokhovsky, S.S.
• Формат: Стаття
• Мова: Українська
• Опубліковано: PROBLEMS IN PROGRAMMING 2026
• Теми: PostgreSQL; indexes; data structures; memory management; generalized suffix trees; database architecture; UDC 004.658:004.65
• Онлайн доступ: https://pp.isofts.kiev.ua/index.php/ojs1/article/view/888
• Назва журналу: Problems in programming

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