Research And Implementation On Learned Index For Navigation Domain Data

Indexes play a crucial role in querying,inserting,modifying and deleting massive data.In modern database systems,indexes implemented using data structures such as B+ trees and dictionary trees have dramatically accelerated the process of manipulating data.However,they do not consider the impact of data distribution laws on indexes.Recently proposed learning indexes take full advantage of data distribution laws: an index can be treated as a model in which the input is the keyword to be queried and the output is the position of the data corresponding to the keyword in the dataset,and thus this model can be obtained by learning the distribution laws of the dataset.Although many learning indexes have greatly improved the query speed and index space compared with the previous traditional index structure,the current learning index structure is not well applied to the field of satellite navigation,because the satellite data has a certain distribution law,but the number of data insertion frequency is high,the data is continuously inserted while querying them,part of the data tend to be accessed frequently.To address these characteristics,this study designs and implements a query-sensitive,updatable,concurrent learning index structure AUBDS.The overall structure of AUBDS can be divided into two parts.The first part is a tree-like structure.Each layer of the tree consists of several models.Each model contains multiple nodes and a model function that fits the data distribution.The second part is a key-value pair consisting of the key to the data and the minimum key value of the data contained in the model.In this study,the algorithms for generating models,querying data,inserting data,and other learning indexes are improved,and additional algorithms are designed to make AUBDS suitable for various scenarios in the navigation field: for learning indexes in small datasets in the case of poor performance,the strategy of delaying the generation of the model is adopted,and at the same time,the greedy idea is used to continuously select data of a certain step size to train the model;when querying the data,the key-value pair is used to quickly locate the model where the data is located,avoiding the need to start from the root;when inserting data,the model is adjusted to solve the insertion conflict through two strategies of model merging and model splitting,which ensures the accuracy and efficiency of the model’s prediction;designs the batch loading data and querying the Nth largest data algorithms to expand the application scenarios of AUBDS;additionally introduce thread-safe model classes and node classes,and implement concurrent read and write algorithms through finegrained locks and version number mechanisms;create a hot key-value pair mapping to solve special query distribution,which ensures the robustness of the model to special queries.This study uses four datasets in a satellite system in the field of navigation,designs nine load experiments,and compares them with six index structures.Under read load experiment,the throughput performance of AUBDS is more than twice that of RMI,and the space occupied is more than 20% smaller than that of RMI;under read and write load experiement,the read and write performance of AUBDS is close to 130% of ALEX performance,and the space occupied like B+ tree.It can be proved that AUBDS is more efficient in time and space than other existing index structures,which provides ideas for the subsequent research on learning indexes applied in the field of navigation.