Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2019-31(3)-16

Полный текст:

Аннотация

Сильно ветвящиеся деревья являются одним из наиболее популярных решений для индексирования больших объёмов данных. Наиболее распространённой разновидностью сильно ветвящихся деревьев являются 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.


Для цитирования:


Ригин А.М., Шершаков С.А. Компонент-расширение РСУБД SQLite для индексирования данных модификациями B-деревьев. Труды Института системного программирования РАН. 2019;31(3):203-216. https://doi.org/10.15514/ISPRAS-2019-31(3)-16

For citation:


Rigin A.M., Shershakov S.A. SQLite RDBMS Extension for Data Indexing Using B-tree Modifications. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(3):203-216. https://doi.org/10.15514/ISPRAS-2019-31(3)-16

Просмотров: 143


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)