InnoDB file structure, a look a the primary key tree structure

Recently, I found a very handy tool, innodb-recovery, that can break an InnoDB file in pages. I am a visual type person so what a better occasion to try to learn more about the InnoDB file structure. To explore the file structure, I used the following table:

Create Table: CREATE TABLE `test_innodb_index` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `data` varchar(50) DEFAULT NULL,
  `spacer` char(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idxdata` (`data`)
) ENGINE=InnoDB AUTO_INCREMENT=1901 DEFAULT CHARSET=latin1

and inserted a bunch of rows like these:

select * from test_innodb_index limit 4;
+----+-------+--------+
| id | data  | spacer |
+----+-------+--------+
|  1 | aaaaa | |      |
|  2 | aaaaa | |      |
|  3 | aaaaa | |      |
|  4 | aaaaa | |      |
+----+-------+--------+
4 rows in set (0.00 sec)

After the insertion, the table status looked like this:

mysql> show table status like 'test_innodb_index'\G
*************************** 1. row ***************************
           Name: test_innodb_index
         Engine: InnoDB
        Version: 10
     Row_format: Compact
           Rows: 2156
 Avg_row_length: 45
    Data_length: 98304
Max_data_length: 0
   Index_length: 65536
      Data_free: 0
 Auto_increment: 1901
    Create_time: 2009-03-06 18:15:23
    Update_time: NULL
     Check_time: NULL
      Collation: latin1_swedish_ci
       Checksum: NULL
 Create_options:
        Comment:
1 row in set (0.01 sec)

As one can notice, the primary key tree has 6 pages (6x16x1024 = 98304). To further ease our task, the innodb-recovery tool groups the pages belonging in the same tree inside a directory. Of course, one of these directories has exactly 6 pages in it which list like:

$ ls
10-00000010.page  12-00000012.page  3-00000003.page  5-00000005.page  6-00000006.page  7-00000007.page

Now comes the fun part… hexdump I guessed the lowest number would be the root page and I found it to be correct. Through hexdump, the page look like this:

00000000  15 0b c5 fb 00 00 00 03  ff ff ff ff ff ff ff ff  |................|
00000010  00 00 00 00 34 5c 25 c6  45 bf 00 00 00 00 00 00  |....4\%.E.......|
00000020  00 00 00 00 00 23 00 02  00 be 80 07 00 00 00 00  |.....#..........|
00000030  00 b6 00 02 00 04 00 05  00 00 00 00 00 00 00 00  |................|
00000040  00 01 00 00 00 00 00 00  00 81 00 00 00 23 00 00  |.............#..|
00000050  00 02 00 f2 00 00 00 23  00 00 00 02 00 32 01 00  |.......#.....2..|
00000060  02 00 1b 69 6e 66 69 6d  75 6d 00 06 00 0b 00 00  |...infimum......|
00000070  73 75 70 72 65 6d 75 6d  00 10 00 11 00 0e 00 00  |supremum........|
00000080  00 01 00 00 00 05 00 00  00 19 00 0e 00 00 00 ff  |................|
00000090  00 00 00 06 00 00 00 21  00 0e 00 00 03 03 00 00  |.......!........|
000000a0  00 07 00 00 00 29 00 0e  00 00 05 07 00 00 00 0a  |.....)..........|
000000b0  00 00 00 31 ff ba 00 00  07 0b 00 00 00 0c 00 00  |...1............|
000000c0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00003ff0  00 00 00 00 00 70 00 63  db a8 30 12 34 5c 25 c6  |.....p.c..0.4\%.|
00004000

Although not completely obvious, we can find the first primary key “00 00 00 01″ starting at position 7e which is followed by “00 00 00 05″ which point to the page begining by the primary key. A quick look to the files listing confirm that there is indeed a page “5″. The next primary key is “00 00 00 ff” which means there are 254 rows in page “5″. The enumeration continues at each 14 bytes which means there are 6 bytes I don’t know what they means. We can also observe that the block header is 125 bytes long.

Going to the leaves, let’s hexdump page “5″ which should begin with primary key “1″. Just the first part is presented here:

00000000  50 a1 22 9e 00 00 00 05  ff ff ff ff 00 00 00 06  |P.".............|
00000010  00 00 00 00 34 59 a9 d2  45 bf 00 00 00 00 00 00  |....4Y..E.......|
00000020  00 00 00 00 00 23 00 40  3d d7 82 17 1e 0d 1f 9b  |.....#.@=.......|
00000030  3d c0 00 05 00 00 00 fe  00 00 00 00 00 00 00 00  |=...............|
00000040  00 00 00 00 00 00 00 00  00 81 00 00 00 00 00 00  |................|
00000050  00 00 00 00 00 00 00 00  00 00 00 00 00 00 01 00  |................|
00000060  02 00 1c 69 6e 66 69 6d  75 6d 00 04 00 0b 00 00  |...infimum......|
00000070  73 75 70 72 65 6d 75 6d  05 00 00 00 10 00 1e 00  |supremum........|
00000080  00 00 01 00 00 00 08 6b  0a 00 00 00 00 32 21 c1  |.......k.....2!.|
00000090  61 61 61 61 61 7c 05 00  00 00 18 00 1e 00 00 00  |aaaaa|..........|
000000a0  02 00 00 00 08 6b 0a 00  00 00 00 32 21 df 61 61  |.....k.....2!.aa|
000000b0  61 61 61 7c 05 00 00 00  20 00 1e 00 00 00 03 00  |aaa|.... .......|
000000c0  00 00 08 6b 0a 00 00 00  00 32 21 fd 61 61 61 61  |...k.....2!.aaaa|
000000d0  61 7c 05 00 04 00 28 00  1e 00 00 00 04 00 00 00  |a|....(.........|
000000e0  08 6b 0a 00 00 00 00 32  22 1b 61 61 61 61 61 7c  |.k.....2".aaaaa||

We do find our first primary key, “00 00 00 01″ beginning at position 7f. In fact, it is probably not the true begining, the preceeding 6 bytes are the “extra bytes” (see MySQL_Internals). The PK is followed by “00 00 00 08 6b 0a 00 00 00 32 21 c1″ which are the offset of column 1 and 2 in that row. Then we have the two strings, the varchar “aaaaa” and the char(1) “|”. The “05″ that follows is probably the length of the varchar. After the varchar length, there are another 6 bytes of “extra bytes “00 00 00 18 00 1e” and the second row.

ref.:
1. http://forge.mysql.com/wiki/MySQL_Internals_InnoDB
2. http://code.google.com/p/innodb-tools/