Компонент-расширение РСУБД SQLite для индексирования данных модификациями B-деревьев

Сильно ветвящиеся деревья являются одним из наиболее популярных решений для индексирования больших объёмов данных. Наиболее распространённой разновидностью сильно ветвящихся деревьев являются B-деревья. Существуют различные модификации B-деревьев, в том числе, рассматриваемые в настоящей работе B⁺-деревья, B^*-деревья и B^*+-деревья, однако данные модификации не поддерживаются по умолчанию в популярной реляционной СУБД с открытым исходным кодом SQLite. Данная работа выполняется на основе проведённого ранее исследования эффективности сильно ветвящихся деревьев в задаче индексирования структурированных данных, с использованием разработанной в рамках него C++-библиотеки структур данных – сильно ветвящихся деревьев. В этом исследовании было разработано B^*+-дерево как структура данных, совмещающая в себе основные свойства B⁺-дерева и B^*-дерева. Также в исследовании были измерены эмпирические вычислительные сложности различных операций над B-деревом и его модификациями и объём потребляемой данными операциями оперативной памяти. Целью настоящей работы является разработка расширения для реляционной СУБД SQLite, позволяющего использовать модификации B-дерева (B⁺-дерево, B^*-дерево и B^*+-дерево) в качестве индексирующих структур данных в РСУБД SQLite. Модификации базовой структуры данных были разработаны в виде C++-библиотеки. Данная библиотека подключается к SQLite, используя разработанный для неё в рамках настоящей работы API на языке C. Расширение для SQLite также реализует новый алгоритм выбора индексирующей структуры данных (одной из модификаций B-дерева) для заданной таблицы в базе данных. Предложенное расширение используется компонентом SQLite EventLog библиотеки LDOPA алгоритмов и структур данных для process mining. Кроме того, проведён эксперимент по сравнению эмпирической вычислительной сложности операций на деревьях разных типов в разработанном расширении для SQLite.

1. . Manyika J., Chui M., Brown B., Bughin J., Dobbs R., Roxburgh C., Hung Byers A. Big data: The next frontier for innovation, competition, and productivity. McKinsey Global Institute, May 2011. Available at: https://www.mckinsey.com/~/media/McKinsey/Business%20Functions/McKinsey%20Digital/Our%20Insights/Big%20data%20The%20next%20frontier%20for%20innovation/MGI_big_data_exec_summary.ashx, accessed Jan. 20, 2019.

2. . Bayer R., McCreight E. Organization and maintenance of large ordered indexes. Acta Informatica, vol. 1, no. 3, 1972, pp. 173 – 189.

3. . Pollari-Malmi K. B+-trees. Available at: https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf, accessed Dec. 24, 2018.

4. . B*-tree. NIST Dictionary of Algorithms and Data Structures. Available at: https://xlinux.nist.gov/dads/HTML/bstartree.html, accessed Dec. 24, 2018.

5. . Rigin A.M. On the Performance of Multiway Trees in the Problem of Structured Data Indexing. Coursework, Dept. Soft. Eng., HSE, Moscow, Russia, 2018 (in Russian) / Ригин В.М. Исследование эффективности сильно ветвящихся деревьев в задаче индексирования структурированных данных. Курсовая работа, Департамент программной инженерии, ФКН, ВШЭ, Москва, 2018.

6. . SQLite Home Page. Available at: https://www.sqlite.org/, accessed Jan. 20, 2019.

7. . Library for Dynamic Operational Process Analysis (LDOPA). xiart.ru Projects. Available at: https://prj.xiart.ru/projects/ldopa, accessed Jul. 1, 2019.

8. . SQLiteStudio. Available at: https://sqlitestudio.pl/, accessed Jan. 26, 2019.