How to get the height of MySQL innodb B+tree

Preface

The reason why MySQL's innodb engine uses B+tree to store indexes is to minimize the number of disk IO times when querying data. The height of the tree directly affects the performance of the query. Generally, the height of the tree is more suitable at 3 to 4 floors. The purpose of database partitioning is also to control the height of the tree. So how do you get the height of the tree? The following example shows how to get the height of a tree.

Sample data preparation

The table creation statement is as follows:

CREATE TABLE `user` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) CHARACTER SET latin1 DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `name` (`name`),
  KEY `age` (`age`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

Insert 1 million records into the table. The data is as follows:

mysql> select * from user limit 2\G
*************************** 1. row ***************************
  id: 110000
name: ab
 age: 100
*************************** 2. row ***************************
  id: 110001
name: ab
 age: 100
2 rows in set (0.00 sec)

Get the height of the tree by querying the relevant data table

Take MySQL 5.6 as an example to explain how to get the height of the tree.

First get page_no

mysql> SELECT b.name, a.name, index_id, type, a.space, a.PAGE_NO FROM information_schema.INNODB_SYS_INDEXES a, information_schema.INNODB_SYS_TABLES b WHERE a.table_id = b.table_id AND a.space <> 0 and b.name='test/user';
+-----------+---------+----------+-------+----------+---------+
| name | name | index_id | type | space | PAGE_NO |
+-----------+---------+----------+-------+----------+---------+
| test/user | PRIMARY | 22 | 3 | 6 | 3 |
| test/user | name | 23 | 0 | 6 | 4 |
| test/user | age | 24 | 0 | 6 | 5 |
+-----------+---------+----------+-------+----------+---------+
3 rows in set (0.00 sec)

page_no is the serial number of the root page in the index tree. The meaning of other items can be found in:
https://dev.mysql.com/doc/refman/5.6/en/innodb-sys-indexes-table.html

Re-read page size

mysql> show global variables like 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)

Finally read the height of the index tree

$ hexdump -s 49216 -n 10 ./user.ibd
000c040 0200 0000 0000 0000 1600
000c04a

It can be found that PAGE_LEVEL is 0200, which means that the height of this secondary index tree is 3. The following 1600 is the index_id value of the index. The hexadecimal number 16 converts to decimal number 22. This 22 is exactly the index_id of the primary key above.
How is 49216 calculated in the above hexdump command? The formula is page_no * innodb_page_size + 64.
3*16384+64=49216

We use this method to check the heights of the other two indexes.

$ hexdump -s 65600 -n 10 ./user.ibd
0010040 0100 0000 0000 0000 1700
001004a
$ hexdump -s 81984 -n 10 ./user.ibd
0014040 0200 0000 0000 0000 1800
001404a

It can be seen that the height of the name index is 2 and the height of the age index is 3.

Estimation based on the index structure

If you do not have permission to the database server. You can also estimate the height of the tree based on the database index structure.
According to the B+Tree structure, non-leaf nodes store index data, and leaf nodes store all the data of each row.
The size of each index item of a non-leaf node is data size + pointer size. Assume pointer size is 8 bytes. Each page will not be fully occupied, leaving 1/5 of the space. Next, we estimate the height of the name and age indexes.

name index height estimate

The number of index entries stored per page for non-leaf nodes. Each page size is 16k. The value of name is ab. Occupies 2 bytes. The size of each data item is 2+8=10 bytes. The number of index items that can be stored on each page is 16384 * 0.8 / 10 = 1310.
The number of indexes stored in each leaf node page. Each page size is 16k. The size of each data item is 4+2+8=14 bytes. The number of indexes that can be stored on each page is 16384 * 0.8 / 14 = 936.
Two layers can store 1310*936=1226160 data records. It can be seen that below 1.2 million records, the height of the tree is 2.

age index height estimation

The number of index entries stored per page for non-leaf nodes. Each page size is 16k. age is of type int. Occupies 4 bytes. The size of each data item is 4+8=12 bytes. The number of index items that can be stored on each page is 16384 * 0.8 / 12 = 1092.
The number of indexes stored in each leaf node page. Each page size is 16k. The size of each data item is 4+4+8=16 bytes. The number of indexes that can be stored on each page is 16384 * 0.8 / 16 = 819.
Two layers can store 1092*819=894348 data records. It can be seen that below 900,000 records, the height of the tree is 2. 1 million records is 3 layers.

Other Tools

There is also a small tool to check out. InnoDB tablespace visualization tool innodb_ruby

The above is the details of the example of getting the height of MySQL innodb's B+tree. For more information about MySQL innodb's B+tree, please pay attention to other related articles on 123WORDPRESS.COM!