What influences database index selection?

In the last article we introduced the data structure behind the index. In this article we will introduce the factor that influences the selection of index data structure — memory access.

Principle of main memory access

The composition of main memory

Main memory (referred to as main memory or memory) includes access body, various logic components and control circuits, etc. The storage body consists of many storage units, and each storage unit contains several storage elements, each of which can store a binary code “0” or “1”. Thus, a memory cell can store a string of binary code, called the memory word, and the number of bits of the binary code is called the memory word length, which can be 8 bits, 16 bits, 32 bits, etc.

The connection between main memory and CPU

The process of accessing main memory

If a storage unit is a building, then each storage unit can be regarded as a room in the building, and each storage unit can be regarded as a bed in the room. If there is someone in the bed, it equals “1”, and if there is no one, it equals “0”. Each room needs a room number so that we can find the room. Similarly, each storage unit can be assigned a number, called the address number of the storage unit.

The main memory works in accordance with the address number of the storage unit to achieve the storage words (write), read (read).

The structure and access principle of modern main memory are quite complicated. Here, a very simple access model is abstracted to explain the working principle of main memory.

The access process of main memory is as follows:

When the system needs to read the main memory, the CPU will first send the address of the word to MAR, through the address bus to main memory, and then issue a read command. After receiving the read command, the main storage locates to the specified storage unit based on the address, and puts the data of the storage unit on the data bus for other components to read.

Write the main storage process is similar, if want to main memory into an information, first of all, the CPU will deposit to the word of the Lord RMB deposit address by MAR to address bus, and the information word into the MDR, and then to main memory write command, main memory had been ordered to write, then write the information on the data bus to to the corresponding address bus pointed out that the main deposit yuan.

Disk Access Principle

As we know, indexes themselves are too large to be stored entirely in memory (the root node resides in memory), but are usually stored as files on disk. The problem is that index retrieval requires disk I/O operations. Unlike memory, disk I/O has a mechanical motion cost, which is orders of magnitude higher than memory access.

Disk Composition

Schematic diagram of the disk’s overall structure:

A disk consists of circular, concentric disks of the same size that can be rotated (each disk must be rotated synchronously). On one side of the disk is a magnetic head holder, which holds a group of magnetic heads, each responsible for accessing the contents of a disk. The magnetic heads cannot rotate, but they can move in the direction of the disk radius (actually tangential). Each magnetic head must also be coaxial at the same time, that is, all magnetic heads overlap at all times when viewed from up to down.

Schematic diagram of disk:

The disk is divided into a series of concentric rings with the center being the center of the disk. Each concentric ring is called a track, and all tracks of the same radius form a cylinder. The track is divided along the radius into small segments, each called a sector, and each sector is the smallest storage unit of the disk.

Disk access process:

When data needs to be read from the disk, the system sends the logical address of the data to the disk. The control circuit of the disk translates the logical address into the physical address according to the addressing logic, that is, it determines the track and sector of the data to be read.

To read data from this sector, we need to place the magnetic head above the sector. To do this:

1. The cylinder must first be found, that is, the head must move to align with the corresponding track. This process is called seek time
2. The target sector is then rotated under the head, i.e. disk rotation rotates the target sector under the head. The time it takes to do this is called rotation time

Therefore, the process of completing a disk access request (read/write) consists of three actions:

1. Seek (time) : the head moves to locate the specified track
2. Rotation delay (time) : Waiting for the specified sector to rotate past under the head
3. Data Transfer (time) : The actual transfer of data between disk and memory

Locality principle and disk prefetch

Due to the characteristics of the storage medium, the disk itself access is much slower than the main memory, coupled with the cost of mechanical movement, the disk access speed is often one millionth of the main memory, so in order to improve efficiency, to minimize the disk I/O. To achieve this goal, the disk does not read data strictly on demand. Instead, the disk prereads each time. Even if only one byte is required, the disk reads a certain length of data backward from this position into memory. The theory behind this is the famous locality principle in computer science:

Principle of locality: When a CPU accesses memory, whether it is to read or write instructions or data, the accessed memory units tend to be clustered in a small contiguous area.

Temporal Locality: If an information item is being accessed, it is likely that it will be accessed again in the near future.

Spatial Locality: Information to be used in the near future is likely to be adjacent in Spatial address to information being used now.

Because sequential disk reads are efficient (no seek time required, very little spin time required), preread can improve I/O efficiency for localized programs.

The prefetch length is an integer multiple of a page. A page is a logical block of computer-managed memory. Hardware and operating systems often divide the main memory and disk storage areas into contiguous, equal-sized blocks. Each block is called a page (in many operating systems, pages are typically 4k in size). When the data that the program is trying to read is not in main memory, a page-missing exception will be triggered. At this time, the system will send a disk read signal to the disk. The disk will find the starting location of the data and load one or more pages back into memory successively.

Select * from B-/+Tree

As mentioned earlier, an important principle of SQL optimization is to reduce the number of disk I/ OS, which is also a measure of index structure.

B-tree analysis:

According to the definition of the B-tree, a maximum of H nodes (height of the B-tree) need to be accessed once. The designers of the database system took advantage of disk prefetch by setting the size of a node equal to one page so that each node could be fully loaded with only one I/O. But logically stored in a page does not mean that is stored on a page in the history of physics, in order to achieve this goal, every time a new node, directly apply for the space of a page, so as to ensure a node is stored on a page in the history of physics, combined with the computer storage allocation are aligned according to the page, it implements a node a single I/O.

A b-tree search requires at most H-1 I/ OS, because the root node is resident in memory. The complexity is O(logdN). In general practice, the degree D is a very large number, usually more than 100, so h is very small (usually no more than 3). Therefore, b-tree is very efficient as an index structure. This is why databases do not use red-black trees as indexes (data structures). First, the height h of red-black trees is much higher. The other is that the nodes of red-black tree may be stored separately physically, and the principle of locality cannot be used. When the complexity is O(H), the efficiency is significantly lower than that of B-tree.

B + Tree analysis:

As mentioned in the previous article, B+Tree is more suitable for indexing. The reasons are as follows: first, the nodes in B+Tree have removed the data field, so they can have a greater degree of output and better performance; Second, all leaf nodes form an ordered linked list, which is convenient for range query. All lookups will eventually reach the leaf node, thus ensuring stable query performance.

reference

• Principles of Computer Composition (2nd Ed.)

• The data structure and algorithm principle behind MySQL index

MySQL — Analyze SQL execution plans through EXPLAIN



MySQL — Index base



MySQL — Index optimization



The data structure behind the database index