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 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. The purpose of the 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. The issues of the work are: 1. the literature review; 2. the existing solutions review; 3. implementation of the C-C++ cross-language API for the existing multiway trees C++ library; 4. development of the SQLite RDBMS extension which allows to use B-tree modifications (B+-tree, B*-tree and B*+-tree) as index structures based on the existing multiway trees C++ library and to output the graphical representation of the B-tree or its modification used in the given table in the GraphViz DOT file format and the main data related to the tree; 5. development and implementation of the algorithm of selecting the index structure for a table indexing from the B-tree modifications (B+-tree, B*-tree and B*+-tree); 6. testing of the developed software product; 7. development of the technical documentation. Keywords — B-tree, multiway tree, data indexing, SQLite, DBMS, RDBMS. The paper contains 33 pages, 3 chapters, 7 illustrations, 11 bibliography items, 4 appendices.