(57)【要約】データベース管理装置は、表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、表データに対するデータ操作に応じて各インデックスエントリを参照することによりツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段と、を備える。
2012081165.tif 000002
【特許請求の範囲】
【請求項１】
表データを格納するデータブロックを含むデータベースを管理するデータベース管理装置において、
前記表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、
前記表データに対するデータ操作に応じて各インデックスエントリを参照することにより前記ツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段と、
を備えることを特徴とするデータベース管理装置。
【請求項２】
前記各インデックスブロック内のインデックスエントリを前記ツリー構造に沿って検索することにより、前記データブロック内の少なくとも１つの行データを抽出する検索手段、
を更に備え、
前記アクセス管理手段は、前記検索手段が前記複数のインデックスブロックのいずれか１つにアクセスする際に、該アクセスされたインデックスブロックのアクセスカウンタを増加させ、続いて、該アクセスされたインデックスブロック内のインデックスエントリにより特定される他のインデックスブロックにアクセスする際に、該他のインデックスブロックのアクセスカウンタを増加させる、
ことを特徴とする請求項１に記載のデータベース管理装置。
【請求項３】
前記データブロックに新たな行データを挿入すると共に、前記データブロックに挿入された行データを特定する新たなインデックスエントリを前記複数のインデックスブロックのうちの挿入対象のインデックスブロックに挿入し、該挿入対象のインデックスブロックに該新たなインデックスエントリを挿入することができない場合には空のインデックスブロックを取得するデータ挿入手段、
を更に備え、
前記アクセスカウンタは、リードカウンタとライトカウンタとを含み、
前記アクセス管理手段は、前記データ挿入手段が前記インデックスブロックに前記新たなインデックスエントリを挿入する際には、前記インデックスブロックのライトカウンタを増加させ、前記データ挿入手段が前記空のインデックスブロックを取得する際には、前記空のインデックスブロックのリードカウンタを増加させる、
ことを特徴とする請求項１又は２に記載のデータベース管理装置。
【請求項４】
前記データブロックから行データを削除すると共に、削除された行データに対応するインデックスエントリを前記複数のインデックスブロックのうちの削除対象のインデックスブロックから削除し、前記削除対象のインデックスブロックを空きブロックにする場合には、前記削除対象のインデックスブロックに残っているインデックスエントリを他のインデックスブロックに移動させるデータ削除手段、
を更に備え、
前記アクセス管理手段は、前記データ削除手段が前記削除対象のインデックスブロックから前記インデックスエントリを削除した場合には、前記削除対象のインデックスブロックのライトカウンタを増加させ、前記データ削除手段が前記削除対象のインデックスブロックを空きブロックにする場合には、前記他のインデックスブロックのライトカウンタを増加させる、
ことを特徴とする請求項３に記載のデータベース管理装置。
【請求項５】
前記複数のインデックスブロックのうちの指定インデックスブロックに関するリード負荷情報及びライト負荷情報を取得し、該指定インデックスブロックのリードカウンタと該リード負荷情報との積、及び、該指定インデックスブロックのライトカウンタと該ライト負荷情報との積の和を、該指定インデックスブロックのアクセス負荷として算出するアクセス負荷評価手段、
を更に備えることを特徴とする請求項３又は４に記載のデータベース管理装置。
【請求項６】
ライトカウンタが全アクセス数に占める割合が所定値よりも高いインデックスブロックを特定する行特定手段、
を更に備えることを特徴とする請求項３から５のいずれか１項に記載のデータベース管理装置。
【請求項７】
複数の子インデックスブロックを特定する複数のインデックスブロックをそれぞれ格納する各親インデックスブロックに関し、該複数の子インデックスブロックのアクセスカウンタに基づいて、全子インデックスブロックへのアクセス回数に対する特定の子インデックスブロックへのアクセス回数の偏りをそれぞれ算出し、偏りの大きいものから所定数分の親インデックスブロックを特定するための情報を出力するアクセス偏り算出手段、
を更に備えることを特徴とする請求項１から６のいずれか１項に記載のデータベース管理装置。
【請求項８】
前記アクセスカウンタは、複数の記憶領域のそれぞれに対応して複数存在し、
前記アクセス管理手段は、前記複数のインデックスブロックのいずれか１つへのアクセスが発生した場合に、アクセスされたインデックスブロックが有するアクセスカウンタであってアクセス先の記憶領域に対応するアクセスカウンタを更新する、
ことを特徴とする請求項１から７のいずれか１項に記載のデータベース管理装置。
【請求項９】
表データを格納するデータブロックを含むデータベースを管理するプログラムにおいて、
コンピュータを、
前記表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、
前記表データに対するデータ操作に応じて各インデックスエントリを参照することにより前記ツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段、
として機能させるためのプログラム。
【請求項１０】
表データを格納するデータブロックを含むデータベースを管理するデータベース管理方法において、
前記表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックを備えるコンピュータが、
前記表データに対するデータ操作に応じて各インデックスエントリを参照し、
前記参照により前記ツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新する、
ことを特徴とするデータベース管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ツリー構造のインデックスが付加されたデータベースの管理技術に関する。
【背景技術】
【０００２】
大量のデータから少量のデータを高速に検索するために、データにインデックスを付与するのが一般的である。検索処理が多く実行されるのはデータベースであり、最も広く用いられているデータベースの一つは、表形式でデータを管理する関係データベースである。表は、行と列を持ち、例えば、一つの行に一つの取引に関するデータを格納する。行は、複数の列から構成され、例えば、ある列に日付データを、別の列に売上金額を格納する。【０００３】
この場合、特定の日付における総売上金額を得る方法には、フルスキャン、インデックススキャン等がある。フルスキャンでは、全ての行に関して日付が一致するかどうかを調べ、一致する行の売上高を加算する。インデックススキャンでは、日付が一致する行をインデックスによって特定し、特定された行から売上高の総和を得る。インデックススキャンは、全行数に比べて日付が一致する行の数が十分に小さいときに効率的である。【０００４】
Ｂツリーは、インデックスを格納するデータ構造の一つとして知られている。例えば、非特許文献１には、Ｂツリーを使った検索、Ｂツリーへのデータの挿入、Ｂツリーへのデータの削除の各アルゴリズムが記載されている。非特許文献２には、広く用いられている関係データベースのＯＲＡＣＬＥ（登録商標）におけるＢツリーの説明が記載されている。【０００５】
このようなＢツリーインデックスを用いることにより、行数をｎとすると、「ｌｏｇ  ｎ」に比例する計算量でデータを検索することができる。なお、フルスキャンの計算量は、ｎに比例する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−１５８１０号公報
【特許文献２】特開２００４−２９５７９０号公報
【特許文献３】特開２００８‐２２５５７５号公報
【特許文献４】米国特許出願公開第２００８／２２２０９０号明細書
【特許文献５】特開２００９‐１２２８５０号公報
【特許文献６】特開２０１０−１４０３６２号公報
【特許文献７】特開平０７−２００３７６号公報
【非特許文献】
【０００７】
【非特許文献１】Comer, D. "Ubiquitous B-Tree", ACM Computing Surveys, vol.11, no.2, p.121-137, June 1979
【非特許文献２】"Oracle Database概要"、10g リリース2、部品番号：B19215-02、2006年3月（図5-7）、http://otndnld.oracle.co.jp/document/products/oracle10g/102/doc_cd/server.102/B19215-02.pdf
【非特許文献３】"Oracle Databaseリファレンス"、10g リリース2、部品番号：B19228-04、2009年6月（図5-7）、http://otndnld.oracle.co.jp/document/products/oracle10g/102/doc_cd/server.102/B19215-02.pdf
【非特許文献４】木脇高太郎、「おら、オラ、オラクル」、翔泳社、2003年5月（pp. 199）
【非特許文献５】Drepper, U. What Every Programmer Should Know about Memory, November, 2007. http://people.redhat.com/drepper/cpumemory.pdf
【発明の概要】
【０００８】
Ｂツリーインデックスが付加されたデータベースでは、一般的には、検索は高速であるが、データの挿入及び削除は低速になる。Ｂツリーインデックスが付加されていないデータベースに対するデータの挿入及び削除は、単に表として記録されたデータを操作すればよい。しかしながら、Ｂツリーインデックスが付加された表に対するデータの挿入及び削除は、Ｂツリーに記録されたデータも操作しなければならないからである。更に、Ｂツリーでは、操作を加えるブロックの空き領域の過不足によって、ブロック自体の追加及び削除が発生する場合もある。この場合、そのブロックの上位のブロックのデータも操作する必要がある。
【０００９】
また、ＣＰＵ（Central Processing Unit）速度とメモリ速度との差の拡大が、データベースの性能に影響を与えている。特に、ランダムアクセス時のメモリのレイテンシは大きく、メモリ上のデータへのアクセスを待っている間、ＣＰＵはストールすることになる。このようなランダムアクセスは、例えば、リストをたどる処理実行時に発生し、Ｂツリーインデックスが利用されるデータベースにおいては、そのリストをたどる処理が頻繁に発生する。
【００１０】
このようにデータベースの性能に影響を与える要因は、処理手法、ハードウェア等、様々であるため、現在、データベースの性能を最適化するのは困難となっている。加えて、データベースの性能を最適化するのに有用な情報が存在しないのが現状である。
【００１１】
本発明の目的は、ツリー構造のインデックスが付加されたデータベースの性能を最適化するためのデータベース管理技術を提供することにある。
【００１２】
本発明の各態様では、上述した課題を解決するために、それぞれ以下の構成を採用する。
【００１３】
第１の態様は、表データを格納するデータブロックを含むデータベースを管理するデータベース管理装置に関する。第１の態様に係るデータベース管理装置は、表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、表データに対するデータ操作に応じて各インデックスエントリを参照することによりツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段と、を備える。
【００１４】
第２の態様は、表データを格納するデータブロックを含むデータベースを管理するデータベース管理方法において、表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックを備えるコンピュータが、表データに対するデータ操作に応じて各インデックスエントリを参照し、その参照によりツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新する。
【００１５】
なお、本発明の他の態様としては、上記構成をコンピュータに実現させるプログラムであってもよいし、このプログラムを記録したコンピュータが読み取り可能な記録媒体であってもよい。
【００１６】
上記各態様によれば、ツリー構造のインデックスが付加されたデータベースの性能を最適化するためのデータベース管理技術を提供することができる。
【図面の簡単な説明】
【００１７】
【図１】図１は、第１実施形態におけるＤＢシステムの構成例を示す概念図である。
【図２】図２は、第１実施形態におけるインデックスブロックの構成例を概念的に示す図である。
【図３】図３は、第１実施形態におけるＤＢシステムの動作例を示すフローチャートである。
【図４】図４は、ブランチブロック、リーフブロック及びデータブロックの関係の例を概念的に示す図である。
【図５】図５は、第２実施形態におけるＤＢシステムの構成例を示す概念図である。
【図６】図６は、第２実施形態におけるインデックスブロックの構成例を概念的に示す図である。
【図７】図７は、第２実施形態におけるＤＢシステムのデータ挿入時の動作例を示すフローチャートである。
【図８】図８は、第２実施形態におけるＤＢシステムのデータ削除時の動作例を示すフローチャートである。
【図９】図９は、第３実施形態におけるＤＢシステムの構成例を示す概念図である。
【図１０】図１０は、第３実施形態におけるインデックスブロックの構成例を概念的に示す図である。
【図１１】図１１は、第４実施形態におけるＤＢシステム１０の構成例を示す概念図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について説明する。
【００１９】
本実施形態に係るデータベース管理装置は、表データを格納するデータブロックを含むデータベースを管理する。このデータベース管理装置は、表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、上記表データに対するデータ操作に応じて各インデックスエントリを参照することによりツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段と、を備える。
【００２０】
上記データベース管理装置では、ツリー構造を持つ各インデックスブロックにはアクセスカウンタがそれぞれ設けられており、データブロック内の行データに対する１つのデータ操作に応じてツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタがそれぞれ更新される。
【００２１】
従って、上記データベース管理装置によれば、ツリー構造のインデックスが付加されたデータベースにおいて、各インデックスブロックに関しアクセスされた回数情報をそれぞれ得ることができる。インデックスブロックへのアクセス回数は、データブロック及びインデックスブロックを含めた全てのブロックへのアクセス回数に対して大きな割合を占めることが多い。インデックスブロックは、通常メモリ上に保持される。そして、ＣＰＵ（Central Processing Unit）とメモリとの速度差のために、インデックスブロックへのアクセスはボトルネックになりがちである。従って、インデックスブロックへのアクセスに関する情報を提供することは、データベースの性能を最適化する上で極めて重要である。
【００２２】
以下、上述の実施形態について更に詳細を説明する。以下の各実施形態は、上述のデータベース管理装置の構成を含むデータベースシステム（以降、ＤＢシステムと表記する）の例である。なお、以下に挙げた各実施形態はそれぞれ例示であり、本発明は以下の各実施形態の構成に限定されない。
【００２３】
［第１実施形態］
〔システム構成〕
図１は、第１実施形態におけるＤＢシステム１０の構成例を示す概念図である。ＤＢシステム１０は、図１に示すように、ハードウェア構成として、ＣＰＵ１、メモリ２（ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスク（ＨＤＤ）等）、入出力インタフェース３等を有する。これら各ハードウェア要素は例えばバス５により接続される。入出力インタフェース３は、外部のコンピュータ等と通信を行うためのネットワークインタフェースやユーザインタフェース等を含む。
【００２４】
ＤＢシステム１０は、例えば、メモリ２に格納されるプログラムがＣＰＵ１により読み出され実行されることにより、以下のような各処理部を実現する。ＤＢシステム１０は、データベース管理部（以降、ＤＢ管理部と表記する）１００、データベース（以降、ＤＢと表記する）部２００等を有する。
【００２５】
なお、図１の例では、ＤＢシステム１０が１台のコンピュータとして実現される例を示すが、複数のコンピュータで実現されてもよい。また、図１の例では、１つのＣＰＵ１のみが示されるが、複数のプロセッサ（例えば、ＣＰＵ、ＤＳＰ（Digital Signal Processor）等）を有していてもよい。例えば、ＤＢ管理部１００とＤＢ部２００とが異なるコンピュータ又はＣＰＵ上で実現されてもよい。本実施形態は、ＤＢシステム１０のハードウェア構成を限定しない。
【００２６】
ＤＢ部２００は、メモリ２上に実現され、複数のブロック２１０（図１では２１０（＃１）、２１０（＃２）、２１０（＃ｎ）として表記）を含む。各ブロック２１０は、例えば、所定容量（例えば、４キロバイト（ＫＢ））の連続した記憶領域として確保される。ブロック２１０間は、連続領域として確保されてもよいし、非連続な各領域として確保されてもよい。本実施形態は、ブロック２１０の領域サイズを限定しない。
【００２７】
各ブロック２１０は、インデックスを格納するブロック（以降、インデックスブロックとも表記される）と、データを格納するブロック（以降、データブロックとも表記される）２４０とに大別される。データブロック２４０は、任意の表（テーブル）を格納する。
【００２８】
インデックスブロックは、ツリー構造（例えば、Ｂツリー（Balanced Tree）構造）を持ち、更に、ブランチブロック２２０と、リーフブロック２３０とに大別される。ブランチブロック２２０及びリーフブロック２３０の各々は、インデックスとなる少なくとも１つのエントリを格納する。各インデックスブロックに格納されるエントリは、インデックスエントリと呼ぶこともできる。インデックスエントリは、検索対象となるキー値と識別子（ＩＤ）とを含む。
【００２９】
リーフブロック２３０は、インデックスブロックの中の最下層のブロックである。リーフブロックのエントリに含まれる識別子は、データブロックのいずれか１つの行データを特定するためのデータである。その識別子は、例えば、特定すべき行データの先頭を指すポインタとその行データのサイズとから構成される。
【００３０】
ブランチブロック２２０は、リーフブロック２３０又は他のブランチブロック２２０へのリンクを持つブロックである。このリンクは、インデックスエントリの識別子によって実現される。即ち、ブランチブロック２２０のエントリに含まれる識別子は、いずれか１つのブランチブロック２２０又はいずれか１つのリーフブロック２３０を特定するポインタである。以降、最上位のブランチブロック２２０をルートブロックと表記する場合もある。ここで、最上位とは、検索時に最初に検索されることを意味する。
【００３１】
以降、インデックスエントリの識別子によりリンクされた各インデックスブロックにおいて、そのインデックスエントリを含むブランチブロック２２０を親ブロックと表記し、そのインデックスエントリの識別子で特定されるリーフブロック２３０又は他のブランチブロック２２０を子ブロックと表記する場合もある。
【００３２】
図２は、第１実施形態におけるインデックスブロックの構成例を概念的に示す図である。図２に示すように、各インデックスブロックは、ブロックヘッダと少なくとも１つのインデックスエントリとをそれぞれ含む。インデックスエントリは、上述したように、キー値（図２の「ｋｅｙ」）と識別子（図２の「ｉｄ」）とを含む。ブロックヘッダには、ブロック種、アクセスカウンタ等が設定される。ブロック種は、リーフブロック、ブランチブロック等を識別するための情報である。アクセスカウンタは、インデックスブロックへのアクセスの数をカウントする。
【００３３】
図２では、インデックスブロック内の連続領域に、ブロックヘッダ内の各値及び各エントリが格納される例を示したが、ブロックヘッダ内の各値と各エントリとは、相互に関連付けられていれば、必ずしも連続した領域に格納されなくともよい。
【００３４】
ＤＢ管理部１００は、アクセス管理部１１０、検索部１２０等を含む。ＤＢ管理部１００を構成するこれら各処理部も、メモリ２に格納されるプログラムがＣＰＵ１により読み出され実行されることにより、ソフトウェア要素として実現される。
【００３５】
検索部１２０は、検索キーを取得し、この検索キーに対応する列（フィールド）のデータを含む行をデータブロック２４０から抽出する。検索キーは、他の装置から通信を介して取得されてもよいし、ＣＰＵ１により実行されているプロセス等のような他の処理部から取得されてもよいし、ユーザインタフェースを介してユーザにより入力されてもよい。
【００３６】
検索部１２０は、データブロック２４０における抽出すべき行を特定するために、インデックス検索を行う。このインデックス検索において、検索部１２０は、まず、ルートブロックにアクセスする。検索部１２０は、ルートブロックに含まれるエントリのうち、検索キー以下の最大のキー値を持つエントリ、又は、検索キー以上の最小のキー値を持つエントリを検索する。
【００３７】
検索部１２０は、抽出されたエントリの識別子により特定される他のブランチブロック２２０又はリーフブロック２３０を読み出す。検索部１２０は、他のブランチブロック２２０が読み出された場合には、上記のルートブロックに対する検索と同様に特定のエントリを抽出する。一方、検索部１２０は、リーフブロック２３０が読み出された場合には、検索キーの条件を満たすエントリを抽出し、そのエントリの識別子で特定される行データをデータブロック２４０から抽出する。
【００３８】
アクセス管理部１１０は、検索部１２０からの指示に応じて動作し、対象のインデックスブロックのブロックヘッダのアクセスカウンタを増加させる。具体的には、アクセス管理部１１０は、検索部１２０がインデックス検索を行うことによりインデックスエントリの識別子により特定されるブランチブロック２２０又はリーフブロック２３０を読み出す際に、その読み出されたインデックスブロックのブロックヘッダのアクセスカウンタを増加させる。但し、ルートブロックは最初に参照されるブロックであるため、検索部１２０は、アクセスした際に、ルートブロックのブロックヘッダのアクセスカウンタを増加させる。
【００３９】
アクセス管理部１１０は、検索部１２０がルートブロックのいずれかのエントリの識別子が示すブランチブロック２２０を読む際に、そのブランチブロック２２０のアクセスカウンタを１増加させる。更に、アクセス管理部１１０は、検索部１２０がこのブランチブロック２２０からたどるリーフブロック２３０にアクセスするときに、リーフブロック２３０のアクセスカウンタを１増加させる。
【００４０】
〔動作例〕
以下、第１実施形態におけるＤＢシステム１０の動作例について図３及び図４を用いて説明する。図３は、第１実施形態におけるＤＢシステム１０の動作例を示すフローチャートである。図３の例では、完全一致検索を行う場合の動作が示される。図４は、ブランチブロック２２０、リーフブロック２３０及びデータブロック２４０の関係の例を概念的に示す図である。ここでは、図４の例において、文字列の大小を辞書順に従って比較することを想定し、検索部１２０が、検索キー「ｇｏ」を列データに含む行を検索する場合を例に挙げて、当該動作例を説明する。
【００４１】
検索部１２０は、検索キーを取得すると、まず、ルートブロックを読み出す（Ｓ１０）。図４の例では、検索部１２０は、検索キー「ｇｏ」を取得すると、キー値「ｅ」、「ｍ」、「ｔ」を含む各インデックスエントリを持つルートブロックを読み出す。
【００４２】
アクセス管理部１１０は、検索部１２０がルートブロックにアクセスした場合に、そのルートブロックのアクセスカウンタを１増加させる（Ｓ１１）。
【００４３】
検索部１２０は、ルートブロック内のインデックスエントリのうち、当該検索キー以下の最大のキー値を持つエントリ、又は、当該検索キー以上の最小のキー値を持つエントリを特定する。いずれの特定方法を取っても一般性を失わないので、ここでは、検索部１２０は、当該検索キー以下の最大のキー値を持つエントリを特定するものとする（Ｓ１２）。このエントリの特定は、ブロック中の全てのエントリを比較することにより実現されてもよいし、ブロック中のエントリをキー値でソートした上で一部のエントリを比較することにより実現されてもよい。
【００４４】
図４の例では、簡略化されているが、キー値「ｅ」については、例えば、キー値「ｅ」を持つエントリと「ｅ」より小さい値を示すキー値（例えば、ＮＵＬＬ）を持つエントリとが含まれる。ここで、検索キー「ｇｏ」以下の最大のキー値は「ｅ」であり、検索キー「ｇｏ」は、キー値「ｅ」より大きくキー値「ｍ」よりも小さいので、左から２番目のブランチブロックを特定する識別子を含むエントリが特定される。
【００４５】
続いて、検索部１２０は、そのように特定されたエントリの識別子によって特定されるインデックスブロックを読み出す（Ｓ１３）。
【００４６】
アクセス管理部１１０は、検索部１２０がインデックスブロックを読み出すと、そのインデックスブロックのアクセスカウンタを１増加させる（Ｓ１４）。
【００４７】
検索部１２０は、ブロックヘッダに設定されるブロック種により、その読み出されたインデックスブロックがリーフブロック２３０かブランチブロック２２０かを判定する（Ｓ１５）。検索部１２０及びアクセス管理部１１０は、その読み出されたインデックスブロックがブランチブロック２２０である場合には（Ｓ１５；ＮＯ）、その読み出されたブランチブロック２２０に関し上記（Ｓ１２）、（Ｓ１３）及び（Ｓ１４）の処理を実行する。
【００４８】
検索部１２０は、その読み出されたインデックスブロックがリーフブロック２３０である場合には（Ｓ１５；ＹＥＳ）、その読み出されたリーフブロック２３０内のエントリの中から、検索キーを含む検索条件に一致するエントリを特定する（Ｓ１６）。ここでは、その検索条件は、検索キーを列データに含む行（完全一致）の検索を示す。図４の例では、キー値「ｇｏ」を含むインデックスエントリが特定される。
【００４９】
このインデックスエントリの特定は、リーフブロック２３０中の全てのエントリを比較することにより実現されてもよいし、リーフブロック２３０中のエントリをキー値でソートした上で一部のエントリを比較することにより実現されてもよい。
【００５０】
検索部１２０は、特定されたインデックスエントリに含まれる識別子で特定される行データを抽出する（Ｓ１７）。図４の例では、キー値「ｇｏ」を含むインデックスエントリの識別子により特定されるデータブロック２４０の行が抽出される。例えば、その識別子に含まれるポインタで、行データの先頭が特定され、その先頭アドレスから行の大きさ（バイト数）分のデータが読み出される。
【００５１】
〔第１実施形態の作用及び効果〕
このように第１実施形態では、検索部１２０によるツリー構造に沿ったインデックス検索に応じて、データブロック２４０の少なくとも１つの行データが抽出されるまでにたどられた検索経路に含まれるインデックスブロックの各アクセスカウンタがアクセス管理部１１０によりそれぞれ更新される。
【００５２】
従って、第１実施形態によれば、検索時にブランチブロック２２０及びリーフブロック２３０へのアクセスの回数がブロック毎に記録されるため、各インデックスブロックのアクセスカウンタを参照することにより、ブロック毎のアクセス負荷を容易に見積もることができる。各ブロックのアクセス負荷を見積もることができれば、例えば、その負荷に応じてＣＰＵキャッシュに置くべきインデックスブロックを決める等、データベースの性能を最適化することも可能である。
【００５３】
なお、第１実施形態では、データブロック２４０へのアクセスの回数はカウントされない。これは、データブロック２４０におけるブロック当たりのアクセス数がインデックスブロックのそれに比べて少ないからである。第１実施形態では、データベース性能を最適化する上で特に有用な情報として、インデックスブロックのアクセス回数がカウントされる。このようにして、第１実施形態では、アクセス回数のカウント処理で使われる負荷を必要最小限としている。もちろん、本実施形態において、データブロック２４０へのアクセスの回数をカウントするようにしてもよい。
【００５４】
［第２実施形態］
〔システム構成〕
図５は、第２実施形態におけるＤＢシステム１０の構成例を示す概念図である。第２実施形態におけるＤＢシステム１０は、図５に示すように、第１実施形態の構成に加えて、データ挿入部１３０及びデータ削除部１４０を更に有する。以下、第２実施形態におけるＤＢシステム１０について、第１実施形態と異なる内容を中心に説明し、第１実施形態と同一の内容についての説明は適宜省略する。データ挿入部１３０及びデータ削除部１４０についても、メモリ２に格納されるプログラムがＣＰＵ１により読み出され実行されることにより、ソフトウェア要素として実現される。
【００５５】
データ挿入部１３０は、挿入する行データを受け取り、データブロック２４０にその行データを書き込む。このとき、データ挿入部１３０は、その挿入された行データに基づいて、インデックスブロック内のインデックスを更新する。データブロック２４０への書き込みは、例えば、挿入すべき行データよりも大きな空き領域を持つブロックのいずれか１つに書き込まれる。
【００５６】
データ挿入部１３０は、インデックスの更新において、少なくとも、対応するリーフブロック２３０に、その挿入された行データに対応する新たなインデックスエントリを追加する。この新たなインデックスエントリは、キーが設定される列であって挿入された行に含まれる列データをキー値として含み、更に、その行を特定するための識別子を含む。
【００５７】
インデックスの更新では、リーフブロック２３０へのエントリの追加に加えて、ブランチブロック２２０にも新たなインデックスエントリを追加することが要求される場合がある。それは、挿入対象のリーフブロック２３０に、新たなインデックスエントリを追加するための十分な空き領域がない場合（オーバーフローが起きた場合）である。
【００５８】
このようにオーバーフローが起きた場合には、データ挿入部１３０は、ブロック分割を行うことによって空き領域を作る。ブロック分割では、データ挿入部１３０は、所定容量の空き領域がなくなったリーフブロック２３０のデータの一部を新たに確保したリーフブロック２３０に移すことで空き領域を作り出す。ブロック分割は、リーフブロック２３０のみでなくブランチブロック２２０においても同様に処理される。ブロック分割の詳細については動作例の項で詳述する。
【００５９】
データ削除部１４０は、削除する行データを特定するための値を受け取り、データブロック２４０から行データを削除し、削除された行データに対応するインデックスエントリをリーフブロック２３０から削除する。例えば、削除する行データを特定するための値は、検索部１２０の検索処理の結果として取得される。
【００６０】
インデックスエントリをリーフブロック２３０から削除することにより、リーフブロック２３０の空き領域が所定サイズ以上となった場合（アンダーフローが起きた場合）、データ削除部１４０は、このリーフブロック２３０を空きブロックにする。このアンダーフロー発生時の処理については動作例の項において詳述する。
【００６１】
図６は、第２実施形態におけるインデックスブロックの構成例を概念的に示す図である。第２実施形態では、図６に示すように、アクセスカウンタとして、リードカウンタとライトカウンタとが設けられる。リードカウンタは、リードアクセスの数をカウントし、ライトカウンタは、ライトアクセス（エントリ削除も含む）の数をカウントする。
【００６２】
これにより、第２実施形態におけるアクセス管理部１１０は、第１実施形態で説明したデータ検索時にはリードカウンタを増加させる。更に、アクセス管理部１１０は、行データ挿入時においてデータ挿入部１３０により新たなインデックスエントリが追加されると、そのインデックスエントリが追加されたインデックスブロックのライトカウンタを１増加させる。このとき、アクセス管理部１１０は、そのインデックスエントリが追加されたインデックスブロックを検索するまでにアクセスされた各インデックスブロックのリードカウンタをそれぞれ１増加させる。
【００６３】
同様に、行データ挿入時においてブロック分割が行われる場合には、アクセス管理部１１０は、そのブロック分割処理においてアクセスされたインデックスブロックのリードカウンタを増加させ、かつ、ブロック分割処理でエントリが移動させられる度に移動先のインデックスブロックのライトカウンタを１増加させる。
【００６４】
また、アクセス管理部１１０は、データ削除部１４０がインデックスブロックからエントリを削除した場合には、そのインデックスブロックのライトカウンタを増加させる。更に、アクセス管理部１１０は、データ削除部１４０がインデックスブロックを空きブロックにする場合には、そのインデックスブロックを空きブロックにするために移動されたエントリの移動先となる他のインデックスブロックのライトカウンタを増加させる。
【００６５】
〔動作例〕
以下、第２実施形態におけるＤＢシステム１０の動作例について図７及び図８を用いて説明する。図７は、第２実施形態におけるＤＢシステム１０のデータ挿入時の動作例を示すフローチャートである。
【００６６】
データ挿入部１３０は、挿入すべき行データを取得すると、この行データを空き領域のある任意のデータブロック２４０に書き込む（Ｓ２０）。
【００６７】
データ挿入部１３０は、挿入された行データに対応するインデックスエントリを挿入すべきリーフブロック２３０を特定する（Ｓ２１）。このリーフブロック２３０の特定は、挿入された行データにおけるキーが設定された列の値を検索キーとしたインデックス検索によりリーフブロック２３０を特定する場合と同様の手法で実現される。図３の動作例によれば、Ｓ１０、Ｓ１１、Ｓ１２、Ｓ１３、Ｓ１４及びＳ１５の処理が実行されることにより、挿入すべきリーフブロック２３０が特定される。
【００６８】
従って、挿入された行データに対応するリーフブロック２３０を特定するために読み出されたインデックスブロックのリードカウンタは、アクセス管理部１１０によりカウントアップされる。
【００６９】
続いて、データ挿入部１３０は、特定されたリーフブロック２３０に挿入すべき新たなインデックスエントリを生成する（Ｓ２２）。新たなインデックスエントリは、挿入された行データにおけるキーが設定された列の値をキー値として含み、挿入された行データを特定するための識別子を含む。
【００７０】
データ挿入部１３０は、特定されたリーフブロック２３０が新たなインデックスエントリの追加によりオーバーフローするか否かを判定する（Ｓ２３）。ここで、オーバーフローとは、新たなインデックスエントリを追加するとブロックの空き領域が所定の比率を下回ることである。
【００７１】
データ挿入部１３０は、オーバーフローしないと判定すると（Ｓ２３；ＮＯ）、その特定されたリーフブロック２３０にその新たに生成されたインデックスエントリを書き込む（Ｓ２４）。このとき、アクセス管理部１１０は、書き込まれたリーフブロック２３０のライトカウンタを１増加させる（Ｓ２５）。
【００７２】
続いて、データ挿入部１３０は、ブロック分割がなされたか否かを判定する（Ｓ２６）。データ挿入部１３０は、ブロック分割がされていない場合には（Ｓ２６；ＮＯ）、処理を終了し、ブロック分割がなされている場合には（Ｓ２６；ＹＥＳ）、ブロック分割がなされたブロックの上位のブランチブロックを特定する（Ｓ２７）。この上位ブランチブロックの特定は、再帰関数的な処理を施すことにより実現してもよいし、ブロックヘッダに上位ブロックの識別子を格納することで実現してもよい。
【００７３】
以降、データ挿入部１３０は、その特定された上位ブランチブロックを対象ブロックとして処理（Ｓ２２）に戻って各処理を実行する。
【００７４】
一方、データ挿入部１３０は、オーバーフローすると判定した場合には（Ｓ２３；ＹＥＳ）、その特定されたブロックに対してブロック分割処理を実行する。この処理において、まず、データ挿入部１３０は、オーバーフローすると判定されたブロックがルートブロックか否かを判定する（Ｓ３０）。
【００７５】
データ挿入部１３０は、オーバーフローすると判定されたブロックがルートブロックである場合（Ｓ３０；ＹＥＳ）、新たなルートブロックとするための新たな空きブロックを取得する（Ｓ３１）。このとき、アクセス管理部１１０は、取得された空きブロックのリードカウンタを１増加させる（Ｓ３２）。
【００７６】
データ挿入部１３０は、オーバーフローすると判定された現在のルートブロック内の最小のキー値及び現在のルートブロックを特定するための識別子を含むインデックスエントリを生成する（Ｓ３３）。データ挿入部１３０は、このように生成されたインデックスエントリを、新たなルートブロックとするために取得された空きブロックに書き込む（Ｓ３４）。言い換えれば、生成されたインデックスエントリは、新たなルートブロックから元のルートブロック（その後のブランチブロック）へリンクするためのデータとなる。
【００７７】
このとき、アクセス管理部１１０は、そのインデックスエントリが書き込まれたブロックのライトカウンタを１増加させる（Ｓ３５）。
【００７８】
続いて、データ挿入部１３０は、ルートブロックを変更する（Ｓ３６）。具体的には、データ挿入部１３０は、オーバーフローすると判定された元のルートブロックから新たに取得されたブロックに、ルートブロックを変更する。例えば、この変更は、ブロックヘッダのブロック種の変更により実現される。
【００７９】
次に、データ挿入部１３０は、空きブロックを更に取得する（Ｓ３７）。データ挿入部１３０は、そのオーバーフローすると判定されたブロック内の移動させるべきエントリを決定し、決定された各エントリを上記取得された空きブロックに順次移動させる（Ｓ３８）。例えば、データ挿入部１３０は、予め閾値を保持しており、オーバーフローすると判定されたブロックのエントリのうち、当該閾値以上のキー値を持つエントリを移動エントリに決定する。その閾値には、中央値などのような、１つ以上のエントリのキー値よりも小さい値を用いる。
【００８０】
このとき、アクセス管理部１１０は、エントリを空きブロックに移すたびに、空きブロックのライトカウンタを１増加させる（Ｓ３９）。
【００８１】
その後、データ挿入部１３０は、エントリの移動によりできた空き領域に処理（Ｓ２２）で生成されたインデックスエントリを書き込む（Ｓ２４）。データ挿入部１３０及びアクセス管理部１１０は、上述した処理（Ｓ２５）以降の各処理を実行する。
【００８２】
図８は、第２実施形態におけるＤＢシステム１０のデータ削除時の動作例を示すフローチャートである。
【００８３】
データ削除部１４０は、削除する行データを特定するための値を受け取り、データブロック２４０から行データを削除する（Ｓ４０）。行データの削除は、行のデータを消去することで実現してもよいし、その行データに無効を示す値を付加することで実現してもよい。
【００８４】
データ削除部１４０は、削除された行データを特定するインデックスエントリを有するリーフブロック２３０を特定する（Ｓ４１）。このリーフブロック２３０の特定は、削除された行データにおけるキーが設定された列の値を検索キーとしたインデックス検索によりリーフブロック２３０を特定する場合と同様の手法で実現される。図３の動作例によれば、Ｓ１０、Ｓ１１、Ｓ１２、Ｓ１３、Ｓ１４及びＳ１５の処理が実行されることにより、当該リーフブロック２３０が特定される。
【００８５】
データ削除部１４０は、特定されたリーフブロック２３０における、削除された行データに対応するインデックスエントリを削除する（Ｓ４２）。このとき、アクセス管理部１１０は、そのインデックエントリが削除されたリーフブロック２３０のライトカウンタを増加させる（Ｓ４３）。
【００８６】
データ削除部１４０は、エントリを削除することによりリーフブロック２３０がアンダーフローするか否かを判定する（Ｓ４４）。データ削除部１４０は、アンダーフローが起きていなければ（Ｓ４４；ＮＯ）、処理を終了する。
【００８７】
データ削除部１４０は、アンダーフローすると判定された場合には（Ｓ４４；ＹＥＳ）、アンダーフローすると判定されたリーフブロック２３０に残るエントリを、他のリーフブロック２３０に移動させ、そのリーフブロック２３０を空きブロックにする（Ｓ４５）。このとき、アクセス管理部１１０は、エントリを移動させた先のリーフブロック２３０のライトカウンタを１増加させる（Ｓ４６）。
【００８８】
なお、移動先ブロックは、一つであってもよいし、複数あってもよく、任意の方法で選択してもよい。データ削除部１４０は、空きブロックとなったリーフブロック２３０のアクセスカウンタ（リードカウンタ及びライトカウンタ）を０に設定する。空きブロックとすることで、このブロックはデータ挿入部１３０によって再利用される。また、空きブロック化されたリーフブロック２３０のアクセスカウンタは、それぞれ移動先のブロックのアクセスカウンタに合算されてもよい。
【００８９】
続いて、データ削除部１４０は、ブロック統合が可能か否か判定する（Ｓ４７）。具体的には、データ削除部１４０は、空きブロック化されたブロックの親ブロックにぶら下がる全子ブロックの全エントリをその親ブロックに入れることができるか否かを判定する（Ｓ４７）。
【００９０】
データ削除部１４０は、ブロック統合が不可能と判定すると（Ｓ４７；ＮＯ）、処理を終了する。一方、データ削除部１４０は、ブロック統合が可能と判定すると（Ｓ４７；ＹＥＳ）、それらブロックを統合する（Ｓ４８）。つまり、子ブロックの全エントリを親ブロックに移しつつ、親ブロックに存在したエントリは削除する。結果、その親ブロックにぶら下がる全ての子ブロックを空きブロックにする。
【００９１】
このとき、アクセス管理部１１０は、上位ブロックのライトカウンタを１増加させる（Ｓ４９）。なお、統合される子ブロックのアクセスカウンタの値は、親ブロックのアクセスカウンタに合算されてもよい。
【００９２】
〔第２実施形態の作用及び効果〕
このように第２実施形態では、行データがデータブロック２４０に挿入された場合、その行データを特定するためのインデックスエントリがリーフブロック２３０に追加されると共に、そのリーフブロック２３０のライトカウンタが更新される。
【００９３】
更に、そのインデックスエントリを追加すべきリーフブロック２３０を特定するためのインデックス検索において参照された各インデックスブロックのリードカウンタが更新される。また、その行データ挿入により、ブロック分割が生じた場合には、新たに取得された空きブロックのリードカウンタが更新され、エントリ移動の度にそのブロックのライトカウンタが逐次更新される。
【００９４】
また、第２実施形態では、データブロック２４０から行データが削除されると、その行データに対応するインデックスエントリがリーフブロック２３０から削除されると共に、そのインデックスエントリが削除されたリーフブロック２３０のライトカウンタが更新される。更に、エントリ削除によりリーフブロック２３０がアンダーフローすると判定された場合には、その空きブロック化に伴い移動されたエントリの移動先のリーフブロック２３０のライトカウンタが更新される。更に、ブロックが統合される場合においても、統合される上位ブロックのライトカウンタが更新される。
【００９５】
このように、第２実施形態によれば、各ブロックへのアクセス回数をリードとライトとを区別してそれぞれ管理することができる。リードアクセスとライトアクセスとでは、同じ１つのアクセスでも負荷が異なる。それは、アクセスに要する時間に差があり、かつ、異なる種類のロックをかける必要があるからである。
【００９６】
従って、第２実施形態によれば、各インデックスブロックについて、アクセス種別毎のアクセス回数情報をそれぞれ管理することにより、データベース性能を最適化する上で一層有用な情報を提供することができる。そのような情報によれば、各インデックスブロックにおける、アクセス負荷や子ブロックへのアクセスの偏り等を正確に見積もることができ、更に、インデックスを付加することで効率化を図れる行とそうでない行とを特定することも可能となる。
【００９７】
具体的には、第２実施形態で管理される、各インデックスブロックのリードカウンタ及びライトカウンタを用いれば、行単位でインデックスを付加すべきか否かを決めることができる。ツリーインデックスが付加されると検索は高速化されるが、更新時には、インデックス操作が必要となるため、効率が低下する。これにより、ライトカウンタの数が所定数より多いインデックスブロックのエントリで特定される行にはインデックスを付与しないほうが効率がよいと判断することができる。
【００９８】
［第３実施形態］
第３実施形態では、各ブロックが格納される記憶領域を区別して各ブロックのアクセスカウンタを管理する。以下、第３実施形態におけるＤＢシステム１０について、上述の各実施形態と異なる内容を中心に説明し、上述の各実施形態と同一の内容についての説明は適宜省略する。
【００９９】
〔システム構成〕
図９は、第３実施形態におけるＤＢシステム１０の構成例を示す概念図である。第３実施形態では、図９に示すように、複数の記憶領域（記憶領域Ａ３００及び記憶領域Ｂ４００）が区別される。例えば、記憶領域Ａ３００は、メモリ２に含まれるアクセス速度の速いメモリ装置上で実現され、記憶領域Ｂ４００は、メモリ２に含まれる記憶領域Ａ３００よりもアクセス速度の遅いメモリ装置上で実現される。
【０１００】
例えば、記憶領域Ａ３００は一次記憶上に実現され、記憶領域Ｂ４００はハードディスク等のような二次記憶上に実現される。なお、記憶領域の区別の仕方は、このような形態に制限されず、ＣＰＵキャッシュ、フラッシュメモリ、ハードディスク等のように記憶装置の種別毎に区別されてもよい。
【０１０１】
第３実施形態におけるＤＢシステム１０は、第２実施形態の構成に加えて、記憶領域管理部１５０を更に有する。記憶領域管理部１５０についても、メモリ２に格納されるプログラムがＣＰＵ１により読み出され実行されることにより、ソフトウェア要素として実現される。
【０１０２】
記憶領域管理部１５０は、区別された各記憶領域Ａ３００及び記憶領域Ｂ４００を管理する。本実施形態では、記憶領域Ａ３００がキャッシュとして扱われ、記憶領域Ｂ４００には、ＤＢ部２００の全てが格納される。記憶領域管理部１５０は、検索部１２０、データ挿入部１３０及びデータ削除部１４０がこれら記憶領域を区別することなく処理できるように制御する。
【０１０３】
記憶領域管理部１５０は、記憶領域Ｂ４００内のＤＢ部２００の一部のブロックの複製を記憶領域Ａ３００に格納する。なお、記憶領域管理部１５０によるこのメモリ制御は、周知のキャッシュ技術が用いられればよいため、ここでは詳細な説明を省略する。
【０１０４】
図１０は、第３実施形態におけるインデックスブロックの構成例を概念的に示す図である。第３実施形態におけるインデックブロックでは、図１０に示すように、アクセスカウンタとして、記憶領域毎に、ライトカウンタとリードカウンタとの組がそれぞれ設けられる。
【０１０５】
ライトカウンタＡ及びリードカウンタＡは、記憶領域Ａ３００に格納されたブロックのアクセス（キャッシュヒット）をカウントし、ライトカウンタＢ及びリードカウンタＢは、記憶領域Ａ３００にはなかったために記憶領域Ｂ４００から複製されたブロックへのアクセス（キャッシュミス）をカウントする。
【０１０６】
アクセス管理部１１０は、アクセスしたブロックの記憶領域を区別し、区別された記憶領域のためのアクセスカウンタを更新する。例えば、アクセス管理部１１０は、記憶領域管理部１５０からのキャッシュミスの発生の通知に応じて、どの記憶領域に格納されたブロックにアクセスしたのかを判別する。なお、本実施形態は、メモリ装置の種別の判別方法をこのような方法に限定するものではないため、周知の他の判別方法が利用されてもよい。
【０１０７】
〔第３実施形態の作用及び効果〕
このように第３実施形態では、記憶領域（メモリ装置）毎に、アクセスカウンタが設けられ、アクセス時にそのインデックスブロックが格納されていた記憶領域に対応するアクセスカウンタが更新される。
【０１０８】
従って、第３実施形態によれば、例えば、ハードディスクなどの二次記憶に格納されているブロックが一次記憶上に複製されてから操作される場合の、一次記憶以外の記憶媒体へのアクセスの影響を考慮できるようになる。アクセス処理に要する時間は、インデックスブロックが格納されている記憶領域のタイプに応じて異なるため、第３実施形態によれば、上述の各実施形態に比べてより正確にアクセス負荷を見積もることができる。例えば、第３実施形態では、次のようにアクセス負荷Ｌを算出することができる。
Ｌ＝ａｒ×ａｒｃ＋ａｗ×ａｗｃ＋ｂｒ×ｂｒｃ＋ｂｗ×ｂｗｃ
【０１０９】
ここで、ａｒ及びａｗは、記憶領域Ａ３００上でのリード負荷及びライト負荷を示し、ａｒｃ及びａｗｃは、記憶領域Ａ３００上でのリードアクセス数及びライトアクセス数を示し、ｂｒ及びｂｗは、記憶領域Ｂ４００上でのリード負荷及びライト負荷を示し、ｂｒｃ及びｂｗｃは記憶領域Ｂ４００上でのリードアクセス数及びライトアクセス数を示す。
【０１１０】
［第４実施形態］
上述の各実施形態では、ブロック毎のアクセス回数を管理する形態の例を示したが、第４実施形態では、そのアクセス回数を利用する形態の例を示す。以下、第４実施形態におけるＤＢシステム１０について、上述の各実施形態と異なる内容を中心に説明し、上述の各実施形態と同一の内容についての説明は適宜省略する。
【０１１１】
〔システム構成〕
図１１は、第４実施形態におけるＤＢシステム１０の構成例を示す概念図である。第４実施形態におけるＤＢシステム１０は、第２実施形態の構成に加えて、アクセス負荷評価部３１０、行特定部３２０、アクセス偏り算出部３３０を更に有する。これら各処理部についても、メモリ２に格納されるプログラムがＣＰＵ１により読み出され実行されることにより、ソフトウェア要素として実現される。
【０１１２】
アクセス負荷評価部３１０は、任意のインデックスブロックを特定するためのデータを取得した場合に、そのデータで特定されるインデックスブロックのアクセス負荷を算出し、算出されたアクセス負荷を示す情報を出力する。アクセス負荷の算出の際に、アクセス負荷評価部３１０は、特定されたインデックスブロックに関する所定のリード負荷及び所定のライト負荷を取得し、かつ、そのインデックスブロックのブロックヘッダからアクセスカウンタを読み出す。
【０１１３】
アクセス負荷評価部３１０は、所定のリード負荷とリードアクセス数との積、及び、所定のライト負荷とライトアクセス数との積の和を算出し、この算出された値をアクセス負荷として出力する。ここで、リード負荷及びライト負荷は、１つのリードアクセスと１つのライトアクセスの処理にかかる各時間をそれぞれ示す。アクセス処理に要する時間にはばらつきがあるが、例えば、それらの平均値や中央値などの代表値がメモリ２に格納されており、その代表値がリード負荷及びライト負荷として利用される。
【０１１４】
任意のインデックスブロックを特定するためのデータは、他の装置から通信を介して取得されてもよいし、ＣＰＵ１により実行されているプロセス等のような他の処理部から取得されてもよいし、ユーザインタフェースを介してユーザにより入力されてもよい。
【０１１５】
アクセス負荷評価部３１０は、任意のインデックスブロックを特定するためのデータを取得することなく、インデックスブロックの識別子とインデックスブロックのアクセス負荷との組がアクセス負荷の高い順に並べられたリストデータを出力するようにしてもよい。
【０１１６】
行特定部３２０は、インデックスを付加することで効率化を図れると推定される行を特定する。具体的には、行特定部３２０は、ライトアクセス数が全アクセス数に占める割合が所定値よりも高いリーフブロック２３０を特定する。行特定部３２０は、このように特定されたリーフブロック２３０に含まれる各インデックスエントリにより特定される行をインデックスを付加することで効率化が図れない行として特定する。
【０１１７】
行特定部３２０は、インデックスを付加することで効率化を図れると推定される行に対する識別子のリストを出力する。また、行特定部３２０は、インデックスを付加することで効率化を図れると推定される行のみにインデックスを付加し、それ以外の行からはインデックスを削除する処理を実行するようにしてもよい。また、行特定部３２０は、ライトアクセス数が全アクセス数に占める割合をその割合が高い順に指定された数分並べたリストを出力するようにしてもよい。
【０１１８】
アクセス偏り算出部３３０は、アクセスに偏りがあるブランチブロック２２０を特定する。ブランチブロック２２０は、通常、複数の子ブロックを持つ。子ブロックに対するアクセスの偏りは、各子ブロックのアクセスカウンタを利用することにより把握することができる。そこで、アクセス偏り算出部３３０は、リードアクセス数、ライトアクセス数、全アクセス数に関して、特定の子ブロックに偏ってアクセスを発生させたブランチブロック２２０を偏りが大きいものから所定数分特定する。
【０１１９】
なお、本実施形態は、偏りの算出手法自体を限定せず、周知の様々な手法が利用されればよい。例えば、全子ブロックへのアクセスのａ％が、特定の子ブロックに対するアクセスであり、当該特定の子ブロックへのアクセス数は全子ブロックに対するアクセス数のｘ％（＝１００−ａ）であった場合には、この偏りは、ａ／ｘにより算出されてもよい。具体例では、ブランチブロック２２０が１０個の子ブロックを持ち、１０個のうちの２個の子ブロックへのアクセスが、１０個の子ブロックへのアクセスの８０％を占めていた場合、偏りは、４（＝８０／２０）と算出される。
【０１２０】
偏りの算出手法としては、ａとｘとのいずれか一方を固定するのが最も単純な方法であるが、（７５＜＝ａ＜＝９０）等のように一方の値の範囲を指定して算出する手法が利用されてもよい。このような手法では、範囲指定された一方の値に対してもう一方の値を決め、求めた組に対して（ａ／ｘ）を算出し、その最大値が偏りとして用いられる。
【０１２１】
アクセス負荷評価部３１０、行特定部３２０及びアクセス偏り算出部３３０により出力された情報は、入出力インタフェース３を介して、他の装置（コンピュータ）に送られてもよいし、表示装置等のユーザインタフェースから出力されてもよいし、ファイル等に格納された状態でメモリ２に保存されてもよい。本実施形態は、それら情報の出力形態を限定しない。
【０１２２】
〔第４実施形態の作用及び効果〕
このように第４実施形態では、上述の各実施形態において管理されるブロック毎のアクセスカウンタを利用することにより、データベースの性能の適正化を図る上で有効となる新たな情報が出力される。具体的には、アクセス負荷評価部３１０により、各インデックスブロックのアクセス負荷の情報が出力され、行特定部３２０により、インデックスを付加することで効率化を図れると推定される行の情報が出力され、アクセス偏り算出部３３０により、アクセスに偏りがあるブランチブロック２２０の情報が出力される。
【０１２３】
例えば、上述のような出力情報を用いれば、行単位でインデックスを付加すべきかそうでないかを決めることができる。これは、検索、挿入及び削除といったデータベースに対する全ての操作を考慮した上でのデータベース性能の最適化に繋がる。また、アクセスの偏りに関する情報やアクセス負荷情報を用いれば、インデックスブロックのツリー構造の再設計や、キャッシュに優先的に置くべきインデックスブロックの特定等のようなデータベース性能の最適化を行うことができる。
【０１２４】
更に、アクセスの偏りに関する情報を用いれば、或るブランチブロック２２０の次にアクセスされる確率の高い他のブランチブロック２２０又はリーフブロック２３０、即ち、連続してアクセスされる確率の高いブロック関係を特定することができる。これにより、例えば、連続してアクセスされる可能性の高い２つのインデックスブロックを連続する記憶領域に配置することにより、それらが非連続の記憶領域に配置される場合と比較して処理を高速化することができる。
【０１２５】
即ち、第４実施形態によれば、データベース性能の最適化を行う上での有益な情報を提供することができる。
【０１２６】
［変形例］
上述の第２実施形態、第３実施形態及び第４実施形態では、アクセスカウンタとして、リードカウンタとライトカウンタとがそれぞれ設けられたが、上述の第２実施形態、第３実施形態及び第４実施形態においても、第１実施形態のようにリードカウンタとライトカウンタとを統合して１つのアクセスカウンタで管理されるようにしてもよい。また、上述の各実施形態では、アクセスカウンタ（リードカウンタ及びライトカウンタを含む）は１ずつ増やされたが、この増加幅は、アクセス種別等に応じて適宜変えてもよい。
【０１２７】
また、上述の各実施形態では、ブランチブロック２２０内のインデックスエントリに含まれる各エントリは、いずれか１つの他のブランチブロック２２０又はいずれか１つのリーフブロック２３０を特定するための１つの識別子を含む例を示したが、複数の識別子が含まれるようにしてもよい。例えば、ブランチブロック２２０内の最小のキー値を持つエントリについては、そのキー値より小さいキー値に対応する子ブロックを特定するための識別子と、そのキー値以上で他のエントリのキー値よりも小さいキー値に対応する子ブロックを特定するための識別子とを含むようにしてもよい。
【０１２８】
なお、上記各実施形態の説明は、複数のフローチャートを用いており、それぞれに複数のステップ（処理）を順番に記載しているが、本実施形態は、各ステップの順番を図示される順番に限定するものではない。本実施形態では、図示される処理ステップの順番を内容的に支障しない範囲で変更することができる。また、上述した各実施形態及び変形例は、その内容が相反しない範囲で組み合わせることができる。
【０１２９】
上記の各実施形態及び変形例の一部又は全部は、以下の付記のようにも記載され得る。但し、各実施形態及び各変形例が以下の記載に限定されるものではない。
【０１３０】
（付記１）表データを格納するデータブロックを含むデータベースを管理するデータベース管理装置において、表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、表データに対するデータ操作に応じて各インデックスエントリを参照することによりツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段と、を備えることを特徴とするデータベース管理装置。
【０１３１】
（付記２）上記各インデックスブロック内のインデックスエントリを上記ツリー構造に沿って検索することにより、上記データブロック内の少なくとも１つの行データを抽出する検索手段、を更に備え、上記アクセス管理手段は、上記検索手段が上記複数のインデックスブロックのいずれか１つにアクセスする際に、そのアクセスされたインデックスブロックのアクセスカウンタを増加させ、続いて、そのアクセスされたインデックスブロック内のインデックスエントリにより特定される他のインデックスブロックにアクセスする際に、当該他のインデックスブロックのアクセスカウンタを増加させる、ことを特徴とする付記１に記載のデータベース管理装置。
【０１３２】
（付記３）上記データブロックに新たな行データを挿入すると共に、上記データブロックに挿入された行データを特定する新たなインデックスエントリを上記複数のインデックスブロックのうちの挿入対象のインデックスブロックに挿入し、この挿入対象のインデックスブロックに当該新たなインデックスエントリを挿入することができない場合には空のインデックスブロックを取得するデータ挿入手段、を更に備え、上記アクセスカウンタは、リードカウンタとライトカウンタとを含み、上記アクセス管理手段は、上記データ挿入手段が上記インデックスブロックに上記新たなインデックスエントリを挿入する際には、上記インデックスブロックのライトカウンタを増加させ、上記データ挿入手段が上記空のインデックスブロックを取得する際には、上記空のインデックスブロックのリードカウンタを増加させる、ことを特徴とする付記１又は２に記載のデータベース管理装置。
【０１３３】
（付記４）上記データ挿入手段は、上記挿入対象のインデックスブロック内のインデックスエントリの少なくとも１つを上記空のインデックスブロックに移動させると共に、上記新たなインデックスエントリを上記挿入対象のインデックスブロックに挿入し、上記アクセス管理手段は、上記データ挿入手段が上記少なくとも１つのインデックスエントリを上記空のインデックスブロックに移動させる場合に、上記空のインデックスブロックのライトカウンタを増加させる、ことを特徴とする付記３に記載のデータベース管理装置。
【０１３４】
（付記５）上記データブロックから行データを削除すると共に、削除された行データに対応するインデックスエントリを上記複数のインデックスブロックのうちの削除対象のインデックスブロックから削除し、上記削除対象のインデックスブロックを空きブロックにする場合には、上記削除対象のインデックスブロックに残っているインデックスエントリを他のインデックスブロックに移動させるデータ削除手段、を更に備え、上記アクセス管理手段は、上記データ削除手段が上記削除対象のインデックスブロックから上記インデックスエントリを削除した場合には、上記削除対象のインデックスブロックのライトカウンタを増加させ、上記データ削除手段が上記削除対象のインデックスブロックを空きブロックにする場合には、上記他のインデックスブロックのライトカウンタを増加させる、ことを特徴とする付記３又は４に記載のデータベース管理装置。
【０１３５】
（付記６）上記複数のインデックスブロックのうちの指定インデックスブロックに関するリード負荷情報及びライト負荷情報を取得し、その指定インデックスブロックのリードカウンタとそのリード負荷情報との積、及び、その指定インデックスブロックのライトカウンタとそのライト負荷情報との積の和を、その指定インデックスブロックのアクセス負荷として算出するアクセス負荷評価手段、を更に備えることを特徴とする付記３から５のいずれか１つに記載のデータベース管理装置。
【０１３６】
（付記７）ライトカウンタが全アクセス数に占める割合が所定値よりも高いインデックスブロックを特定する行特定手段を更に備えることを特徴とする付記３から６のいずれか１つに記載のデータベース管理装置。
【０１３７】
（付記８）複数の子インデックスブロックを特定する複数のインデックスブロックをそれぞれ格納する各親インデックスブロックに関し、当該複数の子インデックスブロックのアクセスカウンタに基づいて、全子インデックスブロックへのアクセス回数に対する特定の子インデックスブロックへのアクセス回数の偏りをそれぞれ算出し、偏りの大きいものから所定数分の親インデックスブロックを特定するための情報を出力するアクセス偏り算出手段、を更に備えることを特徴とする付記１から７のいずれか１つに記載のデータベース管理装置。
【０１３８】
（付記９）上記アクセスカウンタは、複数の記憶領域のそれぞれに対応して複数存在し、上記アクセス管理手段は、上記複数のインデックスブロックのいずれか１つへのアクセスが発生した場合に、アクセスされたインデックスブロックが有するアクセスカウンタであってアクセス先の記憶領域に対応するアクセスカウンタを更新する、ことを特徴とする付記１から８のいずれか１つに記載のデータベース管理装置。
【０１３９】
（付記１０）表データを格納するデータブロックを含むデータベースを管理するプログラムにおいて、コンピュータを、上記表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、上記表データに対するデータ操作に応じて各インデックスエントリを参照することにより上記ツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新するアクセス管理手段と、して機能させるためのプログラム。
【０１４０】
（付記１１）上記コンピュータを、上記各インデックスブロック内のインデックスエントリを上記ツリー構造に沿って検索することにより、上記データブロック内の少なくとも１つの行データを抽出する検索手段、として更に機能させ、上記アクセス管理手段は、上記検索手段が上記複数のインデックスブロックのいずれか１つにアクセスする際に、そのアクセスされたインデックスブロックのアクセスカウンタを増加させ、続いて、そのアクセスされたインデックスブロック内のインデックスエントリにより特定される他のインデックスブロックにアクセスする際に、当該他のインデックスブロックのアクセスカウンタを増加させる、ことを特徴とする付記１０に記載のプログラム。
【０１４１】
（付記１２）上記コンピュータを、上記データブロックに新たな行データを挿入すると共に、上記データブロックに挿入された行データを特定する新たなインデックスエントリを上記複数のインデックスブロックのうちの挿入対象のインデックスブロックに挿入し、その挿入対象のインデックスブロックに当該新たなインデックスエントリを挿入することができない場合には空のインデックスブロックを取得するデータ挿入手段、として更に機能させ、上記アクセスカウンタは、リードカウンタとライトカウンタとを含み、上記アクセス管理手段は、上記データ挿入手段が上記インデックスブロックに上記新たなインデックスエントリを挿入する際には、上記インデックスブロックのライトカウンタを増加させ、上記データ挿入手段が上記空のインデックスブロックを取得する際には、上記空のインデックスブロックのリードカウンタを増加させる、ことを特徴とする付記１０又は１１に記載のプログラム。
【０１４２】
（付記１３）上記データ挿入手段は、上記挿入対象のインデックスブロック内のインデックスエントリの少なくとも１つを上記空のインデックスブロックに移動させると共に、上記新たなインデックスエントリを上記挿入対象のインデックスブロックに挿入し、上記アクセス管理手段は、上記データ挿入手段が上記少なくとも１つのインデックスエントリを上記空のインデックスブロックに移動させる場合に、上記空のインデックスブロックのライトカウンタを増加させる、ことを特徴とする付記１２に記載のプログラム。
【０１４３】
（付記１４）上記コンピュータを、上記データブロックから行データを削除すると共に、削除された行データに対応するインデックスエントリを上記複数のインデックスブロックのうちの削除対象のインデックスブロックから削除し、上記削除対象のインデックスブロックを空きブロックにする場合には、上記削除対象のインデックスブロックに残っているインデックスエントリを他のインデックスブロックに移動させるデータ削除手段、として更に機能させ、上記アクセス管理手段は、上記データ削除手段が上記削除対象のインデックスブロックから上記インデックスエントリを削除した場合には、上記削除対象のインデックスブロックのライトカウンタを増加させ、上記データ削除手段が上記削除対象のインデックスブロックを空きブロックにする場合には、上記他のインデックスブロックのライトカウンタを増加させる、ことを特徴とする付記１２又は１３に記載のプログラム。
【０１４４】
（付記１５）上記コンピュータを、上記複数のインデックスブロックのうちの指定インデックスブロックに関するリード負荷情報及びライト負荷情報を取得し、その指定インデックスブロックのリードカウンタとそのリード負荷情報との積、及び、その指定インデックスブロックのライトカウンタとそのライト負荷情報との積の和を、その指定インデックスブロックのアクセス負荷として算出するアクセス負荷評価手段、として更に機能させることを特徴とする付記１２から１４のいずれか１つに記載のプログラム。
【０１４５】
（付記１６）上記コンピュータを、ライトカウンタが全アクセス数に占める割合が所定値よりも高いインデックスブロックを特定する行特定手段、として更に機能させることを特徴とする付記１２から１５のいずれか１つに記載のプログラム。
【０１４６】
（付記１７）複数の子インデックスブロックを特定する複数のインデックスブロックをそれぞれ格納する各親インデックスブロックに関し、当該複数の子インデックスブロックのアクセスカウンタに基づいて、全子インデックスブロックへのアクセス回数に対する特定の子インデックスブロックへのアクセス回数の偏りをそれぞれ算出し、偏りの大きいものから所定数分の親インデックスブロックを特定するための情報を出力するアクセス偏り算出手段、として更に機能させることを特徴とする付記１０から１６のいずれか１つに記載のプログラム。
【０１４７】
（付記１８）上記アクセスカウンタは、複数の記憶領域のそれぞれに対応して複数存在し、上記アクセス管理手段は、上記複数のインデックスブロックのいずれか１つへのアクセスが発生した場合に、アクセスされたインデックスブロックが有するアクセスカウンタであってアクセス先の記憶領域に対応するアクセスカウンタを更新する、ことを特徴とする付記１０から１７のいずれか１つに記載のプログラム。
【０１４８】
（付記１９）表データを格納するデータブロックを含むデータベースを管理するデータベース管理方法において、上記表データを構成する１つの行データ又は他のインデックスブロックを特定するための少なくとも１つのインデックスエントリ、及び、アクセスカウンタをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックを備えるコンピュータが、上記表データに対するデータ操作に応じて各インデックスエントリを参照し、上記参照により上記ツリー構造に沿ってアクセスされた複数のインデックスブロックの各アクセスカウンタをそれぞれ更新する、ことを特徴とするデータベース管理方法。
【０１４９】
（付記２０）付記１０から１８のいずれか１つに記載のプログラムを記録したコンピュータが読み取り可能な記録媒体。
【０１５０】
この出願は、２０１０年１２月１６日に出願された日本出願特願２０１０−２８０３９７号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2012081165.tif 000003
【図２】
2012081165.tif 000004
【図３】
2012081165.tif 000005
【図４】
2012081165.tif 000006
【図５】
2012081165.tif 000007
【図６】
2012081165.tif 000008
【図７】
2012081165.tif 000009
【図８】
2012081165.tif 000010
【図９】
2012081165.tif 000011
【図１０】
2012081165.tif 000012
【図１１】
2012081165.tif 000013
【国際調査報告】
2012081165.tif 000014
2012081165.tif 000015
2012081165.tif 000016