The following public account “AI Coder” has received a copy of the latest JAVA interview materials for 2021

Why say 20 million? Why not say 1 million, 2 million?

This is not nonsense, of course, it is calculated, and I will show you how it is calculated in the next article.

Before calculating, let’s talk about mysql’s underlying data store structure.

Innodb is the storage engine commonly used by mysql, and the data structure algorithm is basically B+ tree. Of course, those familiar with mysql must know that in addition to B+ Tree, mysql uses data structure algorithm and hash, etc. However, the calculation method in this paper is mainly aimed at the storage method of the data structure B + Tree.

Let’s see what B+ tree looks like.

Insert a picture description here

  • The depth of b+ tree is 3

  • Leaf node stores all node information

  • Data is stored in leaf nodes

  • Leaf nodes are connected by a bidirectional linked list and are sorted sequentially

So if we know what b+ tree looks like, how do we find data in mysql?

Suppose we want to find data with id 21:

  • First load the first page of data

  • You can locate the data between 18 and 30 and find pointer A

  • Then load the corresponding page memory data into the memory according to the memory address corresponding to pointer A

  • Then locate the data in section 20-22 and find pointer E

  • Load the data corresponding to the memory address of E directly

  • Finally, locate the data whose ID is 21

B+ tree data structure B+ Tree data structure B+ Tree data structure

With all that said, I don’t think we have even gotten to the topic of the day.

Insert a picture description here

So how did the 20 million figure come up?

In mysql, a large node is used as a page, and mysql loads data into memory one page at a time

The page size is defined as16KB, which is recommended by mysql and can also be configured.

Mysql refers to such a pair of data as small nodes, and the space occupied by small nodes can be calculated as follows

  • [18] Primary key node integer 8B(8 bytes)

  • [A] pointer node, the maximum range of memory address is 6B

  • So 6B plus 8B is equal to 14B

So how many small nodes can a big node store?

Number of small nodes: 16KB/14B = 1170

Let’s do it this way:

  • The first tier stores 1170 small nodes

  • In the second layer, each small node stores 1170 nodes, totaling 1170*1170

  • Layer 3 Because layer 3 stores data and does not need to store pointer addresses, the calculation method is different from that of the first two layers

    • Primary key node 8B

    • That’s a lot to estimate

    • 8B is equivalent to 1KB and can be ignored

    • So a small node can store 16KB/1KB =16 pieces of data

    • The total number of stored data items is: 1170 * 1170 * 16= 2,1902,400 (20 million)

    By the end, you should know how the 20 million number is calculated!!

Welfare big broadcast

Follow the wechat official account “AI Coder” to receive the interview materials and the latest full set of micro service courses