Deeply understand the underlying data structure and algorithm of MySQL index

The essence of index

Sort the data in the database , Each time you query, you can quickly find the target data according to the conditions .

b-tree Trees

Leaf nodes have the same depth , And the pointer of the leaf node is null ;

Each node stores key-value, All indexes are not duplicate ;

The index is incremented from left to right ;

b+tree Trees

Only leaf nodes store key-value, Other nodes store key;

The leaf node contains all indexes ;

Leaf nodes are connected by pointers , Improve the access performance of the interval ;

MyISAM Storage engine index implementation

Nonclustered index ： Index files and data files are stored separately .

InnoDB The index to achieve

Clustered index ： The index and data are consistent , So you must have a primary key .

Adopted b+tree Tree structure storage , The leaf node contains all indexes and data .

Left most matching principle

The union index needs to match columns from left to right .