• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

RDBMSをブラックボックスにしない

[第6回]Bツリー・インデックスの構造

松山 貴之=日経SYSTEMS 2007/10/09 日経SYSTEMS
出典:日経SYSTEMS 2006年12月号116ページより
(記事は執筆時の情報に基づいており、現在では異なる場合があります)
目次一覧

 この特集の目的は,SQL文の処理手続きの問題点を見抜けるようになることです。処理速度はディスク・アクセス回数に大きく左右されますので,手続きごとのディスク・アクセス回数を見極められるようになることと言ってもいいでしょう。ディスク・アクセス回数を減らす最も基本的な技術が,今回取り上げる「インデックス」です。インデックスにはいろいろな種類があります注1が,ここでは最もよく使われる「Bツリー・インデックス」に絞ります。

 「インデックスを使うと検索時間が短くなる」。このことをきちんと理解するには,インデックスの内部構造を知る必要があります。書籍の索引を例に一般的なインデックスを説明し,その後,データベースのBツリー・インデックスの内部構造について解説します。

ページをめくる回数を減らす書籍の索引

 インデックスを日本語で言えば「索引」です。たいていの専門書籍には,用語とその用語の登場するページ番号をまとめた索引があると思います(図1左)。書籍を頭から読むのではなくピンポイントで何かを調べたい場合,索引があるのとないのとでは,該当ページを見つけるまでの時間に大きな差が生じます。

図1●書籍の索引とデータベースのインデックス
図1●書籍の索引とデータベースのインデックス
索引の用語は(検索条件の)カラム値に,索引のページ番号はポインタに相当する。インデックスはこの二つの要素からなる
[画像のクリックで拡大表示]

 索引がなければ,どうやって該当ページを見つけるのでしょうか。おそらく,先頭からぱらぱらとページをめくって探すことになるでしょう。それらしいページを見つけても,もっと詳しい説明個所があるかもしれないと考え,結局最後のページまでめくることになるかもしれません。索引があれば,用語から該当ページをピンポイントに見つけることができます。索引のページ数は通常少ないので,ページをめくる回数を大幅に削減できることになります。

 データベースのインデックスもこれと同じようなものです。ページをめくることがディスク・アクセスに相当し,索引(インデックス)があることで,ディスク・アクセス回数を大幅に削減できるというわけです。

 書籍の索引をデータベースに置き換えて考えてみましょう。索引に載っている用語は探したい情報ですので,データベースで言えば,SELECT文の検索条件に相当します。シンプルな検索条件(例えば,WHERE 顧客番号=1030)を想定すると,索引の用語は「レコードごとのカラム値」になります。同様に索引のページ番号は,ピンポイントに情報にたどりつくためのものなので,データベースで言えばディスク上の格納場所(本特集では「ポインタ」と呼びます)になります(図1右)。まとめると,データベースのインデックスに含まれるデータは,(1)各レコードのカラム値と,(2)レコードのポインタ注2の二つ。これは,今回取り上げる「Bツリー・インデックス」の構成要素と同じです。

 ただし,書籍の索引とデータベースのBツリー・インデックスでは,構造がまったく異なります。書籍の索引はいわば単純な配列構造です。それに対してBツリー・インデックスは,樹木のような構造(木構造)になっています(図2左)。3層構造になっており,上位に位置するのが「ルート」,中間が「ブランチ」,下位に位置するのが「リーフ」です。レコード数が少ないとブランチが無かったり,逆にレコード数が多いとブランチが複数層になることがあります。ルート,ブランチ,リーフにはすべて(1)カラム値を含みます。

図2●Bツリー・インデックスの構造
図2●Bツリー・インデックスの構造
論理的には左のように3層構造で,ルートは一つである。物理的には右のように,ルート,ブランチ,リーフは別々のブロックに格納している
[画像のクリックで拡大表示]

 レコードをディスクに格納するときはブロック注3単位になりますが,インデックスをディスクに格納するときもブロック単位になります。通常,ルート,ブランチ,リーフは,それぞれ別々のブロックに格納されます(図2右)。(2)レコードのポインタはリーフにのみ含み,ブランチにはリーフのポインタを,ルートにはブランチのポインタを含みます。

監修:藤塚 勤也(ふじづか きんや) NTTデータ 基盤システム事業本部 オープンソース開発センタ 技術開発担当 シニアスペシャリスト
沖電気工業,タンデムコンピューターズ(現日本HP)を経て,2003年より株式会社 NTTデータに勤務。現在は,オープンソース・ソフトウエアを活用したエンタープライズ・システム向けの技術開発・技術支援に従事しており,特にシステムの中核であるRDBMSに注力している。「RDBMS解剖学」(翔泳社)を共著

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

  • 【記者の眼】

    日本人SEが外資系ITに大量流出、これでいいのか?

     日本ハムの二刀流こと、大谷翔平選手のメジャー移籍が話題になっている。23歳という年齢は早すぎる気もするが、メジャーを熱望しながらプロ野球界にとどまった経緯を考えれば、当然の流れといえそうだ。もはや「なぜお前もメジャーに行くのか?」と嘆くよりも、大舞台での雄姿を早く見たいのではないだろうか。

ITpro SPECIALPR

What’s New!

経営

アプリケーション/DB/ミドルウエア

クラウド

運用管理

設計/開発

サーバー/ストレージ

クライアント/OA機器

ネットワーク/通信サービス

セキュリティ

もっと見る