(57)【特許請求の範囲】
【請求項１】
格納装置にデータのユニットを格納するコンピュータシステムの方法であって、データの一群をインデックスするトリーデータ構造の一部として第１関連ノード識別子を有する第１のノードエントリーを格納装置に格納し、該第１のノードエントリーは、キー・バリューを格納するキー・バリューフィールドと、サブノードに対する識別情報を格納する識別情報フィールドと、データのユニットを格納する第１のデータ領域とを備え、
前記データのユニットを前記第１のデータ領域に格納する段階と、
前記サブノードに対する識別情報を前記第１のノードエントリーに格納するため、第２のノードエントリーに対する識別子情報を前記識別情報フィールドに格納する段階とを含み、
前記第２のノードエントリーは、(i)データのみを含み、キー・バリュー及びサブノードに対する識別情報を有していないノード、(ii)キー・バリューを格納するキー・バリューフィールドと、サブノードに対する識別情報を格納する識別情報フィールドと、データのユニットを格納するデータ領域とを備えたノード、及び(iii)サブノードに対してアクセスするためのポインタだけを与えるポインタノードを含む複数のノード形式で格納されることを特徴とする方法。
【請求項２】
前記トリーデータ構造に、前記第１のノードエントリーに対する親ノードエントリーを格納し、該親ノードエントリーは、それに対応付けられた第２のノード識別子を有しかつキー・バリューを格納するフィールドと、サブトリーに対する識別子情報を格納するフィールドと、データのユニットを格納するデータ領域とを備え、該データのユニットは、キー・バリューを有し、
前記親ノードエントリーのキー・バリューを格納するための前記フィールドに前記データのユニットの前記キー・バリューを格納し、
前記親ノードエントリーのサブノードに対する識別子情報を格納するためのフィールドに前記第１のノード識別子を格納する段階を更に具備することを特徴とする請求項１に記載の方法。
【請求項３】
格納装置に関連するキー・バリュー及び大きさを有するデータの選択されたユニットを格納するためのコンピュータシステムの方法であって、
複数のノードエントリー群を前記格納装置に格納し、各ノードエントリー群は、一つ以上のノードエントリーを備えかつある量の利用可能な空間を有し、各ノードエントリーは、固有なノード識別子を有しかつキー・バリュー表と、サブノード表と、データのユニットを格納するデータ領域とを備え、
前記データのユニットの前記キー・バリューに基づいて、前記複数のノードエントリー群のいずれに前記選択されたデータのユニットを記憶すべきかを決定し、
前記データのユニットの前記大きさと前記決定されたノードエントリー群の利用可能な空間の量とに基づいて、前記選択されたデータのユニットが前記決定されたノードエントリー群に格納されうるかどうかを決定し、
前記決定されたノードエントリー群の前記利用可能な空間の量が前記データのユニットの大きさよりも小さいときに、前記格納装置に新たなノードエントリー群を生成し、該新しいノードエントリー群は、新しいノード識別子を有する新しいノードエントリーを包含しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、
前記データのユニットを前記新しいデータ領域に格納する段階であって、
(１)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置する場合は、前記選択されたデータユニットを前記決定されたノードエントリーの次或いは前の新たなノードエントリーに格納し、
(２)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置しない場合、(i)前記新たなノードエントリーが前記決定されたノードエントリーの前方に物理的に位置付けられていれば前記決定されたノードエントリーに格納されたキー・バリューのメディアン（中央値）以下のキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、(ii)これに対して、後方に物理的に位置付けられていれば前記メディアンよりも大きなキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、更に、
前記新しいノードエントリーの前記新しいノード識別子を前記決定されたノードエントリーの前記サブノード表に格納する段階を具備することを特徴とする方法。
【請求項４】
前記ノードエントリーのいずれに前記選択されたデータのユニットを記憶すべきかを決定する段階は、前記選択されたデータのユニットの前記キー・バリューを各ノードエントリーに格納されたキー・バリューと比較する段階を含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記決定されたノードエントリーは、ある量の利用可能な空間を有する固定サイズのページ内に包含され、前記選択されたデータのユニットは、ある大きさを有し、前記選択されたデータのユニットが前記決定されたノードエントリーに格納されうるかどうかを決定する段階は、前記選択されたデータのユニットの前記大きさを前記ページの利用可能な空間の前記量と比較することを含む請求項３に記載の方法。
【請求項６】
格納装置に選択されたデータユニットを格納するコンピュータシステムの方法であり、該格納装置は、複数の固定サイズブロックに論理的に分けられ、各ブロックは、ブロックヘッダーと、タグのアレイと、複数のノードエントリーとを備え、各ノードエントリーは、キー・バリュー表と、サブノード表と、データ表とを備えている方法であって、
キー・バリューを前記選択されたデータユニットに割り当て、
前記割り当てられたキー・バリューに基づいて、どのノードエントリーに前記選択されたデータユニットが格納されるべきかを決定し、
前記選択されたデータユニットが前記決定されたノードエントリーを包含する前記ブロックに格納されうるかどうかを決定し、
前記選択されたデータユニットが前記決定されたノードエントリーを包含する前記ブロックに格納されうるときに、前記選択されたデータユニットが前記決定されたノードエントリーに格納されうるかどうかを決定し、
前記選択されたデータユニットが前記決定されたノードエントリーに格納されうるときに、前記選択されたデータユニットを前記決定されたノードエントリーに格納し、
前記選択されたデータユニットが前記決定されたノードエントリーに格納されえないが前記決定されたノードエントリーを包含する前記ブロックに格納されうるときに、
新しいノードエントリーを生成しかつ前記選択されたデータユニットを前記新しいノードエントリーに格納する際に、
(１)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置する場合は、前記選択されたデータユニットを前記決定されたノードエントリーの次或いは前の新たなノードエントリーに格納し、
(２)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置しない場合、(i)前記新たなノードエントリーが前記決定されたノードエントリーの前方に物理的に位置付けられていれば前記決定されたノードエントリーに格納されたキー・バリューのメディアン（中央値）以下のキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、(ii)これに対して、後方に物理的に位置付けられていれば前記メディアンよりも大きなキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、
前記新しいノードエントリーの前記ノード識別子を前記決定されたノードエントリーの前記サブノード表に格納し、
前記選択されたデータユニットの前記キー・バリューを前記決定されたノードエントリーのキー・バリュー表に格納し、
前記選択されたデータユニットが前記決定されたノードエントリーに格納されえずかつ前記決定されたノードエントリーを包含する前記ブロックに格納されえないときに、
新しいブロックの割り当てを要求し、
新しいノードエントリーを生成しかつ前記選択されたデータユニットを前記新しいノードエントリーに格納し、
ポインタノードを前記決定れたノードエントリーを包含する前記ブロックに格納しかつ前記新しいノードエントリーの前記ノード識別子を前記ポインタノードに格納し、
前記ポインタノードの前記ノード識別子を前記決定されたノードエントリーの前記サブノード表に格納し、
前記選択されたデータユニットの前記キー・バリューを前記決定されたノードエントリーの前記キー・バリュー表に格納する段階を具備することを特徴とする方法。
【請求項７】
データのユニットを格納装置に格納するコンピュータシステムであって、
データの一群をインデックスするトリーデータ構造の一部として前記格納装置に第１及び第２のノードエントリーを格納するノード格納機構と、該第１のノードエントリーは、それに対応付けられて第１のノード識別子を有しかつキー・バリューを格納する第１のキー・バリュー表と、サブノードのノード識別子を格納する第１のサブノード表と、データのユニットを格納する第１のデータ領域とを備え、
前記データのユニットを前記第１のデータ領域に格納するデータ格納機構と、
前記サブノードに対する識別情報を前記第１のノードエントリーに格納するため、前記第２のノードエントリーに対する識別子情報を前記識別情報フィールドに格納するサブノード格納機構とを含み、
前記該第２のノードエントリーは、(i)データのみを含み、キー・バリュー及びサブノードに対する識別情報を有していないノード、(ii)キー・バリューを格納するキー・バリューフィールドと、サブノードに対する識別情報を格納する識別情報フィールドと、データのユニットを格納するデータ領域とを備えたノード、及び(iii)サブノードに対してアクセスするためのポインタだけを与えるポインタノードを含む複数のノード形式で格納されることを特徴とするコンピュータシステム。
【請求項８】
前記ノードエントリーは、前記トリーデータ構造に親ノードエントリーを有し、該親ノードエントリーは、それに対応付けられた第２のノード識別子を有しかつキー・バリューを格納する第２のキー・バリュー表と、サブノードのノード識別子を格納する第２のサブノード表と、データのユニットを格納する第２のデータ領域とを備え、該データのユニットは、キー・バリューを有し、
前記データのユニットの前記キー・バリューを前記第２のキー・バリュー表に格納するキー格納機構と、
前記第１のノード識別子を前記第２のサブノード表に格納するサブノード格納機構とを更に備えていることを特徴とする請求項７に記載のコンピュータシステム。
【請求項９】
選択されたデータのユニットを格納装置に格納するコンピュータシステムであり、該選択されたデータのユニットは、関連するキー・バリューとある大きさを有し、該格納装置は、複数のノードエントリー群を格納し、各ノードエントリー群は、一つ以上のノードエントリーを備えかつある量の利用可能な空間を有し、各ノードエントリーは、固有のノード識別子を有しかつキー・バリュー表と、サブノード表と、データのユニットを格納するデータ領域とを備えるコンピュータシステムであって、
前記データのユニットの前記キー・バリューに基づいて、前記複数のノードエントリー群のどれに前記選択されたデータのユニットが格納されるべきかを決定する手段と、
前記データのユニットの前記大きさ及び前記決定されたノードエントリー群の利用可能な空間の量に基づいて、前記選択されたデータのユニットが前記決定されたノードエントリー群に格納されうるかどうかを決定する手段と、
前記決定されたノードエントリー群の利用可能な空間の量が前記データのユニットの前記大きさよりも小さいときに、新しいノードエントリー群を前記格納装置に生成する手段と、該新しいノードエントリー群は、新しいノード識別子を有する新しいノードエントリーを包含しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、
前記データのユニットを前記新しいデータ領域に格納する手段であって、
(１)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置する場合は、前記選択されたデータユニットを前記決定されたノードエントリーの次或いは前の新たなノードエントリーに格納し、
(２)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置しない場合、(i)前記新たなノードエントリーが前記決定されたノードエントリーの前方に物理的に位置付けられていれば前記決定されたノードエントリーに格納されたキー・バリューのメディアン（中央値）以下のキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、(ii)これに対して、後方に物理的に位置付けられていれば前記メディアンよりも大きなキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、更に、
前記新しいノードエントリーの前記新しいノード識別子を前記決定されたノードエントリーの前記サブノード表に格納する手段とを備えていることを特徴とするコンピュータシステム。
【請求項１０】
前記ノードエントリーのどれに前記選択されたデータのユニットが格納されるべきかを決定する手段は、前記選択されたデータのユニットの前記キー・バリューを各ノードエントリーに格納された前記キー・バリューと比較する手段を含むことを特徴とする請求項９に記載のコンピュータシステム。
【請求項１１】
前記決定されたノードエントリーは、利用可能な空間のある量を有している固定サイズのページ内に包含され、前記選択されたデータのユニットは、ある大きさを有し、前記選択されたデータのユニットが前記決定されたノードエントリーに格納されうるかどうかを決定する手段は、前記選択されたデータのユニットの前記大きさを前記ページの利用可能な空間の前記量と比較することを含むことを特徴とする請求項９に記載のコンピュータシステム。
【請求項１２】
選択されたデータユニットを格納装置に格納するコンピュータシステムであり、該格納装置は、複数の固定サイズブロックに論理的に分けられ、各ブロックは、ブロックヘッダーと、タグのアレイと、複数のノードエントリーとを備え、各ノードエントリーは、キー・バリュー表と、サブノード表と、データ表とを備えているコンピュータシステムであって、
キー・バリューを前記選択されたデータユニットに割り当てる手段と、
前記割り当てられたキー・バリューに基づいて、どのノードエントリーに前記選択されたデータユニットが格納されるべきかを決定する手段と、
前記選択されたデータユニットが前記決定されたノードエントリーを包含する前記ブロックに格納されうるかどうかを決定する手段と、
前記選択されたデータユニットが前記決定されたノードエントリーを包含する前記ブロックに格納されうるときに、前記選択されたデータユニットが前記決定されたノードエントリーに格納されうるかどうかを決定する手段と、
前記選択されたデータユニットが前記決定されたノードエントリーに格納されうるときに、前記選択されたデータユニットを前記決定されたノードエントリーに格納する手段と、
前記選択されたデータユニットが前記決定されたノードエントリーに格納されえないが前記決定されたノードエントリーを包含する前記ブロックに格納されうるときに、
新しいノードエントリーを生成しかつ前記選択されたデータユニットを前記新しいノードエントリーに格納する手段であって、
(１)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置する場合は、前記選択されたデータユニットを前記決定されたノードエントリーの次或いは前の新たなノードエントリーに格納し、
(２)前記決定されたノードエントリーが現在のトリーデータ構造の終わり或いは始まりに位置しない場合、(i)前記新たなノードエントリーが前記決定されたノードエントリーの前方に物理的に位置付けられていれば前記決定されたノードエントリーに格納されたキー・バリューのメディアン（中央値）以下のキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、(ii)これに対して、後方に物理的に位置付けられていれば前記メディアンよりも大きなキー・バリューを有するサブノードを前記新たなノードエントリーに移動させ、
前記新しいノードエントリーの前記ノード識別子を前記決定されたノードエントリーの前記サブノード表に格納する手段と、
前記選択されたデータユニットの前記キー・バリューを前記決定されたノードエントリーのキー・バリュー表に格納する手段と、
前記選択されたデータユニットが前記決定されたノードエントリーに格納されえずかつ前記決定されたノードエントリーを包含する前記ブロックに格納されえないときに、
新しいブロックの割り当てを要求する手段と、
新しいノードエントリーを生成しかつ前記選択されたデータユニットを前記新しいノードエントリーに格納する手段と、
ポインタノードを前記決定れたノードエントリーを包含する前記ブロックに格納しかつ前記新しいノードエントリーの前記ノード識別子を前記ポインタノードに格納する手段と、
前記ポインタノードの前記ノード識別子を前記決定されたノードエントリーの前記サブノード表に格納する手段と、
前記選択されたデータユニットの前記キー・バリューを前記決定されたノードエントリーの前記キー・バリュー表に格納する手段とを備えていることを特徴とするコンピュータシステム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、一般にデータを格納しかつアクセスするコンピュータ方法及び格納構造に関し、より特定的には、多次元データを格納しかつアクセスするコンピュータ方法及び格納構造に関する。
【０００２】
【従来の技術】
周知のＢトリーのような、通常の格納構造は、二次記憶装置に記憶された（データベースのデータレコードのような）データの特定ユニットを速く捜し出すために用いられる。Ｂトリーは、データのユニットへのポインタをクラスタする手段を提供して、ユニットを速く捜し出すことができる。ポインタは、典型的に小さくかつ固定の長さを有する。
図１は、データベース・インデックスを格納している通常のＢトリー１００のブロック図である。Ｂトリー１００は、根ノード（root nodes）１０１、内部ノード１０２、１０３、１０４、及び葉ノード（leaf nodes）１０５、１０６、１０７、１０８、１０９、１１０、１１１、１１２、１１３を有する。根ノード１０１は、トリー１００の頂部のノードであり、葉ノード１０５、１０６、１０７、１０８、１０９、１１０、１１１、１１２及び１１３は、トリーの底部のノードであり、内部ノード１０２、１０３及び１０４は、根ノードと葉ノードの間のノードの全部である。
根ノード１０１は、一つ以上のキー・バリュー（key values）及び内部ノード１０２、１０３及び１０４への二つ以上のポインタを包含する。各内部ノード１０２、１０３及び１０４は、一つ以上のキー・バリュー及び下方レベルの内部ノードまたは葉ノード１０５、１０６、１０７、１０８、１０９、１１０、１１１、１１２及び１１３への二つ以上のポインタを包含する。各葉ノード１０５、１０６、１０７、１０８、１０９、１１０、１１１、１１２及び１１３は、キー・バリュー及びキー・バリューによってインデックスされたデータのユニットへのポインタを包含する。例えば、葉ノード１０７は、キー・バリュー“４０”及びキー・バリュー“４０”に対応するデータレコード１１９へのポインタ１１８を包含する。葉ノードの全ては、Ｂトリーにおいて同じ深度である。
【０００３】
ノードは、次の下方レベルでそれらがポイントする子ノードと考えられるノードに対する親ノードと考えられる。葉ノードは、子ノードを有していない。例えば、内部ノード１０２は、根ノード１０１に対する子ノードであり、かつ葉ノード１０５、１０６、１０７に対する親ノードである。
各キー・バリューは、ノードが親ノードであるサブトリーのそのノードに保持される最も高くインデックスされたキー・バリューを示す。一般に、ある非葉ノード（non-leaf node ）ｘに対して、もしノードｘがｎ［ｘ］キー・バリューを包含するならば、ノードｘは、子ノードへのｎ［ｘ］＋１ポインタをも包含する。ノードｘのキー・バリューは、ノードｘによって処理されたキー・バリューのレンジ（range ）をｎ［ｘ］＋１サブレンジ（subranges ）に分けるための分割点（ディバイディング・ポイント）として用いられる。各サブレンジは、ノードｘの一つの子によって処理される。
この命題は、例により説明することができる。図１において、内部ノード１０２は、二つのキー・バリュー（“１２”及び“３２”）及び、葉ノード１０５への一つのポインタ、葉ノード１０６への一つのポインタ及び葉ノード１０７への一つのポインタの三つのポインタを包含する。葉ノード１０５は、“１２”以下の値を有するキー・バリューを包含し、葉ノード１０６は、“１２”よりも大きくかつ“３２”以下の値を有するキー・バリューを包含し、葉ノード１０７は、“３２”よりも大きくかつ“５０”以下の値を有するキー・バリューを包含する。
【０００４】
Ｂトリーは、二次記憶装置に格納されるので、共通（一般）の最適化（common optimization ）は、ページ全体を占有するノードを有することである。データは、一度に一ページ、二次記憶装置から主記憶装置へ一般に転送されるので、ノードのキー・バリューの全てを読取るためにただ一つの二次記憶アクセスが要求される。
ノードがページ全体を占有することを許容されるときには、ノード及びページがいっぱいになるまで、即ちページに利用できる空間がなくなるまで、キー・バリュー及びポインタがノードへ加えられる。いっぱいのノードへキー・バリューを加えるために、ノードは、二つのノードに分割され、付加のページがＢトリーに割り当てられ、そして二つのノードの一つが新しいページに格納される。他のノードは、付加のページに、分割されたノードとしてＢトリーの同じレベルで格納される。キー・バリュー及び新しいノードへのポインタは、分割されたノードの親ノードに付加される。親ノードがいっぱいになったときには、同じ技法を用いて親ノードも分割される。分割は、根ノードまでずっと伝搬されて、根が分割されるといつでもＢトリーに新しいレベルを生成する。
【０００５】
Ｂトリーにおいて特定なキー・バリューを探索することは、各非葉ノードで双方向分岐決定をする（即ち、二つの子ノードのどれを検査すべきかを決定する）代わりに、多方向分岐決定がなされることを除いて、２分木（binary tree ）を探索することに類似する。多方向分岐決定は、ノードの子ノードに依存する。上述したように、ｎ［ｘ］キー・バリューを包含しているノードｘに対して、ノードｘは、ｎ［ｘ］＋１子ノードを有する。従って、各ノードｘで、ｎ［ｘ］＋１方向分岐決定がなされる。
Ｂトリーにおいてどのように探索が実行されるのかを明らかにするために、例を考慮することが有用である。図１のＢトリーがデータベースファイルへのインデックスであり、かつ各ノードのキー・バリューがデータベースファイルのデータレコードにおけるキー・バリュー・フィールドに対応するものと想定する。
“５０”以下のキー・バリュー・フィールド・バリュー（key value field value ）を有するデータレコードを捜し出すために、根ノード１０１から第１のポインタ１１４が追従される。“５０”以上でかつ“８２”以下のキー・バリュー・フィールド・バリューを有するデータレコードを捜し出すために、根ノード１０１から第２のポインタ１１５が追従される。“８２”以上のキー・バリュー・フィールド・バリューを有するデータレコードを捜し出すために、根ノード１０１から第３のポインタ１１６が追従される。（キー・バリュー“４０”に対応している）データレコード１１９を捜し出すために、ポインタは、根ノード１０１からずっとデータレコード１１９まで追従されうる。［根ノード１０１から内部ノード１０２まで第１のポインタ１１４を追従する。次に、内部ノード１０２から葉ノード１０７まで第３のポインタ１１７を追従する。キー・バリュー“４０”が見つかるまで葉ノード１０７におけるキー・バリューを探索する。最後に、葉ノード１０７からデータレコード１１９までポインタ１１８を追従する。］
Ｂトリーの総合的論考及びＢトリー保守アルゴリズムについて、Cormen著、Introduction to Algorithms（The MIT Press 1991）、pp. 381-399 を参照されたい。
【０００６】
階層データモデルは、データのユニットが多次元“親−子”関係で関連付けられたものである。ファイルシステムにおいて、例えば、ファイル及びサブディレクトリは、主ディレクトリから降順する。システムにおける各逐次的下方レベル（each successively lower level ）は、それの上のものから分岐するサブディレクトリである。ファイルシステムは、各ディレクトリまたはサブディレクトリがファイルと他のディレクトリの両方を包含できるので、多重レベルを包含する。階層データモデルにおいて、使用者は、トリーとして論理的に編成されてデータを見る、そしてデータの“ユニット”は、それら自体がトリー或いはサブトリーでありうる。Ｂトリーは、データのフラット（即ち、埋め込み構造（imbedded structure）でない）な同種の収集に対してのみ有用なので、伝統的なＢトリー構造及び保守アルゴリズムは、階層データモデルを格納するのに不適当である。葉ノードがデータの実際のユニットを包含するＢ* トリーでさえも、データのユニットがより小さなユニットへ論理的に可分であると考慮されないので不適当である。
【０００７】
【発明が解決しようとする課題】
上述した従来の技術では、一つのページにあまりにも多くのデータのユニットを格納しようと試みること、或いはユニットがページの利用可能な空間よりも大きいときに、一つのページに単一のデータのユニットを格納しようと試みることのいずれかにより“ページ溢れ”の原因となりうるという問題点があった。
本発明の目的は、上記従来の技術における問題点に鑑み、ページ溢れを処理する水平及び垂直の両方向ページ分割の方法及びその方法を備えたコンピュータシステムを提供する。
【０００８】
【課題を解決するための手段】
本発明の上記目的は、データの一群をインデックスするトリーデータ構造の一部として格納装置に第１の関連するノード識別子を有する第１のノードエントリーを格納し、第１のノードエントリーは、キー・バリューを格納するフィールドと、サブノードに対する識別情報を格納するフィールドと、データのユニットを格納する第１のデータ領域とを備え、データのユニットを第１のデータ領域に格納する段階を具備する、格納装置にデータのユニットを格納するコンピュータシステムの方法によって達成される。
本発明の方法では、トリーデータ構造の一部として格納装置に第２のノードエントリーを格納し、第１のノードエントリーにサブノードに対する識別情報を格納するためにフィールドに第２のノードエントリーに対する識別子情報を格納する段階を更に具備してもよい。
本発明の方法では、トリーデータ構造の一部として格納装置に第２のノードエントリーを格納する段階は、データだけからなりかつトリー構造の一部として格納装置にキー・バリュー及びサブノードに対する識別情報を有していない、第２のノードエントリーを格納する段階を更に具備してもよい。
【０００９】
本発明の方法では、トリーデータ構造の一部として格納装置に第２のノードエントリーを格納する段階は、トリー構造の一部として格納装置に、フィールド格納キー・バリュー、サブノードに対するフィールド格納識別子情報、及びデータのユニットを格納するためのデータ領域を備えている、第２のノードエントリーを格納する段階を更に具備してもよい。
本発明の方法では、格納装置に前記トリー構造のデータのサブトリーを格納する段階を更に備え、そして第２のノードエントリーを格納する手段は、トリー構造の一部として記憶装置に第２のノードエントリーとしてポインタノードを格納する段階を更に具備し、ポインタノードは、データのユニットのサブトリーへのポインタを保持するようにしてもよい。
本発明の方法では、トリーデータ構造に、第１のノードエントリーに対する親ノードエントリーを格納し、親ノードエントリーは、それに対応付けられた第２のノード識別子を有しかつキー・バリューを格納するフィールドと、サブトリーに対する識別子情報を格納するフィールドと、データのユニットを格納するデータ領域とを備え、データのユニットは、キー・バリューを有し、親ノードエントリーのキー・バリューを格納するためのフィールドにデータのユニットのキー・バリューを格納し、親ノードエントリーのサブノードに対する識別子情報を格納するためのフィールドに第１のノード識別子を格納する段階を更に具備してもよい。
【００１０】
本発明の上記目的は、データの一群をインデックスするトリーデータ構造の一部として格納装置に第１の関連するノード識別子を有する第１のノードエントリーを供給し、第１のノードエントリーは、キー・バリューを格納するフィールドと、サブノードに対する識別子情報を格納するフィールドと、データのユニットを格納する第１のデータ領域とを備え、格納装置にデータのユニットを格納するために要求を受け取り、データのユニットが第１のデータ領域に格納されうるかどうかを決定し、データのユニットが第１のデータ領域に格納されえないことが決定されたときに、格納装置に新しいノードエントリーを生成し、新しいノードエントリーは、新しいノード識別子を有しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、データのユニットを新しいデータ領域に格納し、格納装置にポインタノードエントリーを生成し、ポインタノードエントリーは、ポインタノード識別子を有し、新たなノード識別子をポインタノードエントリーに格納し、ポインタノード識別子を第１のサブノード表に格納し、データのユニットが第１のデータ領域に格納されうることが決定されたときに、データのユニットを第１のデータ領域に格納する段階を具備する、格納装置にデータのユニットを格納するコンピュータシステムの方法によっても達成される。
【００１１】
また、本発明の上記目的は、複数のノードエントリー群を格納装置に格納し、各ノードエントリー群は、一つ以上のノードエントリーを備えかつある量の利用可能な空間を有し、各ノードエントリーは、固有なノード識別子を有しかつキー・バリュー表と、サブノード表と、データのユニットを格納するデータ領域とを備え、データのユニットのキー・バリューに基づいて、複数のノードエントリー群のいずれに選択されたデータのユニットを記憶すべきかを決定し、データのユニットの大きさと決定されたノードエントリー群の利用可能な空間の量とに基づいて、選択されたデータのユニットが決定されたノードエントリー群に格納されうるかどうかを決定し、決定されたノードエントリー群の利用可能な空間の量がデータのユニットの大きさよりも小さいときに、格納装置に新しいノードエントリー群を生成し、新しいノードエントリー群は、新しいノード識別子を有する新しいノードエントリーを包含しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、データのユニットを新しいデータ領域に格納し、新しいノードエントリーの新しいノード識別子を決定されたノードエントリーのサブノード表に格納する段階を具備する、格納装置に関連するキー・バリュー及び大きさを有するデータの選択されたユニットを格納するためのコンピュータシステムの方法によっても達成される。
【００１２】
本発明の方法では、ノードエントリーのいずれに選択されたデータのユニットを記憶すべきかを決定する段階は、選択されたデータのユニットのキー・バリューを各ノードエントリーに格納されたキー・バリューと比較する段階を含むようにしてもよい。
本発明の方法では、決定されたノードエントリーは、ある量の利用可能な空間を有する固定サイズのページ内に包含され、選択されたデータのユニットは、ある大きさを有し、選択されたデータのユニットが決定されたノードエントリーに格納されうるかどうかを決定する段階は、選択されたデータのユニットの大きさをページの利用可能な空間の量と比較することを含むようにしてもよい。
更に、本発明の上記目的は、格納装置に選択されたデータユニットを格納するコンピュータシステムの方法であり、格納装置は、複数の固定サイズブロックに論理的に分けられ、各ブロックは、ブロックヘッダーと、タグのアレイと、複数のノードエントリーとを備え、各ノードエントリーは、キー・バリュー表と、サブノード表と、データ表とを備えている方法であって、キー・バリューを選択されたデータユニットに割り当て、割り当てられたキー・バリューに基づいて、どのノードエントリーに選択されたデータユニットが格納されるべきかを決定し、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるかどうかを決定し、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるときに、選択されたデータユニットが決定されたノードエントリーに格納されうるかどうかを決定し、選択されたデータユニットが決定されたノードエントリーに格納されうるときに、選択されたデータユニットを決定されたノードエントリーに格納し、選択されたデータユニットが決定されたノードエントリーに格納されえないが決定されたノードエントリーを包含するブロックに格納されうるときに、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納し、新しいノードエントリーのノード識別子を決定されたノードエントリーのサブノード表に格納し、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納し、選択されたデータユニットが決定されたノードエントリーに格納されえずかつ決定されたノードエントリーを包含するブロックに格納されえないときに、新しいブロックの割り当てを要求し、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納し、ポインタノードを決定れたノードエントリーを包含するブロックに格納しかつ新しいノードエントリーのノード識別子をポインタノードに格納し、ポインタノードのノード識別子を決定されたノードエントリーのサブノード表に格納し、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納する段階を具備するコンピュータシステムの方法によっても達成される。
【００１３】
また、本発明の上記目的は、データのユニットを格納装置に格納するコンピュータシステムであって、一群のデータをインデックスするトリーデータ構造の一部として格納装置にノードエントリーを格納するノード格納機構と、ノードエントリーは、それに対応付けられて第１のノード識別子を有しかつキー・バリューを格納する第１のキー・バリュー表と、サブノードのノード識別子を格納する第１のサブノード表と、データのユニットを格納する第１のデータ領域とを備え、データのユニットを第１のデータ領域に格納するデータ格納機構とを備えているコンピュータシステムによっても達成される。
本発明のコンピュータシステムでは、ノードエントリーは、トリーデータ構造に親ノードエントリーを有し、親ノードエントリーは、それに対応付けられた第２のノード識別子を有しかつキー・バリューを格納する第２のキー・バリュー表と、サブノードのノード識別子を格納する第２のサブノード表と、データのユニットを格納する第２のデータ領域とを備え、データのユニットは、キー・バリューを有し、データのユニットのキー・バリューを第２のキー・バリュー表に格納するキー格納機構と、第１のノード識別子を第２のサブノード表に格納するサブノード格納機構とを更に備えてもよい。
【００１４】
本発明のコンピュータシステムでは、データのユニットが第１のデータ領域に格納されうるかどうかを決定する機構と、データのユニットが第１のデータ領域に格納されうると決定されたときに、新しいノードエントリーを格納装置に生成するノード生成機構と、新しいノードエントリーは、新しいノード識別子を有しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域と備え、データのユニットを新しいデータ領域に格納する第２のデータ格納機構と、ポインタノードエントリーを格納装置に生成するポインタノード生成機構と、ポインタノードエントリーは、ポインタノード識別子を有し、新しいノード識別子をポインタノードエントリーに格納する第２のノード格納機構と、ポインタノード識別子を第１のサブノード表に格納すうポインタノード格納機構と、データのユニットが第１のデータ領域に格納されうると決定されたときに、データのユニットを第１のデータ領域に格納する第３のデータ格納機構とを更に備えてもよい。
本発明の上記目的は、選択されたデータのユニットを格納装置に格納するコンピュータシステムであり、選択されたデータのユニットは、関連するキー・バリューとある大きさを有し、格納装置は、複数のノードエントリー群（ページ）を格納し、各ノードエントリー群（ページ）は、一つ以上のノードエントリーを備えかつある量の利用可能な空間を有し、各ノードエントリーは、固有のノード識別子を有しかつキー・バリュー表と、サブノード表と、データのユニットを格納するデータ領域とを備えるコンピュータシステムであって、データのユニットのキー・バリューに基づいて、複数のノードエントリー群（ページ）のどれに選択されたデータのユニットが格納されるべきかを決定する手段と、データのユニットの大きさ及び決定されたノードエントリー群（ページ）の利用可能な空間の量に基づいて、選択されたデータのユニットが決定されたノードエントリー群（ページ）に格納されうるかどうかを決定する手段と、決定されたノードエントリー群の利用可能な空間の量がデータのユニットの大きさよりも小さいときに、新しいノードエントリー群（ページ）を格納装置に生成する手段と、新しいノードエントリー群（ページ）は、新しいノード識別子を有する新しいノードエントリーを包含しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、データのユニットを新しいデータ領域に格納する手段と、新しいノードエントリーの新しいノード識別子を決定されたノードエントリーのサブノード表に格納する手段とを備えているコンピュータシステムによっても達成される。
【００１５】
本発明のコンピュータシステムでは、ノードエントリーのどれに選択されたデータのユニットが格納されるべきかを決定する手段は、選択されたデータのユニットのキー・バリューを各ノードエントリーに格納されたキー・バリューと比較する手段を含むように構成してもよい。
本発明のコンピュータシステムでは、決定されたノードエントリーは、利用可能な空間のある量を有している固定サイズのページ内に包含され、選択されたデータのユニットは、ある大きさを有し、選択されたデータのユニットが決定されたノードエントリーに格納されうるかどうかを決定する手段は、選択されたデータのユニットの大きさをページの利用可能な空間の量と比較することを含むように構成してもよい。
更に、本発明の上記目的は、選択されたデータユニットを格納装置に格納するコンピュータシステムであり、格納装置は、複数の固定サイズブロックに論理的に分けられ、各ブロックは、ブロックヘッダーと、タグのアレイと、複数のノードエントリーとを備え、各ノードエントリーは、キー・バリュー表と、サブノード表と、データ表とを備えているコンピュータシステムであって、キー・バリューを選択されたデータユニットに割り当てる手段と、割り当てられたキー・バリューに基づいて、どのノードエントリーに選択されたデータユニットが格納されるべきかを決定する手段と、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるかどうかを決定する手段と、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるときに、選択されたデータユニットが決定されたノードエントリーに格納されうるかどうかを決定する手段と、選択されたデータユニットが決定されたノードエントリーに格納されうるときに、選択されたデータユニットを決定されたノードエントリーに格納する手段と、選択されたデータユニットが決定されたノードエントリーに格納されえないが決定されたノードエントリーを包含するブロックに格納されうるときに、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納する手段と、新しいノードエントリーのノード識別子を決定されたノードエントリーのサブノード表に格納する手段と、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納する手段と、選択されたデータユニットが決定されたノードエントリーに格納されえずかつ決定されたノードエントリーを包含するブロックに格納されえないときに、新しいブロックの割り当てを要求する手段と、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納する手段と、ポインタノードを決定れたノードエントリーを包含するブロックに格納しかつ新しいノードエントリーのノード識別子をポインタノードに格納する手段と、ポインタノードのノード識別子を決定されたノードエントリーのサブノード表に格納する手段と、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納する手段とを備えているコンピュータシステムによっても達成される。
【００１６】
【作用】
本発明は、二次記憶装置に多次元データを格納しかつアクセスするコンピュータ方法及び格納構造を提供する。多次元データは、それがデータのサブユニットに論理的に分けられることを許容する隠れ構造（埋め込み構造）を有する。本発明により提供されるトリー・マネージャは、ポインタ、可変長データレコード、他のＢトリー、及びディレクトリのようなデータを多次元Ｂトリー（ＭＤＢトリー）に格納する。ＭＤＢトリーの各ノードは、ゼロまたはそれ以上のキー・バリュー、サブノード・テーブル、及びデータを包含することが可能な、バイドの物理的に隣接のストリングである。
二次記憶装置は、固定サイズのブロックまたはページにしばしば論理的に分けられるので、ＭＤＢトリーのデータのユニットは、ページサイズ・サブトリーに物理的に分けられる。トリー・マネージャは、一つのページにあまりにも多くのデータのユニットを格納しようと試みること、或いはユニットがページの利用可能な空間よりも大きいときに、一つのページに単一のデータのユニットを格納しようと試みることのいずれかにより“ページ溢れ”の原因となりうる。本発明の方法は、ページ溢れを処理する水平及び垂直の両方向ページ分割を提供する。
【００１７】
トリー・マネージャが一つのページにあまりにも多くのデータのユニットを格納しようと試みるときには、トリー・マネージャは、通常のＢトリーノード分割スキームである、ページを水平方向に分割しなければならない。単一ページの水平分割は、別のレベルがＭＤＢトリーへ付加されるようにすることができ、それによってトリーの探索をスローダウンする。
トリー・マネージャが一つのページにデータのユニットを格納しようと試みかつデータのユニットがページの利用可能な空間よりも大きいときには、トリー・マネージャは、データのユニットを選択し、かつデータのユニットを垂直方向に分割する。垂直方向に分割されるデータのユニットは、その挿入が溢れの原因となったデータのユニットであることを必要としない。トリー・マネージャは、分割するのに最適であると考えられるデータのユニットを選択する。垂直方向の分割は、データのユニットがサブトリーに分けられうるということを想定する。
データのユニットを垂直方向に分割するために、トリー・マネージャは、新しいページの割り当てを最初に要求し、次に、第１ノードとしてトップ・オブ・ページ（ＴＯＰ）ノードを生成しかつ新しいページに格納する。新しいページは、継子ページと称される。次に、トリー・マネージャは、データのユニットを第１及び第２のサブトリーに分け、かつ第２のサブトリーを新しいページに移す。第２のサブトリーは、ＴＯＰノードに対する子ノードになる。トリー・マネージャは、第２のサブトリーが格納されていた、継子ページへのポインタだけを包含する、ポインタノードを格納する。トリー・マネージャは、次に、ポインタノードへのポインタを分割ノードのサブノード・テーブルに配置する。
【００１８】
継子ページの生成は、データの分割ユニットに別のレベルを付加するが、しかしＭＤＢトリーのデータの別のユニットに別のレベルを付加しない。従って、データのユニットを垂直方向に分割することは、ＭＤＢトリーの探索をスローダウンしない。従って、ＭＤＢトリーを走査するときには、トリー・マネージャは、もしサブトリーの最高のノードが必要なキー・バリューを有しないならば、複数のページにまたがっているサブトリーを効果的に無視する。ポインタノード及びＴＯＰノードは、トリー・マネージャを除き、全てに対して見えない。
【００１９】
【実施例】
本発明の好ましい実施例において、多次元Ｂトリー（ＭＤＢトリー）として知られているトリーデータ構造は、データベースような、データの量に対するインデックスとして役立つ。ＭＤＢトリーは、それらがデータを保持しうるように全てが構築される、ノードで形成される。それゆえに、ＭＤＢトリーの葉ノード及び非葉ノードの両方とも、データを保持しうる。ＭＤＢトリーに保持されうるデータの形式は、階層データを含む。階層データに伴う一つの問題点（difficulty）は、階層データが一般的にノードに格納するにはあまりにも大きすぎることである；その結果、ＭＤＢトリーにおいて、階層データは、別個のサブトリー（separate subtree）として格納される。ＭＤＢトリーの対応するノードは、サブトリーをアクセスするためのポインタを保持する。ＭＤＢトリーのノードは、ノードに保持されたキー・バリューの探索を実行することによって捜し出される。サブトリーのノードは、しかしながら、サブトリーに対するキー・バリューを有するノードを捜し出すための探索をまず実行し、次に所望のノードを捜し出すためのサブトリーのノードの第２の探索を実行することによって見出される。そのようにして、サブトリーは、トリーを多次元にするトリーに、追加の次元を供給することがわかる。
【００２０】
図２は、本発明の好ましい実施例を実施するためのコンピュータシステム２０の好ましい実施例のブロック図である。コンピュータシステム２０は、中央処理装置（ＣＰＵ）２１、ランダムアクセスメモリ装置（ＲＡＭ）２２、二次記憶装置２３、出力装置２４、及び入力装置２５を備えている。二次記憶装置２３は、ある種のディスクシステムであることが好ましい。
上述したように、ＭＤＢトリーは、ノードで構成されている。図３は、ノード２９のフォーマットを示す図である。ノード２９は、キー・バリュー表２６、サブノード表２７、及びデータ領域２８を含む。キー・バリュー表は、キー・バリュー、即ちキー・バリューＫ１及びＫ２を保持する。これらのキー・バリューは、ＭＤＢトリーを探索するのに用いられる探索キーとして作用する。サブノード表２７は、サブノードへのポインタ、即ちポインタ１、ポインタ２、及びポインタ３を格納する。サブノードは、他のノード或いはポインタノード（詳細は後述する）でありうる。データ領域２８は、ノードにデータを直接的に取り入れる（組み込む：incorporate ）ことが望ましいデータを保持する。
キー・バリュー表２６のキー・バリュー及びサブノード表２７のポインタによってサーブ（提供）された役割（役務）は、ＭＤＢトリーの小さな部分を調査することによってたぶん最もよく表される。図４は、親ノード３０、第１の子ノード３４、及び第２の子ノード３５を含むＭＤＢトリーの部分のブロック図である。親ノード３０は、そのキー・バリュー表にキー・バリュー“Ｋ１”を保持する。親ノード３０は、（“Ｋ１”以下のキー・バリューに対応付けられたデータを保持する）第１の子ノード３４にポイントするそのサブノード表のポインタ３１及び、（“Ｋ１”より大きいキー・バリューに対応付けられたデータを保持する）第２の子ノード３５にポイントするポインタ３３をも保持する。
【００２１】
図４の説明において、親ノード３０のサブノード表のポインタは、子ノードにだけポイントする。サブノード表のポインタがポインタノードにもポイントしうるということは、評価されるべきである。ポインタノードは、階層データを保持するサブノードへのアクセスを供給する。
図５は、図４の第１の子ノード３４がそのサブノード表のポインタノード３８へのポインタを含むときを説明する図である。ポインタノード３８は、次に、サブトリー３７にポイントする。サブトリー３７は、トップ・オブ・ページ（ＴＯＰ）ノード３９、第１のサブノード４０、及び第２のサブノード４１を含む。ＴＯＰノードは、ノード識別子（即ち、ポインタ）だけを保持する特種なノードである。ＴＯＰノードは、キー・バリュー或いは他のデータを含まない。ポインタノード３８に対するノード識別子は、親ノード３０のサブノード表にポインタとして格納される。ＴＯＰノード３９に対するノード識別子は、ポインタノード３８にポインタとして格納される。加えて、第１のサブノード４０及び第２のサブノード４１に対するノード識別子は、ＴＯＰノード３９に格納される。ポインタノード３８によって供給されるインダイレクション（indirection ）の追加のレベルは、あたかもそれが第１の子ノード３４の“内部（within）”に格納されるようにサブトリー３７を論理的に現すことを許容する。ポインタノード３８及びＴＯＰノード３９の詳細は、後述する。
【００２２】
図４及び５は、それぞれ子ノード及びポインタノードにもっぱらポイントしているポインタを示しているけれども、ノードのサブノード表は、サブノードの多重形式に対するポインタを同時に保持しうるということは、評価されるべきである。それゆえに、ノードのサブノード表は、子ノードへのポインタ及びポインタノードへのポインタを同時に含みうる。
図６は、ＭＤＢトリー４６を説明するブロック図である。根ノード４８は、三つの子サブノード５０、５２、及び５４を有する。次に、サブノード５０は、三つのサブノード５６、５８、及び６０を有する。サブノード５６及び５８は、それらが子ノードを有しないので葉ノードとして知られる。葉ノードは、キー・バリュー或いはサブノードへのポインタを包含しない。サブノード６０は、サブノード７６、７８、８０、及び８２を含むサブトリー７４へのポインタを包含するポインタノードである。根ノード４８のサブノード５２は、複数のサブノード６２、６４、６６をも含む。サブノード６２、６４及び６６は、全て葉ノードである。根ノード４８のサブノード５４は、同様に複数のサブノード６８、７０及び７２を有する。サブノード６８及び７２は、葉ノードであり、サブノード７０は、サブトリー８４にポイントするポインタノードである。サブトリー８４は、ＴＯＰノード８６及び葉ノード８８を含む。
【００２３】
どのように図６に示されるようなＭＤＢトリーがデータをインデックスするのに用いられうるかを説明するために一つの例が有用であろう。以下に示す表Ａは、ＭＤＢトリーに格納されるべくよく適合した実例のデータファイルを包含する。データファイルのデータのユニットは、各ユニットに包含される詳細の種々なレベルにより、種々の長さを有する。階層データを表わすデータのユニットは、ビジネス電話帳（business telephone directory）（即ち、電子ビジネス電話帳（electronic business telephone directory ）））に一般的に見出される。電話帳は、通常、三つ以上の主題ヘッディング（subject headings）を包含するけれども、説明の簡単化のために、データファイルは、三つの主題ヘッディング（Ｉ、II、III ）だけで示されている。
データのユニットは、主題ヘッディング（“AUTOMOTIVE PARTS（自動車部品）”、“MOVING COMPANIES（引っ越し会社）”、及び“WASHERS & DRYERS（洗濯機及び乾燥機）”）によってアルファベット順に示されている。この形式の情報の典型であるように、データのユニットのあるものは、サブユニットに論理的に分けられうる。例えば、引っ越し会社（moving company）“U-HAUL-IT COMPANY ”の異なる店の位置（store locations ）は、１０のサブユニットに論理的に分かれている。サブユニットは、店の番号順である。
【００２４】
【表１】
0003844370.tif 000002
0003844370.tif 000003
ＭＤＢトリーは、表Ａに示されたデータが二次記憶装置２３に効率的に編成されかつ格納されるようにする（図２）。  通常のＢトリーは、キー・バリュー及びデータへのポインタだけを格納するので、通常のＢトリーは、表Ａに示されたデータを収容できない。
【００２５】
葉ノードにデータのユニットを格納する、Ｂ* トリーでさえも、Ｂ* トリーがその葉ノードに小さな、データの最小単位だけを格納するので、表Ａに示されたデータを収容することができない。ＭＤＢトリーは、データを格納できるので、データのユニットは、サブトリーを包含しえ、かつサブトリーのサブノードは、別のサブトリーを包含しうる、等。ＭＤＢトリーは、サブユニットへのデータの論理的な分割を考慮して、それによりデータの大きなユニットがその中に格納されることを許容する。
表Ａのデータを保持する例示のＭＤＢトリーの説明を続ける前に、ＭＤＢトリーに対するページフォーマットを最初に説明することが必要である。図７は、本発明の好ましい実施例のＭＤＢトリーのページ８８に対する格納フォーマットのブロック図である。ページは、格納空間の隣接のブロックであり、一般的に４ＫＢの大きさを有する。ＭＤＢトリーは、二次記憶装置２３に書き込まれかつページユニットで二次記憶装置２３から読み取られる。空間最適化のために、ＭＤＢトリーの各ノードは、長さにおいて一ページであることが好ましい。
ページ８８は、ページ識別子９２及びタグ９４のアレイを包含する、ヘッダー（見出し）領域９０を包含する。ヘッダー領域９０は、ページ８８に残された自由空間の量を特定するインディケータ（標識）をも包含しうる。ページ８８の残った部分は、トップ・オブ・ザ・ページ（ＴＯＰ）ノード・エントリー９６、複数のノード・エントリー９６、９８、１００、及び１０４、そして自由空間領域１０６を包含する。自由空間領域１０６は、現在割り当てられていない格納空間である。タグ９４のアレイは、ページ８８に格納された各ノードエントリーの開始を識別するオフセットを包含する。各ノードエントリー９６、９８、１００、及び１０４は、他のノードエントリーと同じ大きさである必要はない。ＴＯＰノードエントリー９６は、ＴＡＢ［０］（即ち、タグ９４のアレイにおける最初のタグ）によって常に識別されることが好ましい。タグ９４のアレイがページ８８のノードエントリー９６、９８、１００、及び１０４の位置の跡をつけるので、ノードエントリーへの外部参照は、ページ数とタグ数だけの跡をつけなければならない。二次記憶装置にデータのユニットを格納するときに、本願発明によって供給されたトリー・マネージャは、一つのページにあまりにも多くのデータのユニットを格納しようと試みることによって、或いはユニットがページの利用可能な空間よりも大きいときにページにデータのユニットを格納しようと試みることによるいずれかで“ページ溢れ”の原因となりうる。本願発明の方法は、ページ溢れを処理する、水平及び垂直の、双方向ページ分割を提供する。水平分割は、通常のＢトリーアルゴリズムによって用いられる分割の形式である。水平及び垂直ページ分割は、図１２〜８Ｃを参照して、以下に詳細に説明する。
【００２６】
図８は、ＭＤＢトリー１０８に編成されたときの表Ａの上部に示されたデータのブロック図である。第１のページ１１０は、ノード１１２、１１４、１１６、１１８、１２０、１２２、１２４及び１２６を包含する。ページ１１０は、ＴＯＰノード１２８及びポインタノード１３０、１３２を更に含む。ＭＤＢトリー１０８の第２のページ１３４は、ＴＯＰノード１３６とノード１３８を包含する。ＭＤＢトリー１０８の第３のページは、ノード１４２、１４４、及び１４６とＴＯＰノード１４８を包含する。
根ノード１１２は、そのキー・バリュー表にキー・バリュー“Ｂ”及び“Ｐ”を、そしてそのサブノード表に子ノード１１４、１１６、及び１１８に対するノード識別子を包含する。通常のＢトリーにおけるように、ノード１１２に格納されたキー・バリューは、ＭＤＢトリー１０８を探索するときに次の下方レベルへのどの経路を追従すべきかを決定する基礎を供給する。それゆえに、探索されているキー・バリューが“Ｂ”以下であるときには、子ノード１１４にポイントする、ポインタ１１３が追従される。探索されているキー・バリューが“Ｂ”よりも大きいが“Ｐ”以下であるときには、子ノード１１６にポイントするポインタ１１５が追従される。最後に、探索されているキー・バリューが“Ｐ”よりも大きいときには、子ノード１１８にポイントするポインタ１１７が追従される。ノード１１２は、そのデータ領域にいかなるデータをも含まない。より実用的な電話帳は、更に多くのキー・バリューを包含することに注目すべきである。
【００２７】
ノード１１４は、“AUTOMOTIVE PARTS”の主題ヘッディング（主題見出し）の下にエントリーをインデックスする、二次キー・バリュー“Ｇ”を包含する。ノード１１４のサブノード表は、サブノード１２０と１２２に対するノード識別子（即ち、ポインタ１１９と１２１）を包含する。サブノード１２０は、いかなるキー・バリューもノード識別子も包含していない。サブノード１２０は、店名（the name of the store ）、店のアドレス（address of the store）、店の電話番号（telephone number of the store ）、及び部品一覧表（parts list）を含む、“AL'S PARTS STORE”に対するデータを包含する。
サブノード１２２は、サブノード１２０のように、キー・バリューを包含しないが、しかしポインタノード１３０に対するノード識別子１３３を包含する。ポインタノード１３０は、ノード１２２以外のページに格納されるサブトリー１３４に対するノード識別子１３１を包含する。サブトリー１３４は、ＴＯＰノード１３６及びサブノード１３８からなる。ＴＯＰノード１３６は、サブノード１２２と同じページに格納されるにはあまりにも大きいデータを包含する、サブノード１３８に対するノード識別子１３７を包含する。サブノード１３８のデータ領域に格納されたデータは、絵（picture ）のビットマップ及び部品一覧表を含む。サブノード１３８は、そのキー・バリュー表にキー・バリューを包含せず、かつそのサブノード表にノード識別子を包含しない。
【００２８】
子ノード１１６は、主題ヘッディング“MOVING COMPANIES”の下にエントリーをインデックスする、二次キー・バリュー“Ｐ”を包含する。子ノード１１６のサブノード表は、二つのノード識別子１２５と１２７を包含する。ノード識別子１２５は、サブノード１２４にポイントし、かつ“Ｐ”以下の二次キー・バリューを捜しているときに追従される。ノード識別子１２７は、サブノード１２６にポイントし、かつ“Ｐ”よりも大きい二次キー・バリューを捜しているときに追従される。
サブノード１２４は、キー・バリュー或いはノード識別子を含まない葉ノードである。ノード１２４のデータ領域は、しかしながら、“JOE'S MOVERS, INC.”に対するデータを保持する。
サブノード１２６もキー・バリューを含まない。ノード１２６は、他方、ポインタノード１３２にポイントするノード識別子１３３を含む。ポインタノード１３２は、サブトリー１４０にポイントする。サブトリー１４０は、ＴＯＰノード１４８、及び三つのサブノード１４２、１４４、及び１４６からなる。ＴＯＰノード１４８は、サブノード１４４及び１４６に包含されたデータをインデックスする、サブノード１４２にポイントするノード識別子１４１を包含する。サブノード１４４及び１４６のデータ領域は、“U-HAUL-IT-COMPANY ”に関するデータを包含する。
【００２９】
サブノード１４２は、二次キー・バリュー“５”を包含する。サブノード１４２は、更に、それぞれサブノード１４４及び１４６にポイントする、ノード識別子１４３及び１４５を含む。ノード識別子１４３は、“５”以下の格納番号二次キー・バリューに対して追従される。ノード１４４は、そのデータ領域の格納“１”から“５”までに対するデータを保持するサブトリー１４０の葉ノードである。サブノード１４４は、キー・バリュー或いはノード識別子を含まない。サブノード１４６もサブトリー１４０の葉ノードであるが、しかしそのデータ領域の格納“６”から“１０”までに対するデータを保持する。サブノード１４４のように、サブノード１４６は、キー・バリュー或いはノード識別子を含まない。サブノード１４４及び１４６は、サブノード１４２の子ノードである。
子ノード１１８は、ＭＤＢトリー１０８の葉ノードである。子ノード１１８は、キー・バリュー或いはノード識別子を含まない。ノード１１８のデータ領域は、主題ヘッディング“WASHERS & DRYERS”及び相互参照“SEE APPLIANCES”を識別する。
サブトリー１４０がどのように実際に二次記憶装置に格納されるかを理解することは、有用である。しかし、まず初めに、サブトリー１４６に包含されるデータのユニットの構造を調べることは、重要である。図９は、データのユニット１５０のブロック図であり、図１０は、それがサブユニット１５２、１５４、及び１５６に区分された後のデータのユニット１５０のブロック図である。
【００３０】
図１１は、図７の格納フォーマットに基づき二次記憶装置に格納されたサブトリー１４０のブロック図である。サブトリー１４０は、四つのノードエントリー１４８、１４２、１４４、及び１４６からなる。ＴＯＰノード１４８は、サブノード１４２へのポインタ１４１を包含する。ＴＯＰ１４０は、キー・バリュー或いはデータを包含しない。サブノード１４２は、そのキー・バリュー表に“５”を包含し、そのサブノード表にポインタ１４３及び１４５を包含する。ポインタ１４３は、サブノード１４４にポイントし、ポインタ１４５は、サブノード１４６にポインタする。サブノード１４４は、キー・バリュー或いはサブノードへのポインタを包含しないが、データのサブユニット１５２（図１０）を包含する。同様に、サブノード１４６は、キー・バリュー或いはサブノードへのポインタを包含しないが、データのサブユニット１５４（図１０）を包含する。
ここで図８を参照すると、ＭＤＢトリー１０８は、適当なキー・バリューが見出されたときに依存してキー・バリューを調べかつポインタを追従する通常のＢトリー走査ルーチンを用いて走査される。ポインタノード１３０及び１３２そしてＴＯＰノード１３６及び１４８は、ルーチンがノード１２２、１２６の“内部を見る（捜す）”ことがないかぎり、ＭＤＢトリー１０８を保守するルーチンに対して見えない。
【００３１】
ＭＤＢトリー１０８にデータのユニットを挿入するために、本発明の好ましい実施例は、挿入ルーチンを提供する。挿入ルーチンは、図１２〜８Ｃを参照して以下に詳細に説明する。しかしながら、挿入ルーチンの詳細を述べる前に、挿入ルーチン及び水平・垂直分割の概要を最初に述べることは、有用である。
ＭＤＢトリー１０８のどこ（即ち、どのページ）にデータのユニットが属するのかを決定した後に、トリー・マネージャは、ページにデータのユニットを格納することを試みる。もしユニットがページの利用可能な空間よりも大きいならば、好ましい実施例は、ページに現在格納されたデータのユニット、挿入されているデータのユニット、或いはページ自体のいずれかを分割することを試みる。データのユニットを分割することは、垂直分割と呼ばれ、ページを分割することは、水平分割と呼ばれる。
一般的に、垂直分割は、分割されるデータのユニットがサブノードに区分されうることを想定する。サブノードの一つは、ページに格納され、そして他のサブノードは、新しいページにサブトリーとして格納される。（サブトリーは、一つのサブノードだけで表されうる。）次に、新しいページへのポインタは、サブノードのサブノード表にノードエントリーとしてリストされた、ポインタノードに格納される。ポインタノード及び新しいページの生成は、ＭＤＢトリー全体に別のレベルを付加しない。それよりも、分割されたデータのユニットだけが追加のレベルを得る。
【００３２】
データのユニットが分割されるサブユニットの数の決定は、ページで利用可能な自由空間の数及びデータのユニットの構造に依存する。データのユニット１５０（図９）は、あらゆる数のサブユニットに分割されうる。
本発明の好ましい実施例がページにあまりにも多くのデータのユニットを格納することを試みるときには、もしデータのユニットが垂直方向に分割されえないならば、ページは水平方向に分割されうる。一般的に、ページを水平方向に分割するために、トリー・マネージャは、ページのノードエントリーのサブセットを新しい隣接ページに移動し、かつ新しいキー・バリュー及び新しいページへのポインタを、分割されるページの親ページに格納する。通常のＢトリーにおけるように、古いページと新しい隣接ページは、ページヘッダー（page headers）の次ページ及び前ページ・リンクフィールド（next page and previous page link fields ）によってリンクされる。次ページ及び前ページ・リンクフィールドは、トリーの上部レベルページを巡回することを必要とせずにトリー走査を容易にする。
ＭＤＢトリーの構造の上記説明を与えて、どのようにトリーが保守されるかを調べることは、有用である。本発明の好ましい実施例において、ＭＤＢトリーは、ファイルシステムの一部であるトリー・マネージャによって保守される。図１２は、ＭＤＢトリーに新しいデータのユニットを格納することにおけるトリー・マネージャによって実行されるステップスのフロー図である。ステップ１６０では、トリー・マネージャは、新しいデータのユニットが格納されるべきページを選択する。この選択は、適当なページを見出すためにＭＤＢトリーの探索を要求する。ステップ１６２では、現行ページ変数を選択されたページに設定する。現行ページ変数は、値を保持するのに適用なあらゆるデータ構造である。ステップ１６４では、トリー・マネージャは、ＭＤＢトリーに挿入されるべき新しいデータのユニットが、現行ページ変数によって指定されたように現行ページに適合するかどうかを決定する。即ち、トリー・マネージャは、データのユニットの大きさが現行ページの利用可能な空間の大きさよりも小さいかどうかを決定する。もしデータのユニットが現行ページに適合するならば、ステップ１６６では、トリー・マネージャが現行ページにデータのユニットを格納し、そして挿入されたユニットの親ノードを更新する。親ノードの更新は、挿入されたユニットへのポインタを親ノードのサブノード表に格納することを含む。
【００３３】
もしデータのユニットが現行ページに適合しないならば（ステップ１６４）、ステップ１６８では、トリー・マネージャが現行ページの全てのサブトリーの重みを決定する。サブトリーの“重み”は、サブトリーの全てのサブノードの大きさである。もし１ＫＢよりも大きな重みを有するサブトリーが存在するならば（ステップ１７０）、例えば、トリー・マネージャは、そのサブトリーを垂直方向に分割する。垂直分割は、図１３を参照してより詳細に説明する。もし１ＫＢよりも大きな重みを有するサブトリーが存在しないならば（ステップ１７０）、トリー・マネージャは、現行ページを水平方向に分割する。水平分割は、図１４を参照してより詳細に説明する。
図１３は、ノード（図１２及び図１３の“Ｂ”を参照）を垂直方向に分割するためにトリー・マネージャによって実行されるステップのフロー図である。ノードの垂直分割は、ノードのサブトリーを新しいページに移動させる。ステップ１７２では、トリー・マネージャは、１ＫＢよりも大きい重みを有するサブトリーを選択する（ステップ１７０参照）。ステップ１７４では、トリー・マネージャは、ポインタノードを生成し、かつ現行ページにポインタノードを格納する。ステップ１７６では、トリー・マネージャは、選択されたサブトリーの親ノードのサブノード表にポインタノードのノード識別子を格納する。ステップ１７８では、トリー・マネージャは、ファイルシステムによって供給されたメモリマネージメントルーチンから新しいページの割り当てを要求し、新しいページにＴＯＰノードを格納する。ステップ１８０では、トリー・マネージャは、選択されたサブトリーを新しいページに格納し（ＴＯＰノードのサブトリーとして）、かつサブトリーへのポインタをＴＯＰノードのサブノード表に格納する。ステップ１８２では、トリー・マネージャは、ＴＯＰノードへのポインタをポインタノードに格納する。垂直分割の後、ステップ１８４では、トリー・マネージャは、データのユニットが現行ページに適合するかどうかを再び決定する（図１２の“Ｃ”を参照）。もしデータのユニットが現行ページにまだ適合しないならば、トリー・マネージャは、現行ページを水平方向に分割する。もしデータのユニットが現行ページに適合するならば、ステップ１８６では、トリー・マネージャは、データのユニットを現行ページに格納し、かつデータのユニットへのポインタを挿入されたユニットの親ノードのサブノード表に格納する。
【００３４】
図１４は、ページを水平方向に分割すべくトリー・マネージャによって用いられるステップのフロー図である。ステップ１８８では、トリー・マネージャは、ファイルシステムによって供給されたメモリマネージメントルーチンから新しいページの割り当てを要求する。トリーの終わり（または始まり）に新しいノードを挿入するときに、水平分割の特別の場合が発生する。ページの次ページ（または前ページ）リンク・フィールドが空白（null）なので、トリーの終わり（または始まり）を認識することは、容易である。ステップ１９０では、トリー・マネージャは、現行ページがＭＤＢトリーの終わりであるか或いは始まりであるかを決定する。もしそうであれば、半分にページを分割する代わりに、ステップ１９６では、トリー・マネージャは、新しいデータのユニットだけを新たに割り当てられた次ページに格納する。これは、オーバーヘッドをセーブし、かつノードがキー・バリュー・シーケンスで一度に一つ加えられるときに、短縮空間利用（compact space utilization ）に導く。
もし現行ページがＭＤＢトリーの終わりまたは始まりでないならば、ステップ１９２では、トリー・マネージャは、新しいページが現行ページの下（即ち、現行ページよりも下方のアドレス）に物理的に位置付けられているかどうかを決定する。もし新しいページが分割されるページの下に物理的に位置付けられているならば、ステップ１９４では、トリー・マネージャは、中間のキー・バリュー以下のキー・バリューを有する子ノードの全てを新しいページに移動する。中間キー・バリューは、分割されるページに格納された順序付けられたキー・バリューの全ての中間である。もし新しいページが現行ページの上（即ち、より高位のメモリアドレス）に物理的に位置付けられているならば、ステップ１９８では、トリー・マネージャは、中間キー・バリュー以上のキー・バリューを有する子ノードの全てを新しいページに移動する。子ノードを新しいページに移動した後に、ステップ２００では、トリー・マネージャは、中間キー・バリューを、移動した子ノードに対する親ノードのキー・バリュー表に格納し、かつ新しいページのＴＯＰノードのノード識別子を、移動した子ノードに対する親ノードのサブノード表に格納する。
【００３５】
右水平分割は、分割キー・バリュー以上のキー・バリューを有する全ての子ノードを隣接次ページに移動する。左水平分割は、分割キー・バリュー以下のキー・バリューを有する全ての子ノードを隣接前ページに移動する。オリジナル・ページでは、ノードの削除されたサブセットは、ページ空間及びページタグをフリーアップ（free-up ）する。
本発明の好ましい実施例において、上記方法は、格納された情報を表しかつ検索するための均一でかつ容易に保守可能な手段に導く。上記方法は、例えば、大きなレコード、非常に大きなフィールド・オカレンス（field occurrences ）（バイナリ・ラージ・オブジェクト）、及びビットマップを表わすのに有用である。ビットマップ、例えばビデオ画像は、しばしば時間と共に成長するので、ビットマップは、多次元Ｂトリーによって特によく表される。本発明により提供される保守アルゴリズムは、サイズにおけるビットマップの増大を効果的に扱う。
本発明の方法及びシステムは、好ましい実施例により記載されたけれども、本発明がこの実施例に限定されたことを企図していない。本発明のスピリット内における変更は、この技術分野の者にとっては自明であろう。本発明のスコープは、特許請求の範囲によってのみ規定される。
【００３６】
【発明の効果】
本発明のコンピュータシステムの方法では、データの一群をインデックスするトリーデータ構造の一部として格納装置に第１の関連するノード識別子を有する第１のノードエントリーを格納し、第１のノードエントリーは、キー・バリューを格納するフィールドと、サブノードに対する識別情報を格納するフィールドと、データのユニットを格納する第１のデータ領域とを備え、データのユニットを第１のデータ領域に格納する段階を具備するので、ページ溢れを生じることなく効率よく格納装置にデータのユニットを格納することができる。
本発明のコンピュータシステムの方法では、データの一群をインデックスするトリーデータ構造の一部として格納装置に第１の関連するノード識別子を有する第１のノードエントリーを供給し、第１のノードエントリーは、キー・バリューを格納するフィールドと、サブノードに対する識別子情報を格納するフィールドと、データのユニットを格納する第１のデータ領域とを備え、格納装置にデータのユニットを格納するために要求を受け取り、データのユニットが第１のデータ領域に格納されうるかどうかを決定し、データのユニットが第１のデータ領域に格納されえないことが決定されたときに、格納装置に新しいノードエントリーを生成し、新しいノードエントリーは、新しいノード識別子を有しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、データのユニットを新しいデータ領域に格納し、格納装置にポインタノードエントリーを生成し、ポインタノードエントリーは、ポインタノード識別子を有し、新たなノード識別子をポインタノードエントリーに格納し、ポインタノード識別子を第１のサブノード表に格納し、データのユニットが第１のデータ領域に格納されうることが決定されたときに、データのユニットを第１のデータ領域に格納する段階を具備するので、ページ溢れを生じることなく効率よく格納装置にデータのユニットを格納することができる。
【００３７】
本発明のためのコンピュータシステムの方法では、複数のノードエントリー群を格納装置に格納し、各ノードエントリー群は、一つ以上のノードエントリーを備えかつある量の利用可能な空間を有し、各ノードエントリーは、固有なノード識別子を有しかつキー・バリュー表と、サブノード表と、データのユニットを格納するデータ領域とを備え、データのユニットのキー・バリューに基づいて、複数のノードエントリー群のいずれに選択されたデータのユニットを記憶すべきかを決定し、データのユニットの大きさと決定されたノードエントリー群の利用可能な空間の量とに基づいて、選択されたデータのユニットが決定されたノードエントリー群に格納されうるかどうかを決定し、決定されたノードエントリー群の利用可能な空間の量がデータのユニットの大きさよりも小さいときに、格納装置に新しいノードエントリー群を生成し、新しいノードエントリー群は、新しいノード識別子を有する新しいノードエントリーを包含しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、データのユニットを新しいデータ領域に格納し、新しいノードエントリーの新しいノード識別子を決定されたノードエントリーのサブノード表に格納する段階を具備するので、関連するキー・バリュー及び大きさを有するデータの選択されたユニットを、ページ溢れを発生しないで効率よく格納装置に格納することができる。
【００３８】
本発明のコンピュータシステムの方法では、格納装置は、複数の固定サイズブロックに論理的に分けられ、各ブロックは、ブロックヘッダーと、タグのアレイと、複数のノードエントリーとを備え、各ノードエントリーは、キー・バリュー表と、サブノード表と、データ表とを備えている方法であって、キー・バリューを選択されたデータユニットに割り当て、割り当てられたキー・バリューに基づいて、どのノードエントリーに選択されたデータユニットが格納されるべきかを決定し、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるかどうかを決定し、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるときに、選択されたデータユニットが決定されたノードエントリーに格納されうるかどうかを決定し、選択されたデータユニットが決定されたノードエントリーに格納されうるときに、選択されたデータユニットを決定されたノードエントリーに格納し、選択されたデータユニットが決定されたノードエントリーに格納されえないが決定されたノードエントリーを包含するブロックに格納されうるときに、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納し、新しいノードエントリーのノード識別子を決定されたノードエントリーのサブノード表に格納し、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納し、選択されたデータユニットが決定されたノードエントリーに格納されえずかつ決定されたノードエントリーを包含するブロックに格納されえないときに、新しいブロックの割り当てを要求し、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納し、ポインタノードを決定れたノードエントリーを包含するブロックに格納しかつ新しいノードエントリーのノード識別子をポインタノードに格納し、ポインタノードのノード識別子を決定されたノードエントリーのサブノード表に格納し、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納する段階を具備するので、ページ溢れを発生することなく、効率的に選択されたデータユニットを格納装置に格納することができる。
【００３９】
本発明のコンピュータシステムでは、一群のデータをインデックスするトリーデータ構造の一部として格納装置にノードエントリーを格納するノード格納機構と、ノードエントリーは、それに対応付けられて第１のノード識別子を有しかつキー・バリューを格納する第１のキー・バリュー表と、サブノードのノード識別子を格納する第１のサブノード表と、データのユニットを格納する第１のデータ領域とを備え、データのユニットを第１のデータ領域に格納するデータ格納機構とを備えているので、ページ溢れを発生することなく効率よくデータのユニットを格納装置に格納することができる。
本発明のコンピュータシステムでは、選択されたデータのユニットは、関連するキー・バリューとある大きさを有し、格納装置は、複数のノードエントリー群（ページ）を格納し、各ノードエントリー群（ページ）は、一つ以上のノードエントリーを備えかつある量の利用可能な空間を有し、各ノードエントリーは、固有のノード識別子を有しかつキー・バリュー表と、サブノード表と、データのユニットを格納するデータ領域とを備えるコンピュータシステムであって、データのユニットのキー・バリューに基づいて、複数のノードエントリー群（ページ）のどれに選択されたデータのユニットが格納されるべきかを決定する手段と、データのユニットの大きさ及び決定されたノードエントリー群（ページ）の利用可能な空間の量に基づいて、選択されたデータのユニットが決定されたノードエントリー群（ページ）に格納されうるかどうかを決定する手段と、決定されたノードエントリー群の利用可能な空間の量がデータのユニットの大きさよりも小さいときに、新しいノードエントリー群（ページ）を格納装置に生成する手段と、新しいノードエントリー群（ページ）は、新しいノード識別子を有する新しいノードエントリーを包含しかつ新しいキー・バリュー表と、新しいサブノード表と、新しいデータ領域とを備え、データのユニットを新しいデータ領域に格納する手段と、新しいノードエントリーの新しいノード識別子を決定されたノードエントリーのサブノード表に格納する手段とを備えているので、ページ溢れを発生することなく効率よく選択されたデータのユニットを格納装置に格納することができる。
【００４０】
本発明のコンピュータシステムでは、格納装置は、複数の固定サイズブロックに論理的に分けられ、各ブロックは、ブロックヘッダーと、タグのアレイと、複数のノードエントリーとを備え、各ノードエントリーは、キー・バリュー表と、サブノード表と、データ表とを備えているコンピュータシステムであって、キー・バリューを選択されたデータユニットに割り当てる手段と、割り当てられたキー・バリューに基づいて、どのノードエントリーに選択されたデータユニットが格納されるべきかを決定する手段と、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるかどうかを決定する手段と、選択されたデータユニットが決定されたノードエントリーを包含するブロックに格納されうるときに、選択されたデータユニットが決定されたノードエントリーに格納されうるかどうかを決定する手段と、選択されたデータユニットが決定されたノードエントリーに格納されうるときに、選択されたデータユニットを決定されたノードエントリーに格納する手段と、選択されたデータユニットが決定されたノードエントリーに格納されえないが決定されたノードエントリーを包含するブロックに格納されうるときに、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納する手段と、新しいノードエントリーのノード識別子を決定されたノードエントリーのサブノード表に格納する手段と、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納する手段と、選択されたデータユニットが決定されたノードエントリーに格納されえずかつ決定されたノードエントリーを包含するブロックに格納されえないときに、新しいブロックの割り当てを要求する手段と、新しいノードエントリーを生成しかつ選択されたデータユニットを新しいノードエントリーに格納する手段と、ポインタノードを決定れたノードエントリーを包含するブロックに格納しかつ新しいノードエントリーのノード識別子をポインタノードに格納する手段と、ポインタノードのノード識別子を決定されたノードエントリーのサブノード表に格納する手段と、選択されたデータユニットのキー・バリューを決定されたノードエントリーのキー・バリュー表に格納する手段とを備えているので、ページ溢れを発生することなく効率よく選択されたデータユニットを格納装置に格納することができる。
【図面の簡単な説明】
【図１】通常のＢトリーのブロック図である。
【図２】本発明の好ましい実施例を実施するコンピュータシステムの好ましい実施例のブロック図である。
【図３】キー・バリュー・テーブル、サブノード・テーブル、及びデータ領域を備えているノードのブロック図である。
【図４】多次元Ｂトリーの親ノード、第１の子ノード、及び第２の子ノードのブロック図である。
【図５】サブノード及びサブトリーに分割された図４の第１の子ノードのブロック図である。
【図６】多次元Ｂトリー構造のブロック図である。
【図７】本発明の好ましい実施例の多次元Ｂトリーに対する格納フォーマットのブロック図である。
【図８】多次元Ｂトリーのノード及びサブノードに格納されたデータを説明するためのブロック図である。
【図９】図８の多次元Ｂトリーの選択されたサブノードに格納されたデータのユニットのブロック図である。
【図１０】サブユニットに分けられた図９のデータのユニットのブロック図である。
【図１１】図７の格納フォーマットにより第２の格納装置に格納された図１０のデータのサブユニットのブロック図である。
【図１２】図７の格納フォーマットを用いて二次記憶装置にデータのユニットを格納するために好ましい実施例に用いた方法の詳細なフロー図である。
【図１３】図７の格納フォーマットを用いて二次記憶装置にデータのユニットを格納するために好ましい実施例に用いた方法の詳細なフロー図である。
【図１４】図７の格納フォーマットを用いて二次記憶装置にデータのユニットを格納するために好ましい実施例に用いた方法の詳細なフロー図である。
【符号の説明】
２０  コンピュータシステム
２１  中央処理装置（ＣＰＵ）
２２  ランダムアクセスメモリ装置（ＲＡＭ）
２３  二次記憶装置
２４  出力装置
２５  入力装置
２６  キー・バリュー表
２７  サブノード表
２８  データ領域
２９  ノード
【図１】
0003844370.tif 000004
【図２】
0003844370.tif 000005
【図３】
0003844370.tif 000006
【図４】
0003844370.tif 000007
【図５】
0003844370.tif 000008
【図６】
0003844370.tif 000009
【図７】
0003844370.tif 000010
【図８】
0003844370.tif 000011
【図９】
0003844370.tif 000012
【図１０】
0003844370.tif 000013
【図１１】
0003844370.tif 000014
【図１２】
0003844370.tif 000015
【図１３】
0003844370.tif 000016
【図１４】
0003844370.tif 000017