Luchinin Z.S. Data structure for document-oriented databases

Abstract: The article presents an approach for reducing the burden of queries to a non-relational database by using algorithms for tree-structured data storage. The performance of the data processing operations differs depending on the selected data structures. The study of different tree structures such as B+ trees, log-structured trees or fractal trees proved that tree-based algorithms operates faster than MySQL. The article reviews an LSM-tree algorithm in appliance to the document-oriented databases. The author describes algorithm for basic data operations such as creating, reading, editing and deleting. The proposed algorithm for operating with indexes is based on B or B+ trees. The disadvantage of such data structures is in the complexity of tree balancing when new index is added and high demands on resources because indexes are stored in RAM. Log-Structured Merge-Tree (LSM) is a data structure providing a low cost of indexing operations and high speed of adding and removing of data. LMS-based algorithm can be used for the horizontal scaling: each node forms a data sequence sorted by key. The range of keys for each server is stored at the master-server, which allows forming a request to the server storing needed data without additional queries. Thus an increase of the speed of data retrieval and the servers load balancing is achieved.

Keywords: