MySQL innodb B+ツリーの高さを取得する方法

序文

MySQL の InnoDB エンジンがインデックスの保存に B+tree を使用する理由は、データのクエリ時にディスク IO 回数を最小限に抑えるためです。ツリーの高さはクエリのパフォーマンスに直接影響します。一般的に、木の高さは3階から4階が適しています。データベースのパーティション分割の目的は、ツリーの高さを制御することにもあります。では木の高さはどうやって測るのでしょうか?次の例は、木の高さを取得する方法を示しています。

サンプルデータの準備

テーブル作成ステートメントは次のとおりです。

テーブル `user` を作成します (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) 文字セット latin1 デフォルト NULL,
  `age` int(11) デフォルト NULL,
  主キー (`id`)、
  キー `name` (`name`),
  キー `age` (`age`)
) エンジン=InnoDB デフォルト文字セット=utf8

テーブルに 100 万件のレコードを挿入します。データは次のとおりです。

mysql> ユーザー制限 2\G から * を選択
************************** 1. 行 ****************************
  id: 110000
名前: ab
 年齢: 100
************************** 2. 行 ****************************
  id: 110001
名前: ab
 年齢: 100
セット内の 2 行 (0.00 秒)

関連するデータテーブルをクエリして木の高さを取得します

MySQL 5.6 を例に、ツリーの高さを取得する方法を説明します。

まず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';
+-----------+----------+----------+---------+---------+---------+
| 名前 | 名前 | インデックス ID | タイプ | スペース | PAGE_NO |
+-----------+----------+----------+---------+---------+---------+
| テスト/ユーザー | プライマリ | 22 | 3 | 6 | 3 |
| テスト/ユーザー | 名前 | 23 | 0 | 6 | 4 |
| テスト/ユーザー | 年齢 | 24 | 0 | 6 | 5 |
+-----------+----------+----------+---------+---------+---------+
セット内の 3 行 (0.00 秒)

page_no は、インデックス ツリー内のルート ページのシリアル番号です。その他の項目の意味については以下を参照してください。
参考文献

ページサイズを再読み込み

mysql> 'innodb_page_size' のようなグローバル変数を表示します。
+------------------+-------+
| 変数名 | 値 |
+------------------+-------+
| innodb_ページサイズ | 16384 |
+------------------+-------+
セット内の 1 行 (0.00 秒)

最後にインデックスツリーの高さを読み取ります

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

PAGE_LEVEL が 0200 であることがわかります。これは、このセカンダリ インデックス ツリーの高さが 3 であることを意味します。次の 1600 はインデックスの index_id 値です。 16 進数の 16 は 10 進数の 22 に変換されます。この 22 は、まさに上記の主キーの index_id です。
上記の hexdump コマンドでは 49216 はどのように計算されますか?式は、page_no * innodb_page_size + 64 です。
3*16384+64=49216

この方法を使用して、他の 2 つのインデックスの高さを確認します。

$ 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

名前インデックスの高さは 2、年齢インデックスの高さは 3 であることがわかります。

インデックス構造に基づく推定

データベース サーバーへの権限がない場合。データベースのインデックス構造に基づいて木の高さを推定することもできます。
B+ツリー構造によれば、非リーフノードにはインデックスデータが保存され、リーフノードには各行のすべてのデータが格納されます。
非リーフノードの各インデックス項目のサイズは、データ サイズ + ポインタ サイズです。ポインターのサイズは 8 バイトであると想定します。各ページは完全には占有されず、1/5 のスペースが残ります。次に、名前と年齢のインデックスの高さを推定します。

名前 インデックス 高さ 推定

非リーフ ノードのページあたりに保存されるインデックス エントリの数。各ページのサイズは 16k です。 name の値は ab です。 2バイトを占有します。各データ項目のサイズは 2+8=10 バイトです。各ページに保存できるインデックス項目の数は、16384 * 0.8 / 10 = 1310 です。
各リーフ ノード ページに保存されるインデックスの数。各ページのサイズは 16k です。各データ項目のサイズは 4+2+8=14 バイトです。各ページに保存できるインデックスの数は、16384 * 0.8 / 14 = 936 です。
2 つのレイヤーには 1310*936=1226160 のデータ レコードを保存できます。 120 万件のレコード未満では、ツリーの高さは 2 であることがわかります。

年齢指数身長推定

非リーフ ノードのページあたりに保存されるインデックス エントリの数。各ページのサイズは 16k です。 age は int 型です。 4バイトを占有します。各データ項目のサイズは 4+8=12 バイトです。各ページに保存できるインデックス項目の数は、16384 * 0.8 / 12 = 1092 です。
各リーフ ノード ページに保存されるインデックスの数。各ページのサイズは 16k です。各データ項目のサイズは 4+4+8=16 バイトです。各ページに保存できるインデックスの数は、16384 * 0.8 / 16 = 819 です。
2 つのレイヤーには 1092*819=894348 のデータ レコードを保存できます。 90万件のレコード以下ではツリーの高さが2であることがわかります。100万件のレコードは3層です。

その他のツール

チェックするための小さなツールもあります。 InnoDB テーブルスペース可視化ツール innodb_ruby

上記は、MySQL innodb の B+tree の高さを取得する例の詳細です。MySQL innodb の B+tree の詳細については、123WORDPRESS.COM の他の関連記事に注目してください。