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

The previous article:

Summary of MYSQL INNODB index page header Learning and experiment

Http://blog.itpub.net/7728585/viewspace-2063921/

Learning and Experimental Research on INNODB SYSTEM RECORD infimum and supremum

Http://blog.itpub.net/7728585/viewspace-2065464/

The tools used are self-written mysqlblock and bcview.

I put it on Baidu Cloud disk.

Http://pan.baidu.com/s/1num76RJ

For everyone to download and use

This article only discusses the COMPACT line mode

Data:

Mysql > select * from km1

+-+ +

| | id | name |

+-+ +

| | 2 | gaopeng |

| | 4 | gaopeng |

| | 5 | gaopeng |

| | 6 | gaopeng |

| | 7 | gaopeng |

| | 8 | gaopeng |

+-+ +

6 rows in set (0.04 sec)

The last article has found the offset of the first row of data from infimum

For 99, 65, 164.

At the same time, the first row of data was taken out:

Bcview km1.ibd 16 164 30 | more

Current block:00000003--Offset:00164--cnt bytes:30--data is:000001cc64260000002d0272d300000d1201108000000267616f70656e67

Decompose the data.

000001cc6426 ROWID

0000002d0272 transaction id

D300000d120110 roll pointer

80000002 data 2, where 8 appears in the 15th bit, which may be a symbol bit

The ascII value of the 67616f70656e67 data 'gaopeng'

So let's parse to introduce the relevant parts about CLUSTER KEY-LEAF BLOCK.

Obviously my table here has only one block because there is very little data. So let's introduce this first.

Because the offset of the so-called infimum is the beginning of the data to which it points, and the header information

It is recorded in the position of offset-N, N is not sure and you can see it as follows.

Variable field lengths (1-2 bytes* var)

Nullable field bitmap (1 bit * null field)

Info flags (4 bits)

Number of records owned (4 bits)

Order (13 bits)

Record type (3 bits)

Next record offset (2 bytes)

Offset-cluster key fields (N bytes)

Transaction id (6 bytes)

Roll pointer (7 bytes)

Non-key fields (M bytes)

1 、 variable field lengths

Each variable type of variable length stores a length such as varchar and is not recorded for fixed length such as INT.

If there is no variable type of variable length, it takes at least one byte of 00.

2 、 nullable field bitmap

Each NULL value occupies a bit (bit), if less than one byte is counted as a byte, if there is no null value

Occupies at least one byte of 00.

3 、 info flags

The 4-bit (4bits) tag is a row identifier, where binary 0001 represents the row with the smallest non-leaf node

Where binary 0010 represents deleted rows, and infimum and supremum rows are binary 0000 in my test database

4 、 number of records owned

These four bits (4bits) represent the number of records in this page directory (slot). The concept of slot is discussed in detail later.

5 、 order

These 13 bits (13bits) represent the order in which records are inserted into the block, where INFIMUM is always equal to 0 and SPREMUM is always equal to 1, while the ORDER of the data row starts at 2, where order

The conclusion of my experiment is that the order of the actual physical space

6 、 record type

These three bits (3bits) represent the type of record, supermum is always equal to 3 and binary 011 and binary010, node pointer is 1 and 001, data behavior is 000

7 、 next record offset

The two bytes are sorted according to the value of CLUSTER KEY, that is to say, their order has nothing to do with order, and order is the order in which it is inserted.

What is indicated in INFIMUM is the offset of the first row, which is the position of the current record + offset, and this offset points directly to the data and the associated header is the overhead of the line at the beginning of the offset-n.

Of course, the offset of supermum is the null pointer of NULL.

8 、 cluster key fields

These N bytes represent the number of primary key bytes. No, ROWID occupies 6 bytes.

9 、 transaction id

These 6 bytes are the things ID that last modified this line.

10 、 roll pointer

These 7 bytes are fallback pointers used to support multiple versions of MVCC

1bit identification

7bit fallback segment ID

4bytes rollback segment page number

Offset of 2bytes rollback segment page

These people studied in detail when discussing MVCC.

11 、 non-key fields

That is, M bytes of non-primary key field data.

Then we can take out the first line completely.

Let's calculate that I have a variable varchar here that has 1 byte and no null value.

The byte of that line is 1BYTES+1bytes+4BIT+4BIT+13BIT+3BIT+2BYTES=7BYTES.

And the offset is

99'65 '164-wardrobe 7bytes=157byes

Bcview km1.ibd 16 157 37 | more

Here is 37 = line 7BYTES+

CLUSTER KEY (I am ROWID 6BYTES) +

Transaction id (6BYTES) +

Roll pointer (7BYTES) +

Non-key fields (INT 4BYTES+VARCHAR (7BYTES))

Current block:00000003--Offset:00157--cnt bytes:37--data is:0700000018004a000001cc64260000002d0272d300000d1201108000000267616f70656e67

Decompose the data.

Length of 0X07 varchar actual data 'gaopeng'

0X00 null type identification byte I don't have NULL here

0X0 here is 0. He is neither deleting a row nor the minimum row of a non-page node. It is understandable that the row deleted in the node has a value of 0010 on these four bits, and then test it.

0X0 is recorded on slot 0

Why is the first 13 bits of 0X0018 converted to binary 0000 0000 0001 1000 0000 0000 0001 1 = 3? No

Do you say to start with 2? Because the data inserted in the first row here is dropped by my DELETE, and the space is used, the OFFSET sort is sorted by CLUSTER KEY.

000 is record type. Obviously I have a data row here, which is, of course, 000.

Decimal 74 offset of the next data in 0X004a

0X000001cc6426 ROWID

0X0000002d0272d3 things ID

0X00000d120110 rollback pointer

2 of 0X80000002 signed int type

0X67616f70656e67 data 'gaopeng'

Then let's look for the second piece of data.

16474, because the data format is the same

direct

164mm 74-wardrobe 7bytes=231

Fetch 37 bytes

Bcview km1.ibd 16 231 37 | more

Current block:00000003--Offset:00231--cnt bytes:37--data is:0700000028ffdb000001cc64280000002d0278d700000d0601108000000467616f70656e67

Decompose data

07 ditto

00 ditto

0 ditto

0 ditto

0028 0000 0000 0010 1000

0000 0000 0010 1 = decimal 5

000 means ordinary data.

Ffdb noticed that the negative number is stored in the way of complement, and the negative number means that our offset has fallen back, that is, the space of DELETE is used.

Ffdb, that is,-37, you can do your own calculation.

000001cc6428 ditto

0000002d0278d7 ditto

00000d060110 ditto

80000004 actual data 4

67616f70656e67 actual data 'gaopeng'

Then let's look for the third piece of data.

164'74 + (- 37)-7 '194

Bcview km1.ibd 16 19437 | more

Current block:00000003--Offset:00194--cnt bytes:37--data is:0700000020ffb6000001cc65000000002d062bab00000d0c01108000000567616f70656e67

Also decompose the data

07

00

0

0

0020 the decomposition here is the same as 0000 0000 0010 0 = decimal 4, which is order indicates that the data was inserted before the previous data, but the OFFSET is sorted by ROWID.

The way that ffb6 is still a complement is actually-74.

000001cc6500

0000002d062bab

00000d0c0110

80000005 actual data 5

67616f70656e67 actual data 'gaopeng'

Let's take the fourth piece of data.

164'74 + (- 37) + (- 74)-7 '120 here comes the first row of data in physics

Bcview km1.ibd 16 120 37 | more

Current block:00000003--Offset:00120--cnt bytes:37--data is:07000000100094000001cc66000000002d0a2cab00000d0c01108000000667616f70656e67

Decompose data

07

00

0

0

0010 0000 0000 0000 1000

0000 0000 0000 1 = decimal 2

0094 offset

000001cc6600

0000002d0a2cab

00000d0c0110

80000006 actual data 6

67616f70656e67 actual data 'gaopeng'

For the next two pieces of data, I will finish it myself.

The actual location of ID=7 is: 164'74 + (- 37) + (- 74) + 148-7 '268 bcview km1.ibd 16 268 37 | more

Actual location of ID=8 164U74+ (- 37) + (- 74) + 148U37-7305 bcview km1.ibd 16 30537 | more

In fact, we probably got a linked list.

Infimum order 0 offset 65

-- > actual data id=2 rowid 000001cc6426 order 3 offset 74

-- > actual data id=4 rowid 000001cc6428 order 5 offset-37

-- > actual data id=5 rowid 000001cc6500 order 4 offset-37

-- > actual data id=6 rowid 000001cc6600 order 2 offset 148

-- > actual data id=7 rowid 000001cc6700 order 6 offset 37

-- > actual data id=8 rowid 000001cc6800 order 7 offset-200

-- > supermum order 1 offset null

Note that the-200 of the last data is actually the starting position of 164'74 + (- 37) + (- 74) + 148'37-200 '112.

So we see that his order is indeed the sort of ROWID, while ORDER is actually the physical order.

Also note that this is sorted by ROWID because there is no primary key because there is no primary key, and it is not sorted by ID.

Sorted, it's just a coincidence.

If you insert a

Mysql > insert into km1 values (1meme gaop 12')

Query OK, 1 row affected (0.06 sec)

ID=1 's data.

Bcview km1.ibd 16342 40 | more decomposition data is obtained.

-- > actual data id=8 rowid 000001cc6800 order 7 offset 37

-- > actual data id=1 rowid 000001cc6900 order 8 offset-237

-- > supermum order 1 offset null

In addition, we need to do an experiment, that is, whether the deleted row is listed in this linked list, and test the info flags of the deleted row.

Delete the data just inserted

Mysql > delete from km1 where id=1

Query OK, 1 row affected (0.11 sec)

And

-- > actual data id=8 rowid 000001cc6800 order 7 offset 37

-- > actual data id=1 rowid 000001cc6900 order 8 offset-237 deletion

-- > supermum order 1 offset null

Check again

Bcview km1.ibd 16 305 37 | more

Current block:00000003--Offset:00305--cnt bytes:37--data is:0700000038ff38000001cc68000000002d0e2bab00000d0c01108000000867616f70656e67

Break it down.

07

0

0

00

0038

The offset here in ff38 has changed from 37 to-200obviously the deleted row has been deleted from the linked list because it points directly to supermum.

000001cc6800

0000002d0e2bab

00000d0c0110

80000008

67616f70656e67

Let's check again.

Bcview km1.ibd 16 342 39 | more

Current block:00000003--Offset:00342--cnt bytes:40--data is:09002000400000000001cc69000000002d10323200000d17022d8000000167616f70656e673132

09

0

0

20 binary 0010 0000 you can see that the first four bits of this byte become 0010. Indeed, binary 0010 indicates a deleted line.

0040 order did not change to 8.

0000 where the pointer has changed from-237 to zero and null.

000001cc6900

0000002d103232

00000d17022d

80000001

67616f70656e673132

So the linked list just now

Infimum order 0 offset 65

-- > actual data id=2 rowid 000001cc6426 order 3 offset 74

-- > actual data id=4 rowid 000001cc6428 order 5 offset-37

-- > actual data id=5 rowid 000001cc6500 order 4 offset-37

-- > actual data id=6 rowid 000001cc6600 order 2 offset 148

-- > actual data id=7 rowid 000001cc6700 order 6 offset 37

-- > actual data id=8 rowid 000001cc6800 order 7 offset 37

-- > actual data id=1 rowid 000001cc6900 order 8 offset-237 deletion

-- > supermum order 1 offset null

Become

Infimum order 0 offset 65

-- > actual data id=2 rowid 000001cc6426 order 3 offset 74

-- > actual data id=4 rowid 000001cc6428 order 5 offset-37

-- > actual data id=5 rowid 000001cc6500 order 4 offset-37

-- > actual data id=6 rowid 000001cc6600 order 2 offset 148

-- > actual data id=7 rowid 000001cc6700 order 6 offset 37

-- > actual data id=8 rowid 000001cc6800 order 7 offset-200

-- > supermum order 1 offset null

And deleted data

-- > actual data id=1 rowid 000001cc6900 order 8 offset 0 deletion

So we verified two facts.

1. Deleted rows are deleted from the offset linked list

2. It is true that binary 0010 indicates a deleted line

You may remember that there are two pieces of information in index page header.

The offset of the deleted record in the first line of first garbage record offset 2bytes

Garbage space 2bytes deleted space size unit bytes

If the first deleted row is marked, does the deleted row also have a linked list?

Let's first take a look at the current value of these two bytes.

First garbage record offset

Bcview km1.ibd 16 44 2 | more (first garbage record offset)

Current block:00000003--Offset:00044--cnt bytes:02--data is:015d

The current values of 0X15d and 349 point to the OFFSET that just deleted the row. We guess we are testing the beginning of the deleted linked list.

Garbage space

Bcview km1.ibd 16 46 2 | more (garbage space)

Current block:00000003--Offset:00046--cnt bytes:02--data is:0027

The current values are 0X27 and 39, which happens to be the space to delete records.

And 7'6'7'6'4'9 bytes

Infimum order 0 offset 65

-- > actual data id=2 rowid 000001cc6426 order 3 offset 74

-- > actual data id=4 rowid 000001cc6428 order 5 offset-37

-- > actual data id=5 rowid 000001cc6500 order 4 offset-37

-- > actual data id=6 rowid 000001cc6600 order 2 offset 148

-- > actual data id=7 rowid 000001cc6700 order 6 offset 37

-- > actual data id=8 rowid 000001cc6800 order 7 offset-200

-- > supermum order 1 offset null

And deleted data

First garbage record offset

-- > actual data id=1 rowid 000001cc6900 order 8 offset 0 deletion

Let's delete it.

Mysql > delete from km1 where id=2

Query OK, 1 row affected (0.00 sec)

-- > actual data id=2 rowid 000001cc6426 order 3 offset 74

After deletion

View the offset of infimum

Bcview km1.ibd 16 97 2

Current block:00000003--Offset:00097--cnt bytes:02--data is:008b

The 0X8b is 139.

Then the location of the first piece of data is

999.139-70.231

Let's check it out.

Bcview km1.ibd 16 231 37 | more

Current block:00000003--Offset:00231--cnt bytes:37--data is:0700000028ffdb000001cc64280000002d0278d700000d0601108000000467616f70656e67

Decomposition

0700000028

Ffdb offset is still-37 (complement mode)

000001cc64280000002d0278d700000d060110

80000004 can see this data ID=4.

67616f70656e67

Then it proves that the deleted row has been removed from the data linked list.

So our data linked list becomes

Infimum order 0 offset 139

-- > actual data id=4 rowid 000001cc6428 order 5 offset-37

-- > actual data id=5 rowid 000001cc6500 order 4 offset-37

-- > actual data id=6 rowid 000001cc6600 order 2 offset 148

-- > actual data id=7 rowid 000001cc6700 order 6 offset 37

-- > actual data id=8 rowid 000001cc6800 order 7 offset-200

-- > supermum order 1 offset null

Check again

First garbage record offset

Bcview km1.ibd 16 44 2 | more

Current block:00000003--Offset:00044--cnt bytes:02--data is:00a4

The current values are 0XA4 and 164. just now they are 0X15d and 349.

So let's see, 164-7 is the beginning of the line.

Bcview km1.ibd 16 157 37 | more

Current block:00000003--Offset:00157--cnt bytes:37--data is:070020001800b9000001cc64260000002d1038350000014527b68000000267616f70656e67

07

0

0

20-deleted Lin

0018-order is 3

00b9-offset of the next deleted row

000001cc6426 rowid

0000002d103835

0000014527b6

80000002 data ID=2

67616f70656e67

Finally, the data of ID=1 rowid 000001cc6900 is found according to this offset.

1641185( 0Xb9)-716342

Bcview km1.ibd 16 342 39 | more

Current block:00000003--Offset:00342--cnt bytes:39--data is:09002000400000000001cc69000000002d10323200000d17022d8000000167616f70656e673132

Look at this and the one just now.

09002000400000000001cc69000000002d10323200000d17022d8000000167616f70656e673132

Nothing has changed.

Garbage space

Bcview km1.ibd 16 46 2 | more

Current block:00000003--Offset:00046--cnt bytes:02--data is:004c

The current values are 0X4C and 76, which is exactly the space occupied by deleting two records.

So this deleted linked list becomes

First garbage record offset 164

-- > actual data id=2 rowid 000001cc6426 order 3 offset 185

-- > actual data id=1 rowid 000001cc6900 order 8 offset 00

Then I did another test and found that in the delete linked list, the first garbage record offset always points to the offset of the record that was recently deleted, while the space slave always

Use the space pointed to by first garbage record offset first, then add the data linked list after use, and first garbage record offset points to the location of the next node.

So we can describe that deleting a linked list actually adheres to a last-in-first-out principle, which is a bit like the use of stack space, which is also understandable, because in order to ensure that

The orderly reading of the data must be sorted by CLUSTER KEY, but there is no such requirement in the delete linked list, so it is more simple to use this stack-like linked list.

The whole calculation process is rather tedious.

Finally, let's sum up:

1. There are two linked lists in a BLOCK, one is the data linked list and the other is the deleted data linked list

The beginning and end of the data link list are infimum and supermum

The delete linked list begins with first garbage record offset and ends with the last deleted block.

Next offset is 0000 null pointer

2. In the data linked list, next record offset is sorted by CLUSTER KEY size or ROWID.

In the delete linked list, first garbage record offset always points to the offset of the record that was recently deleted, and the order of next record offset is the order of deletion.

Delete linked list space from the use of similar stack space to follow the principle of last-in-first-out.

3. Order is the sort of physical location. It shows the physical location of data in block, infimum and supermum.

They are 0 and 1 respectively, because they are always at the beginning.

4. Info flags is marked as binary 0010 in the page node unless the row is deleted.

5. The deleted row is removed from the data linked list and then mounted to the deleted linked list

6. The data of deleted rows will be reused, and the data of delete can theoretically be recovered before it is used, because they are all in the deleted linked list.

7. The negative offset, that is, the space used after deletion, is given in the form of complement.

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.