usually , The index itself is large , Cannot be completely stored in memory , Therefore, indexes are usually stored on disk as index files . under these circumstances , Disks are generated during index lookup I/O consume .
I/O Access consumption is several orders of magnitude higher than memory access , Therefore, the most important index to evaluate the data structure as an index is the disk during the search process I/O Incremental complexity of the number of operations . let me put it another way , The structure of the index is organized to minimize the disk during the lookup process I/O Number of visits .
MySQL—— The index is stored on disk
The disk consists of disks of the same size and coaxial , The disk can rotate ( Each disk must rotate synchronously ). There is a head holder on one side of the disk , A magnetic head holder holds a set of magnetic heads , Each head is responsible for accessing the contents of a disk . The head cannot rotate , But it can move along the radius of the disk ( It's actually an oblique tangential motion ). Each head must also be coaxial at the same time , in other words , Down from top right , All heads overlap at any time ( But at present , There are a variety of head independent technologies , Not subject to this restriction ).
MySQL—— Index stored on disk
Disk structure
Disk operation ：
seek ： The head is connected to one end of the drive arm . By moving the actuator arm back and forth along the radius axis , The driver can position the head to any track ( Disc does not move , Head movement )
rotate ： Once the track is positioned , The disc will rotate , Every bit on the track passes through the head . read / The write head can detect the value of this bit , Or modify the value ( Head does not move , Disk movement )
Disk storage concept ：
a sector ： Each concentric ring is called a sector , A sector is the smallest storage unit of a disk . When data needs to be read from disk , The system transfers the logical address of the data to disk . The control circuit of the disk converts the logical address into the physical address according to the addressing logic , Namely , Which track and which sector is the data to be read . In order to read the data of the Department , The head needs to be placed above the Department . To achieve this , The head needs to be moved and aligned with the corresponding track . This process is called search , The time spent is called search time ; The disk rotation then rotates the target sector below the head , The time required for this process is called rotation time .
Page： Due to the characteristics of storage media , The access speed of the disk itself is much lower than that of the main memory . Except mechanical movement , The access speed of disk is usually a few percent of that of main memory . therefore , In order to improve efficiency , Maximize efficiency . Reduce disk I/O. In order to achieve this goal , The disk is not read strictly on demand , But every time you preview , Even if only one byte is required , The disk will also start from this location , And read a certain length of data backward . memory . Pre reading can improve I/O efficiency . The length of the preview is usually an integral multiple of the page ( page ： Logical block of computer management memory
-
Usually 4k). Main storage and disk exchange data in pages . When the data to be read by the program is not in the main memory , Page error exception will be triggered . here , The system will send a read signal to the disk , The disk will find the starting position of the data and read one or more pages back in succession . Load in memory . Local principle
The theoretical basis for this is the well-known local principle in computer science ：
When using a data , Data in its vicinity is usually used immediately .
in other words , The data required during program operation is usually centralized . Because the sequential reading of disk is very effective ( No seek time required , Only a small amount of rotation time is required ), Therefore, for procedures with locality , Pre reading can improve I/O efficiency .
The designers of file system and database system use the principle of disk pre reading to set the size of nodes equal to one page , In this way, only one can be fully loaded per node I/O. In order to achieve this goal , every time B +
Tree When creating a new node , It requests page space directly , This ensures that the nodes are physically stored in the page , And computer storage allocation is page aligned . Only one is required to implement the node I/O.
Last : period
Next : period
Share to ：
Technology