表データを格納するデータブロックを含むデータベースを管理するデータベース管理装置において、前記表データを構成する1つの行データ又は他のインデックスブロックを特定するための少なくとも1つのインデックスエントリと、リードカウンタ及びライトカウンタを含むアクセスカウンタとをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、前記表データに対するデータ操作に応じて前記ツリー構造に沿ってアクセスされたインデックスブロックに関し、インデックスブロックへのリードアクセスに応じてリードカウンタを更新し、インデックスブロックへの更新アクセスに応じてライトカウンタを更新するアクセス管理手段と、前記データブロックに挿入される新たな行データを特定するための新たなインデックスエントリを前記複数のインデックスブロックのうちの挿入対象のリーフブロックに挿入するデータ挿入手段と、前記挿入対象のリーフブロックにおける前記リードカウンタと前記ライトカウンタとの比較結果に基づいて、前記新たなインデックスエントリの格納先として、他のインデックスブロックのインデックスエントリにより特定されない拡張ブロックを取得し、当該拡張ブロックを特定するための特定情報を前記挿入対象のリーフブロックに設定する拡張ブロック操作手段と、を備えることを特徴とするデータベース管理装置。前記拡張ブロック操作手段は、前記挿入対象のリーフブロックにおける前記ライトカウンタと前記リードカウンタとの比較結果に基づいて、前記拡張ブロックを他のインデックスブロックのインデックスエントリにより特定されるリーフブロックとなるように設定することを特徴とする請求項1に記載のデータベース管理装置。前記拡張ブロック操作手段は、前記リードカウンタ及び前記ライトカウンタに基づいて、前記挿入対象のリーフブロックにおける全アクセスに対するライトアクセスの比率が所定閾値を超えるか否かを判定し、前記ライトアクセスの比率が所定閾値を超える場合に、他のインデックスブロックのインデックスエントリにより特定されない拡張ブロックを取得する、ことを特徴とする請求項1又は2に記載のデータベース管理装置。前記拡張ブロック操作手段は、前記リードカウンタ及び前記ライトカウンタに基づいて、前記挿入対象のリーフブロックにおける全アクセスに対するリードアクセスの比率が所定閾値を超えるか否かを判定し、前記リードアクセスの比率が所定閾値を超える場合に、前記拡張ブロックを他のインデックスブロックのインデックスエントリにより特定されるリーフブロックとなるように設定する、ことを特徴とする請求項2又は3に記載のデータベース管理装置。前記アクセス管理手段は、前記拡張ブロックに格納されたインデックスエントリに対してアクセスされた場合には、当該拡張ブロックを特定するための特定情報が設定されたリーフブロックのアクセスカウンタを更新する、ことを特徴とする請求項1から4のいずれか1項に記載のデータベース管理装置。表データを格納するデータブロックを含むデータベースを管理するプログラムにおいて、コンピュータに、前記表データを構成する1つの行データ又は他のインデックスブロックを特定するための少なくとも1つのインデックスエントリと、リードカウンタ及びライトカウンタを含むアクセスカウンタとをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックと、前記表データに対するデータ操作に応じて前記ツリー構造に沿ってアクセスされたインデックスブロックに関し、インデックスブロックへのリードアクセスに応じてリードカウンタを更新し、インデックスブロックへの更新アクセスに応じてライトカウンタを更新するアクセス管理手段と、前記データブロックに挿入される新たな行データを特定するための新たなインデックスエントリを前記複数のインデックスブロックのうちの挿入対象のリーフブロックに挿入するデータ挿入手段と、前記挿入対象のリーフブロックにおける前記リードカウンタと前記ライトカウンタとの比較結果に基づいて、前記新たなインデックスエントリの格納先として、他のインデックスブロックのインデックスエントリにより特定されない拡張ブロックを取得し、当該拡張ブロックを特定するための特定情報を前記挿入対象のリーフブロックに設定する拡張ブロック操作手段と、を実現させることを特徴とするプログラム。前記拡張ブロック操作手段は、前記挿入対象のリーフブロックにおける前記ライトカウンタと前記リードカウンタとの比較結果に基づいて、前記拡張ブロックを他のインデックスブロックのインデックスエントリにより特定されるリーフブロックとなるように設定することを特徴とする請求項6に記載のプログラム。表データを格納するデータブロックを含むデータベースを管理するデータベース管理方法において、前記表データを構成する1つの行データ又は他のインデックスブロックを特定するための少なくとも1つのインデックスエントリと、リードカウンタ及びライトカウンタを含むアクセスカウンタとをそれぞれ有し、ツリー構造を持つ複数のインデックスブロックを格納するコンピュータが、前記表データに対するデータ操作に応じて前記ツリー構造に沿ってアクセスされたインデックスブロックに関し、インデックスブロックへのリードアクセスに応じてリードカウンタを更新し、インデックスブロックへの更新アクセスに応じてライトカウンタを更新し、前記データブロックに挿入される新たな行データを特定するための新たなインデックスエントリを前記複数のインデックスブロックのうちの挿入対象のリーフブロックに挿入し、前記挿入対象のリーフブロックにおける前記リードカウンタと前記ライトカウンタとの比較結果に基づいて、前記新たなインデックスエントリの格納先として、他のインデックスブロックのインデックスエントリにより特定されない拡張ブロックを取得し、前記拡張ブロックを特定するための特定情報を前記挿入対象のリーフブロックに設定する、ことを特徴とするデータベース管理方法。前記コンピュータが、更に、前記挿入対象のリーフブロックにおける前記ライトカウンタと前記リードカウンタとの比較結果に基づいて、前記拡張ブロックを他のインデックスブロックのインデックスエントリにより特定されるリーフブロックとなるように設定する、ことを特徴とする請求項8に記載のデータベース管理方法。以下、本発明の実施の形態としてのデータベースシステム以降、DBシステムと表記するについて説明する。なお、以下に挙げる各実施形態はそれぞれ例示であり、本発明は以下の各実施形態の構成に限定されない。[第1実施形態]システム構成図1は、第1実施形態におけるDBシステム10の構成例を示す概念図である。DBシステム10は、図1に示すように、ハードウェア構成として、CPU1、メモリ2RAMRandomAccessMemory、ROMReadOnlyMemory、ハードディスクHDD等、入出力インタフェース3等を有する。これら各ハードウェア要素は例えばバス5により接続される。入出力インタフェース入出力I/F3は、外部のコンピュータ等と通信を行うためのネットワークインタフェースやユーザインタフェース等を含む。DBシステム10は、例えば、メモリ2に格納されるプログラムがCPU1により読み出され実行されることにより、以下のような各処理部を実現する。DBシステム10は、データベース管理部以降、DB管理部と表記する100、データベース以降、DBと表記する部200等を有する。なお、図1の例では、DBシステム10が1台のコンピュータとして実現される例を示すが、複数のコンピュータで実現されてもよい。また、図1の例では、1つのCPU1のみが示されるが、複数のプロセッサ例えば、CPU、DSPDigitalSignalProcessor等を有していてもよい。例えば、DB管理部100とDB部200とが異なるコンピュータ又はCPU上で実現されてもよい。本実施形態は、DBシステム10のハードウェア構成を限定しない。DB部200は、メモリ2上に実現され、複数のブロック210図1では2101、2102、210nとして表記を含む。各ブロック210は、例えば、所定容量例えば、4キロバイトKBの連続した記憶領域として確保される。ブロック210間は、連続領域として確保されてもよいし、非連続な各領域として確保されてもよい。本実施形態は、ブロック210の領域サイズを限定しない。各ブロック210は、インデックスを格納するブロック以降、インデックスブロックとも表記されると、データを格納するブロック以降、データブロックとも表記される240とに大別される。データブロック240は、任意の表テーブルを格納する。インデックスブロックは、ツリー構造例えば、BツリーBalancedTree構造を持ち、更に、ブランチブロック220と、リーフブロック230とに大別される。ブランチブロック220及びリーフブロック230の各々は、インデックスとなる少なくとも1つのエントリを格納する。各インデックスブロックに格納されるエントリは、インデックスエントリと呼ぶこともできる。インデックスエントリは、検索対象となるキー値と識別子IDとを含む。リーフブロック230は、インデックスブロックの中の最下層のブロックである。リーフブロックのエントリに含まれる識別子は、データブロックのいずれか1つの行データを特定するためのデータである。その識別子は、例えば、特定すべき行データの先頭を指すポインタとその行データのサイズとから構成される。ブランチブロック220は、リーフブロック230又は他のブランチブロック220へのリンクを持つブロックである。このリンクは、インデックスエントリの識別子によって実現される。即ち、ブランチブロック220のエントリに含まれる識別子は、いずれか1つのブランチブロック220又はいずれか1つのリーフブロック230を特定するポインタである。以降、最上位のブランチブロック220をルートブロックと表記する場合もある。ここで、最上位とは、検索時に最初に検索されることを意味する。以降、インデックスエントリの識別子によりリンクされた各インデックスブロックにおいて、そのインデックスエントリを含むブランチブロック220を親ブロックと表記し、そのインデックスエントリの識別子で特定されるリーフブロック230又は他のブランチブロック220を子ブロックと表記する場合もある。図2は、ブランチブロック220の構成例を概念的に示す図である。図2に示すように、ブランチブロック220は、ブロックヘッダと少なくとも1つのインデックスエントリとをそれぞれ含む。インデックスエントリは、上述したように、キー値図2のkeyと識別子図2のidとを含む。ブロックヘッダには、ブロック種、アクセスカウンタ等が設定される。ブロック種は、リーフブロック、ブランチブロック等を識別するための情報である。アクセスカウンタは、リードカウンタ及びライトカウンタを含み、インデックスブロックへのアクセスの数をカウントする。具体的には、ブランチブロック220へのリードアクセスに応じてリードカウンタが更新され、ブランチブロック220への更新アクセスエントリ追加及びエントリ削除に応じてライトカウンタが更新される。図3は、リーフブロック230の構成例を概念的に示す図である。図3に示すように、リーフブロック230は、そのブロックヘッダに拡張ポインタを有する点において、ブランチブロック220と異なる。リーフブロック230のその他の構成については、ブランチブロック220と同様である。拡張ポインタは、リーフブロック230の容量を拡張するために追加される拡張ブロックを特定するための情報である。例えば、拡張ポインタには、拡張ブロックのアドレスが設定される。なお、拡張ブロックを持たないリーフブロック230の拡張ポインタには、無効値例えば、NULLが設定される。以降、リーフブロック230を拡張するとの表記は、そのリーフブロック230に拡張ブロックを付加することを意味する。拡張ブロックは、メモリ2上に実現される、上述のブロック210のうちの一つである。拡張ブロックには、リーフブロック230と同様に、データブロックのいずれか1つの行データを特定する識別子を含むインデックスエントリが格納される。拡張ブロックは、他のインデックスブロックブランチブロック220のインデックスエントリにより特定されない点において、インデックスブロックとは異なる。1つのリーフブロック230に対して複数の拡張ブロックが追加された場合には、拡張ブロックには、他の拡張ブロックを特定するための拡張ポインタが設定される。上述のように、図2及び図3では、インデックスブロック内の連続領域に、ブロックヘッダ内の各値及び各エントリが格納される例を示したが、ブロックヘッダ内の各値と各エントリとは、相互に関連付けられていれば、必ずしも連続した領域に格納されなくともよい。以降、ブランチブロック220、リーフブロック230、データブロック240、及び拡張ブロックを単にブロックと表記する場合もある。また、インデックスエントリを単にエントリと表記する場合もある。DB管理部100は、アクセス管理部110、検索部120、データ挿入部130、データ削除部140、拡張ブロック操作部150等を含む。DB管理部100に含まれるこれら各処理部も、メモリ2に格納されるプログラムがCPU1により読み出され実行されることにより、ソフトウェア要素として実現される。検索部120は、検索キーを取得し、この検索キーに対応する列フィールドのデータを含む行をデータブロック240から抽出する。検索キーは、他の装置から通信を介して取得されてもよいし、CPU1により実行されているプロセス等のような他の処理部から取得されてもよいし、ユーザインタフェースを介してユーザにより入力されてもよい。検索部120は、データブロック240における抽出すべき行を特定するために、インデックス検索を行う。このインデックス検索において、検索部120は、まず、ルートブロックにアクセスする。検索部120は、ルートブロックに含まれるエントリのうち、検索キー以下の最大のキー値を持つエントリ、又は、検索キー以上の最小のキー値を持つエントリを検索する。検索部120は、抽出されたエントリの識別子により特定される他のブランチブロック220又はリーフブロック230を読み出す。検索部120は、他のブランチブロック220が読み出された場合には、上記のルートブロックに対する検索と同様に特定のエントリを抽出する。一方、検索部120は、リーフブロック230が読み出された場合には、検索キーの条件を満たすエントリを抽出し、そのエントリの識別子で特定される行データをデータブロック240から抽出する。検索部120は、リーフブロック230が読み出された場合で、かつ、そのリーフブロック230の拡張ポインタに有効値が設定されているそのリーフブロック230が拡張されている場合には、リーフブロック230に含まれるエントリと、その拡張ポインタで特定される拡張ブロックに含まれるエントリとを対象に、検索キーの条件を満たすエントリを抽出する。言い換えれば、検索部120は、拡張ブロックをリーフブロック230のインデックスエントリを格納する領域の一部として扱う。データ挿入部130は、挿入する行データを受け取り、データブロック240にその行データを書き込む。このとき、データ挿入部130は、その挿入された行データに基づいて、インデックスブロック内のインデックスを更新する。データブロック240への書き込みは、例えば、挿入すべき行データよりも大きな空き領域を持つブロックのいずれか1つに書き込まれる。データ挿入部130は、インデックスの更新において、対応するリーフブロック230に、その挿入された行データに対応する新たなインデックスエントリを追加する。この新たなインデックスエントリは、キーが設定される列であって挿入された行に含まれる列のデータをキー値として含み、更に、その行を特定するための識別子を含む。データ挿入部130は、更新対象のリーフブロック230が拡張されている場合には、そのリーフブロック230の拡張ブロックに新たなインデックスエントリを追加する。リーフブロック230が拡張されているか否かは、後述する拡張ブロック操作部150から送られるデータに基づいて判断される。なお、データ挿入部130も、拡張ブロックをリーフブロック230のインデックスエントリを格納する領域の一部として扱う。インデックスの更新では、リーフブロック230へのエントリの追加に加えて、ブランチブロック220にも新たなインデックスエントリを追加することが要求される場合がある。それは、挿入対象のリーフブロック230に、新たなインデックスエントリを追加するための十分な空き領域がない場合オーバーフローが起きる場合である。このようにオーバーフローが起きる場合には、データ挿入部130は、ブロック分割を行うことによって空き領域を作る。ブロック分割では、データ挿入部130は、所定容量の空き領域がなくなったリーフブロック230のデータの一部を新たに確保したリーフブロック230に移すことで空き領域を作り出す。ブロック分割は、リーフブロック230のみでなくブランチブロック220においても同様に処理される。ブロック分割の詳細については動作例の項で詳述する。データ削除部140は、削除する行データを特定するための値を受け取り、データブロック240から行データを削除し、削除された行データに対応するインデックスエントリをリーフブロック230から削除する。例えば、削除する行データを特定するための値は、検索部120の検索処理の結果として取得される。ここで、拡張ブロックは、リーフブロック230のインデックスエントリを格納する領域の一部として扱われるため、削除対象のインデックスエントリが実際には拡張ブロックに格納されている場合であっても、データ削除部140は、特定されたエントリを通常の処理と同様に削除する。インデックスエントリをリーフブロック230又はその拡張ブロックから削除することにより、リーフブロック230又はその拡張ブロックの空き領域が所定サイズ以上となる場合アンダーフローが起きる場合、データ削除部140は、そのリーフブロック230が拡張されているか否かに応じて、以下のような処理を実行する。データ削除部140は、そのリーフブロック230が拡張されていない場合には、このリーフブロック230を空きブロックにし、かつ、必要に応じて、ブロック統合処理を実行する。このブロック統合処理については動作例の項において詳述する。一方、データ削除部140は、そのリーフブロック230が拡張されている場合には、拡張ブロックの統合処理を実行する。具体的には、データ削除部140は、そのリーフブロック230が拡張されている場合で、かつ、リーフブロック230自体にアンダーフローが起きると判定した場合には、拡張ブロック内のインデックスエントリをそのリーフブロック230に移動させる。データ削除部140は、そのリーフブロック230が拡張されている場合で、かつ、拡張ブロックにアンダーフローが起きると判定した場合には、同一リーフブロック230のための他の拡張ブロックに、その拡張ブロックのインデックスエントリを移動させる。拡張ブロック操作部150は、データ挿入部130がブロック分割を行う前に、リーフブロック230のブロック分割を行うか、拡張ブロックを用いたリーフブロック230の容量の拡張を行うかのいずれか一方を選択する。この選択のために、拡張ブロック操作部150は、新たなインデックスエントリが追加されるリーフブロック230における全アクセスに対するライトアクセスの比率が所定閾値を超えるか否かを判定する。具体的には、拡張ブロック操作部150は、ライトカウンタの値Wを、リードカウンタの値とライトカウンタの値との合計WRで除算することにより、当該ライトアクセスの比率W/WRを算出する。拡張ブロック操作部150は、当該ライトアクセスの比率が所定閾値を超える場合に、拡張ブロックを用いたリーフブロック230の容量の拡張を選択し、新たな拡張ブロックを取得する。拡張ブロック操作部150は、拡張ブロックを取得すると、その拡張ブロックへのポインタをリーフブロック230の拡張ポインタに設定する。一方、拡張ブロック操作部150は、当該ライトアクセスの比率が所定閾値以下である場合には、データ挿入部130にリーフブロック230のブロック分割を実行させる。上記所定閾値は、例えば、予め調整可能にメモリ2に格納される。当該所定閾値には、例えば、全インデックスブロックにおけるライトアクセスの全アクセスに対する比率のxパーセンタイルxは例えば10等が用いられる。拡張ブロック操作部150は、検索部120においてリーフブロック230が読み出された場合に、そのリーフブロック230の拡張ポインタ及び拡張ブロックの拡張ポインタを参照することにより、そのリーフブロック230のための全ての拡張ブロックを特定する。拡張ブロック操作部150は、それら拡張ブロックに含まれるエントリを検索対象とするように検索部120に指示する。拡張ブロック操作部150は、データ削除部140により、リーフブロック230と拡張ブロックとの間、又は、拡張ブロック間におけるインデックスエントリの移動が実行される場合に、移動対象とする拡張ブロック及び移動対象とするインデックスエントリを特定する。リーフブロック230と拡張ブロックとの間、及び、拡張ブロック間におけるインデックスエントリの移動は、拡張ブロックを空ブロックとするように実行されることが好ましい。また、拡張ブロック操作部150は、インデックスエントリの移動により、リーフブロック230がオーバーフローしないように、移動させるインデックスエントリの数を決める。アクセス管理部110は、データブロック240に対するデータ操作に応じてツリー構造に沿ってアクセスされた各インデックスブロックに関し、アクセスカウンタをそれぞれ更新する。具体的には、アクセス管理部110は、検索部120、データ挿入部130及びデータ削除部140によるインデックスブロックへのアクセス内容に基づいて、リードアクセス時にはそのインデックスブロックのリードカウンタを更新し、更新アクセス時にはそのインデックスブロックのライトカウンタを更新する。更新アクセスには、エントリの挿入操作及びエントリの削除操作が含まれる。なお、エントリの移動操作は、エントリの挿入操作とエントリの削除操作との組み合わせで実現される。アクセス管理部110は、検索部120がインデックス検索を行うことによりインデックスエントリの識別子により特定されるブランチブロック220又はリーフブロック230を読み出す際に、その読み出されたインデックスブロックのブロックヘッダのアクセスカウンタを増加させる。但し、ルートブロックは最初に参照されるブロックであるため、検索部120は、アクセスした際に、ルートブロックのブロックヘッダのアクセスカウンタを増加させる。アクセス管理部110は、検索部120がルートブロックのいずれかのエントリの識別子が示すブランチブロック220を読む際に、そのブランチブロック220のアクセスカウンタを1増加させる。更に、アクセス管理部110は、検索部120がこのブランチブロック220からたどるリーフブロック230にアクセスするときに、リーフブロック230のアクセスカウンタを1増加させる。アクセス管理部110は、行データ挿入時においてデータ挿入部130により新たなインデックスエントリが追加されると、そのインデックスエントリが追加されたインデックスブロックのライトカウンタを1増加させる。このとき、アクセス管理部110は、そのインデックスエントリが追加されたインデックスブロックを検索するまでにアクセスされた各インデックスブロックのリードカウンタをそれぞれ1増加させる。同様に、行データ挿入時においてブロック分割が行われる場合には、アクセス管理部110は、そのブロック分割処理においてアクセスされたインデックスブロックのリードカウンタを増加させ、かつ、ブロック分割処理でエントリが移動させられる度に移動先のインデックスブロックのライトカウンタを1増加させる。また、アクセス管理部110は、データ削除部140がインデックスブロックからエントリを削除した場合には、そのインデックスブロックのライトカウンタを増加させる。更に、アクセス管理部110は、データ削除部140がインデックスブロックを空きブロックにする場合には、そのインデックスブロックを空きブロックにするために移動されたエントリの移動先となる他のインデックスブロックのライトカウンタを増加させる。ここで、拡張ブロックは、リーフブロック230のインデックスエントリを格納する領域の一部として扱われるため、実際には拡張ブロック内のエントリが操作された場合であっても、その拡張ブロックを持つリーフブロック230のアクセスカウンタが更新される。具体的には、検索部120により拡張ブロック内のエントリが抽出された場合であっても、その拡張ブロックに対応するリーフブロック230のリードカウンタが更新される。同様に、データ挿入部130により拡張ブロックに新たなエントリが追加された場合、及び、データ削除部140により拡張ブロックのエントリが削除された場合であっても、その拡張ブロックに対応するリーフブロック230のライトカウンタが更新される。また、データ削除部140により拡張ブロックの統合処理が実行される場合には、拡張ブロック内のエントリを移動させる度に、その拡張ブロックに対応するリーフブロック230のライトカウンタが更新される。動作例以下、第1実施形態におけるDBシステム10の動作例について図4から図7を用いて説明する。図4は、第1実施形態におけるDBシステム10のデータ検索時の動作例を示すフローチャートである。図4の例では、完全一致検索を行う場合の動作が示される。図5は、ブランチブロック220、リーフブロック230及びデータブロック240の関係の例を概念的に示す図である。ここでは、図5の例において、文字列の大小を辞書順に従って比較することを想定し、検索部120が、検索キーgoを列データに含む行を検索する場合を例に挙げて、当該動作例を説明する。検索部120は、検索キーを取得すると、まず、ルートブロックを読み出すS10。図5の例では、検索部120は、検索キーgoを取得すると、キー値e、m、tを含む各インデックスエントリを持つルートブロックを読み出す。アクセス管理部110は、検索部120がルートブロックにアクセスした場合に、そのルートブロックのリードカウンタを1増加させるS11。検索部120は、ルートブロック内のインデックスエントリのうち、当該検索キー以下の最大のキー値を持つエントリ、又は、当該検索キー以上の最小のキー値を持つエントリを特定する。いずれの特定方法を取っても一般性を失わないので、ここでは、検索部120は、当該検索キー以下の最大のキー値を持つエントリを特定するものとするS12。このエントリの特定は、ブロック中の全てのエントリを比較することにより実現されてもよいし、ブロック中のエントリをキー値でソートした上で一部のエントリを比較することにより実現されてもよい。図5の例では、簡略化されているが、キー値eについては、例えば、キー値eを持つエントリとeより小さい値を示すキー値例えば、NULLを持つエントリとが含まれる。ここで、検索キーgo以下の最大のキー値はeであり、検索キーgoは、キー値eより大きくキー値mよりも小さいので、左から2番目のブランチブロックを特定する識別子を含むエントリが特定される。続いて、検索部120は、そのように特定されたエントリの識別子によって特定されるインデックスブロックを読み出すS13。アクセス管理部110は、検索部120がインデックスブロックを読み出すと、そのインデックスブロックのリードカウンタを1増加させるS14。検索部120は、ブロックヘッダに設定されるブロック種により、その読み出されたインデックスブロックがリーフブロック230かブランチブロック220かを判定するS15。検索部120及びアクセス管理部110は、その読み出されたインデックスブロックがブランチブロック220である場合にはS15;NO、その読み出されたブランチブロック220に関し上記S12、S13及びS14の処理を実行する。検索部120は、その読み出されたインデックスブロックがリーフブロック230である場合にはS15;YES、その読み出されたリーフブロック230内のエントリを取得するS16。図5の例では、リーフブロック230内のエントリキー値gameを含むエントリからキー値giftを含むエントリまでが取得される。続いて、拡張ブロック操作部150が、その読み出されたリーフブロック230の拡張ポインタが無効か否かを判定するS17。この判定は、拡張ポインタに有効値が設定されているか否かにより行われる。拡張ブロック操作部150は、拡張ポインタが有効であると判定するとS17;NO、その拡張ポインタにより特定される拡張ブロック内のエントリを取得するS18。図5の例では、リーフブロック230の拡張ブロック内のエントリキー値giveを含むエントリからキー値hearを含むエントリまでが取得される。拡張ブロック操作部150は、その拡張ブロック内の拡張ポインタに有効値が設定されている場合には、更に、その拡張ポインタで特定される他の拡張ブロック内のエントリも取得する。このようにして、拡張ブロック操作部150は、その読み出されたリーフブロック230のための各拡張ブロック内のエントリをそれぞれ取得するS18。なお、リーフブロック230の拡張ポインタが無効であると判定するとS17;YES、検索部120は、処理S20を実行する。検索部120は、処理S16で取得されたリーフブロック230内のエントリ、及び、処理S18で取得された拡張ブロック内のエントリの中から、検索キーを含む検索条件に一致するエントリを特定するS20。ここでは、その検索条件は、検索キーを列データに含む行完全一致の検索を示す。図5の例では、キー値goを含むインデックスエントリが特定される。このインデックスエントリの特定は、リーフブロック230及びそのリーフブロック230が持つ拡張ブロック内の全てのエントリを比較することにより実現されてもよいし、それらエントリをキー値でソートした上で一部のエントリを比較することにより実現されてもよい。検索部120は、特定されたインデックスエントリに含まれる識別子で特定される行データを抽出するS21。図5の例では、キー値goを含むインデックスエントリの識別子により特定されるデータブロック240の行が抽出される。例えば、その識別子に含まれるポインタで、行データの先頭が特定され、その先頭アドレスから行の大きさバイト数分のデータが読み出される。図6は、第1実施形態におけるDBシステム10のデータ挿入時の動作例を示すフローチャートである。データ挿入部130は、挿入すべき行データを取得すると、この行データを空き領域のある任意のデータブロック240に書き込むS31。データ挿入部130は、挿入された行データに対応するインデックスエントリを挿入すべきリーフブロック230を特定するS32。このリーフブロック230の特定は、挿入された行データにおけるキーが設定された列の値を検索キーとしたインデックス検索によりリーフブロック230を特定する場合と同様の手法で実現される。図4の動作例によれば、S10、S11、S12、S13、S14及びS15の処理が実行されることにより、挿入すべきリーフブロック230が特定される。このとき、挿入された行データに対応するリーフブロック230を特定するために読み出されたインデックスブロックのリードカウンタは、アクセス管理部110によりカウントアップされる。続いて、データ挿入部130は、特定されたリーフブロック230に挿入すべき新たなインデックスエントリを生成するS33。新たなインデックスエントリは、挿入された行データにおけるキーが設定された列の値をキー値として含み、挿入された行データを特定するための識別子を含む。データ挿入部130は、特定されたリーフブロック230が新たなインデックスエントリの追加によりオーバーフローするか否かを判定するS34。ここで、オーバーフローとは、新たなインデックスエントリを追加するとブロックの空き領域が所定の比率を下回ることである。データ挿入部130は、オーバーフローしないと判定するとS34;NO、その特定されたリーフブロック230にその新たに生成されたインデックスエントリを書き込むS35。このとき、アクセス管理部110は、書き込まれたリーフブロック230のライトカウンタを1増加させるS36。続いて、データ挿入部130は、ブロック分割がなされたか否かを判定するS37。データ挿入部130は、ブロック分割がされていない場合にはS37;NO、処理を終了し、ブロック分割がなされている場合にはS37;YES、ブロック分割がなされたブロックの上位のブランチブロックを特定するS38。この上位ブランチブロックの特定は、再帰関数的な処理を施すことにより実現してもよいし、ブロックヘッダに上位ブロックの識別子を格納することで実現してもよい。以降、データ挿入部130は、その特定された上位ブランチブロックを対象ブロックとして処理S33に戻って各処理を実行する。一方、データ挿入部130は、オーバーフローすると判定した場合にはS34;YES、そのオーバーフローすると判定されたインデックスブロックがリーフブロック230であるか否かを判定するS40。対象のインデックスブロックがリーフブロック230でない場合にはS40;NO、データ挿入部130は、その対象のインデックスブロックに対してブロック分割処理を実行する。ブロック分割処理では、まず、データ挿入部130は、オーバーフローすると判定されたインデックスブロックがルートブロックか否かを判定するS50。データ挿入部130は、当該インデックスブロックがルートブロックである場合S50;YES、新たなルートブロックとするための新たな空きブロックを取得するS51。このとき、アクセス管理部110は、取得された空きブロックのリードカウンタを1増加させるS52。データ挿入部130は、オーバーフローすると判定された現在のルートブロック内の最小のキー値及び現在のルートブロックを特定するための識別子を含むインデックスエントリを生成するS53。データ挿入部130は、このように生成されたインデックスエントリを、新たなルートブロックとするために取得された空きブロックに書き込むS54。言い換えれば、生成されたインデックスエントリは、新たなルートブロックから元のルートブロックその後のブランチブロックへリンクするためのデータとなる。このとき、アクセス管理部110は、そのインデックスエントリが書き込まれたインデックスブロックのライトカウンタを1増加させるS55。続いて、データ挿入部130は、ルートブロックを変更するS56。具体的には、データ挿入部130は、オーバーフローすると判定された元のルートブロックから新たに取得されたブロックに、ルートブロックを変更する。例えば、この変更は、ブロックヘッダのブロック種の変更により実現される。次に、データ挿入部130は、空きブロックを更に取得するS57。データ挿入部130は、そのオーバーフローすると判定されたインデックスブロック内の移動させるべきエントリを決定し、決定された各エントリを上記取得された空きブロックに順次移動させるS58。例えば、データ挿入部130は、予め閾値を保持しており、オーバーフローすると判定されたインデックスブロックのエントリのうち、当該閾値以上のキー値を持つエントリを移動エントリに決定する。その閾値には、中央値などのような、1つ以上のエントリのキー値よりも小さい値を用いる。このとき、アクセス管理部110は、エントリを空きブロックに移すたびに、空きブロックのライトカウンタを1増加させるS59。その後、データ挿入部130は、エントリの移動によりできた空き領域に処理S33で生成されたインデックスエントリを書き込むS35。以降、データ挿入部130及びアクセス管理部110は、上述した処理S36以降の各処理を実行する。一方、データ挿入部130は、オーバーフローすると判定されたインデックスブロックがリーフブロック230である場合にはS40;YES、更に、そのリーフブロック230が拡張されているか否かを確認するS41。具体的には、データ挿入部130は、そのリーフブロック230の拡張ポインタが有効であるか否かを拡張ブロック操作部150に判定させるS41。データ挿入部130は、そのリーフブロック230が拡張されている場合にはS41;YES、更に、そのリーフブロック230が、処理S33で生成されたインデックスエントリを挿入したとしてもオーバーフローしない拡張ブロックを持つか否かを判定するS42。このとき、拡張ブロック操作部150は、そのリーフブロック230の拡張ポインタを参照することにより、リーフブロック230のための拡張ブロックを特定する。データ挿入部130は、そのリーフブロック230がオーバーフローしない拡張ブロックを持つ場合にはS42;YES、その拡張ブロックをインデックスエントリ挿入のための対象ブロックに設定するS43。一方、拡張ブロック操作部150は、そのリーフブロック230が拡張されているがオーバーフローしない拡張ブロックを持たない場合S42;NO、新たな拡張ブロックを取得し、その取得された拡張ブロックをインデックスエントリ挿入のための対象ブロックに設定するS45。このとき、拡張ブロック操作部150は、その取得された拡張ブロックを特定するためのポインタを拡張ポインタとしてそのリーフブロック230又は既に存在する拡張ポインタに設定するS45。拡張ブロック操作部150は、そのリーフブロック230が拡張されていない場合S41;NO、そのリーフブロック230における全アクセスに対するライトアクセスの比率を算出する。拡張ブロック操作部150は、算出されたライトアクセスの比率が所定閾値を超えるか否かを判定するS44。拡張ブロック操作部150は、ライトアクセスの比率が所定閾値を超えない場合S44;NO、データ挿入部130に、そのリーフブロック230に対して上述したようなブロック分割処理を実行させる。これにより、データ挿入部130は、上述した処理S57、S58及びS59を実行する。一方、拡張ブロック操作部150は、ライトアクセスの比率が所定閾値を超える場合S44;YES、新たな拡張ブロックを取得し、その取得された拡張ブロックをインデックスエントリ挿入のための対象ブロックに設定するS45。このとき、拡張ブロック操作部150は、その取得された拡張ブロックを特定するためのポインタを拡張ポインタとしてそのリーフブロック230又は既に存在する拡張ポインタに設定するS45。その後、データ挿入部130は、上述の処理S43又はS45でインデックスエントリ挿入のための対象ブロックに設定された拡張ブロックに、処理S33で生成されたインデックスエントリを書き込むS35。以降、データ挿入部130及びアクセス管理部110は、上述した処理S36以降の各処理を実行する。なお、当該拡張ブロックに新たなインデックスエントリが書き込まれた場合においても、データ挿入部130は、その拡張ブロックに対応するリーフブロック230のライトブロックを更新する。図7は、第1実施形態におけるDBシステム10のデータ削除時の動作例を示すフローチャートである。データ削除部140は、削除する行データを特定するための値を受け取り、データブロック240から行データを削除するS61。行データの削除は、行のデータを消去することで実現してもよいし、その行データに無効を示す値を付加することで実現してもよい。データ削除部140は、削除された行データを特定するインデックスエントリを有するリーフブロック230を特定するS62。このリーフブロック230の特定は、削除された行データにおけるキーが設定された列の値を検索キーとしたインデックス検索によりリーフブロック230を特定する場合と同様の手法で実現される。図4の動作例によれば、S10、S11、S12、S13、S14及びS15の各処理が実行されることにより、当該リーフブロック230が特定される。データ削除部140は、特定されたリーフブロック230における、削除された行データに対応するインデックスエントリを削除するS63。このとき、特定されたリーフブロック230が拡張されている場合には、データ検索時の処理と同様に、リーフブロック230及び拡張ブロック内の全エントリを対象にして、削除対象となるインデックスエントリが特定される。更に、このとき、アクセス管理部110は、そのインデックエントリが削除されたリーフブロック230のライトカウンタを増加させるS64。削除されたインデックスエントリが拡張ブロック内に存在していたとしても、その拡張ブロックに対応するリーフブロック230のライトカウンタが更新される。データ削除部140は、エントリを削除したリーフブロック230又は拡張ブロックがアンダーフローするか否かを判定するS65。データ削除部140は、アンダーフローが起きていなければS65;NO、処理を終了する。拡張ブロック操作部150は、データ削除部140により、アンダーフローすると判定された場合にはS65;YES、削除対象として特定されたリーフブロック230の拡張ポインタに無効値が設定されているか否かを判定するS66。データ削除部140は、拡張ポインタに無効値が設定されている場合にはS66;YES、リーフブロック230に残るエントリを、他のリーフブロック230に移動させ、そのリーフブロック230を空きブロックにするS67。このとき、アクセス管理部110は、エントリを移動させた先のリーフブロック230のライトカウンタを1増加させるS68。なお、移動先ブロックは、一つであってもよいし、複数あってもよく、任意の方法で選択すればよい。また、移動先のリーフブロック230が拡張されている場合には、その移動先のリーフブロック230のための拡張ブロックを移動先ブロックに選択してもよい。この場合においても、拡張ブロックは、リーフブロック230のインデックスエントリを格納する領域の一部として扱われるため、移動されたエントリの格納される領域が実際には拡張ブロック内であったとしても、そのエントリ移動処理は、通常のエントリ移動処理と同様の処理で実現可能である。データ削除部140は、空きブロックとなったリーフブロック230のアクセスカウンタリードカウンタ及びライトカウンタを0に設定する。空きブロックとすることで、このブロックはデータ挿入部130又は拡張ブロック操作部150によって再利用される。また、空きブロック化されたリーフブロック230のアクセスカウンタは、それぞれ移動先のブロックのアクセスカウンタに合算されてもよい。続いて、データ削除部140は、ブロック統合が可能か否か判定するS69。具体的には、データ削除部140は、空きブロック化されたリーフブロック230の親ブロックブランチブロック220にぶら下がる全子ブロックの全エントリをその親ブロックに入れることができるか否かを判定するS69。データ削除部140は、ブロック統合が不可能と判定するとS69;NO、処理を終了する。一方、データ削除部140は、ブロック統合が可能と判定するとS69;YES、それらブロックを統合するS70。つまり、子ブロックの全エントリを親ブロックに移しつつ、親ブロックに存在したエントリは削除する。結果、その親ブロックにぶら下がる全ての子ブロックが空きブロックとされる。このとき、アクセス管理部110は、上位ブロックのライトカウンタを1増加させるS71。なお、統合される子ブロックのアクセスカウンタの値は、親ブロックのアクセスカウンタに合算されてもよい。一方で、削除対象として特定されたリーフブロック230の拡張ポインタに有効値が設定されている場合にはS66;NO、拡張ブロック操作部150が、移動対象のエントリ及び移動先を特定し、データ削除部140が当該移動対象のエントリを当該移動先のブロックに順次移動させるS72。これにより、アンダーフローしているリーフブロック230に関し、拡張ブロック間、又は、拡張ブロックとそのリーフブロック230との間で、エントリの移動が実行される。このとき、拡張ブロック操作部150は、リーフブロック230自体がアンダーフローしている場合には、拡張ブロック内のインデックスエントリを移動対象に決定し、アンダーフローしているリーフブロック230を移動先に決定する。また、拡張ブロック操作部150は、拡張ブロックがアンダーフローしている場合には、その拡張ブロック内のエントリを移動対象に決定し、同一リーフブロック230のための他の拡張ブロックを移動先に決定する。アクセス管理部110は、エントリの移動が行われる度に、対応するリーフブロック230のライトカウンタを増加させるS73。第1実施形態の作用及び効果このように第1実施形態では、各インデックスブロックには、リードカウンタとライトカウンタとがそれぞれ設けられ、データブロック240に対するデータ操作に応じて、検索部120、データ挿入部130及びデータ削除部140によりアクセスされたインデックスブロックのリードカウンタ及びライトカウンタがアクセス管理部110により更新される。このように、第1実施形態によれば、各インデックスブロックへのアクセス回数が、リードアクセスとライトアクセスとで区別されそれぞれ管理される。更に、第1実施形態では、データ挿入部130によりデータ挿入処理が実行される際に、拡張ブロック操作部150により、挿入対象のリーフブロック230における全アクセスに対するライトアクセスの比率が所定閾値を超えるか否かが判定され、ライトアクセスの比率が所定閾値を超える場合に、そのリーフブロック230に拡張ブロックが追加される。この拡張ブロックは、インデックスブロックとは異なり、他のブロック内のインデックスエントリにより特定されず、リーフブロック230の拡張ポインタで特定される。この拡張ブロックは、検索部120、データ挿入部130及びデータ削除部140によるインデックスエントリの操作において、この拡張ブロックを特定するための拡張ポインタが設定されたリーフブロック230のインデックスエントリを格納する領域の一部として扱われる。また、リーフブロック230がアンダーフローする場合には、そのリーフブロック230と拡張ブロックとの間、又は、拡張ブロック間でブロック統合が実施される。このように、第1実施形態によれば、ライトアクセスの比率が大きいリーフブロック230がオーバーフローすると判定された場合には、そのリーフブロック230には、他のブロック内にそれを特定するためのインデックスエントリを設定しなくてもよい拡張ブロックが追加され、リーフブロック230のインデックスエントリを格納するための領域が拡張される。従って、第1実施形態によれば、他のブロックのエントリに影響を与えない拡張ブロックを用いることにより、データ挿入速度を向上させることができる。ところが、拡張ブロックを用いた場合、検索対象となるエントリが増加することになるため、拡張ブロックにより拡張されたリーフブロック230に対する検索速度は低下することになる。そこで、第1実施形態では、ライトアクセスが集中するブロックのみを対象に拡張ブロックを付加することにより、システム全体のパフォーマンスを最適化することができる。なお、上述したright-growingindexは、インデックスブロック間でライトアクセスの比率に差が生じる典型例である。[第2実施形態]以下、第2実施形態におけるDBシステム10について説明する。第2実施形態は、上述の第1実施形態の構成に加えて、上記拡張ブロックを、リードアクセスの比率に応じて、リーフブロック230となるように設定する構成を更に有する。第2実施形態では、DBシステム10の構成は上述の第1実施形態と同様であるが、各処理部の処理が第1実施形態と異なる。以下、第2実施形態におけるDBシステム10について、第1実施形態と異なる内容を中心に説明し、第1実施形態と同一の内容についての説明は適宜省略する。拡張ブロック操作部150は、拡張ブロックを持つリーフブロック230に関し、全アクセスに対するリードアクセスの比率が所定閾値を超えるか否かを判定し、リードアクセスの比率が所定閾値を超える場合に、当該拡張ブロックをリーフブロック230となるように設定する。具体的には、拡張ブロック操作部150は、リードカウンタの値Rを、リードカウンタの値とライトカウンタの値との合計RWで除算することにより当該リードアクセスの比率R/RWを算出する。なお、拡張ブロックをリーフブロック230となるように設定する処理の詳細については、動作例の項において説明する。リードアクセスの比率と比較される所定閾値は、第1実施形態におけるライトアクセスの比率との比較で利用された所定閾値と共に、予め調整可能にメモリ2に格納される。リードアクセスの比率と比較される所定閾値についても、例えば、全インデックスブロックにおけるリードアクセスの全アクセスに対する比率のxパーセンタイルxは例えば10等が用いられる。なお、リードアクセスの比率と比較される所定閾値と、第1実施形態におけるライトアクセスの比率との比較で利用された所定閾値とは1つの値であってもよい。動作例図8は、第2実施形態におけるDBシステム10の動作例を示すフローチャートである。図8では、第1実施形態におけるDBシステム10のデータ検索時と同じ処理については図4と同じ符号が付されている。第2実施形態におけるDBシステム10は、データ検索時において、第1実施形態と同様の処理S10から処理S21を実行する。インデックスエントリに含まれる識別子で特定される行データが検索部120により抽出されるとS21、拡張ブロック操作部150は、特定されたリーフブロック230の拡張ポインタに有効値が設定されているか否か、かつ、リードアクセスの比率が所定閾値を超えているか否かを判定するS81。拡張ブロック操作部150は、特定されたリーフブロック230の拡張ポインタに無効値が設定されている、又は、リードアクセスの全アクセスに対する比率が所定閾値以下である場合にはS81;NO、処理を終了する。一方、拡張ブロック操作部150は、特定されたリーフブロック230の拡張ポインタに有効値が設定されており、かつ、リードアクセスの比率が所定閾値を超えている場合にはS81;YES、そのリーフブロック230が有する拡張ブロックをインデックスブロックとなるように設定するS82。処理S82において、拡張ブロック操作部150は、リーフブロック230内のその拡張ブロックを特定するための拡張ポインタに無効値を設定する。更に、拡張ブロック操作部150は、その拡張ブロックを図3に示される形態に設定する。例えば、拡張ブロック操作部150は、ブロックヘッダを、ブロック種がリーフブロック230を示すように設定し、ブロックヘッダにリードカウンタ及びライトカウンタを設ける。なお、拡張ブロックにも、予め、リーフブロック230と同様のブロックヘッダが設けられていてもよい。この場合には、拡張ブロックのブロックヘッダは、拡張ポインタ以外利用されなければよい。拡張ブロック操作部150は、更に、リーフブロック230及びそのリーフブロック230の拡張に利用される拡張ブロックに格納される全エントリをキー値を用いてソートし、最も小さいキー値を持つエントリから所定数のエントリをリーフブロック230に格納し、それ以降のエントリを拡張ブロックに格納する。上記所定数は、例えば、全エントリの数を、リーフブロック230及び拡張ブロックの数で割った値に設定される。拡張ブロック操作部150は、上述のようなエントリのソートをした後、データ挿入部130に、その拡張ブロックを特定するための識別子を含むインデックスエントリをブランチブロック220に追加するように指示する。これにより、データ挿入部130は、その拡張ブロックを対象にして、ブロック分割により生じた新たなブロックを挿入する処理と同様の処理を実行する。具体的には、データ挿入部130は、図6に示される処理S38以降の処理を実行する。リーフブロック230が複数の拡張ブロックにより拡張されている場合には、上述のような処理S82は、それら全ての拡張ブロックを対象に実行される。また、上述のような拡張ブロックをインデックスブロックとなるように設定する処理S81及びS82は、図8のフローチャートで示される処理の順番に限定されない。例えば、検索部120により処理S21が実行されるのと並行して、処理S81及びS82が実行されてもよい。更に、当該処理S81及びS82は、データ検索処理とは無関係に、任意のタイミング例えば、周期的で、全リーフブロック230を対象に実行されてもよい。第2実施形態における作用及び効果このように第2実施形態では、データ挿入速度を向上させるために追加された拡張ブロックが、リードアクセスの比率が所定閾値を超える場合に、リーフブロック230となるように設定される。即ち、第2実施形態では、ライトアクセスの比率が大きいリーフブロック230には拡張ブロックが付加され、そのリーフブロック230のリードアクセスの比率が大きくなると、その拡張ブロックがリーフブロック230となるように設定される。リーフブロック230及びブランチブロック220には近い値を持つキーが格納されるため、特定の範囲のキーが頻繁に挿入される場合、対応するブロックにはライトアクセスが集中する。一方、特定の範囲のキーが頻繁に検索されれば、対応するブロックにはリードアクセスが集中する。したがって、インデックスを張ることで検索速度を向上させるべきブロックとインデックスを張らずに挿入速度を向上させるべきブロックが存在し得る。第2実施形態によれば、アクセス比率に応じてインデックスを張るブロックとインデックスを張らないブロック拡張ブロックとを決めているため、ライトアクセスが多いブロックとリードアクセスが多いブロックが混在していても、効率的にデータを処理することができる。言い換えれば、キーの値の範囲によってリードとライトのアクセス比率が異なる場合でも、高い処理性能が実現され得る。更に、第2実施形態によれば、アクセス比率の変化に動的に追随できるために、ワークロードが変化しても十分な性能を達成することができる。上述のような第1実施形態及び第2実施形態における作用効果を具体例に基づいて以下に説明する。例えば、データブロック240が売上明細表を格納し、その売上明細表の中の商品番号がキー値に設定され、その売上明細表に対して、売上明細の挿入及び検索集計の各処理が発生する例を想定する。また、この例において、各リーフブロック230に5パーセントから15の比率でライトアクセスがそれぞれ発生し、リーフブロック230を拡張するか否かの判断に用いられる所定閾値が25に設定されていると仮定する。この例において、商品番号1300の商品の特売がされた場合、この特売商品の売り上げが増加すれば、例えば、商品番号1000から商品番号1999までの商品の売り上げを記録しているリーフブロック230へのライトアクセス行の挿入操作が増加する。このとき、定常的なリードアクセスに大きな変化はなく、ライトアクセスの比率が30まで増加した場合、上記リーフブロック230には拡張ブロックが付加される。本実施形態によれば、このような一時的かつ部分的なライトアクセスの増加に対して、自動的に、ライトアクセスに対する処理の高速化とリードアクセスに対する処理の低速化とが実現される。そして、本実施形態によれば、増加したライトアクセスに対する処理が高速化された結果、システム全体としての性能が向上する。逆に、特売が終了することにより、ライトアクセスの比率が下がれば、拡張ブロックは、通常のリーフブロック230となるように設定されるため、インデックスが付与されることにより、リードアクセスに対する処理の高速化が実現される。また、本実施形態は、right-growingindexの問題にも有効である。例えば、データブロック240に格納されるデータ表が現在時刻を示す列を持ち、この現在時刻の列がキーに設定される場合、最も新しい時刻を示す一番右側のリーフブロック230にライトアクセスが集中する。本実施形態では、このリーフブロック230に拡張ブロックが付与されるため、現在時刻を更新するためのライトアクセスに対する処理を高速化することができる。一方で、このリーフブロック230と拡張ブロックとを1回検索するのに発生するリードアクセスの数は、拡張ブロックの増加に伴って増加する。例えば、或るリーフブロック230に9つの拡張ブロックが付加されていたとすると、1回の検索で、10回のリードアクセスが発生する。これに対して、1行を挿入するのに発生するライトアクセスは基本的には1回であるため、ライトアクセスの比率は下がる傾向にある。当該比率が或る程度まで下がると、拡張ブロックはリーフブロック230となるように設定される。その結果、一番右側には新たなリーフブロック230が追加され、より最近の時刻を示すキーが挿入される。一般に、ブロックの挿入は、1つずつよりもまとめた方が効率的に処理できることを注記する。[変形例]上述の第1実施形態では、リーフブロック230を拡張するか否かの判断は、そのリーフブロック230における全アクセスに対するライトアクセスの比率と所定閾値との比較結果に基づいて実施されたが、単に、ライトカウンタがリードカウンタより多い場合に、リーフブロック230を拡張すると判断するようにしてもよい。また、リードカウンタに対するライトカウンタの比率と所定閾値との比較により、リーフブロック230を拡張するか否かの判断が実施されてもよい。また、上述の第2実施形態では、拡張ブロックをリーフブロック230となるように設定するか否かの判断は、そのリーフブロック230における全アクセスに対するリードアクセスの比率と所定閾値との比較結果に基づいて実施されたが、単に、リードカウンタがライトカウンタより多い場合に、拡張ブロックをリーフブロック230となるように設定すると判断するようにしてもよい。また、ライトカウンタに対するリードカウンタの比率と所定閾値との比較により、拡張ブロックをリーフブロック230となるように設定するか否かの判断が実施されてもよい。また、上述の各実施形態では、リーフブロック230及び各拡張ブロックには1つの拡張ポインタがそれぞれ設けられたが、拡張ブロックには拡張ポインタを設けず、リーフブロック230に複数の拡張ポインタを設けるようにしてもよい。また、上述の各実施形態では、アクセスカウンタリードカウンタ及びライトカウンタを含むは1ずつ増やされたが、この増加幅は、アクセス種別等に応じて適宜変えてもよい。なお、上記各実施形態の説明は、複数のフローチャートを用いており、それぞれに複数のステップ処理を順番に記載しているが、本実施形態は、各ステップの順番を図示される順番に限定するものではない。本実施形態では、図示される処理ステップの順番を内容的に支障しない範囲で変更することができる。また、上述した各実施形態及び変形例は、その内容が相反しない範囲で組み合わせることができる。この出願は、2011年2月22日に出願された日本出願特願2011-035437を基礎とする優先権を主張し、その開示の全てをここに取り込む。