2026/04/14 2:22
# B ツリーとデータベースのインデックス（2024 年） ## 1. はじめに B ツリーは、現代の大多數のデータベースが大量のデータを効率的に管理するために採用している基本的なデータ構造です。この構造は、限られたメモリリソースを備えたシステムにおいても、レコードの検索、挿入、削除を高速に行うことを可能にします。 ## 2. 基本概念 ### 構造 - **ルートノード**: 子ノードへのポインタを含む最も上位のノードです。 - **内部ノード**: キーと子ノードへのポインタを含み、実際のデータレコードは格納しません。 - **リーフノード**: 実際のデータレコードを格納し、データベース内の特定の項目に対応するキーを含みます。 - **バランス性**: すべてのリーフノードが同じレベルに位置していることで、検索操作に対し $O(\log n)$ の時間計算量を確保します。 ### 主要な特徴 - **自己平衡**: ノードへの挿入や削除に応じて自動的に再平衡を行い、バランスを維持します。 - **高い分岐数（High Fan-Out）**: 各ノードは多数の子ノードを持つことができ、ツリーの高さを低く抑え、キャッシュの活用効率を向上させます。 - **結合と分割操作**: 挿入および削除の際にバランスを維持するために使用されます。 ## 3. 他のインデックスタイプとの比較 | 特徴 | B ツリー | B+ ツリー | ハッシュテーブル | |----------------------|----------------|------------------|---------------------| | **検索速度** | $O(\log n)$ | $O(\log n)$ | 平均で $O(1)$ | | **範囲クエリへの対応**| 優れている | 優れている | 劣る | | **昇順での出力** | 可能 | 可能（順序ソート） | なし | | **メモリ使用量** | 中程度 | 低（リーフのみで十分） | 高い | ## 4. データベースでの利用ケース - リラショナルデータベースにおける主キーのインデックス化（例：MySQL、PostgreSQL）。 - フィルタリングやソートクエリに対する二次インデックス。 - 一貫性と耐久性を必要とするトランザクション系システムへの対応。 ## 5. 課題と現代への適応 - **オンメモリインデックス**: LSM ツリーなどの新興手法は、書き込みがメインの負荷に対して B ツリーを補完する役割を果たします。 - **ハイブリッド構造**: あるデータベースでは、正確な一致探索には B ツリー、バッチ書き込みには LSM ツリーを採用しています。 - **圧縮技術**: 最新のインデックスでは、ビットマップ圧縮やデルタ符号化などを組み込むことでストレージのオーバーヘッドを削減しています。 ## 6. まとめ B ツリーは、堅牢性、バランス、ならびに大量データセットの処理における効率性の点から、リラショナルデータベースシステムにとって不可欠な構成要素です。特定のユースケース向けに新しい構造が次々と登場する一方、多くの本番環境において B ツリーは、インデックス付きデータアクセスの基盤として引き続き重要な役割を果たしています。
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
現在の要約は質が高いが、やや範囲が狭い。キーポイントリストと完全に整合させながら過度に長くすることなく、以下の点を追加することを推奨する：非整数型の主要キー（例：タイムスタンプに対する文字列）を振る舞いのパターンとして簡潔に言及する。
改訂された要約：
テキストから得られる最も重要な示唆は、データベースのパフォーマンスに不可欠であることはいうまでもなく、効率的な主要キーの選択が特に重要であり、それは MySQL の InnoDB エンジンにおける B+ツリーの利用を通じて明確となる。順次整数は無作為識別子（UUIDv4）や順序化されていない文字列（例：電子メール地址）よりもはるかに優れている。これは、木の右側のリーフ上で予測可能な挿入を可能にし、木をバランスよく保ちかつ浅く維持するためである。無作為キーが非連続なリーフノードにデータを散らばらせるのに対し、順次キー（およびタイムスタンプベースのキー）はソートされたリーフを維持し、範囲スキャンを高速化するとともに、ノード訪問を減らすことでディスク入出力を最小限に抑える。B+ツリーは固定サイズのディスクブロック（通常 16KB）と整合しており、非効率的なキーサイズである UUIDv4 の 16 バイトは、より小さな整数キー（8 バイト）と比較してバッファプールメモリを浪費することになり、その結果として木が浅くlookup が高速化される。さらに、補助索引は値に対してこれらの主要キーに依存しており 2 ステップの lookup を行うが、最適化された主要キーの構造は依然として、不必要なパフォーマンス劣化なく高ボリュームデータベースが高速かつスケーラブルであることを保証する上で基本的である。
本文
B ツリーとは何ですか？
B ツリーは、特にデータベース管理システム（DBMS）など多くのソフトウェアの基盤となる重要な役割を果たしています。MySQL、Postgres、MongoDB、Dynamo など、多数のシステムがインデックスを通じてデータ検索を効率的に行うために B ツリーに依存しています。この記事を読み終える頃には、B ツリーと B+ツリーの仕組み、なぜデータベースがそれらを検索用インデックスとして採用するのか、そして UUID を主キーとして使用するのに懸念すべき点があるのかを理解していることでしょう。また、本文中で議論されているデータ構造のインタラクティブなアニメーションを実際に操作する機会も得られます。クリックする準備をしておきましょう。
コンピュータ科学には、データを保存・検索・管理するために利用可能な多種多様なデータ構造が存在します。B ツリーはその一例であり、データベースアプリケーションで広く使用されています。B ツリーは、プログラマーが「木構造」と呼ぶ形式にデータを保存します。「ツリー」という用語の使い方にご馴染みでない方におきましては、実際の構造は根（root）から枝分かれしていくような樹形に見えます。
以下に、当ブログにおける最初のインタラクティブな要素をご紹介します。これにより、B ツリーの構造を視覚化でき、キー/値ペアを追加したり、ノードあたりのキー/値ペアの数を増減させて変化を確かめることができます。「Add」または「Add random」ボタンを数回クリックしてみて、詳細に入る前に直感的に仕組みを理解してみましょう。
上記のアニメーションが速すぎたり遅すぎたりする場合は、本記事全体における B ツリーの動作速度を下側から調整可能です。
すべての B ツリーは、「ノード」（矩形）と「子ポインタ」（ノードを繋ぐ線）で構成されています。一番上のノードをルートノード（root node）、最下層のノードをリーフノード（leaf nodes）、それ以外のノードを内部ノード（internal nodes）と呼びます。B ツリーの正式な定義は出典により異なりますが、以下は一般的な定義です。
B ツリーにおける形式定義
K 階の B ツリーとは、以下の性質を持つ木構造のことです：
- 各ノードには N つのキー/値ペアが格納されており、N は 1 より大きく、かつ K 以下である（1 < N ≤ K）。
- 各内部ノードは少なくとも N/2 のキー/値ペアを有し（内部ノードとはリーフノードまたはルートノードを除くノードの総称）、
- 各ノードには N+1 個の子ノードが接続されている。
- ルートノードは少なくとも 1 つの値と 2 つの子ノードを持ち、それが単独のノードである場合を除く。
- すべてのリーフノードは同じ層にある。
順序付けと検索
B ツリーのもう一つの重要な特徴は「順序付け（ordering）」です。各ノード内では要素が順序付けられて格納されており、あるキーの左側にある子ノードにはそのキーよりも小さい値のみを含み、右側の子ノードにはより大きい値のみを含みます。
この強制された順序付けにより、キーの検索を非常に効率的に行うことができます。ルートノードから始めて以下のように操作します：
- 対象とするキーが存在するか確認する。
- もし存在しなければ、そのキーが挿入されるべき位置（ノード内）を見つける。
- その位置に対応する子ポインタを辿り、次の層へ進み、同じプロセスを繰り返す。
この方法で検索する場合、各階層あたり 1 つのノードのみを訪れれば済みます。したがって、訪問するノード数（あるいは木の高さ）が少ないほど、検索は高速化されます。下のツリーでいくつかのキーを検索してみましょう：
B ツリーは、大量のデータを長期ストレージ（ディスク）に永続させる必要がある場合に特に適しています。これは、各ノードが固定されたバイト数を消費するためであり、このサイズをディスクブロックと調和させることができるからです。
ハードディスクドライブ（HDD）やソリッドステートドライブ（SSD）でのデータの読み書きは「ブロック」と呼ばれる単位で行われます。これらは通常、4096 バイト（4k）、8192 バイト（8k）、または 16384 バイト（16k）の長さのバイト列であり、単一のディスクには数百万から数十億ブロック以上の容量を持ちます。一方、RAM は通常、バイト単位でアドレス指定可能です。
このことが、B ツリーがディスク上で永続データを整理・保存する際に非常に効果を発揮する理由です。B ツリーの各ノードは、ディスクブロックのサイズ（またはその倍数）に合わせるように設定可能だからです。
ツリー各ノードが格納できる値の数は、割り当てられたバイト数と 1 つのキー/値ペアで消費されるバイト数に基づいて決定されます。上記の例では、非常に小さなノード——具体的には 3 つの整数値と 4 つの子ポインタを格納するもの——を見ていただきました。もしディスクブロックおよび B ツリーノードが 16k（16,384 バイト）で、キー・値・子ポインタすべてが 8 ビット（1 バイト）の場合には、各ノードに 682 つのキー/値ペアと 683 つの子ポインタを格納することが可能です。高さ 3 レベルの木であれば、300,000,000 個以上のキー/値ペア（682 × 682 × 682 = 317,214,568）を格納できます。
B+ツリー
B ツリーは優れた構造ですが、多くのデータベースインデックスではより洗練されたバリエーションである「B+ツリー」を使用します。これは B ツリーに似ていますが、以下のルール変更が施されています：
- キー/値ペアはリーフノードのみに格納される。
- 非リーフノードにはキーと対応する子ポインタのみが格納される。
MySQL のインデックスにおける B+ツリーの実装特有の追加ルールとして、以下のものがあります：
- 非リーフノードは N 個の子ポインタを格納し（B ツリーでは N+1）、
- すべてのノードには「次（next）」および「前（previous）」ポインタも含まれ、ツリーの各層が双方向連結リストとしても機能する。
以下は、これらの改まった特性を備えた B+ツリーがどのように動作するかを示す別の視覚化です。今回は、内部ノードのキー数やリーフノードのキー数、さらにキー/値ペアの追加数を個別に調整可能です。
なぜ B+ツリーがデータベースに適しているのか？
主な理由は 2 つあります：
- 内部ノードは値を格納する必要がないため、内部ノードあたりに格納できるキー数を増やせます！これにより木構造を浅く保つのに役立ちます。
- すべての値は同じ階層に配置され、最下層の連結リストを介して順序通りに巡回できます。
ぜひ B+ツリー上の検索も試してみましょう：
MySQL における B+ツリー
世界で最も人気のあるデータベース管理システムの筆頭である MySQL は、複数のストレージエンジンをサポートしています。最も一般的に使われているのは InnoDB であり、これらは B+ツリーに大きく依存しています。実際には、InnoDB はテーブルのデータをすべて B+ツリーとして保存し、テーブルの主キーをツリーのキーとして使用します。
新しい InnoDB テーブルを作成する際、主キーを指定することが義務付けられています。データベース管理者やソフトウェアエンジニアは、この値として単純な自動増分整数をよく用います。その背後では、MySQL + InnoDB は各新規作成されたテーブルに対して B+ ツリーを作成します。このツリーのキーは、設定した主キーに一致し、値は各行の残りの列値であり、リーフノードのみで保存されます。
これらの B+ ツリーにおける各ノードのサイズは、デフォルトで 16k に設定されています。MySQL がデータをアクセスする際（キー、値など）、そのデータが関連付けられたページ（B+ツリーノード）全体をディスクから読み込みます。たとえそのページに必要としない他のキーや値が含まれていてもです。
各ノードに格納される行の数は、テーブルの「幅」によって決まります。「狭い」テーブル（列が少ない）では、各リーフは数百行を格納できます。「広い」テーブル（列が多い）では、各リーフには単位の桁数のみ（例えば 1〜9 行）しか格納できない場合があります。InnoDB は行サイズがディスクブロックを超える場合もサポートしていますが、本稿では詳細に踏み込みません。
下の視覚化を使用して、内部ノードおよびリーフノードのキー数がツリー深度に与える影響を見てみましょう。木が深いほど要素を検索する速度が遅くなるため、データベースには浅い木構造が望ましいです！
また、InnoDB テーブルに対して主キー以外の列に基づくセカンダリインデックスを作成することも一般的です。これらは、SQL クエリの WHERE 句でのフィルタ処理を高速化するために必要な場合があります。各セカンダリインデックスには追加の永続的な B+ ツリーが構築されます。これらの場合、キーはユーザーがインデックス作成対象とした列で、値は関連する行の主キーとなります。セカンダリインデックスをクエリに使用する場合：
- セカンダリインデックス用の B+ ツリー上で検索が行われ、
- 一致する結果に対応付けられた主キーが収集され、
- 次にこれらがメインテーブルの B+ ツリー上の追加検索（複数回可）に利用されて、実際の行データを取得する。
次のデータベーススキーマを考えましょう：
CREATE TABLE user ( user_id BIGINT UNSIGNED AUTO_INCREMENT NOT NULL, username VARCHAR(256) NOT NULL, email VARCHAR(256) NOT NULL, PRIMARY KEY (user_id) ); CREATE INDEX email_index ON user(email);
これにより 2 つの B+ツリーインデックスが作成されます：
- テーブルの主キー用のインデックス（キーは
、値には他の 2 つの列を使用）。user_id
（キーはemail_index
、値はemail
）。user_id
次のようなクエリを実行した場合：
SELECT username FROM user WHERE email = 'x@planetscale.com';
まず
email_index'x@planetscale.com'user_idusername全体として、クエリを完了するために訪問する必要のあるブロックやノードの数を最小限に抑えることが望ましいです。訪問するノード数が少ないほど、クエリの実行速度が向上します。テーブルに選択した主キーは、必要なノード訪問回数を最小化するために極めて重要です。
挿入操作
テーブルデータが B+ ツリー内にどのように配置されるかは、選択したキーの影響を受けます。つまり、主キーの選択はディスク上のデータ配置と結果としてのパフォーマンスに影響します。主キーを選ぶ際は慎重に検討しましょう！
主キーに関する一般的な選択肢は以下の通りです：
- 整数シーケンス（例：
）BIGINT UNSIGNED AUTO_INCREMENT - UUID（複数のバージョンが存在します）
まずは UUIDv4 を主キーとして使用する場合の影響を考察してみましょう。UUIDv4 はほぼランダムな 128 ビット整数です。これらをシミュレートするために、B+ ツリー可視化ツールにランダムな整数を多数挿入します。各挿入において、アクセスされたノードが緑色で強調表示されます。また、ノード分割時に既存ノードに保持すべきキーの割合も制御できます。「Add random」ボタンを数回クリックして試してみましょう。どのような現象が観察されるか考えてみてください。
UUIDv4 に関する観察事項
いくつかの観察結果：
- 挿入に対する訪問するノードは事前には予測不可能である。
- 挿入先のリーフノードも予測不可能である。
- リーフ内の値は順序付けられていない。
問題 1 と 2 は問題となるのは、多数の挿入が行われる過程でツリーの多くのノード（ページ）を訪問せざるを得なくなるためです。この過剰な読み書きはパフォーマンス低下を引き起こします。問題 3 は、挿入順序に基づいてデータを検索・閲覧する意図がある場合に特に問題となります。
同様の問題は他の一部の UUID バージョンでも起こり得ますが、それほど極端ではありません（例：UUID v3 および v5 はハッシュ化によって生成されるため、連続性を持たず、ランダム挿入に似た挙動を示します）。一方、UUIDv7 はこれらの課題のいくつかを効果的に克服しています。
代わりに順序付きの
BIGINT UNSIGNED AUTO_INCREMENTこれにより上記の問題はすべて回避されます：
- 新しい値を挿入する際、常に右端のパスを辿ります。
- リーフノードはツリーの右側のみにも追加されます。
- リーフレベルでは、挿入時点を基準にデータが順序付けされます。
- 項目 1 と 2 のため、連続して多数の挿入が行われると同じページパスを再訪問し、多数のキー/値ペアを挿入する際に I/O リクエストが削減されます。
下の棒グラフは、上記の 2 つの B+ ツリーにおける直近 5 回の挿入で訪問した一意のノードの数を示しています。深さが等しい場合、ランダムなパターンの方がわずかに高い値を示し、つまりパフォーマンスが悪いことを意味します。
分割割合が順序付き挿入とランダム挿入のパターンに与える影響について興味がある方は、以下のインタラクティブ可視化をご覧ください。スライダーを使用して分割割合を設定し、400 キーの挿入シーケンス中における各段階で訪問したノード数を示すライングラフを確認してください。ほとんどのケースにおいて、順序付き挿入はランダム挿入に比べて著しく少ないノード訪問数しか必要なく、かつ予測可能性が高いことがわかります。
データの順序付け
データベースから時系列順でデータを検索することは一般的です。X 上のタイムラインや Slack のチャット履歴などを思い浮かべてください。私たちは通常、投稿やメッセージを時間経過順（または逆順）で見たいと考えています。これは、「近接した時間範囲内の」データブロックを読み取ることを意味します。このようなクエリは次のように表されます：
SELECT username, message_text, ... FROM post WHERE sent > $START_DATETIME AND sent < $END_DATETIME ORDER BY sent DESC;
UUIDv4 を主キーとして使用する場合、これをどのように扱うかを考えましょう。下の B+ ツリーでは、多数のランダムキーとその値がテーブルに挿入されています。値範囲を見つけようとしてください。何が見られるか？
注意してください。値シーケンスは多くの非連続なリーフノードに分散しています。一方、順序付きで挿入された値を検索することを考えましょう：
この場合、検索結果を持つすべてのページは隣接しており、いくつかの行を検索してもそれらがすべて単一のページ内で隣り合うこともあります。このようなクエリパターンに対しては、順序付き主キーを用いることで必要な読み込むページ数を削減できます。
主キーサイズ
また重要な考慮点としてキーサイズがあります。私たちは常に主キーを以下のようにしたいと考えています：
- 枯渇に遭わないほど大きく
- 過度なストレージ使用を避けるほど小さく
整数シーケンスの場合、小規模なテーブルでは MEDIUMINT（1,600 万個の一意値）または INT（40 億個の一意値）で十分かもしれません。大規模なテーブルでは、安全のために BIGINT（約 18 セクシリオンの可能性）にジャンプするのが一般的です。BIGINT は 64 ビット（8 バイト）、UUID は通常 128 ビット（16 バイト）であり、MySQL の最大整数型の倍のサイズになります。B+ ツリーノードが固定サイズであるため、BIGINT を使用すると UUID よりも各ノードあたりのキー数を増やせます。これにより木構造が浅くなり、検索速度が向上します。
例えば、ツリーノードが 100 バイト、子ポインタが 8 バイト、値が 8 バイトの場合、各ノードに 4 つの UUID（および 4 つの子ポインタ）を収められます。下の挿入シーケンスボタンを押して動作を確認しましょう。
もし BIGINT を使用していた場合、代わりに各ノードに 6 つのキー（および対応する子ポインタ）を収められます。これにより木構造が浅くなり、パフォーマンス向上につながります。
ページと InnoDB
B+ ツリーの大きな利点の一つは、ノードサイズを自由に設定できるという点にあります。InnoDB では、B+ ツリーノードのサイズは InnoDB ページサイズである 16k に設定されることが一般的です。
クエリ実行（つまり B+ツリー上的な巡回）において、InnoDB はディスクから個々の行や列を読み込んではいません。データアクセスが必要な場合、関連するページ全体をディスクから読み込みます。
InnoDB はこれに対するいくつかの工夫を持っており、中でも主要なのが「バッファプール」です。バッファプールは InnoDB ページのためのインメモリキャッシュであり、ディスク上のページと MySQL クエリ実行の間で機能します。MySQL がページを読み取る際、まずバッファプール内に既に存在するか確認します。存在すればそこから読み取り、ディスク I/O をスキップできます。存在しなければディスク上に位置を見つけ、バッファプールに追加してクエリ処理を続行します。
バッファプールはクエリパフォーマンスに大きく寄与します。これがない場合、クエリワークロードを処理するために大幅に多くのディスク I/O 操作が発生することになります。バッファプールがあるにもかかわらず、訪問する必要のあるページ数を最小化することでパフォーマンス向上が可能であり（1）バッファプール内のページ查找にもわずかなコストがかかり、かつ（2）バッファプールの読み込みと除去の回数を削減できるためです。
他の状況
ここでは主に順序付きキーとランダム/UUID キーを比較することに焦点を当ててきましたが、ここで示された原則は、どのような主キーまたはセカンダリキーを検討しているかに関係なく心に留めておくのに役立ちます。例えば、
user.created_at逆に、
user.email_address結論
これはすでに長いブログ記事となりましたが、B+ ツリー、インデックス、MySQL の主キー選択についてはさらに多くを語ることも可能です。一見単純そうに見えますが、データベースのパフォーマンスの極限を引き出すためには考慮すべきニュアンスは莫大です。より深く実験したい場合は、専用インタラクティブ B+ ツリーウェブサイトにご確認ください。通常の B ツリーをご覧になりたい場合はこちらをご覧ください。インデックスについて少しでも理解を深めていただけたら幸いです！
早期レビューをご快諾いただいた Sam Rose 様にも特別感謝申し上げます。