Shulou(Shulou.com)06/01 Report--

Introduction

Indexes are used to speed up data access. Compare the computer disk to a dictionary, and the index is the directory of the field. when we want to find a word quickly, we only need to find the number of pages in which the word is located by querying the directory, and then open a page directly. The most commonly used index in MySQL is the B+ tree index. Why do you use B+ as the index of MySQL? this is a question that many interviewers must ask.

Why B+ Tree hardware related knowledge

The disk of a computer is the interface of a disk, and there are circles on the disk, and the data is recorded on the sectors of these circles. As shown in the following figure

When a computer system reads data, it goes through the following steps:

1. First, the moving arm moves the magnetic head to the desired cylinder according to the cylinder number. This process is called seeking. The time spent is called seek time (ts).

2. The target sector rotates under the head, and the time spent in this process is called rotation time.

Therefore, the time to access the disk consists of three parts: seek time + rotation time + data transfer time.

In the first part, the seek time delay is the highest, and the maximum can reach 100ms. The rotation time depends on the speed of the disk. The average rotation time of the disk with a speed of 7200 rpm / min is about 5ms. Disk reading is based on block (disk block), and the data located in the same disk block can be read out at once. Try to reduce the number of times the head moves back and forth when reading and writing data, so as to avoid excessive search time. If you have to go through the above processes every time you read data from disk, then the efficiency is undoubtedly extremely low.

Why B+ tree

As you can see from above, if the speed of random access to the disk is very slow, it is necessary to design a reasonable data structure to reduce the number of random access to the disk. B-tree is such a data structure.

B tree, B + tree introduction B tree

B-tree is a kind of multi-fork balanced search tree designed for storage devices. It is similar to the red-black tree, but the B tree performs better in reducing IO operations, the biggest difference between the B tree and the red-black tree is that the B tree can have multiple child nodes, and the red-black tree has at most two child nodes, which determines that in most cases the height of the B tree is much lower than that of the red-black tree, so the number of IO can be reduced when searching. The following picture shows a B-tree:

B-tree is also called balanced multipath search tree. The characteristics of an m-order B-tree are as follows:

a. Each node in the tree contains a maximum of m children (m > = 2)

b. Except for the root node and the leaf node, each node has at least [ceil (m / 2)] children (where ceil (x) is an upper bound function).

c. If the root node is not a leaf node, there are at least 2 children (special case: the root node without the child, that is, the root node is the leaf node, the whole tree has only one root node).

d. All leaf nodes appear in the same layer, and leaf nodes do not contain any keyword information.

e. Each non-terminal node contains n keyword information: (nrecine P0 Magi K1 Magi P1 Magi K2 P2 Magi. Where:

A) Ki (iMel 1... n) is the keyword, and the keywords are sorted in ascending order K (iMel 1) < Ki.

B) Pi is the contact point to the root of the subtree, and the key words of the pointer P (imur1) pointing to all nodes of the subtree are less than Ki, but larger than K (imur1).

C) the number of keywords n must satisfy: [ceil (m / 2)-1]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.