Одной из самых распространенных структур для реализации ин­декса в системах управления базами данных является B+ дерево. Дан­ная структура используется и в MySQL. Существует модификация B+ дерева, разработанная для многопоточных нагрузок, называемая B-link деревом. В рамках данной работы были изучены разные алгоритмы син­хронизации потоков при работе с B-link деревом и отобран наиболее перспективный из них - алгоритм Jaluta. Алгоритм Jaluta, а также существующий алгоритм индекса MySQL были реализованы с применением оптимизаций, которые ис­ пользуются в индексе MySQL. Затем были проведены эксперименты для анализа производительности решений. Результаты экспериментов показали, что при интенсивной мно­гопоточной вставке алгоритм Jaluta показывает до 7 раз большую производительность по сравнению с решением из MySQL. Однако су­ществуют условия, при которых алгоритм Jaluta показывает худшие результаты в сравнении с исходным. Исходя из результатов экспериментов был сделан вывод, что алго­ритм Jaluta может быть внедрен в качестве опционального алгоритма для работы с индексом и использоваться при интенсивной многопоточ­ной вставке.

One of the most common data structures used for implementing an index in database management systems is the B+ tree, which is also used in MySQL. There is a modification of the B+ tree designed for multithreaded workloads, known as the B-link tree. In this study, various thread synchronization algorithms for working with the B-link tree were examined, and the most promising one, the Jaluta algorithm, was selected. The Jaluta algorithm, as well as the existing MySQL index algorithm, were implemented with optimizations commonly used in the MySQL index. Then, experiments were conducted to analyze the performance of the solutions. The experimental results showed that during intensive multithreaded insertion, the Jaluta algorithm exhibits up to 7 times higher performance compared to the MySQL solution. However, there are conditions under which the Jaluta algorithm performs worse than the original solution. Based on the experimental results, it can be concluded that the Jaluta algorithm can be implemented as an optional algorithm for working with the index and can be used for intensive multithreaded insertion.

• ВВЕДЕНИЕ
• 1. Постановка задачи
• 2. Исследование предметной области
  • 2.1. Альтернативные B+ деревьям структуры индекса СУБД
  • 2.2. Обзор существующих исследований в области производительности B+деревьев
  • 2.3. Обзор реализации индекса в MySQL
• 3. Описание алгоритмов
  • 3.1. Основные принципы работы B+ деревьев
  • 3.2. Использование блокировок при работе с B+ деревьями
  • 3.3. Алгоритм B+ дерева индекса в InnoDB
  • 3.4. Алгоритм B-link дерева, не поддерживающий удаления
  • 3.5. Алгоритм Jaluta
  • 3.6. Алгоритм Malbrain'a
  • 3.7. Выбор алгоритма для реализации
• 4. Реализация алгоритмов
  • 4.1. Архитектура разрабатываемого решения
  • 4.2. Выбор средства синхронизации
  • 4.3. Детали реализации
  • 4.4. Дополнительные оптимизации
• 5. Разработка и проведение экспериментов для анализа производительности решений
  • 5.1. Виды нагрузок
  • 5.2. Замер производительности с помощью трассировки
  • 5.3. Проведение экспериментов
• 6. Анализ результатов экспериментов
• 7. Результаты работы
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ