JPH1131096A - データ格納検索方式 - Google Patents

Abstract

(57)【要約】 【目的】従来のデータ格納方式は、ブロックの物理的な
位置の連続性や、格納する為のブロックを事前に作成し
ておく必要があるなど制約が多い物であった。また、検
索にはインデックスの作成が必要で、創生の時間が長
く、また、更新処理を行なう場合には、インデックスの
更新が発生し排他の範囲が広〈なる為、デッドロックが
発生しやすい構造を持っていた。これを半導体のランダ
ムアクセス性を利用し、高速化と同時にメンテナンスの
負荷を最小限にする。 【構成】インデックスの代わりとして、ロケーションテ
ーブルと代替キーテーブルとよぶものを新たに導入す
る。またレコードは原則として複数のレコードを１つの
ブロックに格納する。可変長レコードやスパンドレコー
ドも扱う事が可能である。ロケーションテーブルは、格
納ブロックを管理する。代替キーブロックは代替キーと
ブロック番号、主キー値からなり、いずれもこのテーブ
ルを検索する事により目的のレコードの検索を行なう。
テーブルの検索は、バイナリー・サーチが良く知られて
いる高速な方法であるが、他の方法でも可能である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はコンピューターのデータ
格納、読み出しに関連し、高速かつ高格納率でデータの
格納及び検索が行なえ、メンテナンスの手間を大幅に削
減するもので、データ管理に関する。

【０００２】

【従来の技術】従来のデータ格納方式は、ブロックの物
理的な位置が連続していることや、予め格納する為のブ
ロックを作成しておかなければならないなどという、使
用する上で制約が多い物であった。また、ランダムアク
セスに関しては、一部の方式を除くと、インデックスの
作成が必要で、創生の時間が長く、また、更新処理を行
なう場合には、インデックスの更新が発生し排他の範囲
が広〈なる為、デッドロックが発生しやすい構造を持っ
ていた。インデックスを使用しない方式としてダイレク
トアクセス方式があるが、この方式は、レコードのキー
と格納場所をランダマイズルーチンという特殊なプログ
ラムで関連付ける方式であり、順次アクセスが実用上無
理であり、格納効率もインデックスを使用する方法に比
較すると、低いものであった。

【０００３】

【発明が解決しようとする課題】このような方式は、磁
気ディスクを前提にした技術であったため、止むを得な
い面があった。一方、半導体の価格低下はめざましいも
のが有り、半導体を記憶装置として利用する条件が整い
つつある。半導体は、物理的な移動や回転といった動作
が不要であり、アドレスが連続していなくても高速な格
納、読み出しが可能となる。この性質を利用し、半導体
のみまたは半導体とランダムアクセス型記憶媒体を用い
て記憶装置を構成すれば高速な格納・検索処理が行なえ
る。半導体は主記憶装置を使用する事も可能であるし、
本発明用に外部記憶装置として構成する事も可能であ
る。データの格納はブロックに順次に格納し、データの
挿入によりあふれた場合はオーバーフローブロックを利
用して格納し、ランダムアクセスに関しては、インデッ
クスを使用せず格納ブロックを管理するロケーションテ
ーブルまたは代替キーブロックを使用し、それに対して
検索を行なう事により、高速な格納、読出しを可能と
し、データの格納効率も良くデッドロックの発生を最小
限にとどめる。

【０００４】

【課題を解決する為の手段】インデックスの代わりとし
て、ロケーションテーブルと代替キーテーブルとよぶも
のを新たに導入する。また、レコードは単独で格納する
のではなく、原則として複数のレコードを１つのブロッ
クに格納する。ブロックの構成は図４に示す。この図中
のＦＲＯＭ、ＴＯはそれぞれ当該ブロック中の最小キー
値、最大キー値を示すが、必ずしも両方が必要ではな
く、片方のみでも本方式の適用は可能である。長さが長
いレコードを使用する場合は、一つのブロックに一つの
レコードとしてもよい。また、２つ以上のブロックに１
つのレコードが格納される形態（スパンドレコード）も
可能である。また、ブロックはプライマリーブロック、
オーバーフローブロックそれぞれ毎に、１つのファイル
では全て同一の長さとし、領域管理を容易にする。ブロ
ックに格納することにより、可変長レコードを格納して
も、ブロック単位では固定長となるため、ブロック検出
は固定長の操作で行なえる。ロケーションテーブルは事
前に必要な連続領域を確保する。ロケーションテーブル
の１レコード（エントリー）は、データレコード格納領
域のプライマリーブロック１ブロックを管理する。複数
のプライマリーブロックを管理する方法も可能である
が、プライマリーブロックのサイズは任意の大きさがと
れるので、大きさの変更を行なえばよく複数ブロックの
管理は行なわない方が管理が容易になる。ブロックはプ
ライマリーとオーバーフローに分けられ、ロケーション
テーブルで管理されるのはプライマリーブロックのみで
ある。レコードはまずプライマリーブロックに格納され
る。そのブロックに対して、レコードの挿入が発生しそ
のブロックに格納できなくなった場合は、そのブロック
に対するオーバーフローブロックを１つ割り当てる。そ
のオーバーフローブロックにも格納出来なくなった場合
は更に１つのオーバーフローブロックを割り当てる。オ
ーバーフローブロックはプライマリーブロックの従属ブ
ロックとして管理され、プライマリーブロックからポイ
ンティングされるのみで、ロケーションテーブルには管
理されない。

【０００５】オーバーフローブロックをロケーションテ
ーブルで管理しないので、ロケーションテーブルへのレ
コード挿入が発生せず、ロケーションテーブルの書換え
に要する時間が必要最小限ですみ、更に、ロケーション
テーブルの書換えが１レコードのみである為、排他が発
生してもその範囲が極小化でき、デッドロックの可能性
が大幅に減少する。デッドロックは、１つのコンピュー
ター上で、２つの異なるタスクが、２つ以上の同じ資源
を異なる順序で排他を行なう為に発生し、排他の順序が
同一であれば発生せず、排他の範囲が狭ければ確率は減
少する。従来のインデックスは、数レベルから成り立っ
ている。必要なレコードをアクセスし、更新処理を行っ
た際にレコードのキーが変更されると、インデックスも
変更されるが、これが最下位のインデックスにのみ影響
する場合は排他範囲は限定されるが、場合によっては上
位のインデックスに影響する場合もある。そうなると、
多数のレコードの範囲に排他が及ぶとともに、インデッ
クスの更新にも時間を要する事から、排他の時間が長時
間に及ぶことになり、デッドロックが多発する原因とな
る。

【０００６】

【作用】コンピューターの記憶領域に本方式を適用す
る。

【０００７】

【実施例】本方式で格納するレコードは、必ず１つのユ
ニークな主キーとゼロ個若しくは１個以上のノンユニー
ク（結果的にユニークであっても問題はない）なキー
（代替キー）を持つレコードに限定される。ユニークな
キーを持たないレコードは対象としない。但し、ユニー
クなキーが無いレコードに対して、レコードの追加時に
連続番号などのユニークなキーを強制的に付加し、読み
出しは物理順もしくは代替キーの順にのみ行なう事は可
能である。この場合は挿入が行われない為、レコードの
更新によりレコード長が増加する以外にはオーバーフロ
ーブロックが発生しない。以下の説明で追加とは、現在
格納されているレコードの主キーより大きな主キーを持
つレコードの格納をさし、挿入は、最大の主キーより小
さな主キーを持つレコードの格納をさす。

【０００８】まず、格納方式を説明する。ロケーション
テーブルは予めレコードの格納予定数とブロックの大き
さ、ロケーションテーブル１レコード当たりのプライマ
リーブロック数から計算して必要十分な領域を連続領域
として確保しておく。同様に代替キー・ブロックも格納
するレコードの数のエントリーが格納できる様に、ブロ
ックの大きさと数を決定し、連続領域として確保する。
しかしながら、当初想定した数を上回って格納が行われ
る場合に、連続領域が満杯になり、格納が不可能になっ
てしまう可能性がある。このような場合には、更に追加
で連続領域の確保を行ない、アドレス変換テーブルを用
いて、複数の連続領域があたかも１つの連続領域である
かのように扱う事により、当初の想定レコード数を超え
る数の格納が行われるような事態にも対処が可能であ
る。代替キーが複数ある場合は、それぞれ毎に領域を確
保する。異なる代替キーの代替キーブロック同士は連続
する必要は無い。ロケーションテーブルとブロックの関
係を図２に示す。サブレンジに分割する格納方式を採用
する場合は、各々のサブレンジの予定格納レコード数に
見合ったロケーションテーブルをサブレンジ毎に作成す
る。ロケーションテーブルの各々は連続している領域で
ある必要があるが、ロケーションテーブル同士は連続し
た領域である必要はない。代替キーブロックは、すべて
のレコードを対象とした大きさの連続領域を、分割せず
に用意する。

【０００９】最初のレコードを格納する場合は、まず、
最終ポインターを排他モードで参照する。最終ポインタ
ーは、ブロックとロケーションテーブルをどこまで使用
しているかを管理するもので、形式は図１に示すとお
り。最初は格納されているレコードが何も無いので、ま
ず、最終ポインターに１ブロック目が最後のブロックで
ある事を登録する。最終ポインターにはブロック＃と主
キーの値とを登録する。次に１つのプライマリーブロッ
クを排他モードで確保し、その物理アドレスとブロック
番号（この場合は０。番号は０からスタートする。）を
登録する。ブロックをディスク上に確保する場合は、主
キーの値もエントリーに含める。次にそのブロックにレ
コードを登録する。その後総ての排他を解除する。

【００１０】２レコード目の登録は、まず、最終ポイン
ターを排他モードで参照し、主キーが最終ポインターの
キー値より大きいか否かを判定する。まず、レコードの
追加の場合として説明を行なう。ブロック番号が０なの
でロケーションテーブルのブロック番号０を排他モード
で参照し、０ブロックの物理位置を知り、その物理位置
にあるブロック０を読み出す。そのブロックに十分な空
き領域があれば、レコードを格納し、最終ポインターに
主キーの登録を行ない、総ての排他を解除する。

【００１１】以下、同様の操作で追加格納が行われる
が、０ブロックに入りきらない場合の説明を行なう。ｍ
番目のレコード追加で上記操作を行ない０ブロックを読
み出した際に、０ブロックに十分な余裕が無い場合、プ
ライマリーブロックを１つ（ブロック番号１）排他モー
ドで確保する。ｍ番目のレコードをブロック１に格納す
る。その後、ロケーションテーブルの２レコード目を排
他モードで参照し、このレコードにプライマリーブロッ
ク１の物理位置を登録する。この後総ての排他を解除す
る。このように、追加は論理的に最後のレコードの後に
なる位置に格納される。サブレンジに分割されている場
合は、サブレンジ毎に同様の操作が発生する。

【００１２】次に、レコードの挿入になる場合を説明す
る。既に複数のロケーションテーブルレコード、プライ
マリーブロック、データレコードが存在しているとす
る。まず、挿入されるレコードを、どのブロックに格納
すべきかを判別する必要がある。これはロケーションテ
ーブルに対して検索を行なう。高速な検索の方法の一例
としてバイナリー・サーチが知られている。ここではバ
イナリー・サーチを行なう方法を例として記述するが、
他の方法でも目的のエントリーを探す事は可能である。
方法としては２分割点を探し、そのレコードが指してい
るプライマリーブロックにオーバーフローブロックがあ
る場合にはオーバーフローブロックを含めて、そのブロ
ック（当該ブロック）に格納されているレコードの主キ
ーの値（以下、格納主キー値と略す）と挿入レコードの
主キーの値（以下、挿入主キー値と略す）を比較する。
挿入主キー値が格納主キー値の最小値より大きいか、当
該ブロックの格納主キー値の最大値より大きく、次のブ
ロックの格納主キー値の最小値より小さい場合は、当該
ブロックに格納される。この判定に該当しない場合は、
更に当該ブロックの格納主キー値と挿入ブロック主キー
値の大小を比較し、挿入主キー値が小さい場合は前方
の、そうでない場合は後方の２分割点を探し、同様な操
作を行ない、レコードを格納するブロックを探す。ロケ
ーションテーブルが複数の連続領域から構成されている
場合は、そのままではバイナリー・サーチが行なえない
が、アドレス変換テーブルを利用して、あたかも連続領
域であるかのように扱う事により、バイナリー・サーチ
を行なう事が可能となる。サブレンジに分割されている
場合は、サブレンジ毎のロケーションテーブルの先頭も
しくは最後の主キーの値をまず比較し、どのサブレンジ
が対象となるかを探す。その後、そのサブレンジに関し
て、上記と同様に、バイナリー・サーチを行い、該当す
るブロックを探し出す。

【００１３】ｎ番目のブロックに格納することになった
場合以下のようになる。ブロックの中でレコードを挿入
する位置を探す。レコードは主キーの順に並んでいるの
で挿入レコードより大きい主キーを持ったレコードの直
前が挿入位置となる。まず、主キーの重複が無いかをチ
ェックする。重複していた場合は格納できないのでエラ
ーとして処理を行なう。重複していない場合、挿入レコ
ードより後の位置にあるレコード（１つ以上）を挿入レ
コードが丁度入る大きさだけ後方にずらす。この際に、
ずらしたレコードがブロックの中に収まればそれで処理
は終了するが、納まらない場合は、オーバーフローブロ
ックを１つ切り出して、プライマリーブロックからのポ
インター付けを行い、必要なだけオーバーフローブロッ
クに格納する。その後、プライマリーブロックに挿入レ
コードと挿入レコードに続くレコードを格納する。プラ
イマリーブロックとオーバーフローブロックの論理的な
関係を図６に示す。

【００１４】既にオーバーフローブロックが存在する場
合は、プライマリーブロックとオーバーフローブロック
の双方を併せて格納が可能であればよい。また、オーバ
ーフローブロックは一部分しか使用されずに、領域が有
効に使用されない可能性がある。これを防ぐ為、複数の
プライマリーブロックに対して１つのオーバーフローブ
ロックを設ける事ができる。また、オーバーフローブロ
ックの大きさは総て同一とするが、プライマリーブロッ
クに比べて小さくすることが可能である。また、複数の
プライマリーブロックから１つのオーバーフローブロッ
クをポイントし使用するようにする事が可能である。こ
の他に、オーバーフローしたレコードを、単独で格納領
域に格納し、プライマリーブロックからポインター付け
を行なう方法も採用する事が可能である。しかしなが
ら、この方法はオーバーフローレコードが多い場合に
は、オーバーフローブロックを利用する場合に比較し
て、検索に時間がかかるというデメリットもあり、レコ
ードの発生状況に応じた、格納方法の選択が必要であ
る。

【００１５】次に、代替キーの格納、更新の場合の説明
を行なう。代替キーテーブルは代替キーブロック中に代
替キーの順番に並ぶように格納する。代替キーテーブル
のエントリーは代替キー、そのキー値のレコードが格納
されているブロックの物理アドレス、そのキー値のレコ
ードの主キーからなる。代替キーテーブルはレコードの
追加、更新に伴いエントリー数が変動するが、エントリ
ーの増加に対しては、エントリーが挿入になる可能性が
高く、追加型で発生する可能性は非常に少ない。この
為、主キーと同様の管理ではうまく行なえない。最終格
納予定レコード数に比較して、既に多数のレコードが存
在する場合は、代替キーブロックにエントリーを格納す
る際に、一定の空き領域を設ける事により、挿入を効率
的に処理できるが、初期のレコードの数が最終格納予定
レコード数に比較して少ない場合は、キーの挿入により
オーバーフロー代替キーブロックが多数発生する事にな
る。この場合は、プレ代替キー・ブロックを使用する。
プレ代替キーブロックは、代替キー・ブロックと同様な
構造とし、ブロックの数は代替キーブロックの数のエン
トリーが格納できる大きさを、ブロックのサイズで割っ
て求めた数とする。プレ代替キーブロックのエントリー
数が、代替キーブロックの数と同じになった時点で、プ
レ代替キーブロックから代替キーブロックにエントリー
を移動する。移動時には、代替キーブロックには原則と
して一つのエントリーを格納するが、同一の代替キーを
持つエントリーは、同一の代替キーブロックに格納す
る。同一の代替キーを持つエントリーの数が多くて代替
キーブロックに格納できない場合は、代替キー・オーバ
ーフロー・ブロックを追加し格納する。例えば、最終格
納予定レコード数を１００万件と想定しているとする。
一つの代替キー・ブロックに１００エントリーの格納が
可能とすると、代替キー・ブロックは１万個必要とな
る。エントリーが１万になるまで、プレ代替キー・ブロ
ックに格納し、１万になった時点で、代替キー・ブロッ
クにエントリーを移し替える。

【００１６】また、代替キーブロックの数が多く、プレ
代替キーブロックを１段階設けた場合では、プレ代替キ
ーブロックの数が多くなり、挿入が頻繁に発生し更新処
理が非効率になる可能性がある。この場合は、プレ代替
キーブロックを複数段階設ける様にする。前記の例で言
えば、プレ代替キーブロックに１００００件のエントリ
ーを格納する事になるが、１つのブロックに１００エン
トリーが格納可能なので、これを２段階とし、最初のプ
レ代替キー・ブロックは１００エントリーを管理し、エ
ントリーが１００になった時点で、２段回目のプレ代替
キーブロックに移し替えるという方法である。移し替え
の具体例を図５に示す。この例は２段階のプレ代替キー
ブロックを設けた例である。

【００１７】次に、主キーでのレコード検索の方法を述
べる。これは、レコードの挿入で、挿入位置を調べる為
におこなった方法と同様に行なう。ここでは、挿入の例
と同様にバイナリー・サーチの例を記述する。まずロケ
ーションテーブルの２分割点を探し、そのレコードが指
しているプライマリーブロックにオーバーフローブロッ
クがある場合にはオーバーフローブロックを含めて、そ
のブロック（当該ブロック）に格納されているレコード
の主キーの値（以下、格納主キー値と略す）と挿入レコ
ードの主キーの値（以下、挿入主キー値と略す）を比較
する。挿入主キー値が格納主キー値の最小値より大きい
か、当該ブロックの格納主キー値の最大値より大きく、
次のブロックの格納主キー値の最小値より小さい場合
は、当該ブロックに目的のレコードが存在するか、その
キー値のレコードはファイル上に存在しないかの何れか
である。ブロックの中は主キーの順に並んでいるのでブ
ロックを検索することにより、目的のレコードを検出す
るか、ファイル上に存在しないかを確認する事ができ
る。この判定に該当しない場合は、更に当該ブロックの
主キー値と目的レコードの主キー値の大小を比較し、目
的主キー値が小さい場合は前方の、そうでない場合は後
方の２分割点を探し、同様な操作を行ない、レコードが
格納されているブロックを探す。

【００１８】次に代替キーによる検索について説明す
る。代替キーでの検索は代替キーブロックを検索する。
検索の方法としてはバイナリー・サーチが代表的である
が、これについては、主キーの検索で述べてあるので省
略する。目的の代替キーが含まれる代替キーブロックを
探し出す。更に代替キーブロックの中の目的の代替キー
テーブルを探す。結果は、主キーの場合と同様にそのブ
ロック内にエントリーが存在するか、その代替キー値を
もつレコードはファイル中に存在せず、エントリーが無
いかの何れかである。代替キーブロックに代替キー・オ
ーバーフローブロックが存在するときには、その双方を
検索の対象とする。

【００１９】目的のキー値を持つ代替キーテーブル（エ
ントリー）が探し出せた場合は、そのエントリーにある
物理ブロック番号から物理ブロックにアクセスし、その
ブロック内でエントリー中にある主キー値と一致するレ
コードを探し出す。また、代替キーはノンユニークでい
いので、代替キーブロック中の次のエントリーを見、代
替キー値が同一である場合は、更にそのエントリーに対
するレコードの検索を行ない、同一キー値を持つエント
リーが無くなるまで実行する。

【００２０】次に、創生に関して説明する。創生とは、
本方式のファイル上に既にレコードが複数存在してお
り、オーバーフローブロックが増加した等の理由で再創
生する場合と、バックアップ媒体から本方式の適用媒体
に展開する場合、それと、本方式で述べる格納方式以外
の方法で格納されていたレコードを方法式に移行する場
合が考えられるが、いずれも同様な方法で行なえる。再
創生の場合は、ファイルを順次呼び出し方式にて主キー
の順に読みだし、順編成ファイルを作成する。創生の場
合も同様に順編成ファイルを作成する。

【００２１】次に、ロケーションテーブルと代替キーブ
ロックを準備する。ロケーションテーブルの数は、格納
を予定しているレコードの数を１ブロックに格納できる
レコード数で割った数分を連続領域として確保する。代
替キーブロックは代替キーの種類別に確保する。１つの
種類の代替キーブロックは同一の大きさとし、その数
は、次のように求める。１つの代替キーブロックに格納
できるエントリー数（Ａ）を求める。格納予定レコード
数をＡで割って求めた商が代替キーブロックの数とな
る。また、プレ代替キー・ブロックを準備する。

【００２２】レコードは主キーの順に、ブロックに格納
する。この際に予め挿入の頻度を予測または統計データ
から算出し、ブロック内に一定の割合の余裕を設けるこ
とができる。また、隙間無くレコードを格納することも
可能である。これは、挿入がどの程度行われるかで決定
する。ブロック内の余裕はブロック毎に割合を変える事
も可能である。格納に伴い、ロケーションテーブルへの
記入も行なう。代替キーはまずレコードから代替キーエ
ントリーを作成し、順編成ファイルに格納する。すべて
のレコードの代替キーエントリーの作成が終了したら、
代替キーの順にソートを行い、ソート後のエントリーを
代替キーブロックに格納する。代替キーは代替キーブロ
ックに格納するが、格納は、創生レコード数を最終レコ
ード数で割った商を求め、その商に相当する割合で代替
キーブロックに格納を行なう。これは、代替キーの発生
が挿入型になる為である。

【００２３】代替キーの特殊な使用法も可能となる。現
在のキーは、レコードの特定の位置に格納されているフ
ィールドに対して、キーを設定するもので、例えば商品
コードとか得意先コードといったように長さや形式が同
一であった。本方式では、キーとレコードの関連付けが
行なえれば良いので、文章データにキーを作る事が可能
である。図７で示すように非定型なレコードにキーをつ
ける事が可能となる。この例のように、フィールドの場
所が一定せず、フィールドの長さも固定でないレコード
に代替キーの設定が可能である。

【００２４】

【発明の効果】 高速に主キーと代替キーによるランダムアクセスが行
える。 順次読み出し、書き込みも高速に行なえる。 インデックスを使用せず、ロケーションテーブルと代
替キーブロックを使用する為、データの追加変更削除に
伴う変更が少なく、処理時間が短くレコードの格納が高
速に行える。 ロケーションテーブルや代替キーブロックの作成（創
生）に関する時間がインデックス作成に比較して短時間
ですむ。 ロケーションテーブルや代替キーブロックの排他の範
囲が最小限で済み、デッドロックが起きにくい。 予め、ブロックを作成する必要が無い。 物理的な空きスペースが無くなるまで、ブロックの追
加が行える。 可変長レコードが扱え挿入も可能な為、レコード圧縮
が可能（一般的には、圧縮レコードの更新ができないケ
ースが多い）。 代替キーも問題無く複数使用できる。 データベースのメンテナンスの手間が大幅に削減でき
る。

【図面の簡単な説明】

【図１】ロケーションテーブル、最終ポインター構成。
各々のバイト数は参考であり、この内容と異なる長さで
構成は可能である。

【図２】ロケーションテーブルとブロックの関係。

【図３】代替キーテーブル（エントリー）と代替キーブ
ロックの構成。バイト数は参考であり、この内容と異な
る長さで構成は可能である。ＦＲＯＭ、ＴＯは当該ブロ
ック中のキー値の最小値と最大値である。代替キーブロ
ックのキー値の持ち方は、両方を持つ、または、いずれ
か一方のみでも可能である。

【図４】ブロックの構成。

【図５】プレ代替キーブロックの構成。

【図６】ブロックとオーバーフローブロックの関係図。
解りやすくする為に、ブロックが連続領域にあるような
図にしてあるが、実際には連続領域である必要は無い。

【図７】文章データにキーをつける例。

Claims (2)

【特許請求の範囲】
1. 【請求項１】コンピューターにおける、データ格納方式
   において、 データレコード中に一つのユニークなキー（異なるレ
   コードのキー値が重複しないもので、以降、主キーと呼
   ぶ）と、ゼロ個もしくは１個以上のノンユニークなキー
   （異なるレコードのキー値が重複してもかまわないもの
   で、以降、代替キーと呼ぶ）を持つレコードを固定長の
   ブロックの中に主キーの順番に並ぶように１個以上格納
   し、 ブロックはプライマリーブロックとオーバーフローブ
   ロックで構成し、レコードはまずプライマリーブロック
   に格納し、 レコードの挿入によりプライマリーブロック中に格納
   できなくなった場合に、そのプライマリーブロックに対
   してオーバーフローブロックを割り当て、１つのオーバ
   ーフローブロックでは格納できない場合は更に１つづつ
   オーバーフローブロックを割り当て、各々のブロックを
   連携してレコードを格納し、 レコードの追加に対して最終プライマリーブロックに
   格納できない場合は、新たなプライマリーブロックを割
   り当ててレコードを格納し、 プライマリーブロックの位置管理は、ロケーションテ
   ーブルを用いることにより、各々のブロックの物理的な
   位置に関しては何らの制限を受けず配置でき、 各々のブロックは予め作成しておく必要が無く、必要
   に応じて作成し、物理的なデータ格納エリアが満杯にな
   るまで作成でき、 複数の特定のプライマリーキーの後に、レコード挿入
   が多数行われる型のファイルに対しては、挿入が行われ
   る位置で複数のサブレンジに分割し、挿入ではなくレコ
   ード追加とし、オーバーフローレコードの発生を防ぎ、 プライマリーおよびオーバーフローブロックを複数の
   コンピューター上に分割して保持できる構造の、格納方
   式。
2. 【請求項２】前記の格納方式において、 キーによる検索の為の方法としてインデックスを用い
   ず、ロケーションテーブルと代替キーテーブルを使用
   し、各々は、格納するレコードの数に見合った大きさの
   連続領域を予め確保する。 ロケーションテーブルはロケーションテーブルの番号
   （０からの連続番号でプライマリーブロックの番号と同
   一）とプライマリーブロックの物理アドレスを一つのエ
   ントリーにし、ロケーションテーブルの番号の順番に並
   べた構造とする。主キーによる検索は、ロケーションテ
   ーブルに対して検索を行う。目的のキー値を含むブロッ
   クをもとめ、次にブロック中のレコードを検索する事に
   より目的のレコードの検索を行なう。 レコードの格納にランダムアクセス型記憶媒体装置を
   使用する場合は、ロケーションテーブルのエントリーに
   該当ブロックの主キーを含めたものを１エントリーと
   し、ブロック検索が、ロケーションテーブルのみで行な
   えるようにする。 代替キーを使用する場合は、代替キーテーブルを作成
   する。代替キーテーブルは代替キーブロックに格納する
   方式とし、そのブロックを代替キーブロックと呼ぶ。代
   替キーブロックは予め同一の大きさで必要数を連続して
   確保し、一つの代替キーブロックに複数のエントリーが
   格納可能とする。エントリーは、代替キーと該当レコー
   ドが格納されているブロック番号、該当レコードの主キ
   ーからなり、これを代替キーの昇順に並べたもので、同
   一の代替キーに複数のレコードが存在する場合は、これ
   らを一つのエントリーとする方法も使用できる。同一の
   代替キーを持つエントリーは同一の代替キーブロックに
   格納する。同一の代替キーを持つエントリーの数が多
   い、もしくは代替キーの挿入により、代替キーブロック
   に格納できない場合代替キー・オーバーフロー・ブロッ
   クを代替キーブロックに追加し格納する。 代替キーによる検索は、この代替キーブロックを検索
   することにより、目的の代替キー値を持つエントリーを
   検出し、そのエントリーから目的のレコードの格納され
   ているブロック番号を知り、そのブロック中の当該レコ
   ードの検索を行う。代替キーブロックのみを検索の対象
   とし、探索された代替キーブロックに代替キー・オーバ
   ーフロー・ブロックがある場合は、両方のブロックに格
   納されているエントリーを検索する。 データレコードが最終格納レコード数に比較して非常
   に少ない場合は、その後のレコードの追加で、代替キー
   の挿入が頻繁に発生する可能性が大きいが、この場合
   は、最終レコード数に対応した代替キーブロックに最初
   から格納せず、レコード数が代替キーブロックの数に到
   達するまで、プレ代替キーブロックに格納する。プレ代
   替キーブロックは、代替キー・ブロックと同様な構造と
   し、ブロックの数は代替キーブロックの数のエントリー
   が格納できる大きさを、ブロックのサイズで割って求め
   た数とする。プレ代替キーブロックのエントリー数が、
   代替キーブロックの数と同じになった時点で、プレ代替
   キーブロックから代替キーブロックにエントリーを移動
   する。移動時には、代替キーブロックには原則として一
   つのエントリーを格納するが、同一の代替キーを持つエ
   ントリーは、同一の代替キーブロックに格納する。同一
   の代替キーを持つエントリーの数が多くて代替キーブロ
   ックに格納できない場合は、代替キー・オーバーフロー
   ・ブロックを追加し格納する。 主キーによる、順次読み出しは、ロケーションテーブ
   ルでプライマリー物理ブロックアドレスを検出し、その
   プライマリーブロック内のレコードと、オーバーフロー
   ブロックが存在する場合にはオーバーフローブロック内
   のレコードを順次読み出すことにより読み出しを行う。
   次のブロックはロケーションテーブルの次のエントリー
   を求め、そのエントリーから物理ブロックを求める。 代替キーによる順次呼び出しは、まず、により最初
   のレコードを読み出し、次のレコードの読み出しは、代
   替キーブロックの次のエントリーのレコードを順次に呼
   び出す事により行なう。検索方式。