Detailed explanation of the underlying implementation principles of MySQL indexes

The underlying implementation principle of MySQL index

• • 1. Preface
  • 2. Index type
  • • 1, Hash index
    • 2, BTree index and B Tree index
    • • (1) BTree index
      • (2) B Tree index
      • (3) Advantages of B Tree compared to BTree:
    • 3. Full text index

Related free learning recommendations: mysql video tutorial

##1. Preface

MySQL supports many storage engines, and various storage engines have different support for indexes. Therefore, the MySQL database supports multiple index types, such as BTree index, B Tree index, Hash index, Full text indexing and more.

2. Index type

1. Hash index

Only the memory (memory) storage engine supports Hash index, Hash The index refers to the value of the index column to calculate the hashCode of the value, and then stores the physical location of the row data where the value is located at the corresponding location of the hashCode. Because the hash algorithm is used, the access speed is very fast, but one value can only correspond to one hashCode, and It is hash distributed, so Hash index does not support range search and sorting functions.

2. BTree index and B Tree index

(1) BTree index

BTree index is a balanced search for multi-fork trees. If the tree The depth is 2d (d > 1) and the height is h, then the BTree must meet the following conditions:

① The height of each leaf node must be the same, equal to h;
② Each leaf node is composed of n-1 It consists of keys and n pointers, where d <= n <= 2d, keys and points are spaced apart from each other, and both ends of the node must be keys;
③The leaf node pointers are all null;
④ The keys of non-leaf nodes are all [key, data] tuples, where key represents the key as the index, and data is the data of the row where the key value is located.

(2) B Tree index

B Tree is a variant of BTree. If d is the degree of the tree and h is the height of the number, the main differences between B Tree and BTree are:

① Non-leaf nodes in B Tree do not store data, only key values;
② The leaf nodes of B Tree have no pointers, all key values ​​will appear on the leaf nodes, and the key values ​​stored in the key correspond to the data data The physical address;
③Each non-leaf node of B Tree consists of n key values ​​and n pointers.

(3) Advantages of B Tree compared to BTree:

① Disk reading and writing costs are lower;

② Query speed is more stable.

3. Full-text index

FullText (full-text) index can only be used for MyISAM and InnoDB. For larger data, generating a full-text index consumes a lot of time and space. .

When generating a FullText index, a list of words will be generated for the text, and the index will be based on this list of words during indexing.

Related free learning recommendations: mysql database(Video)

The above is the detailed content of Detailed explanation of the underlying implementation principles of MySQL indexes. For more information, please follow other related articles on the PHP Chinese website!