MySQLインデックスの背後にあるデータ構造とアルゴリズムの原理

序文

プログラミングの分野では、「プログラム = データ構造 + アルゴリズム」というよく知られたルールがあります。私は個人的にこの意見にあまり賛成できません (プログラムは単なるデータ構造とアルゴリズムの組み合わせではないと思うため) が、日々の勉強や仕事の中で、データ構造とアルゴリズムの重要性を感じています。多くのことにおいて、もう少し深く掘り下げる気があれば、間違いなくさまざまなデータ構造とアルゴリズムの知識に直面することになります。たとえば、ほぼすべてのプログラマーはデータベースを扱う必要があります。データベースがデータの保存、テーブルの作成、インデックスの作成、追加、削除、変更、クエリの実行にのみ使用される場合、データ構造はこれとは何の関係もないと思うかもしれません。しかし、ある日突然、もっと詳しく知りたくなり、データベースを最適化する方法を勉強したいと思ったら、必然的にインデックスの原理を勉強しなければなりません。インデックスの仕組みと、インデックスを合理的に使用してデータベースを最適化する方法を本当に理解したいのであれば、必然的に、さまざまなデータ構造とアルゴリズムに巻き込まれることになります。したがって、「プログラムの中核となる基礎＝データ構造＋アルゴリズム」と言われれば、私も全く同感です。達人を目指すプログラマーは、プログラムの中核となる基礎を必ず学ぶでしょう。

さて、ここまで述べてきましたが、私が実際に言いたいのは、データベースのインデックスを明確に学びたいのであれば、データ構造とアルゴリズムを入り口として学ぶ必要があるということです。残念ながら、私はまだインターネット上でデータベースのインデックスを原理レベルから紹介する資料を見つけていません（ここでは学術論文ではなく、一般的な資料のみを参照しています）。ハイレベルのプログラマーがいないわけではありませんが、この点を徹底的に説明できるデータベースの専門家は当社にたくさんいます。ただ、仕事が忙しかったり個人的な興味があったりするため、これらの専門家にはこのテーマに関する記事を書く時間も興味もありません。仕事の都合で、半端なプログラマーである私も、MySQL データベースのインデックスについて急いで勉強してきました。この点についての私の理解は大物たちの理解にはるかに及ばないものの、それでもこの浅い知識をここでまとめておきたいと思います。

まとめ

この記事では、MySQL データベースを研究対象として取り上げ、データベースインデックスに関連するいくつかのトピックについて説明します。 MySQL は多くのストレージエンジンをサポートしており、さまざまなストレージエンジンがインデックスに対して異なるサポートを提供していることに特に注意することが重要です。そのため、MySQL データベースは、BTree インデックス、ハッシュインデックス、フルテキストインデックスなど、複数のインデックスタイプをサポートしています。混乱を避けるため、この記事では BTree インデックスのみに焦点を当てます。これは、MySQL を使用するときに扱う主なインデックスだからです。ハッシュインデックスとフルテキストインデックスについては、この記事では説明しません。

記事の主な内容は3つの部分に分かれています。

***パート 1 では、主にデータ構造とアルゴリズム理論の観点から、MySQL データベースインデックスの数学的基礎について説明します。

パート 2 では、クラスター化インデックス、非クラスター化インデックス、カバーリングインデックスなどのトピックと、MySQL データベースの MyISAM および InnoDB データストレージエンジンのインデックスアーキテクチャ実装の組み合わせについて説明します。

パート 3 では、上記の理論的基礎に基づいて、MySQL でインデックスを高パフォーマンスで使用する戦略について説明します。