(57)【要約】【課題】  オーバーフロー・ブロックの管理を容易にし、高速なアクセスが可能なシステムを提供すること。【解決手段】  コンピュータにデータを格納し、検索するデータ格納検索システムにおいて、主キー項目を含むデータ項目を持つデータレコードと、データレコードを主キーの順に格納するプライマリー・ブロック１１とオーバーフロー・ブロック１２と、プライマリー・ブロック１１のアドレスを格納するロケーション・テーブル・レコードと、ロケーション・テーブル・レコードを主キーの順に連続領域に格納するロケーション・テーブル１０と、ロケーション・テーブル１０の使用領域の最後を示す最終ポインターと、オーバーフロー・ブロックのアドレスを管理するオーバーフロー・ブロック管理テーブル２０と、オーバーフロー・ブロック管理テーブル２０の使用領域の最後を示すオーバーフロー・ブロック最終ポインターとを備えている、データ格納検索システム。【選択図】        図１
2005215869.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにデータを格納し、検索するデータ格納検索システムにおいて、
主キー項目を含むデータ項目を持つデータレコードと、
データレコードを主キーの順に格納するプライマリー・ブロックとオーバーフロー・ブロックと、
プライマリー・ブロックのアドレスを格納するロケーション・テーブル・レコードと、
ロケーション・テーブル・レコードを主キーの順に格納するロケーション・テーブルと、
ロケーション・テーブルの使用領域の最後を示す最終ポインターと、
オーバーフロー・ブロックのアドレスを管理するオーバーフロー・ブロック管理テーブルと、
オーバーフロー・ブロック管理テーブルの使用領域の最後を示すオーバーフロー・ブロック最終ポインターとを備えていることを特徴とする、データ格納検索システム。
【請求項２】
コンピュータにデータを格納し、検索するデータ格納検索システムにおいて、
主キー項目を含むデータ項目を持つデータレコードと、
データレコードを主キーの順に格納するプライマリー・ブロックとオーバーフロー・ブロックと、
プライマリー・ブロックのアドレスを格納するロケーション・テーブル・レコードと、
ロケーション・テーブル・レコードを主キーの順に格納する現用ロケーション・テーブルと、
現用ロケーション・テーブルの使用領域の最後を示す現用最終ポインターと、
オーバーフロー・ブロックのアドレスを管理する現用オーバーフロー・ブロック管理テーブルと、
現用オーバーフロー・ブロック管理テーブルの使用領域の最後を示す現用オーバーフロー・ブロック最終ポインターと、を備え、
再編成の際、
現用ロケーション・テーブルの再編成位置の最後を示す現用再編成ポインターと、
プライマリー・ブロックのアドレスを格納する新規ロケーション・テーブルと、
新規ロケーション・テーブルの再編成位置の最後を示す新規再編成ポインターと、
オーバーフロー・ブロックのアドレスを管理する新規オーバーフロー・ブロック管理テーブルと、
新規オーバーフロー・ブロック管理テーブルの使用領域の最後を示す新規オーバーフロー・ブロック最終ポインターと、
を備えていることを特徴とする、データ格納検索システム。
【請求項３】
請求項１に記載のデータ格納検索システムにおいて、
プライマリー・ブロックのアドレスを格納するフランド・ロケーション・テーブルと、
オーバーフロー・ブロックのアドレスを管理するフランド・オーバーフロー・ブロック管理テーブルと、を備えていることを特徴とする、データ格納検索システム。
【請求項４】
コンピュータにデータを格納し、検索するデータ格納検索システムにおいて、
代替キー・レコードを代替キーの順に格納する代替キー・ブロックと代替キー・オーバーフロー・ブロックと、
代替キー・ブロックのアドレスを格納する代替キー・ロケーション・テーブル・レコードと、
代替キー・ロケーション・テーブル・レコードを代替キーの順に格納する代替キー・ロケーション・テーブルと、
代替キー・ロケーション・テーブルの使用領域の最後を示す最終ポインターと、
代替キー・オーバーフロー・ブロックのアドレスを管理する代替キー・オーバーフロー・ブロック管理テーブルと、
代替キー・オーバーフロー・ブロック管理テーブルの使用領域の最後を示す代替キー・オーバーフロー・ブロック最終ポインターとを備えていることを特徴とする、データ格納検索システム。
【請求項５】
コンピュータにデータを格納し、検索するデータ格納検索システムにおいて、
代替キー・レコードを代替キーの順に格納する代替キー・ブロックと代替キー・オーバーフロー・ブロックと、
代替キー・ブロックのアドレスを格納する代替キー・ロケーション・テーブル・レコードと、
代替キー・ロケーション・テーブル・レコードを代替キーの順に格納する現用代替キー・ロケーション・テーブルと、
現用代替キー・ロケーション・テーブルの使用領域の最後を示す現用代替キー最終ポインターと、
代替キー・オーバーフロー・ブロックのアドレスを管理する現用代替キー・オーバーフロー・ブロック管理テーブルと、
現用代替キー・オーバーフロー・ブロック管理テーブルの使用領域の最後を示す現用代替キー・オーバーフロー・ブロック最終ポインターと、を備え、
再編成の際、
現用代替キー・ロケーション・テーブルの再編成位置の最後を示す現用再編成ポインターと、
代替キー・ブロックのアドレスを格納する新規代替キー・ロケーション・テーブルと、
新規代替キー・ロケーション・テーブルの再編成位置の最後を示す新規再編成ポインターと、
代替キー・オーバーフロー・ブロックのアドレスを管理する新規代替キーオーバーフロー・ブロック管理テーブルと、
新規代替キー・オーバーフロー・ブロック管理テーブルの使用領域の最後を示す新規代替キー・オーバーフロー・ブロック最終ポインターと、
を備えていることを特徴とする、データ格納検索システム。
【請求項６】
請求項４に記載のデータ格納検索システムにおいて、
代替キー・ブロックのアドレスを格納するフランド・代替キー・ロケーション・テーブルと、
代替キー・オーバーフロー・ブロックのアドレスを管理するフランド・代替キー・オーバーフロー・ブロック管理テーブルと、を備えていることを特徴とする、データ格納検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを使用してデータを格納し検索するシステムに関するものである。
【背景技術】
【０００２】
従来のコンピュータによるデータベース格納検索方式は、「Jeffrey D.Ullman著、国井他１名訳、"データベース・システムの原理" 、第1版、日本コンピュータ協会、1985年5月25日、p45-71」、「Samuel Leffler他著/中村明他訳、”UNIX4.3BSDの設計と実装”、丸善株式会社、1991年6月30日、p193-191」及び「Michael J.Folk他著/楠本博之訳、"bit別冊 ファイル構造"、共立出版 株式会社、1997年6月5日、p169-191」に記載されているように、基本的には階層型のインデックスを使用するものであった。
【０００３】
本発明者は、従来の階層型インデックスに代えてロケーション・テーブルと代替キー・テーブルという概念を導入し、インデックスの処理に伴う複雑な処理を簡素化し、ロケーション・テーブル自体の検索をバイナリー・サーチなどの手法を用いることにより、高速化と、メンテナンスの容易性を確保できるようにした「データ格納検索方式」を発明した（日本国特許第３３４５６２８、米国特許第６６５４８６８号参照）。この「データ格納検索方式」では、プライマリー・ブロックにオーバーフロー・ブロックが連結され、更に、オーバーフロー・ブロックにオーバーフロー・ブロックが連結される、という形式になっていた。
【０００４】
更に、本発明者は、「データベースの再編成システム、並びに、データベース」（以下「データベース再編システム」と呼ぶ。ＰＣＴ／ＪＰ０３／１１５９２）を発明した。「データ検索格納方式」で発明したデータベースに対して、データベースを稼動させながら再編成が行える仕組を発明した。更に、代替キー・テーブルに対して代替キー・ロケーション・テーブルを付加することにより、効率的な再編成が可能となることを発明した。また、本発明に関連する既存の発明として、「データベースのアクセラレーター機能（ＰＣＴ／ＪＰ０３／１３４４３）」を発明した。
【０００５】
また、本発明者は「データベースのアクセラレーター機能（以下、「アクセラレーター機能」と呼ぶ。ＰＣＴ／ＪＰ0３／１３４４３）」を発明した。これは、フランド・ロケーション・テーブルとフランド・代替キー・ロケーション・テーブルという、プライマリー・システムにおけるロケーション・テーブルと代替キー・ロケーション・テーブルと機能的に同一であるものを、アクセラレーター・システムに持たせることにより、データベースに対して並行的にアクセスが可能となるものである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
＜１＞本発明は、効率の良い記憶領域の管理を計ることにある。
＜２＞本発明は、また、データベース・システムの性能向上を測ることにある。
【課題を解決するための手段】
【０００７】
本発明は、コンピュータにデータを格納し、検索するデータ格納検索システムにおいて、主キー項目を含むデータ項目を持つデータレコードと、データレコードを主キーの順に格納するプライマリー・ブロックとオーバーフロー・ブロックと、プライマリー・ブロックのアドレスを格納するロケーション・テーブル・レコードと、ロケーション・テーブル・レコードを主キーの順に連続領域に格納するロケーション・テーブルと、ロケーション・テーブルの使用領域の最後を示す最終ポインターと、オーバーフロー・ブロックのアドレスを管理するオーバーフロー・ブロック管理テーブルと、オーバーフロー・ブロック管理テーブルの使用領域の最後を示すオーバーフロー・ブロック最終ポインターとを備えている、データ格納検索システムにある。
【発明を実施するための最良の形態】
【０００８】
＜１＞データ格納検索システムの基本構成と問題の解決
データ格納検索システムは、コンピュータにデータを格納し、検索するものであり、例えば図１に示すように、主キー項目を含むデータ項目を持つデータレコードと、データレコードを主キーの順に格納するプライマリー・ブロック１１とオーバーフロー・ブロック１２と、プライマリー・ブロック１１のアドレスを格納するロケーション・テーブル・レコードと、ロケーション・テーブル・レコードを主キーの順に連続領域に格納するロケーション・テーブル１０と、ロケーション・テーブル１０の使用領域の最後を示す最終ポインターＦＰと、オーバーフロー・ブロック１２のアドレスを管理するオーバーフロー・ブロック管理テーブル２０と、オーバーフロー・ブロック管理テーブル２０の使用領域の最後を示すオーバーフロー・ブロック最終ポインターＯＦとを備えている。
【０００９】
オーバーフロー・ブロック管理テーブル・レコード（またはオーバーフロー・ブロック管理テーブル・エントリー）は、当該レコードが管理しているオーバーフロー・ブロック１２のアドレスと、当該オーバーフロー・ブロック１２の主キー値の最小値と最大値の双方、または何れか一方、次のオーバーフロー・ブロック管理テーブル・レコードのアドレスからなる。更に、ロケーション・テーブル１０にオーバーフロー・ブロック管理テーブル・レコードへのポインターを設ける。オーバーフロー・ブロック管理テーブル・レコードは、オーバーフロー・ブロック１２が発生する都度、そのアドレスを記憶し、一つのプライマリー・ブロック１１に対してオーバーフロー・ブロック１２が２つ以上存在する場合には、１番目のオーバーフロー・ブロック管理テーブル・レコードが２番目のオーバーフロー・ブロックのオーバーフロー・ブロック管理テーブル・レコードを指し、２番目が３番目を指す、というようにチェーンする。使用しているオーバーフロー・ブロック管理テーブル２０のレコードの最後を示すために、オーバーフロー・ブロック管理テーブル・ポインター２０を設ける。以上の説明は、代替キー・オーバーフロー・ブロックに対しても同様である。
【００１０】
データ格納検索システムは、以下のような問題点を解決できる。先ず、プライマリー・ブロック１１にオーバーフロー・ブロック１２が連結し、そのオーバーフロー・ブロック１２に更にオーバーフロー・ブロック１２が連結する、という形式であり、連結の方法は、直前のプライマリー・ブロック１１またはオーバーフロー・ブロック１２が、それに続くオーバーフロー・ブロック１２のアドレスを保持する場合、目的のレコードを見つけるには、次々とオーバーフロー・ブロック１２を探していかなければならない。その場合、ロケーション・テーブル１０と代替キー・ロケーション・テーブルを高速なランダム・アクセス・メモリに配置し、ブロックと代替キー・ブロックをハード・ディスクなど相対的に安価であるがアクセス速度が比較的遅い媒体に格納する場合、オーバーフロー・ブロック１２や代替キー・オーバーフロー・ブロックの数が多くなると、遅い記憶媒体内で、次々とオーバーフロー・ブロック１２を探していかなければならず、目的のオーバーフロー・ブロック１２を探す時間が長くなってしまう問題点がある。例えば、高速なランダム・メモリーが１００ｎｓでアクセスでき、一方で、オーバーフロー・ブロックが１０ｍｓのアクセス速度が必要であるとすると、その差は１０万倍となってしまう。この問題は、連結されたオーバーフロー・ブロック１２の数が多くなればなるほど問題となる。
【００１１】
オーバーフロー・ブロック管理テーブル２０を用いた場合には、オーバーフロー・ブロック管理テーブル２０を検索するだけで、どのプライマリー・ブロック１１またはオーバーフロー・ブロック１２に目的のレコードが格納されているかを識別できるため、プライマリー・ブロック１１またはオーバーフロー・ブロック１２に対するアクセスは１回のみで良いことになる。
【００１２】
次に、オーバーフロー・ブロック１２が複数存在している場合に、比較的前方のオーバーフロー・ブロック１２やプライマリー・ブロック１１に対してレコード挿入が行われる場合に、そのレコードの後方のレコードを総て移動しなくてはならず、それに要する負荷が増大することになる。この問題に関しては、プライマリー・ブロック１１とオーバーフロー・ブロック１２、または、オーバーフロー・ブロック１２とオーバーフロー・ブロック１２の間に新たにオーバーフロー・ブロック１２を挿入することにより、レコードの移動を最小にすることが可能となる。
【００１３】
＜２＞データレコード
データレコードは、必ず１つのユニークな主キーとゼロ個若しくは１個以上のノンユニーク（結果的にユニークであっても問題はない）なキー（代替キー）を持つ。主キーは、従業員データベースの場合、従業員コードなど従業員を識別できるコードであり、代替キーは、氏名や生年月日などであり、データベースによっては、無くても良いし、複数あっても構わない。また、意味を持った主キーとなるべき項目が存在しないレコードに関しては、格納順の連番などを付与して、それを主キーとしても良い。
【００１４】
＜３＞プライマリー・ブロック
プライマリー・ブロック１１は、ロケーション・テーブル・エントリーによって管理されるブロックで、ロケーション・テーブル・エントリー１つに対して１つのみ存在する。これらのブロックは、データレコードを主キーの順に格納する。
【００１５】
＜４＞ロケーション・テーブル
ロケーション・テーブルＬＣ１０は、ロケーション・テーブル・レコード（又は、ロケーション・テーブル・エントリー）を連続した領域に予め確保する。ロケーション・テーブル・レコードは、例えば図２に示すように、プライマリー・ブロック１１のアドレス、オーバーフロー・ブロックがある場合、プライマリー・ブロック１１に連結するオーバーフロー・ブロック１２を管理しているオーバーフロー・ブロック管理テーブル・エントリーのアドレスなどを有している。ここで連続した領域とは、論理的な順序であり、物理的な領域では、離れていても良い。物理的な領域が離れている場合には、アドレス変換テーブルを用いて、論理的に連続していると扱うことができる（以下、同様である）。ロケーション・テーブルの使用領域の最後を示すために、最終ポインターＦＰ（図５の１０１）を用いる。最終ポインターＦＰにより、ロケーション・テーブル・レコードが記憶されている領域の最後のアドレスを知ることができる。
【００１６】
最後のプライマリー・ブロック１１にデータレコードが追加できない場合は、その後に新たなプライマリー・ブロック１１を追加して、データレコードの格納を行う。その追加したプライマリー・ブロック１１のアドレスロケーション・テーブル・レコードを、ロケーション・テーブルＬＣ１０に書き、最終ポインターＦＰの位置を１つ後方に動かす。
【００１７】
＜５＞オーバーフロー・ブロック
プライマリー・ブロック１１にデータレコードを追加する場合に、プライマリー・ブロック１１が満杯である場合に、オーバーフロー・ブロック１２を、そのプライマリー・ブロック１１に連結して、データレコードを格納する。オーバーフロー・ブロック１２に、更にオーバーフロー・ブロック１２を連結することが可能である。ここで、連結とは、物理的に連結されていることを意味するのではなく、各々がアドレス・ポインターによって指し示されていることをいう。「データ格納検索方式」では、プライマリー・ブロック１１が一番目のオーバーフロー・ブロック１２のアドレスを保持し、１番目のオーバーフロー・ブロック１２が２番目のオーバーフロー・ブロック１２のアドレスを保持する、としていた。また、この明細書では新たに、オーバーフロー・ブロック管理テーブル２０を用いて連結する方式を記載している。
【００１８】
＜６＞主キーによるアクセス
或る主キーを持ったレコードを検索する方法は、ロケーション・テーブル１０の最初のレコードと、最終ポインターが指しているロケーション・テーブル・レコードの間をバイナリー・サーチし、目的のプライマリー・ブロック１１を見つけ、そのプライマリー・ブロック１１の中を検索して、目的のレコードを見つける。そのプライマリー・ブロック１１にオーバーフロー・ブロック１２が連結されている場合には、オーバーフロー・ブロック１２も検索の対象となる。
【００１９】
＜７＞代替キー・テーブル
代替キー・テーブル（２０Ａ、２０Ｂ、２０Ｃ）は、例えば図５に示すように、代替キー・ロケーション・テーブル（ＡＡＬＣ、ＡＢＬＣ、ＡＣＬＣ）と代替キー・ブロック（２２Ａ、２２Ｂ、２２Ｃ）を備えている。代替キー・ロケーション・テーブルと代替キー・ブロックは、主キーについてのロケーション・テーブルとプライマリー・ブロックに類似している。代替キー・ブロックは、代替キー値と主キー値からなる代替キー・レコード（または代替キー・エントリー）を代替キー値の順番に格納する。代替キー・ロケーション・テーブルは、各代替キー・ブロックのアドレスが記載された代替キー・ロケーション・テーブル・レコード（または、代替キー・ロケーション・テーブル・エントリー）を連続領域に有する。代替キー・ロケーション・テーブルは連続した領域に予め確保する。代替キー・ロケーション・テーブルの使用領域の最後を示すために、代替キー最終ポインターＦＰ（２９Ａ、２９Ｂ、２９Ｃ）を用いる。代替キー・レコードの追加において、既存の代替キー・レコードの代替キー値より大きい代替キー値を持つ代替キー・レコードは、最後の代替キー・ブロックに格納し、その代替キー・ブロックに格納できない場合には新たに代替キー・ブロックを作成し、その代替キー・ブロックに当該代替キー・レコードを格納する。
【００２０】
＜８＞代替キーによるアクセス
或る代替キーを持ったレコードを検索する方法は、代替キー・ロケーション・テーブルの最初のレコードと、代替キー最終ポインターが指している代替キー・ロケーション・テーブル・レコードの間をバイナリー・サーチし、目的の代替キー・ブロックを見つけ、その代替キー・ブロックの中を検索して、目的の代替キーを持つ代替キー・レコードを見つける。その代替キー・ブロックに代替キー・オーバーフロー・ブロックが連結されている場合には、代替キー・オーバーフロー・ブロックも検索の対象となる。
【００２１】
次に、その代替キー・レコードの主キーによって、ロケーション・テーブルＬＣをバイナリー・サーチし、目的のプライマリー・ブロックを見つけ、そのプライマリー・ブロックとそれに連結されたオーバーフロー・ブロックから目的のレコードを見つけ出す。ここでは、ロケーション・テーブルをバイナリー・サーチする、としたが、「データ格納検索方式」では、代替キー・エントリーにプライマリー・ブロックのアドレスまたは番号を持つことができるとしてある。このように、代替キー・エントリーにプライマリー・ブロックのアドレスまたは番号を持っている場合には、ロケーション・テーブルをバイナリー・サーチすることなく、直接、ブロックに対してアクセスすることが可能である。
【００２２】
尚、代替キーはノンユニークであるので、同一の代替キー値を持ったデータレコードが複数存在する可能性がある。この場合は、代替キー・ブロック中の次の代替キー・レコードが同一の代替キー値である場合には、上記と同様な動作を繰り返す。複数の代替キーが存在する場合には、代替キーの種類と同じ数の代替キー・テーブルを作成し、使用することになる。
【００２３】
＜９＞オーバーフロー・ブロック管理テーブルを利用した格納
オーバーフロー・ブロック管理テーブル２０は、オーバーフロー・ブロック管理テーブル・レコード（またはオーバーフロー・ブロック管理テーブル・エントリー）を有し、オーバーフロー・ブロック１２の管理をするものである。オーバーフロー・ブロック管理テーブル・レコードは、例えば図３に示すように、そのエントリーが管理しているオーバーフロー・ブロック１２のアドレスと、オーバーフロー・ブロック１２の主キー値の最小値と最大値の何れか一方または双方と、次のオーバーフロー・ブロック１２の管理テーブル・レコードのアドレスとを有する。ロケーション・テーブル１０には、図２に示すように、オーバーフロー・ブロック管理テーブル・レコードのアドレスを格納する項目を設ける。なお、ロケーション・テーブル１０において、オーバーフロー・ブロック管理テーブル・レコードのアドレスを格納する項目には、オーバーフロー・ブロック１２が存在する場合は、そのレコードのアドレスを格納し、オーバーフロー・ブロックが存在しない場合には、存在しないことを識別できる特定の値を格納してオーバーフロー・ブロックが存在しないことを示す。オーバーフロー・ブロック管理テーブル・レコードの「次のオーバーフロー・ブロック管理テーブル・レコードのアドレス」は、次のオーバーフロー・ブロック１２が連結されていない場合には、次のオーバーフロー・ブロックが存在しないことを識別できる特定の値を格納して存在しないことを示す。
【００２４】
オーバーフロー・ブロック管理テーブル２０は、ロケーション・テーブル１０と同様に、予め連続した領域に確保する。ここで連続した領域とは、論理的な順序であり、物理的な領域では、離れていても良い。このような場合には、アドレス変換テーブルを用いて、論理的に連続していると扱うことができる。これは、以下の説明でも同様である。このようにアドレス変換テーブルを用いて、物理的には連続していない領域を使用することができるので、最初に確保した領域が足りなくなった場合には、増分の領域を確保することが可能であり、領域不足により稼動しなくなることを避けることができる。即ち、オーバーフロー・ブロック１２が発生する都度、領域を確保し、それらの領域を次々にポイントする、という方法をとることも可能である。オーバーフロー・ブロック管理テーブル２０を使用していることを、データベース・システムに記述しておくことが好ましい。
【００２５】
オーバーフロー・ブロック管理テーブル・レコードの何処までを使用しているかを識別するために、オーバーフロー・ブロック管理テーブル・ポインター（ＯＦＰ）を設け、最終オーバーフロー・ブロック管理テーブル・レコードの次のアドレスを指すようにする。図１を用いて説明する。ＯＦＰは、最初はオーバーフロー・ブロック管理テーブル２０の先頭を指している。オーバーフロー・ブロック管理テーブル・レコード内の数字は、最初の数字が、オーバーフロー・ブロック管理テーブル・レコードの番号、括弧内が、そのレコードが管理しているオーバーフロー・ブロックの番号である。
【００２６】
プライマリー・ブロック１１のブロック１に対して、オーバーフロー・ブロックが発生すると、オーバーフロー・ブロック管理テーブルの最初のレコード０を、オーバーフロー・ブロック１−１用に確保する。ロケーション・テーブル・レコード１にオーバーフロー・ブロック管理テーブル・レコード０のアドレスを格納する。次に、オーバーフロー・ブロック１−１のアドレスを、オーバーフロー・ブロック管理テーブル・レコード０に格納する。図１では、上記のアドレス格納を点線で示している。実線は、従来どおり、ロケーション・テーブル１０からプライマリー・ブロック１１、プライマリー・ブロック１１からオーバーフロー・ブロック１２を指していることを示している。この実線で示したリンク、つまり、プライマリー・ブロック１がオーバーフロー・ブロック１−１のアドレスを保持することは、設けても設けなくてもよい。次に、オーバーフロー・ブロック１２のブロック１−１に格納されているレコードの最大値と最小値の双方または何れか一方を、オーバーフロー・ブロック管理テーブル・レコード０に格納する。ＯＦＰは、オーバーフロー・ブロック管理テーブル・レコード１の先頭を指すように変更する。
【００２７】
オーバーフロー・ブロック１−１に、次のオーバーフロー・ブロックは存在しないので、オーバーフロー・ブロック管理テーブル・レコード０の、「次のオーバーフロー・ブロックの管理テーブル・レコードのアドレス」は、特定の値を入れて、次のオーバーフロー・ブロックが存在しないことを識別できるようにする。
【００２８】
図１では、次にオーバーフロー・ブロック４−１が発生している。この発生に伴う動作は、上記と同様である。次にオーバーフロー・ブロック４−２が発生すると、オーバーフロー・ブロック４−２は、オーバーフロー・ブロック４−１の後続となるので、オーバーフロー・ブロック管理テーブル・レコード１の「次のオーバーフロー・ブロックの管理テーブル・レコードのアドレス」を、オーバーフロー・ブロック管理テーブル・レコード２のアドレスとし、オーバーフロー・ブロック管理テーブル・レコード２の、「次のオーバーフロー・ブロックの管理テーブル・レコードのアドレス」は、特定の値とする。その他の動作は、上記の説明と同様である。図１では、オーバーフロー・ブロック４−３までの追加が行われた時点を示している。
【００２９】
＜１０＞オーバーフロー・ブロック管理テーブルを使用したデータレコードのアクセス
次に、オーバーフロー・ブロック管理テーブル２０を使用したアクセスに関して図１〜図３を用いて説明する。図２は、ロケーション・テーブル・レコードの例である。図３は、オーバーフロー・ブロック管理テーブル・レコードの例である。オーバーフロー・ブロック管理テーブルを使用しない場合は、ロケーション・テーブル１０をバイナリー・サーチすることによって、目的のプライマリー・ブロック１１を見つけ、そのプライマリー・ブロックとそれに連結されたオーバーフロー・ブロック１２から、目的のデータレコードを探し出す。
【００３０】
ロケーション・テーブルのバイナリー・サーチは、ロケーション・テーブルの最初のアドレスと最終ポインターが指すアドレスの中間のアドレスを読み、主キーがそのアドレスのロケーション・テーブル・レコードにあるか、又は上位アドレス、又は下位アドレスにあるかを調べる。上位アドレス、又は下位アドレスにある場合、更にその中間のアドレスをバイナリー・サーチで検索して、主キーを含んでいるプライマリー・ブロック１１およびそれに連結されているオーバーフロー・ブロック１２を見つける。
【００３１】
オーバーフロー・ブロック管理テーブル２０を使用している場合のアクセスは、次のようになる。目的のデータレコードの主キー値（ターゲットキー値）でロケーション・テーブルをバイナリー・サーチして、目的のレコードを格納しているプライマリー・ブロック１１およびそれに連結しているオーバーフロー・ブロック１２を見つける。ロケーション・テーブル・エントリーには、そのエントリーが管理しているプライマリー・ブロックとそれに連結されているオーバーフロー・ブロック全体に格納されているレコードの主キー値の最小値、最大値の双方または何れか一方が格納されているので、その値とターゲットキー値を比較することにより目的のプライマリー・ブロックおよびそれに連結しているオーバーフロー・ブロックを見つけることが可能である。例えば、図１のプライマリー・ブロック３が目的のプライマリー・ブロックであったとする。次に、ロケーション・テーブル・レコード３に記載のオーバーフロー・ブロックの存在の有無を示す記号を調べる。この場合はオーバーフロー・ブロックが無いので、プライマリー・ブロック３のアクセスを行い、目的のデータレコードを見つける。
【００３２】
次に、目的のプライマリー・ブロックがブロック４だった場合について説明する。この場合、ロケーション・テーブル・レコード４を見るとオーバーフロー・ブロックが存在していることが識別できる。また、そのオーバーフロー・ブロック管理テーブル・レコードは、オーバーフロー・ブロック管理テーブル・レコード１となっている。よって、オーバーフロー・ブロック管理テーブル・レコード１（オーバーフロー・ブロック４−１）を参照する。そのレコードには、図３に示すように、オーバーフロー・ブロック４−１に格納されているレコードの主キー値の最小値と最大値の双方、又は、何れか一方が格納されている。この最小値と最大値と目的の主キー値とを比較し、そのオーバーフロー・ブロックにデータレコードが含まれているか否かを判別する。目的の主キー値が、オーバーフロー・ブロック４−１の最小値よりも小さい場合には、目的のレコードはプライマリー・ブロックに存在することになる。目的の主キー値が、オーバーフロー・ブロック管理レコード１の最小値と最大値と等しいかその間にある場合は、目的のレコードは、オーバーフロー・ブロック４−１に格納されていることになる。オーバーフロー・ブロック管理テーブル・レコードに、主キー値の最小値または最大値の一方のみが格納されている場合には、当該オーバーフロー・ブロック管理テーブル・レコードの論理的な前後のブロックの最小値または最大値をオーバーフロー・ブロック管理テーブル２０上で参照することで、当該オーバーフロー・ブロックに目的のレコードが格納されているか否かが判別できる。
【００３３】
オーバーフロー・ブロック４−１の最大値より、目的の主キー値が大きい場合は、オーバーフロー・ブロック管理テーブル・レコード２（オーバーフロー・ブロック４−２）を参照する。ここでも、目的のデータレコードがない場合は、オーバーフロー・ブロック管理テーブル・レコード４（オーバーフロー・ブロック４−３）を参照する。何れにも含まれない場合は、データレコードが存在しないことになる。主キー値がオーバーフロー・ブロック４−３に含まれているとすると、オーバーフロー・ブロック４−３にアクセスを行い、その中で目的のデータレコードを見つける。レコードがプライマリー・ブロックまたはオーバーフロー・ブロックに含まれるとされる場合であっても、目的のキー値の誤りなどによって、レコードが存在しない場合もある。このように、オーバーフロー・ブロックに対するアクセスは、オーバーフロー・ブロックの数に関係なく、１回のみとなる。オーバーフロー・ブロックが低速な装置に格納されている場合には、アクセスの高速化が実現できる。
【００３４】
上記では、検索の場合に関して述べたが、データレコードの更新・追加・削除も全く同様に行える。データレコードの更新は、検索で見つけたデータレコードに対して更新を行う。削除は、検索で見つけたデータレコードの削除を行い、削除レコードより後方のデータレコードを、削除レコードの占めていた領域の分、前方に移動する。追加は、検索の方法を利用して追加するデータレコードを格納する場所を見つけ、格納場所より後のデータレコードを後方に移動した後に、データレコードの格納（追加）を行う。更新・追加・削除は、プライマリー・ブロックとそれに連結されているオーバーフロー・ブロックを排他して実行する。
【００３５】
以上の説明は、ロケーション・テーブル１０とオーバーフロー・ブロック管理テーブル２０を用いて、オーバーフロー・ブロックの管理とアクセスを効率的に行う方法に関して説明したが、代替キー・ロケーション・テーブルと代替キー・オーバーフロー・ブロック管理テーブルに対しても、代替キー・オーバーフロー・ブロック管理テーブルを用いることで、同様の効果を生むことができる。図１０にあるように、各代替キー・ロケーション・テーブル（ＡＬＡ０、ＡＬＢ０、ＡＬＣ０）に対して、オーバーフロー・ブロック管理テーブル（２０Ａ、２０Ｂ、２０ｃ）を設ける。更に、各々のオーバーフロー・ブロック管理テーブルに対して、オーバーフロー・ブロック管理テーブル・ポインターＯＦＰ（２０Ａ１、２０Ｂ１、２０Ｃ１）を設ける。これらの使用法とアクセスの方法は、ロケーション・テーブルとブロックの場合の説明と同様であり、重畳するので省略する。
【００３６】
＜１１＞オーバーフロー・ブロックの途中挿入
オーバーフロー・ブロックが多数存在する場合に、比較的前方のオーバーフロー・ブロックやプライマリー・ブロックに対して、データレコード挿入が発生すると、そのレコード以降のレコードを総て後方に移動しなくてはならず、その移動が大きな負荷になるが、途中にオーバーフロー・ブロックを挿入することにより、そのデータレコード以降のデータレコードを後方に移動する必要がなくなく、データレコードを挿入することができる。そこで、途中にオーバーフロー・ブロックを挿入する場合の動作を図４で説明する。新たに、オーバーフロー・ブロック４−０を確保する。プライマリー・ブロック４がオーバーフロー・ブロック４−１を指していたが、これを、プライマリー・ブロック４がオーバーフロー・ブロック４−０を指すようにし、オーバーフロー・ブロック４−０がオーバーフロー・ブロック４−１を指すようにする。次に、プライマリー・ブロック４またはオーバーフロー・ブロック４−１の何れか、または双方に格納されているレコードのうち、必要なものをオーバーフロー・ブロック４−０に移動する。単純に行う場合には、挿入レコードを格納するための空間を空けるだけのレコードを移動すればよいが、前後のプライマリー・ブロックまたはオーバーフロー・ブロックの格納率が同じくらいになるように移動することが好ましいその場合は、そのレコードとロケーション・テーブル・レコードも書き換える。オーバーフロー・ブロック管理テーブル・レコード５を追加する。オーバーフロー・ブロック管理テーブル・レコード５がオーバーフロー・ブロック４−０を管理するようにする。ロケーション・テーブル・レコード４は、オーバーフロー・ブロック管理テーブル・レコード１（管理対象はオーバーフロー・ブロック４−１）を指していた。これを、ロケーション・テーブル・レコード４が、オーバーフロー・ブロック管理テーブル・レコード５（オーバーフロー・ブロック４−０）を指すように変更する。オーバーフロー・ブロック管理テーブル・レコード５が、オーバーフロー・ブロック管理テーブル・レコード１（オーバーフロー・ブロック４−１）を指すようにアドレスを書く。４−１から４−２、４−２から４−３は、変更が無い。また、オーバーフロー・ブロック管理テーブル・レコード５（オーバーフロー・ブロック４−０）には、４−０に格納されたレコードの主キー値の最小値、最大値の双方または何れか一方を格納する
【００３７】
以上の説明は、ロケーション・テーブル１０とオーバーフロー・ブロック管理テーブル２０を用いて、オーバーフロー・ブロック１２の挿入を効率的に行う方法に関して説明したが、代替キー・ロケーション・テーブルと代替キー・オーバーフロー・ブロック管理テーブルを用いて、代替キー・レコードの挿入を行う場合にも同様の方法を用いることが可能である。つまり、代替キー・レコードの挿入に伴う代替キー・オーバーフロー・ブロックの追加を、代替キー・ブロックと代替キー・オーバーフロー・ブロック、または、代替キー・オーバーフロー・ブロックと代替キー・オーバーフロー・ブロックの間に行うことにより、代替キー・レコードの挿入を効率的に行うことが可能となる。
【００３８】
以下に、データ格納検索システムの再編成システムへの適用例を説明する。
【００３９】
＜１＞データベース再編成システム
「データベース再編成システム」に関して、図７を用いて説明する。再編成とは、オーバーフロー・ブロックの解消、適正な初期格納率の確保、フラグメンテーションの解消の３つを行うことである。オーバーフロー・ブロックの解消とは、次のようなことである。プライマリー・ブロック１１にオーバーフロー・ブロック１２、１３が多数連結されると、それらのブロックに対して、レコードを挿入しようとしたときに、プライマリー・ブロック１１とオーバーフロー・ブロック１２、１３にまたがってデータレコードが主キー値の順に並んでいなければならないので、移動すべきデータレコードの数が多くなってしまう。データレコードの検索をする場合でも、複数のブロックにまたがって検索を行わなければならないので、効率が低下してしまう。このようなことを避けるために、オーバーフロー・ブロック１２、１３を無くして、プライマリー・ブロック１１にする。
【００４０】
適正な初期格納率の確保とは次のようなことである。プライマリー・ブロック内に予め適当な割合の空き空間を設けておくと、データレコードの挿入が発生した場合でも、直ちにオーバーフロー・ブロック１２を追加することなくデータレコードの挿入が行える。ところがデータレコードの挿入が幾度も繰り返されると、適正な初期格納率から外れた空き空間になってしまう。これを初期の状態に戻すものである。フラグメンテーションの解消は、適正な初期格納率の確保と似ているが、不要になったプライマリー・ブロック１１やオーバーフロー・ブロック１２を削ったり、格納率が少ないプライマリー・ブロックまたはオーバーフロー・ブロックは、統合するなどして、プライマリー・ブロックやオーバーフロー・ブロックが均一に使用された状態にすることである。ここでは、プライマリー・ブロック１１とオーバーフロー・ブロック１２に関して述べたが、代替キー・ブロックと代替キー・オーバーフロー・ブロックに関しても全く同様である。
【００４１】
ロケーション・テーブルとプライマリー・ブロック、オーバーフロー・ブロックの再編成においては、ロケーション・テーブル１０を現用ロケーション・テーブルＬＣと新規ロケーション・テーブルＬＮの２つ用意する。更に、各々のロケーション・テーブルに対して、再編成がどこまで終了しているかを示すための再編成ポインターＲＰＬＣを現用ロケーション・テーブルに対して１つ設ける。新規ロケーション・テーブルに対して１つの再編成ポインターＲＰＬＮを設ける。また、新規ロケーション・テーブル用の再編成ポインターＲＰＬＮは、最終ポインターＦＰで代用することも可能である。
【００４２】
図７では、オーバーフロー・ブロックの解消に関して図示している。現用ロケーション・テーブルＬＣが指しているブロックは、プライマリー・ブロック１１と、オーバーフロー・ブロック１２、１３からなる。現用ロケーション・テーブルＬＣの最初のブロックは、プライマリー・ブロック０のみからなるので、新規ロケーション・テーブルＬＮの最初のロケーション・テーブル・レコード０に書き移す。次に、プライマリー・ブロック１を見ると、オーバーフロー・ブロック１−２、１−３が連結されている。プライマリー・ブロック１を、新規ロケーション・テーブルＬＮのロケーション・テーブル・レコード１に書き移す。次に、オーバーフロー・ブロック１−２の連結を切り離し、新規ロケーション・テーブルＬＮのレコード２にオーバーフロー・ブロック１−２のアドレスを書き、プライマリー・ブロックとする。同様に、オーバーフロー・ブロック１−３も、新規ロケーション・テーブルＬＮのレコード３にオーバーフロー・ブロック１−３のアドレスを書き、プライマリー・ブロックとする。
【００４３】
同様に、次々とオーバーフロー・ブロックの切り離しを行い、現用ロケーション・テーブルＬＣのレコード３が管理していたプライマリー・ブロック３までのオーバーフロー・ブロック解消が終了した時点を、図７は示している。現用ロケーション・テーブルの再編成ポインターＲＰＬＣは、現用ロケーション・テーブルＬＣのレコード３の次のアドレスを指している。また、新規ロケーション・テーブルの再編成ポインターＲＰＬＮは、新規ロケーション・テーブルのレコード６の次のアドレスを指している。
【００４４】
次に適正な初期格納率の確保と、フラグメンテーションの解消は、１時点で複数のブロックを対象にし、それらのプライマリー・ブロック、オーバーフロー・ブロック間で、適正な初期格納率になっていないブロック間でデータレコードの移動を行い、ブロック内に適正にデータレコードが格納されるようにするもので、状況によって、ブロックを削除したり、追加したりする。ここでは、プライマリー・ブロックとオーバーフロー・ブロックに関して述べたが、代替キー・ブロックと代替キー・オーバーフロー・ブロックに関しても全く同様である。
【００４５】
再編成中にデータベースをアクセスすることか可能である。まず検索に関して述べる。検索は、再編成ポインターＲＰＬＣが指しているレコードが指しているブロックに格納されているレコードの主キー値が、目的の主キー値より大きいか小さいかの判定を行う。小さい場合には、新規のロケーション・テーブルＬＮを用いて、先頭と再編成ポインターＲＰＬＮが指している間に対してバイナリー・サーチを行うことにより、目的のレコードの検索を行う。大きいか等しい場合は、現用のロケーション・テーブルＬＣを用いて、再編成ポインターＲＰＬＣと最終ポインターＦＰが指している間に対してバイナリー・サーチを行うことにより、目的のレコードの検索を行う。ここでは検索の場合を説明したが、更新、追加、削除も同様に行える。代替キー・テーブルにおける再編成やアクセスも、ロケーション・テーブルとブロックの場合と、ほぼ同様な方式で実行可能である。
【００４６】
＜２＞データベース再編成システムの適用方法
「データベース再編成システム」で再編成を行う場合に、オーバーフロー・ブロック管理テーブルのレコードを解消する方法に関して説明する。「データベース再編成システム」では、オーバーフロー・ブロックの解消、フラグメンテーションの解消、適正な初期格納率の確保の３つを同時に行う方法に関して記載している。この中で、オーバーフロー・ブロックの解消を行うに際して、オーバーフロー・ブロック管理テーブル２０が本発明で追加されているため、この組み合わせにおいて、再編成を行う方法を図８を用いて説明する。この説明では、オーバーフロー・ブロックの解消に関して説明を行うが、実際に再編成を実行する場合には、フラグメンテーションの解消と適正な初期格納率の確保を同時に行うことが好ましい。
【００４７】
再編成を行うには、現用ロケーション・テーブルＬＣに対して、新規ロケーション・テーブルＬＮを設けて、ロケーション・テーブル・レコードを、現用ロケーション・テーブルから新規ロケーション・テーブルに書き移していく。その際に、オーバーフロー・ブロックが存在すると、そのオーバーフロー・ブロックをプライマリー・ブロックとし、新規ロケーション・テーブルに新しいロケーション・テーブル・レコードを作成する。その分だけ、新規ロケーション・テーブルのレコード数が、現用ロケーション・テーブルのレコード数より増加する。図８は、そのように、オーバーフロー・ブロックをプライマリー・ブロックにする再編成を実行して、現用ロケーション・テーブルＬＣのレコード４まで、新規ロケーション・テーブルＬＮのレコード９まで再編成が終了した時点の図である。
【００４８】
再編成は、現用ロケーション・テーブル・レコード０から開始する。ロケーション・テーブル・レコード１はオーバーフロー・ブロック１−１を連結していることが、現用ロケーション・テーブル・レコード１を参照することにより判別できる。ロケーション・テーブル・レコード１は、オーバーフロー・ブロック管理テーブル・レコード０を指しているので、オーバーフロー・ブロック管理テーブル・レコード０が指しているオーバーフロー・ブロック１−１のアドレスを、新規ロケーション・テーブルＬＮのレコード２に格納する。また、オーバーフロー・ブロック管理テーブル・レコード０が不要となる。
【００４９】
次に、現用ロケーション・テーブル・レコード２を新規ロケーション・テーブル・レコード３に書き移す。以下同様に、現用ロケーション・テーブル・レコード３、４を、新規ロケーション・テーブル・レコード４、５に書き移す。現用ロケーション・テーブル・レコードが管理しているプライマリー・ブロック４には、オーバーフロー・ブロックが４つ連結されている。オーバーフロー・ブロック管理テーブルでは、オーバーフロー・ブロック管理テーブル・レコードの５、１、２、４の順に格納されている。前述のように、オーバーフロー・ブロック管理テーブル・レコードが指しているオーバーフロー・ブロックのアドレスを、新規ロケーション・テーブル・レコード６、７、８、９に格納する。それにより、オーバーフロー・ブロック管理テーブル・レコードの５、１、２、４は不要となる。前述のように、図８は、ここまで再編成が終了した時点を示している。
【００５０】
ここでは、新規ロケーション・テーブルの他に、現用オーバーフロー・ブロック管理テーブルに対して、新規オーバーフロー・ブロック管理テーブルを設けている。図８の現用オーバーフロー・ブロック管理テーブルのレコード（０、１、２、４、５）は、再編成によりオーバーフロー・ブロックが解消されているため、不要となったレコードである。オーバーフロー・ブロック管理テーブル・レコードは、再編に伴いこのように、ばらばらに不要となる。一方で、再編成が完了する前に、既に再編成が終了したオーバーフロー・ブロックに対して、更にオーバーフロー・ブロックが発生する可能性がある。
【００５１】
これらの新たに発生するオーバーフロー・ブロックを管理するために、新規オーバーフロー・ブロック管理テーブルを設ける。新規オーバーフロー・ブロック管理テーブルには、新規ロケーション・テーブルで管理しているプライマリー・ブロックに対してオーバーフロー・ブロックが発生した場合に、そのオーバーフロー・ブロックのアドレスや最大値、最小値を格納する。現用ロケーション・テーブルが管理しているプライマリー・ブロックに対して、オーバーフロー・ブロックが発生した場合には、現用オーバーフロー・ブロック管理テーブルを使用する。再編成が完了した場合には、現用ロケーション・テーブルと現用オーバーフロー・ブロック管理テーブルは不要となる。
【００５２】
以上で、ロケーション・テーブルとブロック、オーバーフロー・ブロックの再編成に関して説明を行ったが、この方法を用いることで、代替キー・ロケーション・テーブルと代替キー・ブロック、代替キー・オーバーフロー・ブロック、代替キー・オーバーフロー・ブロック管理テーブルの再編成を全く同様に実施できる。
【００５３】
以下に、データ格納検索システムのアクセラレーターへの適用例を説明する。
【００５４】
＜１＞アクセラレーター・システム
図９を用いて、アクセラレーター・システムの説明を行う。アクセラレーター・システムの原理は次のようなものである。ロケーション・テーブルや代替キー・ロケーション・テーブルに対して、バイナリー・サーチを行って目的のレコードを見つける。ロケーション・テーブルに対してバイナリー・サーチを行う際には、二分割点を幾度も探すことになり、この回数は、プライマリー・ブロックまたはオーバーフロー・ブロック内でレコードを探すための回数よりも多くなることが一般的である。また、同時に複数のプロセスから、同じプライマリー・ブロックまたはオーバーフロー・ブロック内のレコードを要求する可能性は相当に低いものである。よって、ロケーション・テーブルと代替キー・ロケーション・テーブルのコピーを複数保有し、各々に対して並行してバイナリー・サーチが行えるようにすれば、レコードに対するアクセス要求を数多く実行することが可能となる。
【００５５】
図１０では、アクセラレーター・システムが１つの場合を示している。アクセラレーター・システム３では、ロケーション・テーブル（フランド・ロケーション・テーブル）、代替キー・ロケーション・テーブル（フランド・代替キー・ロケーション・テーブル）を保有しているが、プライマリー・ブロック、オーバーフロー・ブロック、代替キー・ブロック、代替キー・オーバーフロー・ブロックは保有していない。アクセラレーター・システムのフランド・ロケーション・テーブルは、プライマリー・システム１のロケーション・テーブルと機能的に同等のものである。同様にアクセラレーター・システム３のフランド・代替キー・ロケーション・テーブルＡＬＡ１、ＡＬＢ１、ＡＬＣ１は、プライマリー・システム１の代替キー・ロケーション・テーブルＡＬＡ０、ＡＬＢ０、ＡＬＣ０と機能的に同等なものである。アクセラレーター・システム３のフランド・ロケーション・テーブル１６の各レコードは、プライマリー・システムの各ロケーション・テーブル１０のレコードと同じブロックを指している。
【００５６】
アクセラレーター・システムでは、アクセス要求があると、主キーの場合はフランド・ロケーション・テーブルに対してバイナリー・サーチを行い、目的のプライマリー・ブロックとそれに連結されたオーバーフロー・ブロックを探し、そのブロック内のレコード検索をプライマリー・システムに依頼する。代替キーの場合は、フランド・代替キー・ロケーション・テーブルのバイナリー・サーチを行い、目的の代替キー・ブロックとそれに連結された代替キー・オーバーフロー・ブロックを見つけ、プライマリー・システムが保持している代替キー・ブロックから目的の代替キー・レコードを見つけ、その代替キー・レコードによって、フランド・ロケーション・テーブルのバイナリー・サーチを行って目的のレコードを見つける。ここでは検索の方法を述べたが、この方法を適用することで、レコードの更新、追加、削除が行える。また、代替キーの場合に、代替キー・レコードに基づいてフランド・ロケーション・テーブルのバイナリー・サーチを行う、としたが、代替キー・レコードに、プライマリー・ブロックのアドレスやブロック番号を保持している場合には不要である。このようにして、複数のアクセラレーター・システムで並行してレコードの検索や更新を行うことにより、処理量を増加させることが可能となる。
【００５７】
図１０では、アクセラレーター・システムはロケーション・テーブル１つと代替キー・ロケーション・テーブル３種を保持しており、プライマリー・システムと同じ数となっている。これを、「アクセラレーター」では対称システムと呼んでいる。これに対して、例えば、ロケーション・テーブルと代替キー・ロケーション・テーブルを２種類のみ保持しているようなアクセラレーター・システムを想定しており、ロケーション・テーブルのみ、代替キー・ロケーション・テーブルのみ、といったアクセラレーター・システムを作成することが可能である。これを非対称システムと呼んでいる。アクセラレーター・システムに関しても、プライマリー・ブロックとオーバーフロー・ブロック、代替キー・ブロックと代替キー・オーバーフロー・ブロックに関して、ほぼ同様に扱うことができる。
【００５８】
＜２＞アクセラレーター・システムへの適用
次に、「アクセラレーター機能」を用いたシステムへの適用に関して図１０を用いて説明する。プライマリー・システム１では、ロケーション・テーブル１０に対して、オーバーフロー・ブロック管理テーブル２０を持ち、代替キー・ロケーション・テーブルＡＬＡ０に対して、代替キー・オーバーフロー・ブロック管理テーブル２０Ａを持ち、同様に、代替キー・ロケーション・テーブルＡＬＢ０に対して代替キー・オーバーフロー・ブロック管理テーブル２０Ｂを持ち、代替キー・ロケーション・テーブルＡＬＣ０に対して、代替キー・オーバーフロー・ブロック管理テーブル２０Ｃを持っている。また、オーバーフロー・ブロック管理テーブルには、オーバーフロー・ブロック管理テーブル・ポインター２０１を設け、代替キー・オーバーフロー・ブロック管理テーブル２０Ａに対して、代替キー・オーバーフロー・ブロック管理テーブル・ポインター２０Ａ１を設け、同様に、代替キー・オーバーフロー・ブロック管理テーブル・ポインター２０Ｂ１、２０Ｃ１を設けている。更に、最終ポインター（１０１、１０Ａ１、１０Ｂ１、１０Ｃ１）を持っている。
【００５９】
アクセラレーター・システム３では、フランド・ロケーション・テーブル１６に対して、フランド・オーバーフロー・ブロック管理テーブル２１を設け、ＡＬＡ１、ＡＬＢ１、ＡＬＣ１の各フランド代替キー・ロケーション・テーブルに対して、それぞれフランド代替キー・オーバーフロー・ブロック管理テーブル２１Ａ、２１Ｂ、２１Ｃを設ける。２１Ａ、２１Ｂ、２１Ｃの各フランド代替キー・オーバーフロー・ブロック管理テーブルに対して、それぞれフランド代替キー・オーバーフロー・ブロック管理テーブル・ポインター２１Ａ１、２１Ｂ１、２１Ｃ１を設ける。更に、最終ポインター（１６１、１６Ａ１、１６Ｂ１、１６Ｃ１）を持っている。
【００６０】
アクセラレーター・システム３では、プライマリー・システム１で、ロケーション・テーブルまたは代替キー・ロケーション・テーブルに変更が発生した場合に、アクセラレーター・システム３に対して、その変更を通知し、アクセラレーター・システム３では、当該フランド・ロケーション・テーブルまたはフランド代替キー・ロケーション・テーブルの変更を行うことになっている。これを、次のように改めることにより、本発明のオーバーフロー・ブロック管理テーブル、代替キー・オーバーフロー・ブロック管理テーブルを用いてもアクセラレーター・システム３を動かすことが可能となる。プライマリー・システム１で、ロケーション・テーブル１０、オーバーフロー・ブロック管理テーブル２０、最終ポインター１０１、オーバーフロー・ブロック管理テーブル・ポインター２０１、代替キー・ロケーション・テーブル（ＡＬＡ０、ＡＬＢ０、ＡＬＣ０）、代替キー・ロケーション・テーブルの最終ポインター（１０Ａ１、１０Ｂ１、１０Ｃ１）、代替キー・オーバーフロー・ブロック管理テーブル（２０Ａ、２０Ｂ、２０Ｃ）、代替キー・オーバーフロー・ブロック管理テーブル・ポインター（２０Ａ１、２０Ｂ１、２０Ｃ１）の何れかに変更が発生した場合に、その変更部分をアクセラレーター・システム３に通知する。アクセラレーター・システム３では、その通知に基づいて、当該フランド・ロケーション・テーブル１６、フランド・オーバーフロー・ブロック管理テーブル２１、フランド最終ポインター１６１、フランド・オーバーフロー・ブロック管理テーブル・ポインター２１１、フランド代替キー・ロケーション・テーブル（ＡＬＡ１、ＡＬＢ１、ＡＬＣ１）、フランド代替キー・ロケーション・テーブルの最終ポインター（１６Ａ１、１６Ｂ１、１６Ｃ１）、フランド代替キー・オーバーフロー・ブロック管理テーブル（２１Ａ、２１Ｂ、２１Ｃ）、フランド代替キー・オーバーフロー・ブロック管理テーブル・ポインター（２１Ａ１、２１Ｂ１、２１Ｃ１）の何れかに対して、当該変更部分の変更を行う。
【００６１】
このように、プライマリー・システム１から変更部分をアクセラレーター・システム３に通知し、アクセラレーター・システム３で直ちにその変更を適用することにより、アクセラレーター・システム３の、フランド・ロケーション・テーブル１６、フランド・オーバーフロー・ブロック管理テーブル２１、フランド最終ポインター１６１、フランド・オーバーフロー・ブロック管理テーブル・ポインター２１１、フランド代替キー・ロケーション・テーブル（２１Ａ、２１Ｂ、２１Ｃ）、フランド代替キー・ロケーション・テーブルの最終ポインター（２１Ａ１、２１Ｂ１、２１Ｃ１）、フランド代替キー・オーバーフロー・ブロック管理テーブル（２１Ａ、２１Ｂ、２１Ｃ）、フランド代替キー・オーバーフロー・ブロック管理テーブル・ポインター（２０Ａ１、２０Ｂ１、２０Ｃ１）は、プライマリー・システムと同等に保たれる。
【００６２】
アクセラレーター・システム３でのアクセスは、オーバーフロー・ブロック管理テーブルを用いたアクセスで説明したことと、アクセラレーター・システム３で説明した方法を組み合わせることで実現できる。
【００６３】
上記では、アクセラレーター・システム３の対称システムを想定した説明を行ったが、非対称システムの場合には、プライマリー・システムで変更があった部分を保持するアクセラレーター・システムのみが、その変更を受け取り更新することになる。
【図面の簡単な説明】
【００６４】
【図１】オーバーフロー・ブロック管理テーブルを使用したデータベースの説明図
【図２】ロケーション・テーブルのレコードの説明図
【図３】オーバーフロー・ブロック管理テーブルのレコードの説明図
【図４】オーバーフロー・ブロック管理テーブルを使用したオーバーフロー・ブロック挿入の説明図
【図５】代替キーによる検索の説明図
【図６】可変長のプライマリー・ブロックの説明図
【図７】再編成の説明図
【図８】オーバーフロー・ブロック管理テーブルを使用した再編成の説明図
【図９】アクセラレーター・システムの原理を説明した図
【図１０】アクセラレーター・システムのオーバーフロー・ブロック管理テーブルの適用例の説明図
【符号の説明】
【００６５】
１・・・・プライマリー・システム
３・・・・アクセラレーター・システム
１０・・・ロケーション・テーブル
１１・・・プライマリー・ブロック
１２・・・オーバーフロー・ブロック
１３・・・オーバーフロー・ブロック
１６・・・フランド・ロケーション・テーブル
２０・・・オーバーフロー・ブロック管理テーブル
２２Ａ・・代替キー・ブロック
ＡＬＡ０・代替キー・ロケーション・テーブル
ＡＬＡ１・フランド代替キー・ロケーション・テーブル
ＬＣ・・・現用ロケーション・テーブル
ＬＮ・・・新規ロケーション・テーブル
ＦＰ・・・最終ポインター
ＯＦＰ・・オーバーフロー・ブロック管理テーブル・ポインター
ＲＰＬＣ・現用ロケーション・テーブルの再編成ポインター
ＲＰＬＮ・新規ロケーション・テーブルの再編成ポインター
【図１】
2005215869.tif 000003
【図２】
2005215869.tif 000004
【図３】
2005215869.tif 000005
【図４】
2005215869.tif 000006
【図５】
2005215869.tif 000007
【図６】
2005215869.tif 000008
【図７】
2005215869.tif 000009
【図８】
2005215869.tif 000010
【図９】
2005215869.tif 000011
【図１０】
2005215869.tif 000012