An index is a data structure that stores and sorts the values of one or more columns in a database table. It speeds up the search by reducing the number of records that need to be queried in a table. If there is no index, the database will have to perform Full table scan. The index is equivalent to the table of contents in the book, you can quickly find the content you need according to the page number on the table of contents, and improve the query speed.
Commonly used data structures such as binary search tree (Binary Search Tree, BST) each node can only hold one data, resulting in a high tree height, the data of logically adjacent nodes may be far away, if in memory This is not a big problem for data manipulation in the middle, but because the speed of reading and writing to the disk is much slower than that of the memory, the unit of reading and writing to the disk each time is much larger than the smallest unit of reading and writing the memory.