Abstract: In the era of big data,data access speed is an important indicator to measure the performance of large-scale storage systems.Index is one of the main technologies to improve data access performance in database system.In recent years,learned index(LI) is proposed,which uses machine learning models instead of traditional B+-tree indexes,leverages pattern about the under-lying data distribution to train the models and optimize the indirect search of data query into the direct search of function calculation,learned index can speed up queries and reduce the size of an index.However,the fitting effect of LI is general,and it assumes that the data is static and read-only,it does not support modification operations such as insertion.This paper presents GDLIN,a novel form of a learned index,which uses gradient descent algorithm to fit the data.Gradient descent algorithm can reduce the error between the predict position and the actual position,which can reduce the cost of local research.Besides,GDLIN recursive calls the construction algorithm until only one model is created,which makes full use of keys’ distribution,and avoids the increase of the size of index with the data volume.In addition,GDLIN uses the sorted linked list to address the problem of data insertion.Experiment results demonstrate GDLIN improves the lookup throughput by 2.1× compared with the traditional B＋-trees without insertion.Besides,GDLIN improves the lookup performance by 1.08× compared with the LI when the factor of insertion is 0.5.

Key words: Learned index, Gradient descent, Fitting data model, Linked list