SQLite RDBMS Extension for Data Indexing Using B-tree Modifications
Multiway trees are one of the most popular solutions for the big data indexing. The most commonly used kind of the multiway trees is the B-tree. There exist different modifications of the B-trees, including B+-trees, B*-trees and B*+-trees considered in this work. However, these modifications are no...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2019-09-01
|
| Series: | Труды Института системного программирования РАН |
| Subjects: | |
| Online Access: | https://ispranproceedings.elpub.ru/jour/article/view/1188 |
| _version_ | 1811278219749359616 |
|---|---|
| author | Anton Mikhailovitch Rigin Sergey Andreevich Shershakov |
| author_facet | Anton Mikhailovitch Rigin Sergey Andreevich Shershakov |
| author_sort | Anton Mikhailovitch Rigin |
| collection | DOAJ |
| description | Multiway trees are one of the most popular solutions for the big data indexing. The most commonly used kind of the multiway trees is the B-tree. There exist different modifications of the B-trees, including B+-trees, B*-trees and B*+-trees considered in this work. However, these modifications are not supported by the popular open-source relational DBMS SQLite. This work is based on the previous research on the performance of multiway trees in the problem of structured data indexing, with the previously developed multiway trees C++ library usage. In this research the B*+-tree was developed as the data structure which combines the main B+-tree and B*-tree features together. Also, in the research the empirical computational complexities of different operations on the B-tree and its modifications were measured as well as the memory usage. The purpose of the current work is the development of the SQLite RDBMS extension which allows to use B-tree modifications (B+-tree, B*-tree and B*+-tree) as index structures in the SQLite RDBMS. The modifications of the base data structure were developed as a C++ library. The library is connected to the SQLite using the C-C++ cross-language API which is developed in the current work. The SQLite extension implements the novel algorithm for selecting the index structure (one of B-tree’s modifications) for some table of a database. The provided SQLite extension is adopted by the SQLite EventLog component of the LDOPA process mining library. In addition, the experiment on the counting the empirical computational complexities of operations on the trees of different types is conducted using the developed in this work SQLite extension. |
| first_indexed | 2024-04-13T00:32:01Z |
| format | Article |
| id | doaj.art-3026c9209bd54e089b20c1045addc8ea |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-04-13T00:32:01Z |
| publishDate | 2019-09-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-3026c9209bd54e089b20c1045addc8ea2022-12-22T03:10:27ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262019-09-0131320321610.15514/ISPRAS-2019-31(3)-161176SQLite RDBMS Extension for Data Indexing Using B-tree ModificationsAnton Mikhailovitch Rigin0Sergey Andreevich Shershakov1Национальный исследовательский университет "Высшая школа экономики"Национальный исследовательский университет "Высшая школа экономики"Multiway trees are one of the most popular solutions for the big data indexing. The most commonly used kind of the multiway trees is the B-tree. There exist different modifications of the B-trees, including B+-trees, B*-trees and B*+-trees considered in this work. However, these modifications are not supported by the popular open-source relational DBMS SQLite. This work is based on the previous research on the performance of multiway trees in the problem of structured data indexing, with the previously developed multiway trees C++ library usage. In this research the B*+-tree was developed as the data structure which combines the main B+-tree and B*-tree features together. Also, in the research the empirical computational complexities of different operations on the B-tree and its modifications were measured as well as the memory usage. The purpose of the current work is the development of the SQLite RDBMS extension which allows to use B-tree modifications (B+-tree, B*-tree and B*+-tree) as index structures in the SQLite RDBMS. The modifications of the base data structure were developed as a C++ library. The library is connected to the SQLite using the C-C++ cross-language API which is developed in the current work. The SQLite extension implements the novel algorithm for selecting the index structure (one of B-tree’s modifications) for some table of a database. The provided SQLite extension is adopted by the SQLite EventLog component of the LDOPA process mining library. In addition, the experiment on the counting the empirical computational complexities of operations on the trees of different types is conducted using the developed in this work SQLite extension.https://ispranproceedings.elpub.ru/jour/article/view/1188b-деревоиндексирование данныхsqliteсубдрсубдсильно ветвящееся дерево |
| spellingShingle | Anton Mikhailovitch Rigin Sergey Andreevich Shershakov SQLite RDBMS Extension for Data Indexing Using B-tree Modifications Труды Института системного программирования РАН b-дерево индексирование данных sqlite субд рсубд сильно ветвящееся дерево |
| title | SQLite RDBMS Extension for Data Indexing Using B-tree Modifications |
| title_full | SQLite RDBMS Extension for Data Indexing Using B-tree Modifications |
| title_fullStr | SQLite RDBMS Extension for Data Indexing Using B-tree Modifications |
| title_full_unstemmed | SQLite RDBMS Extension for Data Indexing Using B-tree Modifications |
| title_short | SQLite RDBMS Extension for Data Indexing Using B-tree Modifications |
| title_sort | sqlite rdbms extension for data indexing using b tree modifications |
| topic | b-дерево индексирование данных sqlite субд рсубд сильно ветвящееся дерево |
| url | https://ispranproceedings.elpub.ru/jour/article/view/1188 |
| work_keys_str_mv | AT antonmikhailovitchrigin sqliterdbmsextensionfordataindexingusingbtreemodifications AT sergeyandreevichshershakov sqliterdbmsextensionfordataindexingusingbtreemodifications |