EUVIMEDEUVIMED entdecken
Crossref

Implementing indexes in POSTGRESQL

D.V. Zvazhii, S.S. Gorokhovsky

PROBLEMS IN PROGRAMMING · 2026 · (1) · 14-24

DOI: 10.15407/pp2026.01.014 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PROBLEMS IN PROGRAMMING, 2026. Verfasst von D.V. Zvazhii und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 20 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Zvazhii, D., & Gorokhovsky, S. (2026). Implementing indexes in POSTGRESQL. PROBLEMS IN PROGRAMMING, 14-24. https://doi.org/10.15407/pp2026.01.014

Vancouver

Zvazhii D, Gorokhovsky S. Implementing indexes in POSTGRESQL. PROBLEMS IN PROGRAMMING. 2026:14-24. doi:10.15407/pp2026.01.014

BibTeX
@article{Zvazhii2026,
  author = {Zvazhii, D.V. and Gorokhovsky, S.S.},
  title = {Implementing indexes in POSTGRESQL},
  journal = {PROBLEMS IN PROGRAMMING},
  year = {2026},
  number = {1},
  pages = {14--24},
  doi = {10.15407/pp2026.01.014}
}
Kostenlos starten →