Review and Performance Comparison of Trie-like Indexes for Main-Memory Databases
Accelerating query performance over massive data has become a major challenge in da-tabase systems in the big data era.Building main-memory database systems on top of large mem-ory has been a feasible way to support real-time big data access.Accordingly,main-memory in-dexes for accelerating data access have been a research focus in recent years.However,main-memory indexes face a few challenges.Taking the main-memory B+tree as an example,the first issue is its low space efficiency stemming from the space overheads incurred by the internal nodes.Second,the B+tree's query complexity directly correlates with data size,leading to di-minishing search efficiency as dataset volumes escalate.Third,the B+tree cannot deal with vari-able-length keys efficiently,failing to meet the real requirements of applications.In recent years,trie-like indexes(also called trie indexes)have emerged as a focal point in main-memory index re-search due to their advantages of low space cost,high data-scale-independent query efficiency,and supporting variable-length keys.This paper focuses on trie-like indexes for main-memory da-tabases.We first introduce some foundational aspects of trie indexes,including their concept,characteristics,and history.Then,we summarize the current achievements and advances of trie-like indexes.Next,we provide a new taxonomy to classify trie-like indexes,based on which we implement six prominent trie-like indexes and evaluate their performance on various datasets and workloads.Further,we present some suggestions for the design and use of trie-like indexes based on the experimental results.Finally,we discuss the future development of trie-like inde-xes.
万方数据
维普
