Moment For Technology

Dense and sparse indexes

Posted on Aug. 9, 2023, 7:11 a.m. by Hayley Owen
Category: The back-end Tag: The back-end

Dense indexing: Each search code value in a file corresponds to an index value, that is, the leaf node holds the entire row, as in InnoDB

Sparse indexing: The file only builds index entries for certain values of the index code, such as MyISAM

Table data of a dense index is stored sequentially, that is, the index sequence is the same as the physical storage sequence of table records. Therefore, only one dense index can be created for a table

What are InnoDB's dense index selection rules?

1, if a primary key is defined, the primary key as a dense index 2, if it does not have a primary key is defined, the table of the first non-empty index is only as a dense index 3, if does not meet the above conditions, the InnoDB will generate a hidden inside the primary key (dense index) 4, the primary key index to store related keys and their corresponding primary key value, contains two search

As shown in the figure above: InooDB primary key index and data are stored in the same file, so during retrieval, the corresponding data is also loaded when the primary key of loaded leaf node enters the memory. If primary key query is used, the corresponding row data can be obtained only by finding the primary key according to the rules of B+Tree. If the sparse index conducts data filtering, it will go through two steps. The first step is to retrieve the key in the sparse index B+Tree, such as Ellison, and obtain the primary key information. After obtaining the primary key information, it needs to go through the second step: search in the PRIMARY key's B+Tree.

For MyISAM, all sparse indexes are used. The two B+ trees of the sparse index are actually no different, with completely the same structure but different contents. The B+Tree of the primary key index stores the primary key, and the B+Tree of the secondary key string stores the secondary key, but the data is stored in independent places. In other words, the index and data are stored separately. The leaf nodes of both B+ trees store the address pointing to the data. Since the secondary keyrope is independent, there is no need to use the primary key.

We can create a table to verify that the statement is as follows and the effect is as follows:

Now that we've figured out the difference between dense and sparse indexes, let's ask ourselves a question: Is more indexes better?

The answer is of course no, the small data volume table does not need to build index, build will increase the index overhead; Data changes require indexes to be maintained, so more indexes mean more maintenance costs, and more indexes mean more space!

About (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.