Research indexJournal article
ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ В АВЛ-ДЕРЕВІ З УРАХУВАННЯМ ІЄРАРХІЇ ПАМ'ЯТІ
Shostak
Системи управління навігації та зв’язку Збірник наукових праць18 Sep 2026Open access
NobleIDark:/48914/w1/20261105/A92662E6DOI10.26906/sunz.2026.3.131
ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ В АВЛ-ДЕРЕВІ З УРАХУВАННЯМ ІЄРАРХІЇ ПАМ'ЯТІ
Shostak · Системи управління навігації та зв’язку Збірник наукових праць · 2026
NobleIDark:/48914/w1/20261105/A92662E6DOI10.26906/sunz.2026.3.131
Abstract
Background Investigating the effects of data spatial locality, branch prediction, and software prefetching on search performance is of considerable interest in the development of high-performance data structures. Subject of the study: search methods in an AVL tree represented as an array using the Eytzinger layout, and the impact of the processor memory hierarchy on their performance. Purpose of the study: to experimentally evaluate the efficiency of various search methods in an array-based AVL tree depending on the array size and the location of the working data set relative to the levels of the processor memory hierarchy. Research objectives. To implement and experimentally investigate the Binary, AVL, Eytzinger, EytzingerB, and EytzingerBP search algorithms; to determine the ranges of array sizes corresponding to different levels of the memory hierarchy; to compare the performance of the investigated algorithms; and to determine the effects of data spatial locality, branch mispredictions, and software prefetching on search efficiency. Research methods. The study employs algorithmic analysis, experimental software performance evaluation, and statistical processing of measurement results. The experimental evaluation was performed using BenchmarkDotNet on the .NET 8 platform with processor hardware performance counters. Research results. It was established that the efficiency of search algorithms is determined not only by their computational complexity but also by the characteristics of their interaction with the processor memory hierarchy. The results show that when the working data are located in the L1/L2 caches, the EytzingerB algorithm provides the shortest search time, whereas when the data are located in the L3 cache and main memory, the EytzingerBP algorithm, which uses software prefetching, demonstrates the best performance. Experimental relationships between search time and array size were obtained, the ranges of effective application of the investigated algorithms were determined, and the performance gains achieved by the most efficient search methods were quantitatively evaluated. The experiments demonstrated a change in the most efficient search algorithm as the working data move between levels of the processor memory hierarchy: within the L1/L2 range, the EytzingerB algorithm provides the shortest search time, whereas within the L3 and main-memory range, the EytzingerBP algorithm is the most efficient. Conclusions Representing an AVL tree using the Eytzinger array layout provides a substantial increase in search performance compared with the conventional pointer-based tree implementation. Experimental results confirm that the choice of the optimal search method is determined by the level of the memory hierarchy in which the working data set resides. The obtained results can be used in the design of high-performance search data structures and in the optimization of search algorithms for modern multi-level memory subsystems.