• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Educational Programme
Final Grade
Year of Graduation
Anton Rigin
SQLite RDBMS Extension for Data Indexing Using B-tree Modifications
Software Engineering
(Bachelor’s programme)
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.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses