頭の中でMySQLのTreeを描けるようになろう
動機
業務でIndexがわからないと辛いということが多々あったので一旦BTreeを描くことができるようになろうとなりました。
結論から言うと、以下の動画がとても参考になりました。この研修を公開してくださったサイボウズさんありがとうございます。
https://www.youtube.com/watch?v=4Zj7Qgvt7RE
文字の方が得意という方は、こちらの記事も良いと思います。
要点まとめ
以下は自分の認識を深めるために、MySQLのサンプルテーブルであるWorldを使って色々遊んだ備忘録になります。
MySQL :: Other MySQL Documentation
ブランチノードとリーフノードがある
country(以下のようなデータ)で、主キーがCode、NameにIndexが貼られている場合Indexのツリーを描いていきます。
まず、ルートノードがあります。
次にNameのブランチノードができます。ブランチノードとは、Indexの値を範囲で取ったノードです。例えばWhere Name = Japanで検索する場合、Japan : Kenyaのブランチノードの中身のみを見れば良いのでとても効率が良くなります。
Japan:Kenyaのブランチノードに紐づくリーフノードを描くとこのようになります。
IndexのリーフノードはPrimaryKeyの値を持つためこのような形になります。
そのため、以下のようにNameが特定の値と一致する全ての情報が欲しい場合は一旦Indexに対してクエリを発行し、PrimaryKeyを取得して再度全情報を取得するクエリを発行することになります。
SELECT * FROM `country` WHERE `Name` = 'Japan'; //*なので、IndexのTreeだけでは欲しい情報が得られない 1. SELECT * FROM `country_index_name` WHERE `Name` = 'Japan'; -> JPN 2. SELECT * FROM `country` WHERE `Code` = "JPN";
一方で、全ての情報ではなく、Codeが欲しいだけの場合Indexに対するクエリだけで要望を満たすことができます。Indexのみで情報の取得ができることをカバリングインデックスと呼ばれます。
複合インデックスがある場合、順序が重要になる
では、複合インデックスの場合どのようなTreeになるかを考えていきましょう。
cityテーブルに、都市の地域と都市名で複合Indexを貼ります(日本だけで言えば、市名の重複を避けるようになっています)。
日本列島「地名」をゆく！：ジャパンナレッジ 第61回 同一市名あれこれ（1）
alter table `city` add index `multiple_idx` (`Name` , `District`);
この場合、Indexのツリーは以下のようになります。複合キーがある分ブランチノードが増えています。
ここで、以下のクエリを実行するとこの順序で読み取りが行われます。
SELECT * FROM city WHERE Name = "Cartagena" AND District = "Bolivar"
少し横に逸れてカーディナリティの差によるデータの読み込み量についてみてみましょう。
今回の例はカーディナリティにあまり差はありませんが、複合キーの順序を逆にしてみます。
alter table `city` add index `multiple_idx` (`District` , `Name`);
リーフノードが1つ増えています。
もっとカーディナリティに差があれば、カーディナリティが低いものを前に持ってくるとIndexを使っても参照範囲があまり減らないことが分かりやすいでしょう。
- 複合プライマリキーの場合、どのようなB木になるのだろう
最小、最大に対応するリーフノードがある
ブランチノードとリーフノードのところでは描きませんでしたが、概念的にはリーフノードには最小と最大があり、リーフノード間にはGAPというものがあります。
MySQL :: MySQL 5.6 リファレンスマニュアル :: 14.2.6 InnoDB のレコード、ギャップ、およびネクストキーロック
UPDATEやDELETEクエリ・FOR UPDATEを単なるユニークなレコードへ使用した場合問題にはなりませんが、非ユニークな要素に対してクエリを実行すると前後のGAPもロックが施されます。
実際に試してみましょう。
countryのNameにINDEXを貼り、以下のクエリを実行します。この時点では、NameにUNIQUE制約がないため前後のGAPもロックされます。
begin; SELECT *FROM `country` WHERE `Name` = "Japan" FOR UPDATE;
-- 当然ながらLock wait timeout exceeded; try restarting transaction UPDATE country SET IndepYear = "-600" WHERE Name = "Japan"; -- japanの次のGAPに入れようとするためLock wait timeout INSERT INTO `country` (`Code`, `Name`, `Continent`, `Region`, `SurfaceArea`, `IndepYear`, `Population`, `LifeExpectancy`, `GNP`, `GNPOld`, `LocalName`, `GovernmentForm`, `HeadOfState`, `Capital`, `Code2`) VALUES ('HGE', 'japan1', 'Asia', '', '0.00', NULL, '0', NULL, NULL, NULL, '', '', NULL, NULL, ''); -- japanと関係のないところに入るため成功 INSERT INTO `country` (`Code`, `Name`, `Continent`, `Region`, `SurfaceArea`, `IndepYear`, `Population`, `LifeExpectancy`, `GNP`, `GNPOld`, `LocalName`, `GovernmentForm`, `HeadOfState`, `Capital`, `Code2`) VALUES ('HGE', 'hoge', 'Asia', '', '0.00', NULL, '0', NULL, NULL, NULL, '', '', NULL, NULL, ''); -- これもGAPには影響がないため問題ない UPDATE country SET Name = "hoge" WHERE Code = "KZN"
続いて、UNIQUE制約をつけた上で実行してみます。
UNIQUE制約がついたことでGAPがロックされないため、INSERTすることができるようになります。
