JPH01191229A - ファイル制御方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデータベースシステム等の如き電子計算機利用
システムで採用されるファイル制御方式に関し、特に、
データをデータレコードとしてデータファイルに格納す
る際に、後の検索処理を検索キー値に基づいて速やかに
行なえるよう、格納するデータをその検索キー値に応じ
たデータファイル内の格納単位に格納するようにしたフ
ァイル制御方式に関する。

〔従来の技術〕

従来のこの種のファイル制御方式の構成を第８図に示す
。同図において、９１はデータをデータレコードとして
記憶するための外部記憶媒体上のデータファイルであり
、第９図に示すように複数の格納単位りから構成され、
それぞれの格納単位りはデータファイル９１内で一意と
なるアドレスを持っている。

格納手段９３は、格納すべきデータを受取ると、そのデ
ータの全部または一部を検索キー値とし、これをアドレ
ス変換手段９２に渡す。アドレス変換手段９２はこれに
応答して例えばその検索キー値をデータファイル９１を
構成する格納単位りの数で割った余りをハツシュ値とし
て求め、そのハフシュ値に対応する格納単位りのアドレ
スを格納手段９３に通知する。

格納手段９３はアドレス変換手段９２からアドレスを受
取ると、そのアドレスが指し示す格納単位りに今回のデ
ータをデータレコードとして格納する。通常、一つの格
納単位りには複数のデータレコードを格納でき、それら
は格納単位毎にある制御レコードにデータポインタで結
合されて管理される。また、同一ハフシュ値となるデー
タの個数が増大し、そのハ・ノシュ値に対応する格納単
位りが満杯になると、例えば別のハツシュ値に対応する
空きの格納単位りをその格納用として一時的に使用し、
オーバフローしたデータレコードをそれに格納した後、
格納単位り間でリンクを採る方法等により、対処してい
る。

〔発明が解決しようとする問題点〕

上述した従来の方式では、ハツシュ値毎に一つの格納単
位が割当てられる。このため、検索キー値の選定やハツ
シュ値の算出方法が良くないと、格納単位毎のデータレ
コードの量に偏りが発生し、以下のような問題が生じる
。

ハツシュ値の採りうる値の数を多くすると、多くの格納
単位を必要とする上、格納するデータレコード数が少な
い場合には無駄な空き領域が増え、データファイル９１
の有効利用が困難となる。即ち、第１０図（ａ）に示す
ようにハツシュ値の数を多くして多くの格納単位りを使
用すれば、各々の格納単位りに格納されるデータレコー
ド数は同図のハンチングを施した部分に示すように少な
くなるが、各格納単位り内での空き領域が増大し、デー
タファイルの有効利用ができない。

反対に、データファイルの有効利用を図るため、ハツシ
ュ値の数を少なくすると、同一ハフシュ値に対応するデ
ータレコード数が増大してオーバフローする確率が高く
なり、検索時の処理が局所的に悪化する。即ち、第１０
図（ｂｌに示すようにハツシュ値の数を少なくして格納
単位りを少なくすれば、各格納単位り内の空き領域は減
るが、同一ハツシュ値に対応するデータレコードＳＲが
オーバフローして複数の格納単位にまたがって格納され
る確率が増え、そのハツシュ値に対応するデータレコー
ドの検索処理の速度が低下する。

本発明の目的は、データファイルの有効利用が可能で、
且つ、検索処理も比較的効率良く行なうことができるフ
ァイル制御方式を提供することにある。

〔問題点を解決するための手段〕

本発明は上記目的を達成するために、 外部記憶媒体上にデータをデータレコードとして記憶す
るためのデータファイルを備え、該データファイルは、
各々データファイル内で一意となるアドレスを持ち且つ
使用中、未使用の二つの状態で管理される複数の格納単
位で構成されているシステムにおいて、 格納単位のアドレスを記憶するための複数のアドレス記
憶域から構成され、各アドレス記憶域はハツシュ値に対
応しているアドレス記憶手段と、データの検索キー値か
らハツシュ値を求め、該求めたハツシュ値に対応する前
記アドレス記憶域から前記検索キー値に現在対応してい
る格納単位のアドレスを取得するアドレス変換手段と、
未使用の格納単位を使用中の格納単位として組込み、同
じ格納単位のアドレスを記ｊｌする複数のアドレス記憶
域のうちの一部のアドレス記憶域に設定されているアド
レスを、前記組込んだ格納単位のアドレスに変更すると
共に、該変更したアドレス記憶域に対応するデータレコ
ードを前記元の格納単位から前記組込んだ格納単位に移
送する格納単位分割手段とを設け、 データの検索キー値を用いて前記アドレス変換手段によ
り検索キー値に対応する格納単位を求め、該求めた格納
単位に前記データをデータレコードとして格納できる空
き領域がある場合にはその格納単位に前記データをデー
タレコードとして格納し、空き領域が無い場合には前記
格納単位分割手段により分割した後の格納単位に前記デ
ータをデータレコードとして格納するように構成される
。

〔作用〕

本発明の作用を、理解を容易とする為に単純化した例を
示す図面を参照して説明する。

今、第１図（ａｌに示すように、アドレス記憶装置中の
二つのアドレス記憶域Ａｉ、Ａｊ　　（Ａｔはハツシュ
値Ｈｔに、Ａｊはハフシュ値Ｈｊに対応している）に同
一の格納単位Ｄｉのアドレスｄｉが記憶されているとす
る。検索すべきデータの検索キー値によりアドレス変換
手段で求められたハツシュ値に対応するアドレス記憶域
がＡｉ、Ａｊとなるデータレコード群ＲＨｉ、ＲＨｊは
、格納単位Ｄｉに空き領域がある限り、第１図ｉａｌに
示すようにその格納単位Ｄｉに格納される。

新たに格納すべきデータが発生し、その検索キー値によ
りアドレス変換手段で求まったハツシュ値に対応するア
ドレス記憶域が例えばＡｉであり、格納単位Ｄ＋に充分
な空き領域がなかった場合、格納単位分割手段が起動さ
れる。格納単位分割手段は起動されると、第１図（ｂｌ
に示すように、未使用の格納単位を一つ使用中の格納単
位ＤＪとして組込み、アドレス記憶域Ａｔ、　Ａｊの一
方たとえばＡｊに設定されているアドレスｄｉを格納単
位ＤＪのアドレスｄｊに変更し、この変更したアドレス
記憶域Ａｊに対応するデータレコードつまりハツシュ値
がＨｊとなるデータレコード（データレコード群ＲＨｊ
に含まれるデータレコード）を、格納単位Ｄｊに移送す
る。これにより格納単位Ｄｉ、ｐｊに空き領域が生成さ
れたので、今回のデータのデータレコードＲを該当する
格納単位（今の場合はＤｉ）に格納する。

〔実施例〕

次に本発明の実施例について図面を参照して説明する。

第２図を参照すると、本発明を適用したファイル制御方
式の実施例は、データファイル１と、アドレス記憶装置
２と、アドレス変換手段３と、格納単位分割手段４と、
格納手段５と、検索手段６とで構成される。

データファイル１は、データをデータレコードとして記
憶するための外部記憶媒体上のファイルであり、第３図
に示すように複数の格納単位Ｄ１゜Ｄ２等で構成され、
各格納単位Ｄｉ、０２等はデータファイル１内で一意と
なるアドレスｄｉ、ｄ２等を持っている。各格納単位Ｄ
ｉ、Ｄ２等は使用中と未使用の二つの状態で管理され、
使用中の格納単位は使用領域Ｕとして管理され、未使用
の格納単位は未使用領域ＮＵとして管理されている。

アドレス記憶装置２は、例えば第４図に示すように、格
納単位のアドレスを記憶するための複数のアドレス記憶
域Ａ１〜Ａｍから構成される。各アドレス記憶域Ａ１〜
Ａｍの総数ｍは採用するハツシュ値の数に応じて決定さ
れる。各アドレス記憶域Ａ１〜Ａｍのアドレス記憶装置
２の先頭からの順番号は、そのアドレス記憶域に対応す
るハツシュ値を示している。

アドレス変換手段３は、格納手段５または検索手段６か
ら検索キー値Ｋが通知されると、Ｋをアドレス記憶域の
数ｍで割算した余りＱをハツシュ値とし、このハツシュ
値に対応するアドレス記憶域に記憶されたアドレスを要
求元の格納手段５または検索手段６に通知する手段であ
る。なお、ハツシュ値の計算方法は上記のものに限らず
、その他各種の方法が採用可能である。アドレス変換手
段３の処理例を第５図に示す。

格納単位分割手段４は、格納手段５から起動されると、
新たな使用中格納単位の獲得、アドレス記憶装置２の更
新、データファイルｌ内の該当する格納単位に格納され
たデータレコードの分割等を行なう手段であり、その処
理例を第６図に示す。

格納手段５は、格納すべきデータが外部から通知される
と、そのデータの検索キー値をアドレス変換手段３に通
知して格納単位のアドレスを返してもらい、そのアドレ
スが指し示す格納単位に空き領域があれば格納すべきデ
ータをデータレコードとしてその格納単位に格納し、空
き領域がなければ格納単位分割手段４を起動することに
より生成された格納単位の空き領域にデータレコードを
格納する手段であり、その処理の一例を第７図に示す。

検索手段６は、外部から検索キー値を指定した参照、更
新の要求を受けると、その検索キー値をアドレス変換手
段３に通知して格納単位のアドレスを返してもらい、そ
のアドレスが指し示す格納単位内を検索することにより
、その検索キー値を持つデータレコードを取得し、参照
要求時は取得したデータレコードのデータを要求元に返
却し、更新要求時は要求された値でそのデータレコード
を更新してデータファイル内の元の位置に再び格納する
手段である。

次に、このように構成された本実施例の動作を説明する
。

データファイル１に一つもデータレコードが格納されて
いない初期の状態において、アドレス記憶装置２の各ア
ドレス記憶域Ａ１〜Ａｍにどのようなアドレスを格納し
ておくかについては、各種の方式が採用できる。例えば
、極端な場合、一つの使用中の格納単位ＤＩだけを確保
し、全てのアドレス記憶域Ａ１〜Ａｍにその格納単位Ｄ
１のアドレスｄｌを格納しておくこともできるし、二つ
の使用中の格納単位ＤＩ、Ｄ２を確保し、アドレス記憶
域Ａ１〜Ａｍを２分割した一方の側の全てのアドレス記
憶域に格納単位Ｄ１のアドレスｄ１を、他方の側の全て
のアドレス記憶域に格納単位Ｄ２のアドレスｄ２をそれ
ぞれ格納しておくこともできる。更に、アドレス記憶域
の個数ｍの半分の数の使用中格納単位を確保し、二つず
つのアドレス記憶域に同一のアドレスを設定しておくこ
ともできる。要するに、初期状態においてどれだけの数
の格納単位を使用中とするのか、同しアドレス値を持つ
アドレス記憶域をどの程度当初から用意するか等に依存
して決定される。

さて、アドレス記憶装置２に初期のアドレスが設定され
た状態で（従って、幾つかの格納単位も使用中の状態と
して確保された状態で）、外部より格納すべきデータが
格納手段５に通知されると、格納手段５は第７図に示す
ように、まず今回格納するデータの検索キー値を通知し
てアドレス変換手段３を起動する（３２１）。

起動されたアドレス変換手段３は、第５図に示すように
、通知された検索キー値をアドレス記憶域Ａ１〜Ａｍの
数ｍで割り、その余りをその検索キー値に対応するハフ
シュ値つまりアドレス記憶域の番号としくＳｌ）、その
アドレス記憶域からアドレスを取出して格納手段５に通
知する（Ｓ２）。

アドレスの返却を受けた格納手段５は、そのアドレスが
指し示すデータファイル１内の格納単位に、今回のデー
タを格納するのに充分な空き領域が存在するか否かを調
べる（Ｓ　２２）。そして、存在した場合（Ｓ２３でＹ
ＥＳの場合）、今回のデータをデータレコードとしてそ
の格納単位に格納しく５２５）、処理を終える。

反対に、格納単位に空き領域がない場合（３２３でＮＯ
の場合）、その格納単位のアドレスを通知して格納単位
分割手段４を起動する（Ｓ２４）。

起動された格納単位分割手段４は、第６図に示すように
、先ず未使用領域ＮＵから格納単位を一つ使用領域Ｕに
組込み（Ｓｌｌ）、格納手段５から通知されたアドレス
と同じアドレスが記憶されているアドレス記憶装置２内
の複数のアドレス記憶域のうちの幾つかのアドレス記憶
域（幾つのアドレス記憶域とするかは任意である）に、
ステップ３１１で使用領域Ｕに組込んだ格納単位が持つ
アドレスを格納する（３１２）。そして、アドレスを格
納し直したアドレス記憶域に対応する検索キー値（即ち
ハツシュ値）を持つデータレコードを元の格納単位中か
ら捜し出し、それらを上記組込んだ格納単位に移送する
（５１３）。そして、制御を格納手段５に戻す。

格納手段５は、制御が格納単位分割手段４から戻される
と、再びステップＳ２１から処理を開始し、アドレス変
換手段３から今回の検索キー値に対応するアドレスを再
度通知してもらう（この通知アドレスは前回と同一の場
合と異なる場合とがある）。そして、アドレスが返却さ
れると、このときは空き領域が存在するのでステップＳ
２２゜３２３を経てステップ３２５に進み、該当格納単
位に今回のデータレコードを格納して処理を終える。

以上のような処理が繰返されることにより、データファ
イルｌ内に多数のデータレコードが格納される。なお、
格納手段５から通知されたアドレスを記憶するアドレス
記憶域が一つになった場合は、例えば格納単位分割手段
４は分割不可を格納手段５に通知し、格納手段５は従来
と同様にオーバフローに伴う処理を行なうが、本発明で
はアドレス記憶域の数ｍを適当に大きくしておくことに
より、そのような事態が発生する確率は充分に小さくな
る。

また、外部より検索キー値を指定した検索要求を検索手
段６が受取ると、検索手段６は、その検索キー値をアド
レス変換手段３に通知する。アドレス変換手段３は第５
図に示した処理によりその検索キー値に対応する格納単
位のアドレスを返すので、検索手段６はそのアドレスが
指し示すデータファイルｌ内の格納単位中を検索するこ
とにより、今回の検索キー値を持つデータレコードを探
索する。そして、参照、更新に応じた処理を行なう。

Ｃ発明の効果〕 以上説明したように、本発明では、アドレス変換手段で
求まるハツシュ値はアドレス記憶装置内のアドレス記憶
域に対応するだけで、格納単位と一対一で対応しなくて
良い。従って、データレコード数が少ない場合、複数の
アドレス記憶域に同一の格納単位のアドレスを記憶する
ことができ即ち異なるハツシュ値になるデータレコード
を同一の格納単位に格納することができ、格納単位の使
用数を少なくすることができる。

また、成る格納単位に空き領域がなくなって新たなデー
タレコードを格納することができなくなると、その格納
単位のアドレスが設定されている複数のアドレス記憶域
の一部のアドレス記憶域に、新たに使用中に組込んだ格
納単位のアドレスが設定され、このアドレス変更したア
ドレス記憶域に対応するデータレコードが上記新たに確
保された格納単位に移送されて、格納の為の空き領域が
生成される。つまり、使用中の格納単位の数は格納され
るデータレコードの増加に応じて動的に制御されるので
データファイルの有効的な利用が可能となり、然も予め
アドレス記憶域の敗すなわちハツシュ値の採りうる数を
多くしておくことにより、複数の格納単位間にまたがっ
て検索しなければならない事態を回避でき、検索処°理
の効率を高めることができる。

【図面の簡単な説明】

第１図は本発明の詳細な説明図、 第２図は本発明の実施例の構成図、 第３図はデータファイルｌの構成例を示す図、第４図は
アドレス記憶装Ｗ２の構成例を示す図、第５図はアドレ
ス変換手段３の処理例の流れ図、第６図は格納単位分割
手段４の処理例の流れ図、第７図は格納手段５の処理例
の流範図、第８図は従来方式の構成図、 第９図は従来方式のデータファイル９１の構成図および
、 第１０図は従来方式の問題点の説明図である。 図において、 １・・・データファイル ２・・・アドレス記憶装置 ３・・・アドレス変換手段 ４・・・格納単位分割手段 ５・・・格納手段 ６・・・検索手段 Ｄｉ、］）ｊ・・・格納単位 ｄｉ、ｄｊ・・・格納単位Ｄｉ、Ｄｊの７ドレスΔｉ、
Ａｊ・・・アドレス記憶域

Claims (1)

1. 【特許請求の範囲】 外部記憶媒体上にデータをデータレコードとして記憶す
   るためのデータファイルを備え、該データファイルは、
   各々データファイル内で一意となるアドレスを持ち且つ
   使用中、未使用の二つの状態で管理される複数の格納単
   位で構成されているシステムにおいて、 格納単位のアドレスを記憶するための複数のアドレス記
   憶域から構成され、各アドレス記憶域はハッシュ値に対
   応しているアドレス記憶装置と、データの検索キー値か
   らハッシュ値を求め、該求めたハッシュ値に対応する前
   記アドレス記憶域から前記検索キー値に現在対応してい
   る格納単位のアドレスを取得するアドレス変換手段と、
   未使用の格納単位を使用中の格納単位として組込み、同
   じ格納単位のアドレスを記憶する複数のアドレス記憶域
   のうちの一部のアドレス記憶域に設定されているアドレ
   スを、前記組込んだ格納単位のアドレスに変更すると共
   に、該変更したアドレス記憶域に対応するデータレコー
   ドを前記元の格納単位から前記組込んだ格納単位に移送
   する格納単位分割手段とを設け、 データの検索キー値を用いて前記アドレス変換手段によ
   り検索キー値に対応する格納単位を求め、該求めた格納
   単位に前記データをデータレコードとして格納できる空
   き領域がある場合にはその格納単位に前記データをデー
   タレコードとして格納し、空き領域が無い場合には前記
   格納単位分割手段により分割した後の格納単位に前記デ
   ータをデータレコードとして格納するようにしたことを
   特徴とするファイル制御方式。