Ðóñ Eng Cn Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

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:

databases, document-oriented databases, data structure, B+ trees, LSM-trees, non-relational systems, data retrieval, data processing, activity throughput, treelike structures.


This article can be downloaded freely in PDF format for reading. Download article

This article written in Russian. You can find original text of the article here .
References
1.
2.