In-depth explanation of MySQL indexes and structures

B-tree

B-Tree is also called a balanced multi-path search tree (not binary). Using the B-tree structure can significantly reduce Locate the intermediate process experienced when recording, thereby speeding up access.
Left sub-node key value The algorithm for retrieving data by key in B-Tree is very intuitive: first perform a binary search from the root node, if found Then the data of the corresponding node is returned, otherwise the node pointed to by the pointer of the corresponding interval is searched recursively until the node is found or the null pointer is found. The former search is successful, and the latter search fails.

(key is the key value of the record. For different data records, the key is different from each other; data is the data in the data record except key)

B+tree

B+Tree is an improved B-tree.

(key is the key value of the record. For different data records, the key is different from each other; data is the data in the data record except key)

Compatible with B-Tree Compared with B+Tree, there are the following differences:

• The upper limit of the pointer of each node is 2d instead of 2d+1.

• Internal nodes do not store data, only keys; leaf nodes do not store pointers.

Why does the database use B-tree

The mechanical disk of the computer? In order to amortize the waiting time for mechanical movement, the disk will access multiple data items at one time. Not one, such an information unit read at a time is page. We can use the number of pages read or written as the main approximation of the total disk access time. At any time, B Tree algorithms only need to keep a certain number of pages in memory. The design of B-tree takes into account disk pre-reading. A B-tree node is usually as large as a complete disk page (page), and the size of the disk page limits the children that a B-tree node can contain The number (branching factor), of course, this also depends on the size of a keyword relative to a page.

In order to minimize I/O operations, disk reads are read ahead every time, and the size is usually an integer multiple of the page. Even if only one byte needs to be read, the disk will read one page of data (usually 4K) and put it into the memory. The memory and the disk exchange data in units of pages. Because the principle of locality holds that when one piece of data is usually used, nearby data will also be used immediately.

B-Tree: If a retrieval requires access to 4 nodes, the database system designer uses the principle of disk read-ahead to design the size of the node as one page, then reading one node only requires one I/O operation , to complete this retrieval operation, up to 3 I/Os are required (the root node is resident in memory).

The smaller the data record, the more data is stored in each node, the smaller the height of the tree, the fewer I/O operations, and the retrieval efficiency increases.

B+Tree: Non-leaf nodes only store keys, which greatly reduces the size of non-leaf nodes. Then each node can store more records,

The tree is shorter, and I/O Less operations. So B+Tree has better performance.

What is an index

To put it bluntly, an index is a data structure.

The cost of index

The index also comes at a cost: the index file itself consumes storage space, and the index will increase the burden of inserting, deleting, and modifying records. In addition, MySQL will also Resources are consumed to maintain indexes, so more indexes are not always better. Generally, it is not recommended to build an index in two situations.

The first situation is that the table records are relatively small.
The other situation where it is not recommended to build an index is that the selectivity of the index is low. The so-called index selectivity (Selectivity) refers to the ratio of unique index values ​​(also called cardinality) to the number of table records (#T)

Types of indexes

1. Ordinary index

2. Unique index
3. Primary key index
4. Combined index

Index used in MySQL

B+Tree is commonly used as index in MySQL. But the implementation differs according to clustered index and non-clustered index.

Clustered index and non-clustered index

The so-called clustered index means that the main index file and the data file are the same file. Clustered index is mainly used in the Innodb storage engine. In this index implementation, the data on the leaf nodes of B+Tree is the data itself, and the key is the primary key. As shown below:

(t1 table)

(t2 table)

(file corresponding to the database)
Because of InnoDB The data files themselves must be aggregated by primary key, so InnoDB requires that the table must have a primary key (MyISAM may not have one). If not explicitly specified, the MySQL system will automatically select a column that can uniquely identify the data record as the primary key. If such a column does not exist , then MySQL automatically generates an implicit field as the primary key for the InnoDB table. The length of this field is 6 bytes and the type is long.

MyISAM and InnoDB data storage engines in MySQL database

Main differences:
MyISAM is non-transactionally safe, while InnoDB is transactionally safe.
The granularity of MyISAM locks is table level, while InnoDB supports row-level locking.
MyISAM supports full-text type indexes, while InnoDB does not support full-text indexes.
MyISAM is relatively simple, so it is better than InnoDB in terms of efficiency. Small applications can consider using MyISAM.
MyISAM tables are saved in the form of files. Using MyISAM storage in cross-platform data transfer will save a lot of trouble.
InnoDB tables are more secure than MyISAM tables. You can switch non-transactional tables to transactional tables (alter table tablename type=innodb) while ensuring that data will not be lost.
Application scenarios:
MyISAM manages non-transaction tables. It provides high-speed storage and retrieval, as well as full-text search capabilities. If your application needs to perform a large number of SELECT queries, MyISAM is a better choice.
InnoDB is used for transaction processing applications and has numerous features, including ACID transaction support. If your application needs to perform a large number of INSERT or UPDATE operations, you should use InnoDB, which can improve the performance of multi-user concurrent operations.

Supplement

Main memory storage

Fetch process
When the system needs to read the main memory, the address signal is put on the address bus and passed to the main memory. After the main memory reads the address signal, it parses the signal and locates the specified storage unit, and then puts the data of this storage unit on the data bus for other components to read.
The process of writing to main memory is similar. The system places the unit address and data to be written on the address bus and data bus respectively. The main memory reads the contents of the two buses and performs corresponding write operations.
It can be seen here that the time of main memory access is only linearly related to the number of accesses. Because there is no mechanical operation, the "distance" of the data accessed twice will not have any impact on the time. For example, fetch first The time consumption of fetching A0 and then A1 is the same as fetching A0 and then D3.

Disk access principle

When data needs to be read from the disk, the system will transfer the data logical address to the disk , the disk's control circuit translates the logical address into a physical address according to the addressing logic, that is, determines which track and sector the data to be read is on. In order to read the data in this sector, the magnetic head needs to be placed over this sector. In order to achieve this, the magnetic head needs to move to align with the corresponding track. This process is called seek, and the time spent is called seek time. Then the disk rotation will The target sector is rotated under the head. The time spent in this process is called rotation time.

The above is an in-depth and detailed explanation of MySQL index and structure. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!