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

1. This paper proves that all the key values of the composite index are stored in the branch nodes (non-leaf nodes are also stored).

2. This paper gives how the B+ index verifies its B+ tree structure.

For more information about B-tree structure (not B + tree), please refer to:

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

Script:

Mysql > create table testzh (id int primary key auto_increment, id2 int,id3 int,name varchar (20), key (id2,id3))

Query OK, 0 rows affected (0.07 sec)

Delimiter / /

Create procedure ins ()

Begin

Declare i int

Set iTunes 0

While i select * from information_schema.INNODB_SYS_INDEXES where TABLE_ID=132

+-+ +

| | INDEX_ID | NAME | TABLE_ID | TYPE | N_FIELDS | PAGE_NO | SPACE | MERGE_THRESHOLD |

+-+ +

| | 160 | PRIMARY | 132 | 3 | 1 | 3 | 207 | 50 | |

| | 161 | id2 | 132 | 0 | 2 | 4 | 207| 50 | |

+-+ +

Note that the program counting block starts from 0 and is specified for being close to the Calgary + array.

[root@testmy test] #. / b_level testzh.ibd | grep 161

Block id is 4:Index page no is 161B + Tree Level is 1

Block id is 8:Index page no is 161B + Tree Level is 0

Block id is 9:Index page no is 161B + Tree Level is 0

Block id is 12:Index page no is 161B + Tree Level is 0

Block id is 14:Index page no is 161B + Tree Level is 0

Block id is 19:Index page no is 161B + Tree Level is 0

Block id is 20:Index page no is 161B + Tree Level is 0

Block id is 21:Index page no is 161B + Tree Level is 0

Block id is 22:Index page no is 161B + Tree Level is 0

Block id is 31:Index page no is 161B + Tree Level is 0

Block id is 32:Index page no is 161B + Tree Level is 0

Block id is 34:Index page no is 161B + Tree Level is 0

Block id is 35:Index page no is 161B + Tree Level is 0

Block id is 36:Index page no is 161B + Tree Level is 0

Block id is 37:Index page no is 161B + Tree Level is 0

Block id is 38:Index page no is 161B + Tree Level is 0

Block id is 41:Index page no is 161B + Tree Level is 0

Block id is 53:Index page no is 161B + Tree Level is 0

Block id is 54:Index page no is 161B + Tree Level is 0

Block id is 55:Index page no is 161B + Tree Level is 0

.

Block id is 348:Index page no is 161B + Tree Level is 0

Block id is 349:Index page no is 161B + Tree Level is 0

Block id is 350:Index page no is 161B + Tree Level is 0

Block id is 351:Index page no is 161B + Tree Level is 0

Block id is 352:Index page no is 161B + Tree Level is 0

Block id is 353:Index page no is 161B + Tree Level is 0

Block id is 354:Index page no is 161B + Tree Level is 0

Block id is 355:Index page no is 161B + Tree Level is 0

Block id is 356:Index page no is 161B + Tree Level is 0

Block id is 357:Index page no is 161B + Tree Level is 0

Block id is 358:Index page no is 161B + Tree Level is 0

Block id is 359:Index page no is 161B + Tree Level is 0

Block id is 360:Index page no is 161B + Tree Level is 0

Block id is 361:Index page no is 161B + Tree Level is 0

Block id is 362:Index page no is 161B + Tree Level is 0

Block id is 363:Index page no is 161B + Tree Level is 0

Block id is 364:Index page no is 161B + Tree Level is 0

This is all the blocks of my 161index key (id2,id3)

Here we see that our composite index is a 2-tier B + tree structure.

Block id is 4:Index page no is 161B + Tree Level is 1

This block is the root node, so we need to read it and use another Mini Program I wrote.

Used to read its data, but this program is written to read 2 INT type data as follows, given in order

And give the offset and the pointing block (note that the pointing block is my guess, and then verify it):

Then let's read BLOCK 4 (put the dataview program at the end)

[root@testmy test] #. / dataview testzh.ibd 4

Index_no is:161

Find first one record!

B:23,A:59613,offset:126,leaf block:8

B:736,A:31951,offset:2106,leaf block:249

B:1591,A:58218,offset:1072,leaf block:203

B:2390,A:34725,offset:2326,leaf block:324

B:3231,A:16448,offset:500,leaf block:54

B:3647,A:95182,offset:3118,leaf block:360

B:4050,A:42271,offset:1776,leaf block:235

B:4751,A:62810,offset:1028,leaf block:201

B:5614,A:53731,offset:1886,leaf block:240

B:6482,A:29372,offset:346,leaf block:34

B:7216,A:26606,offset:2524,leaf block:333

B:8028,A:78263,offset:1138,leaf block:206

B:8777,A:61401,offset:2238,leaf block:255

B:9562,A:34379,offset:698,leaf block:63

B:10353,A:93823,offset:2150,leaf block:251

B:11114,A:50825,offset:1358,leaf block:216

B:11859,A:57029,offset:2634,leaf block:338

B:12611,A:67208,offset:214,leaf block:19

B:13378,A:43201,offset:2062,leaf block:247

B:14179,A:72734,offset:940,leaf block:197

B:14972,A:39942,offset:2458,leaf block:330

B:15743,A:9319,offset:632,leaf block:60

B:16488,A:33875,offset:2392,leaf block:327

B:17320,A:32881,offset:1204,leaf block:209

B:18117,A:6361,offset:2084,leaf block:248

B:18966,A:70177,offset:368,leaf block:35

B:19722,A:16497,offset:1710,leaf block:232

B:20563,A:60667,offset:896,leaf block:195

B:21357,A:38077,offset:2040,leaf block:246

B:22151,A:15974,offset:522,leaf block:55

B:22612,A:89791,offset:3008,leaf block:355

B:23070,A:74154,offset:1534,leaf block:224

B:23935,A:42535,offset:852,leaf block:193

B:24814,A:51733,offset:1644,leaf block:229

B:25714,A:232,offset:170,leaf block:12

B:26468,A:119,offset:2678,leaf block:340

B:27177,A:3573,offset:1402,leaf block:218

B:27870,A:22983,offset:2700,leaf block:341

B:28679,A:71426,offset:676,leaf block:62

B:29439,A:77570,offset:2216,leaf block:254

B:30160,A:66775,offset:1424,leaf block:219

B:30865,A:17274,offset:2722,leaf block:342

B:31611,A:25970,offset:390,leaf block:36

B:32377,A:56419,offset:1930,leaf block:242

B:33117,A:8818,offset:1292,leaf block:213

B:33838,A:19538,offset:2898,leaf block:350

B:34489,A:92156,offset:742,leaf block:129

B:35286,A:6546,offset:2194,leaf block:253

B:36076,A:40723,offset:1314,leaf block:214

B:36763,A:20769,offset:2876,leaf block:349

B:37450,A:46558,offset:236,leaf block:20

B:38214,A:7960,offset:2568,leaf block:335

B:38945,A:498,offset:984,leaf block:199

B:39726,A:40552,offset:2260,leaf block:321

B:40462,A:1439,offset:588,leaf block:58

B:41208,A:19781,offset:2612,leaf block:337

B:41939,A:99119,offset:1248,leaf block:211

B:42637,A:26247,offset:2436,leaf block:329

B:43441,A:1592,offset:434,leaf block:38

B:44198,A:74037,offset:2480,leaf block:331

B:44889,A:50243,offset:1226,leaf block:210

B:45599,A:7689,offset:2788,leaf block:345

B:46378,A:44374,offset:786,leaf block:131

B:47200,A:3361,offset:2370,leaf block:326

B:47932,A:52288,offset:1336,leaf block:215

B:48736,A:82841,offset:2128,leaf block:250

B:49492,A:68781,offset:148,leaf block:9

B:50257,A:38011,offset:2348,leaf block:325

B:51074,A:96951,offset:1446,leaf block:220

B:51847,A:62231,offset:2744,leaf block:343

B:52618,A:31192,offset:654,leaf block:61

B:53362,A:72348,offset:2590,leaf block:336

B:54029,A:82275,offset:1380,leaf block:217

B:54788,A:28840,offset:2546,leaf block:334

B:55538,A:98163,offset:324,leaf block:32

B:56313,A:20704,offset:2282,leaf block:322

B:57065,A:90078,offset:1116,leaf block:205

B:57525,A:17975,offset:3096,leaf block:359

B:57973,A:52757,offset:1798,leaf block:236

B:58427,A:8888,offset:3140,leaf block:361

B:58890,A:65370,offset:764,leaf block:130

B:59627,A:28852,offset:1996,leaf block:320

B:60454,A:26779,offset:1160,leaf block:207

B:61261,A:35533,offset:2304,leaf block:323

B:62009,A:21826,offset:280,leaf block:22

B:62517,A:26392,offset:2986,leaf block:354

B:62950,A:3417,offset:1556,leaf block:225

B:63882,A:92888,offset:874,leaf block:194

B:64651,A:5358,offset:1732,leaf block:233

B:65511,A:32339,offset:544,leaf block:56

B:66290,A:26183,offset:1952,leaf block:243

B:67063,A:60386,offset:1182,leaf block:208

B:67767,A:48347,offset:2502,leaf block:332

B:68527,A:49114,offset:412,leaf block:37

B:69290,A:16760,offset:1864,leaf block:239

B:70112,A:32543,offset:1050,leaf block:202

B:70941,A:92527,offset:1908,leaf block:241

B:71758,A:23571,offset:610,leaf block:59

B:72210,A:32172,offset:3030,leaf block:356

B:72689,A:9869,offset:1666,leaf block:230

B:73155,A:27492,offset:3162,leaf block:362

B:73580,A:84669,offset:918,leaf block:196

B:74380,A:61469,offset:1754,leaf block:234

B:75228,A:21920,offset:192,leaf block:14

B:75625,A:16519,offset:3052,leaf block:357

B:76082,A:45066,offset:1600,leaf block:227

B:76901,A:3530,offset:962,leaf block:198

B:77370,A:45042,offset:3184,leaf block:363

B:77786,A:63188,offset:1688,leaf block:231

B:78604,A:5492,offset:566,leaf block:57

B:79500,A:6597,offset:1842,leaf block:238

B:80265,A:85811,offset:1094,leaf block:204

B:81035,A:6126,offset:2018,leaf block:245

B:81911,A:21386,offset:302,leaf block:31

B:82717,A:10268,offset:1622,leaf block:228

B:83172,A:46978,offset:3206,leaf block:364

B:83602,A:89835,offset:830,leaf block:192

B:84063,A:98697,offset:2964,leaf block:353

B:84571,A:9764,offset:1578,leaf block:226

B:85033,A:59776,offset:3074,leaf block:358

B:85471,A:83888,offset:478,leaf block:53

B:86224,A:39031,offset:2172,leaf block:252

B:86980,A:61579,offset:1006,leaf block:244

B:87142,A:42336,offset:1974,leaf block:200

B:87905,A:39935,offset:2656,leaf block:339

B:88630,A:74063,offset:258,leaf block:21

B:89335,A:42509,offset:2810,leaf block:346

B:90013,A:10693,offset:1490,leaf block:222

B:90671,A:21582,offset:2920,leaf block:351

B:91364,A:38857,offset:720,leaf block:128

B:92062,A:98705,offset:2414,leaf block:328

B:92852,A:82534,offset:1270,leaf block:212

B:93665,A:57106,offset:1820,leaf block:237

B:94450,A:36182,offset:456,leaf block:41

B:95109,A:82179,offset:2854,leaf block:348

B:95803,A:39017,offset:1468,leaf block:221

B:96562,A:53131,offset:2832,leaf block:347

B:97236,A:69746,offset:808,leaf block:132

B:97963,A:33843,offset:2766,leaf block:344

B:98709,A:78567,offset:1512,leaf block:223

B:99367,A:91536,offset:2942,leaf block:352

Where B represents the value of ID1, A represents the value of ID2, so here we

It is proved that all the key values of the combined index are stored in the branch node of the B + number.

What is stored here is the start value of the physical location in the leaf node.

Check casually:

Mysql > select * from testzh where id2=23

+-+

| | id | id2 | id3 | name | |

+-+

| | 99428 | 23 | 9079 | gaopeng |

| | 378 | 23 | 59613 | gaopeng |

| | 90301 | 23 | 93864 | gaopeng |

+-+

3 rows in set (0.00 sec)

Mysql > select * from testzh where id2=736

+-+

| | id | id2 | id3 | name | |

+-+

| | 2716 | 736 | 31951 | gaopeng |

| | 95328 | 736 | 53286 | gaopeng |

| | 75440 | 736 | 85983 | gaopeng |

+-+

3 rows in set (0.00 sec)

Mysql > select * from testzh where id2=1591

+-+

| | id | id2 | id3 | name | |

+-+

| | 10056 | 1591 | 58218 | gaopeng |

+-+

You can see that these values are available.

Then we go a step further, in order to calculate the space occupied by each row, I need to take out the root node to sort the actual physical space:

. / dataview testzh.ibd 4 | awk-F','{print $3}'| awk-F':'{print $2}'| sort-n

Come to the conclusion

one hundred and twenty six

one hundred and forty eight

one hundred and seventy

one hundred and ninety two

two hundred and fourteen

two hundred and thirty six

two hundred and fifty eight

.

3074

3096

3118

3140

3162

3184

3206

Because the field bytes are fixed, it is calculated that in the root node, the space occupied by a row of data is 22 bytes, 6 bytes of header overhead, 8 bytes of data overhead, and the remaining 8 bytes.

For a pointer (I just guess that the last 2 bytes are block numbers and the other 6 bytes are unknown), then we can verify that the data that the pointer points to the block contains our root

The pointing data of the node, we know that all the leaf nodes in the B+ tree contain all the data of the branch node, generally speaking, as long as we verify the pointing data of the branch node.

If it exists in the leaf node, it proves that the pointing block is correct. In the case of a query, once the page block is located, then the remaining work is to find the data by dichotomy.

Because I don't understand the meaning of all the digits of the pointer, but the last few bytes look like block numbers, so this is verified.

Of course, people who understand the source code to see my method is too low, I really do not have the ability to understand the source code.

Let's verify whether the pointing block contains pointing data. Here, leaf block is meaningless because it is a leaf node.

Write a script:

Test.sh

. / dataview testzh.ibd 8 | grep BRU 23pr ARO 59613

. / dataview testzh.ibd 249 | grep Bvu 736 Magi Avu 31951

. / dataview testzh.ibd 203 | grep Blaze 1591 Magazine 58218

. / dataview testzh.ibd 324 | grep BRU 2390 Magazine 34725

. / dataview testzh.ibd 54 | grep Bazu 3231 Magazine 16448

. / dataview testzh.ibd 360 | grep BRU 3647 Magi ARO 95182

. / dataview testzh.ibd 235 | grep BRU 4050 Magna 42271

. / dataview testzh.ibd 201 | grep Bvu 4751 Magazine 62810

. / dataview testzh.ibd 240,240,000,000,514,53731, dataview testzh.ibd

. / dataview testzh.ibd 34 | grep Bvu 6482

. / dataview testzh.ibd 333 | grep Blaze 7216 Magazine 26606

.

A total of 141 lines are validated

[root@testmy test] # sh test.sh

B:23,A:59613,offset:126,leaf block:24

B:736,A:31951,offset:126,leaf block:24

B:1591,A:58218,offset:126,leaf block:24

B:2390,A:34725,offset:126,leaf block:24

B:3231,A:16448,offset:126,leaf block:24

B:3647,A:95182,offset:126,leaf block:24

B:4050,A:42271,offset:126,leaf block:24

B:4751,A:62810,offset:126,leaf block:24

B:5614,A:53731,offset:126,leaf block:24

B:6482,A:29372,offset:126,leaf block:24

B:7216,A:26606,offset:126,leaf block:24

B:8028,A:78263,offset:126,leaf block:24

B:8777,A:61401,offset:126,leaf block:24

B:9562,A:34379,offset:126,leaf block:24

B:10353,A:93823,offset:126,leaf block:24

B:11114,A:50825,offset:126,leaf block:24

.

Output 141

As follows:

[root@testmy test] # sh test.sh | wc-l

one hundred and forty one

[root@testmy test] # cat test.sh | wc-l

one hundred and forty one

Then we can find that all the records of the root nodes are found in the leaf nodes, and we can see that the offsets are all physical offsets.

126and the first physical record (because I don't have delete data here), we also verified that the branch node storage is the physical location.

The first value in the upper block, and the value of the offset 126 here.

Finally, we draw a picture with five values, and maybe you will understand that there are root nodes above and leaf nodes below.

(note that all leaf nodes get the starting value. Do not assume that the leaf node has only one value, and that the same layer of B + tree is actually a two-way linked list.

About two-way linked list reference: http://blog.itpub.net/7728585/viewspace-2125114/

)

The level is limited. If there is any mistake, please let me know.

. / b_level tool source code:

Click (here) to collapse or open

# include

# include

# include

Void* reverse (void* pjinint length) / / Little_endian reverse

{

Int i

Char* s = (char*) (p)

Char* temp = (char*) calloc (1 dint length)

Memcpy (temp,s,length)

For (iSuppli)

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.