moitvivt Моделирование, оптимизация и информационные технологии Modeling, Optimization and Information Technology 2310-6018 Издательство 10.26102/2310-6018/2021.32.1.013 905 Разработка алгоритма индексирования данных на основе структуры данных CW-tree с применением параллельных вычислений Development of a data indexing algorithm based on the CW-tree data structure using parallel computing 0000-0001-5121-201X Шевский Владислав Сергеевич Shevskiy Vladislav Sergeevich immortalghost@yandex.ru aff-1 ФГАОУ ВО «Санкт-Петербургский государственный электротехнический уни-верситет «ЛЭТИ» им. В.И. Ульянова (Ленина)» FSAEI OF HE Saint Petersburg State Electrotechnical University “LETI” named after V.I. Ul-yanov (Lenin), 01 01 2026 1 1 10.26102/2310-6018/2021.32.1.013 Copyright © Авторы, 2026 2026 This work is licensed under a Creative Commons Attribution 4.0 International License

Цель данного научного исследования состояла в разработке алгоритма индексирования данных с использованием технологий параллельных вычислений, применение которого приводило бы к уменьшению времени на обработку запросов к базе данных. В ходе исследования был разработан алгоритм индексирования данных на основе специальной структуры хранения данных на базе дерева, получившей название CW-tree (Constantly-Wide tree). Проход по CW-tree в соответствии с предлагаемым алгоритмом индексирования осуществляется в асинхронном режиме, что достигается благодаря использованию дополнительных стартовых вершин. Как показало тестирование, по сравнению с существующими аналогами алгоритмов индексирования предложенный алгоритм на основе CW-tree обладает преимуществами, главным из которых является полное распараллеливание поиска данных как на верхнем уровне, так и на уровне листьев дерева. Для установления эффекта от использования алгоритма CW-tree было проведено сравнительное исследование, а именно: чтение данных с применением B-tree, которое широко используется практически во всех современных системах управления базами данных, и чтение данных с применением предложенного CW-tree. В ходе исследования запросы к базе данных строились таким образом, чтобы проводился поиск по определенному ключу, устанавливалось, какой подход быстрее обработает некоторое число запросов поиска. Результаты проведенного тестирования показали, что на поиск данных в CW-tree затрачивается значительно меньше времени, чем на поиск в B-tree.

The purpose of this scientific research was to develop an algorithm for data indexing using paral-lel computing technologies, the use of which would lead to a decrease in the time for processing queries to the database. In the course of the research, an algorithm for data indexing was devel-oped based on a special tree-based data storage structure called CW-tree (Constantly Wide tree). The CW-tree traversal in accordance with the proposed indexing algorithm is carried out in an asynchronous mode, which is achieved through the use of additional start vertices. Testing has shown that, in comparison with existing analogs of indexing algorithms, the proposed algorithm based on the CW-tree has advantages, the main of which is the complete parallelization of data retrieval both at the top level and at the level of the tree leaves. To establish the effect of using the CW-tree algorithm, a comparative study was carried out, namely: reading data using the B-tree, which is widely used in almost all modern database management systems, and reading data using the proposed CW-tree ... In the course of the study, queries to the database were built in such a way that a search was carried out for a specific key, it was established which approach would process a certain number of search queries faster. According to the results of the testing, it was found that searching for data in the CW-tree takes much less time than searching in the B-tree.

 алгоритмы индексирования данных структура данных дерева параллельные вычисления многопоточный режим базы данных запросы поиска стартовая вершина целевая вершина data indexing algorithms tree data structure parallel computing multithreading databases search queries start node target node Исследование выполнено без спонсорской поддержки. The study was performed without external funding. References Nouri Z., Tu Y. GPU-Based Parallel Indexing for Concurrent Spatial Query Processing; Distributed and Parallel Databases. SSDBM'18: Proceedings of the 30th International Confer-ence on Scientific and Statistical Database Management. 2018;1–12. Доступно по: https://doi.org/10.1145/3221269.3221296 (дата обращения: 20.02.2020) Shun J., Blelloch G. E. A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction. Proceedings of the Thirteenth Workshop on Algorithm En-gineering and Experiments (ALENEX). 2011;(1):48–58. Jarke M., Koch J. Query optimization in database systems. ACM Computing Surveys (CsUR). 1984;16(2):111–152. Smith J. M., Chang P. Y. T. Optimizing the performance of a relational algebra database interface. Communications of the ACM (CACM). 1975;18(10):568-579. Wu S., Li F., Mehrotra S., Chhin Ooi B. Query Optimization for Massively Parallel Data Processing. SoCC Conference. 2011;(12):1–13. Shnaiderman L., Shmueli O. A Parallel Tree Pattern Query Processing Algorithm for Graph Databases using a GPGPU. Proceedings of the Workshops of the EDBT/ICDT 2015 Joint Conference (EDBT/ICDT). 2015;1330(24):141. Доступно по: http://ceur-ws.org/Vol-1330/paper-24.pdf (дата обращения: 20.01.2020) Battre D., Angulo D. S. MPI framework for parallel searching in large biological data-bases. Journal of Parallel and Distributed Computing. 2006;66(12):1503–1511. Dewan H. M., Stolfo S. J. Scalable Parallel and Distributed Expert Database Systems with Predictive Load Balancing. Journal of Parallel and Distributed Computing. 1994;22(3):506–522. Ren D. Q. Algorithm level power efficiency optimization for CPU-GPU processing element in data intensive SIMD/SPMD computing. Journal of Parallel and Distributed Computing. 2011;72(2):245–253. Liu P., Sun W., Zhang J., Zheng B. An automaton-based index scheme supporting twig queries for on-demand XML data broadcast. Journal of Parallel and Distributed Computing. 2015;(86):82–97. Wani M. A., Bhat W. A. Dataset for forensic analysis of B-tree file system. Data in Brief. 2018;(18):2013–2018.

The authors declare that there are no conflicts of interest present.