| Summary: | The modern era is characterized by an explosive growth in the amount of data stored and processed. In such circumstances, the performance of storing and indexing of data in external memory become especially important.
There are a variety of applications that require access to the history of data changes, such as backup applications, information systems in banking, medicine, etc. The data with history, i.e., objects that have a lifetime on a certain timescale, is called chronological data.
A new algorithm for indexing chronological data is proposed, LSM with shared components, which combines the ability to store a part of the index in external memory, the efficiency of write operations to external memory (writes are always performed in sequential mode due to out-of-place update design), the complexity of key-range time-slice queries that does not depend on the number of object versions and the possibility of separating "historical" ("cold") data and storing it on separate media.
The algorithm was analyzed theoretically, implemented and benchmarked. Its behavior was studied in comparison with known approaches for several use cases.
|
|---|