LASSIC Media らしくメディア

テーブルの行数が増えるほど検索が遅くなる場面で、開発会社から「B木を使ったインデックスです」という説明を受けても、具体的に何を意味するのかを掴みにくいと感じる発注担当者もいるでしょう。索引の設計しだいで検索速度や書き込み負荷は大きく変わるため、仕組みを知らないまま提案を受け入れると、後になって性能面の想定違いに気づくこともあります。サービスが成長し、扱うデータ量が増えてから索引の設計不足に気づく、という展開は避けたいところです。

この記事では、発注者やプロジェクトマネージャーに向けて、B木とは何か、なぜ多くのデータベースがこの構造を索引に選んでいるのか、そしてインデックス設計をレビューする際に押さえておきたい勘所を整理します。実装コードの深掘りではなく、開発会社との会話や判断に役立つ考え方に絞って解説します。

B木とは

B木とは、1つのノードが複数の子を持つ平衡木の一種で、ディスク上の大量データを少ない読み込み回数で探索・追加・削除できるように設計されたデータ構造です。データベース管理システムの多くは、このB木やその派生であるB+木を、テーブルの索引(インデックス)の方式として採用しています^*3。

「木構造」と聞くと実装の内部事情のように思えるかもしれませんが、発注者やプロジェクトマネージャーにとっても無縁ではありません。索引の設計しだいで検索速度や書き込み負荷が大きく変わるため、開発会社からの提案やレビューを的確に判断するには、B木の基本的な仕組みを押さえておくことが欠かせないのです。

本稿で扱うのは、B木そのものを自前で実装する話ではありません。多くの場面では既存のデータベース製品が内部でB木を管理してくれるため、発注者に求められるのは、その仕組みを踏まえてどの列に索引を張るべきかを判断し、開発会社の提案を評価する視点です。

PostgreSQLでは索引を作成すると既定でB木が使われ^*1、MySQLでも主要な索引方式としてB木(B-Treeインデックス)が採用されています^*2。特定の製品に限った知識ではなく、リレーショナルデータベースを扱ううえで土台となる考え方だといえるでしょう。

索引の設計は、システムを開発した直後よりも、データが積み上がった運用後半になって効いてくる要素です。B木の基本を知らないまま設計を丸ごと開発会社に任せてしまうと、どの列に索引を張るべきかの根拠を尋ねられても判断できず、性能劣化が起きてから原因を切り分けるのに時間を取られかねません。発注段階で仕組みの勘所を押さえておくことは、後工程のやり直しを避ける手立てにもなります。

索引になぜ木構造を使うのか

索引の役割を理解するには、索引が無い状態を思い浮かべると分かりやすいでしょう。索引の無いテーブルで特定の行を探す場合、データベースは先頭から順に全行を読み比べる全件走査(フルスキャン)します。行数が10倍に増えれば、比較回数も単純に10倍へ膨らむのです。テーブルが小さいうちはこの方式でも体感できるほどの遅さにはなりませんが、行数が積み上がるほど、全件走査の負担は目に見える形で表れてきます。

この全件走査の計算量はO(n)と表され、データ件数nに比例して探索コストが増えていく性質のものです。これに対し、平衡木を使った索引では探索1回ごとに調べる範囲を大きく絞り込めるため、計算量はO(log n)に抑えられます^*3。件数が増えても比較回数の伸びがゆるやかにとどまる点こそ、木構造を索引に使う狙いにほかなりません。

加えて、実務ではもう一つの狙いがあります。データベースはディスクや低速なストレージにデータを保存するため、1回のデータ読み込み(ディスクI/O)にかかる時間が、メモリ上の計算に比べて大きなコストになるのです。索引の木を浅く保ち、読み込み回数そのものを減らすことがB木の設計思想の根幹にあります^*3。

紙の辞書を思い浮かべると、この違いは掴みやすいでしょう。ページの端が索引順に並んでいるからこそ、目的の単語を数回のページめくりで見つけられます。もし単語がでたらめな順で並んでいたら、最初から順にめくって探すしかありません。データベースにおける索引の有無も、これと同じ差を生んでいるのです。

加えて、データベースの多くは、頻繁に参照される索引の上位階層をメモリ上にキャッシュする仕組みを備えています。ルートに近いノードほどアクセスが集中するため、キャッシュに乗りやすく、実際にディスクへアクセスする回数は理論上の目安よりもさらに少なく収まる場面が多いのです。木構造そのものの効率と、こうした周辺の仕組みが組み合わさって、実務での応答速度が保たれています。

ノードと次数、平衡が生む探索の速さ

B木の基本単位は「ノード」です。1つのノードには複数のキー(検索対象の値)と、それに対応する子ノードへのポインタが格納されます。1つのノードが持てる子の数の上限を「次数」と呼び^*3、次数を大きく取るほど、少ない階層で多くのデータを保持できるようになるのです。

もう一つの要が「平衡」です。B木は根から葉までの深さ(高さ)が、どの経路をたどってもそろうように保たれる設計になっています^*3。二分探索木のように特定の経路だけが深くなる偏りが起きにくいため、最悪の場合でも探索速度が大きく落ち込みにくいのです。

探索は、ルートノードのキーと目的の値を比較し、該当する範囲の子ノードへ進むという手順を、葉ノードに到達するまで繰り返します。データを新しく追加する際は、対応する葉ノードにキーを挿入し、その結果キー数が上限を超えたら、ノードを2つに分割して親ノードへ新しいキーを渡します。分割が親ノードにも連鎖することがありますが、根まで到達すると新しい根が1つ作られ、木全体の高さが1段だけ増えるという形で決着するのです。

削除の場合は逆に、キー数が下限を割り込んだノードを隣接ノードと統合したり、隣からキーを1つ借りたりして調整します。追加・削除のどちらであっても、根から葉までの深さがそろった状態を保ち続ける点は変わりません。実装の詳細を追う必要はありませんが、「データが増減しても自動的にバランスを取り直す」という性質を押さえておけば十分でしょう。

木構造による探索の効き目は、件数が増えるほどはっきり表れます。次の表は、全件走査と、1回の比較で対象をおおむね半分に絞り込む探索とで、目安となる比較回数がどう変わるかを示したものです。

実際のB木は1ノードに複数のキーを持たせて次数を大きく取る設計のため、上表の絞り込み型探索よりもさらに少ない階層で目的のデータへたどり着けます^*3。件数が大きくなるほど、索引の有無が応答時間に与える影響は開いていくと考えてよいでしょう。

次数を大きく取る背景には、ディスクの読み書きが「ブロック」と呼ばれる一定サイズの単位で行われる、という事情があります。1回のディスクアクセスで読み込めるブロックの中に、なるべく多くのキーを詰め込んでおけば、木を1段たどるごとに一度のディスクアクセスで済むのです。B木のノード設計が、計算上の探索効率だけでなく、ディスクI/Oの実際の回数を意識してつくられている理由は、この点にあります。

二分探索木・B+木とどう違うのか

木構造を使った探索と聞くと、二分探索木を思い浮かべる方もいるでしょう。二分探索木は1つのノードが持てる子が2つまでに限られる木構造です。データ件数が増えると木の高さも比例して伸びやすく、ディスク上のデータを扱う索引としてはノードの数(=ディスクへのアクセス回数)が増えすぎる弱点を抱えます。

B木は1ノードに複数のキーと子を持たせることで、この弱点を補います。次の表に、二分探索木・B木・B+木の主な違いをまとめました。

B+木は、実際のデータを葉ノードだけに集め、内部ノードには経路案内用のキーだけを持たせる構成です^*4。加えて、葉ノード同士を連結リストでつないでおくことで、「ある値以上」といった範囲検索の際に、木を上下にたどり直さずに葉のリストを順にたどるだけで結果を集められます^*4。関係データベースの索引にこの構造が使われる場面が多いのは^*4、単純な検索だけでなく範囲指定やソートを伴う問い合わせが実務で頻繁に発生するためだと考えられます。

発注者やプロジェクトマネージャーの立場では、B木とB+木のどちらを自分で選ぶ場面はほとんどありません。採用するデータベース製品ごとに、内部で使う木構造はあらかじめ決まっているためです。それでも、範囲検索やソートを多用する要件があるなら、その処理に強い設計が製品側に備わっているかを、選定段階で確認しておく価値はあるでしょう。

もともとB木は、ブロック単位でしか読み書きできない補助記憶装置の上に木構造を実装する目的で考案された経緯があります^*3。データベース以外にも、ファイルシステムがディレクトリやファイルの情報を管理する際の索引として、B木系の構造を採用している例が見られます。用途は違っても、「ディスクの読み書きを少ない回数にまとめたい」という動機は共通しているのです。

なお、B木にはB+木のほかにもB*木と呼ばれる派生形が存在します^*3。いずれもノードの分割・統合の条件や葉の持たせ方に手を加えた改良版であり、基本となる「複数の子を持つ平衡木でディスクI/Oを減らす」という考え方そのものは共通しています。発注者の立場では、個々の派生形の違いを覚えるよりも、この共通の考え方を押さえておくほうが実務では役立つでしょう。

インデックス設計で押さえる勘所

B木の仕組みが分かると、インデックス設計における実務上の判断軸も見えてきます。索引は「とりあえず張っておけばよい」というものではなく、対象の列・組み合わせ・データの分布によって効き方が変わる設計事項です。ここでは、発注者やレビュー担当者が押さえておきたい4つの観点を整理します。

複合インデックスは列の並び順で効き方が変わる

複数の列をまとめた複合インデックスは、左側の列から順に絞り込みに使われる性質を持ちます^*2。よく検索条件に使う列や、値の種類が多く絞り込み効果の高い列を先頭に置かないと、インデックスを作成しても想定した速度が出ないことがあります。列の並び順は、クエリのWHERE句やORDER BY句の使われ方に合わせて決める必要があるのです。

この性質を知らずに複合インデックスを設計すると、「索引は作ったのにクエリが速くならない」という状況に陥りがちです。開発会社にレビューを依頼する際は、想定する主要なクエリのパターンを先に共有し、そのクエリで実際に使われる列順になっているかを確認してもらうとよいでしょう。

選択性の低い列への索引は効果が薄い

性別や真偽値のように値の種類が少ない列は、索引を張っても絞り込める行数があまり減らず、効果が限定的です。索引が有効に働くかどうかは、列の値がどれだけ散らばっているか(選択性)に大きく左右されます。設計段階では、対象列の値の分布を確認してから索引の要否を判断することが望ましい対応です。

選択性の低い列は、単独では効果が薄くても、選択性の高い列と組み合わせた複合インデックスの一部としてなら意味を持つことがあります。列単体の性質だけでなく、実際のクエリでどの列と組み合わせて条件を絞り込むのかまで見て判断する必要があるのです。

カバリングインデックスで読み込みを減らす

クエリが必要とする列をすべてインデックス側に含めておくと、本体のテーブルを読みに行かずインデックスだけで結果を返せる場合があります。この設計をカバリングインデックスと呼びます。参照頻度の高い定型クエリに対しては、有効な選択肢の一つとなるでしょう。

ただし、含める列を増やすほどインデックス自体のサイズは大きくなり、更新時のコストも上がっていきます。すべてのクエリをカバリングインデックスで対応しようとするのではなく、アクセス頻度が特に高い処理に絞って適用するのが現実的な進め方です。

索引は書き込みコストとのトレードオフで考える

索引を追加すると検索は速くなりますが、行の追加・更新・削除のたびに索引側のB木も更新され、ノードの分割や統合が発生します^*3。索引を増やしすぎると、書き込み処理の負荷がかえって増える点には注意が必要です。読み取りと書き込みのどちらを優先するアプリケーションなのかを踏まえ、索引の数と対象列を選ぶ姿勢が欠かせません。

とくに、更新頻度の高いテーブルに対して「念のため」で索引を積み増していくと、書き込み遅延がじわじわと積み重なっていきます。定期的に使われていない索引を洗い出し、必要な索引だけを残す運用も、設計段階からあわせて計画しておきたいところです。

発注・レビューで確認すべき点

インデックス設計を内製・外部委託のどちらで進める場合でも、発注者側で最低限の判断材料を持っておくと、開発会社との認識合わせがスムーズになります。

インデックス設計を的確に行うには、対象のデータベース製品の内部構造への理解に加え、実際のクエリの傾向を分析して使用頻度の高いパターンを把握するスキルが求められます。社内にEXPLAINの結果を読み解ける担当者がいない場合は、設計そのものは開発会社に任せつつ、レビュー観点だけを整理して確認する、という役割分担も現実的な選択肢になるでしょう。

性能要件を数値で共有する

「検索を速くしてほしい」という要望だけでは、どこまで索引設計に投資すべきか判断できません。想定する同時アクセス数や、許容できる応答時間の目安をできる限り数値で共有することが、適切な設計判断の前提になります。

想定データ量とその増加ペースを伝える

索引の効果は、テーブルの行数が少ないうちは実感しにくいものです。しかし運用開始後にデータが積み上がると、索引の有無や設計の良し悪しが応答時間の差として表面化してきます。リリース時点の件数だけでなく、数年後に想定される件数の規模感も開発会社に伝えておくとよいでしょう。

EXPLAIN(実行計画)の確認を依頼する

PostgreSQLやMySQLでは、EXPLAINコマンドでクエリが索引を使っているかどうかを確認できます^*1,*2。レビューの際は、想定した索引が実際に使われているかを実行計画で確認してもらうよう依頼すると、設計と実装のずれを早い段階で見つけられます。索引の設計を後回しにしたまま本番相当のデータ量で稼働させると、クエリの遅延やタイムアウトが発生してから対処に追われる展開になりかねません。設計段階での確認を怠らない姿勢が、手戻りを防ぐ近道です。

使われていない索引の棚卸しを依頼する

索引は作った時点の設計が、運用が進んでもそのまま最適であり続けるとは限りません。アプリケーションの改修でクエリのパターンが変われば、かつて有効だった索引が使われなくなることもあるのです。リリース後の保守フェーズでも、一定の周期でどの索引が実際に使われているかを確認し、不要になった索引を整理する棚卸し作業を依頼事項に含めておくとよいでしょう。書き込みコストの削減にもつながる、地味ながら効果の大きい見直しといえます。

ここまでの確認事項を、レビュー時に見返せるよう一覧にまとめました。

まとめ

本稿では、B木の基本的な仕組みと、それが多くのデータベースの索引に採用されている理由を整理しました。実装コードを追う必要はなくとも、これらの考え方を知っておくと、開発会社との設計レビューで具体的な視点を持てるようになるはずです。要点は次の5つに集約できます。

• B木は、1ノードが複数の子を持つ平衡木で、少ないディスク読み込みで探索・追加・削除できるよう設計された索引の基盤である。
• 全件走査のO(n)に対し、B木を使った索引はO(log n)に近い探索コストで済み、件数が増えるほど効果が際立つ^*3。
• 二分探索木と異なり1ノードに複数のキーを持たせて次数を高め、平衡を保つことで木の高さを一定に抑える。
• B+木は葉ノードのみにデータを持たせ葉同士を連結する構成で、範囲検索に強く、多くのRDBの索引に採用されている^*4。
• 複合インデックスの列順・選択性・カバリングインデックス・書き込みコストを踏まえて設計することが、実務での勘所となる。
• 発注・レビュー側は、性能要件とデータ量の共有、EXPLAINでの検証依頼、既存索引の棚卸しの4点を押さえておくと認識合わせがしやすい。

よくある質問

著者：テレリモ総研編集部　鈴木 亮佑

ご不明な点はお問い合わせフォームからもご連絡いただけます。

出典

• PostgreSQL公式ドキュメント「11.2. Index Types」
• MySQL 8.4 リファレンスマニュアル「8.3.1 B-Tree and Hash Indexes」
• Wikipedia日本語版「B木」
• Wikipedia日本語版「B+木」

Tweet