Abstract: Index tuning is an important problem in database performance tuning and has been studied consistently by worldwide researchers. Due to the theoretical complexity of index tuning as well as the advent of the big data era, manual tuning by DBA is no longer feasible for modern database systems, hence automated and intelligent solutions have been developed. With the development of machine learning techniques, more and more index tuning solutions have integrated with machine learning techniques for better performance and significant progress has been made recently. In this survey, we formulate the problem of index tuning under a search-based paradigm, and under this context, we analyze the main tasks and challenges of this problem. We categorize relevant studies into three main components of the search-based paradigm, namely the generation of the index configurations’ search space, the evaluation of specific index configurations, and the enumeration or the search of index configurations. Then we discuss and compare the related work in each category. We further identify and analyze new challenges for the online index tuning problem where the workload is ad hoc, dynamic, and shifting. We summarize the existing solutions under the online feedback control loop framework. Finally, we discuss the state-of-the-art index tuning tools. Hopefully, with the thorough discussion and evaluation of current research, this survey can provide insights to interested researchers and conclude with future research directions for index tuning.