JPH0449132B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、電子計算機による情報処理におけ
る、データの保存、検索、更新・削除のための方
法に関する。

〔発明の背景〕

電子計算機による情報処理においては記録（＝
レコード：関連する情報（データ）の集まり）を
主記憶装置または補助記憶装置上に実現されるフ
アイルに保存し、必要に応じフアイル内のレコー
ドを検索、更新したり、フアイルへ新たにレコー
ドを登録したり、また、フアイルからレコードを
削除したり、といつたことが一般に行われる。こ
の時のレコードの登録・検索・削除のしかたに
は、レコードが個有に持つている索引情報（キー
情報）の値によつてレコードを検索、登録、削
除、更新を行つたり、索引情報（キー情報）の値
の大きさの順にレコードを読み出したり、ある指
定された索引情報（キー情報）の値を持つ全ての
レコードを走査したり、といつたフアイル・アク
セスの形態があり、計算機システムには、これら
多様なデータ・アクセスの形態を高速に且つ効率
良く実現することが要求されている。

索引データ（キー）を持つレコードに対する、
フアイルへの格納構造及びアクセスの方法につい
ての従来技術として、以下のような方法およびフ
アイル構成法がある。

(1) 線形検索法 フアイルへのレコード登録は、フアイル内の
任意の位置に追加し、レコード検索はフアイル
内の全てのレコードについてキーの一致するレ
コードが見つかるまで順番に照合をくり返して
いくという方法である。

(2) ２分検索法 フアイル内にレコードをそのキーの値の順番
になるように並べておき検索範囲を２分しなが
ら、その対象を絞り込んでいきキーの一致する
レコードを検索する。また、レコードの追加・
削除時には追加又は削除すべきレコードのキー
の値によつて、それ以降の全てのレコードの詰
め換えを行う方法である。

(3) ハツシユ法 ハツシユ法とは、あるレコードのキーが与え
られた時に、キーに依存して生成される（ハツ
シユ関数による）アドレスによつて探索場所を
決定し、指定されたキーを含むレコードを探索
する手法である。これの基本的な考え方は、キ
ーからアドレスへの変換を行うハツシユ関数を
適当に選択することにより、レコードをフアイ
ル記憶領域内になるべく衝突のないように分散
して格納し、探索時に少ない記憶参照回数で、
目的とするレコードを探索しようとするもので
ある。

(4) 木構造による探索法 この方法は、（ｎ−１）個のキーとｎ個の下
位の節へのポインターとから成る節により、木
構造を構成し、この木の根にある節から枝の方
向へ節を辿つていくことにより、指定されたキ
ーを持つレコードを探索しようとするものであ
る。ｎが２の場合には、２分探索木となり、ま
た、これを応用して追加・削除時の木構造の再
構成時に木のバランス化を図つたものにＢ木探
索法がある。

ここに挙げた従来技術の他に、これらの変形の
方法が種々あり、これらは、情報処理学会発行
「情報処理」VOL.24No.４（1983.4）p.391〜p.400
や、Knuth.D.E著「The Art of Computer
Programming VOl.3（Sorting and Searching）」
（Addison−Wesley、1973）等に詳しく記載され
ている。

以上に述べた従来の方法においては、しかしな
がら、次のような問題点があつた。

() 方法(1)及び(3)では、レコードをキーの値の
順に読み出そうとした場合、フアイル内の全レ
コードをソーテイングする必要があり、読み出
しに著しく処理時間がかかる。

() 方法(2)では、追加、削除の度に、平均し
て、フアイル内総レコードのうちの約半分のレ
コードの詰め換えが発生し、詰め換えのオーバ
ーヘツドのために、計算機処理性能の低下を招
く結果となる。

() 方法(4)においては、木構造における各節を
ポインターにより結合して構成しているため、
このポインターの部分が破壊される、または、
故障した場合、その影響を局所化できず、フア
イル全体のダウンとなつてしまうという危険性
がある。また、ポインターで複雑に構成されて
いるため故障の可能性が高いという欠点があ
る。

〔発明の目的〕

本発明の目的は、索引（キー）を持つデータに
対する高速かつ効率の良いフアイル入出力方法を
提供することにある。

〔発明の概要〕

本発明は記憶装置へのデータの入力を管理する
方法であつて、連続記憶領域にデータを記録登録
する記憶単位領域を複数有するとき、それぞれの
単位領域について記録が登録されているか否かを
識別管理してデータの順序付けキー情報の順序を
保持し、かつ記憶領域上に空実状態が平均的に散
在するように入力記憶せしめることに特徴があ
る。

平均的散在の具体的手法にはレコードの追加は
空き状態範囲の中央に順次入力する方法、あるい
は該空き範囲両端のキー情報値と追加される入力
データのキー情報の値の大きさの比率による方法
などが考えられる。

〔発明の実施例〕

本発明は、前記した問題点を解決し、索引（キ
ー）順でのデータの読み出し、及び、データの検
索、登録、削除、更新を高速に行い、且つ、局所
的な記憶領域の破壊や故障によりフアイル全体の
故障を招かないようなフアイル構成法を実現す
る、索引付きデータの管理方法及び入出力装置で
ある。はじめにその基本的な考え方及び構成方法
を第２図、第３図により説明する。

第２図は、本発明における基本的なデータの構
成方法の考え方を示す図である。１はレコードを
格納するレコード格納メモリ（記憶領域）であ
り、１〜Ｎの各記憶単位に対してレコード（記
録）を１ケずつ保持できる。記憶単位のうち、斜
線の施してある部分は、レコードが登録されてい
ない（空の）記憶単位であり、各記憶単位毎に、
２で示すレコード空、実管理ビツトマツプ・メモ
リなどにより、その空／実が管理される記憶単位
の中にある数字は、そこに格納されているレコー
ドのキー情報の値を示すものであり、連続する記
憶領域上に、レコードがそのキー情報の値の順番
に、均一的に散在して配置されるように構成す
る。つまり、本発明におけるデータ構成法の特徴
は、 (1) レコードを格納する記憶領域上に、レコード
がなるべく均一的な密度で、まばらに散らばる
ようにする (2) レコードを格納する記憶領域上に、レコード
のキーの値の順番にレコードが並ぶようにする
という２つの条件を満たすようにすることであ
り、これを実現するためのレコードの追加登録
は以下に示すような方法により行う。

（レコード登録の方法） (1) 登録すべき新たなレコードのキーの値から、
記憶領域上にレコードがキーの値の順番に並ぶ
ような空きの記憶領域を求める。このための方
法としては、２分検索法（バイナリ・サーチ
法）と同様の方法が可能であり、探索する記憶
領域の範囲をせばめていくことにより新たなレ
コードを登録可能な空きの記憶領域を範囲及
び、その直前・直後にあるレコードのキーの値
を効率良く求めることが出来る。

(2) (1)で求めた空きの記憶領域の中から、新たな
レコードを登録すべき記憶単位を決定する。記
憶単位を決定するための判定基準として、記憶
領域上のレコードの登録状況（空、実状態）が
出来るだけ片寄らず、平均的に分散してまばら
な状態となるようにする。このための１つの方
法として、空きの記憶領域の両端にあるレコー
ドのキーの値と、新たに追加するレコードのキ
ーの値とを評価し、空きの記憶領域の範囲が追
加するレコードにより、適当な割合に分割され
る。この方法は、なるべく今後追加されるであ
ろうキーの値の割合いが、分割された空き領域
の配分に近くなるようにすることであり、これ
により次に述べる、「レコードの移動」の量を
少なくする。

(3) (1)において、登録すべき記憶領域の範囲に空
きがない場合は、別の空き領域へ既に登録され
ているレコードをキーの値の順序は変えずに、
順番に移動させることにより、新たなレコード
を登録すべき空きの記憶領域を作り、しかる
後、(1)、(2)の方法に従つてレコードを追加す
る。この時、レコードを移動させるに当つて
は、移動するレコードの個数が出来るだけ少な
くなるように、また、レコードの登録状況（記
憶領域の空実状態）がなるべく、平均的に分散
且つまばらな状態となるように、移動すべきレ
コード群と移動位置を決定する。

このレコード登録の方法の手順を第２図に示
す。第３図において、Ｂの部分は、ある限られ
た、新しいレコードを追加すべき記憶領域の範囲
内でのレコード登録空実状態の均一化のための処
理であり、Ａの部分が、フアイル全体に及ぶ記憶
領域空実状態均一化のための処理である。

以上述べた、本発明の方法では、 (a) ある特定のキーを持つレコードの検索は、２
分検索法と同様の検索方法により行える、 (b) レコードの削除は、(a)によりレコードを検索
し、該レコードの登録されている記憶単位を空
き状態にするだけでよい、 (c) レコードの追加は、空き記憶領域へデータを
登録し、該記憶単位を実の状態とするのみ、ま
たは、レコードの移動を必要とする場合でも、
フアイルへのレコードの登録比率（ロート比率
＝（登録レコード数÷フアイル内記憶単位数））
を低く抑えることによつて、平均して数レコー
ドの移動のみで可能となる、 (d) レコードをキーの値の順番に取り出すために
は、フアイルの記憶領域を物理的に順に読み出
すだけでよい、 といつた特徴がある。

次に本発明の特徴を従来技術との対比で述べ
る。

まず、実現手段レベルでの最も近い従来技術と
の対比として、ハツシユ法との相違点を述べる。

＜ハツシユ法との相違点＞ ハツシユ法はフアイルに登録されるレコードの
キーの値を特定の関数によりフアイル領域上のア
ドレスにマツピングして、レコードを登録・参照
するものであり、その要点は、同一アドレスに対
して複数レコードが対応（衝突）しないようにマ
ツピングを出来るだけ、フアイル領域上に平均的
に且つ一様に分散させるようにすることにある。
つまり、ハツシユ法では、ある時点においてフア
イルに登録されるキーの集合に対して、その値を
フアイル内アドレスの変換した結果が、フアイル
内アドレスの領域に対して一様になるようにす
る。このために、キーからアドレスへの変換の関
数としてランダマイズ関数が用いられる。

一方、本発明では、フアイル内に登録すべきレ
コードを、そのキーの値の順番にフアイル内記憶
領域に出来るだけ空実状態が均一にまばらに並ぶ
ようにする。つまり、レコードの登録時において
レコードを追加すべき記憶単位のアドレスは、キ
ーの値の順序関係に従つて決定され、レコードを
追加すべき空き領域がない場合に、フアイル内の
レコードを順次移動させて再構成させるようにす
ることにより、結果的に、均一にまばらに並ぶよ
うにするものである。

よつて、ハツシユ法と本発明の方法との、原理
上の基本的な相違は、ハツシユ法が、フアイル上
へのレコードの一様な分散を、レコードのキー値
に依存するランダマイズ関数により、静的に実現
しようとしているのに対し、本発明の方法では、
レコードの追加・削除を行つていく過程で、レコ
ードの分散の仕方がまばらになるように徐々にレ
コードを移動させていくことにより、動的にこれ
を実現しようとしている点にある。

次に、実現機能レベルでの最も近い従来技術と
の対比として、Ｂ−tree（又はB_- ⁺tree）法との相
違点を述べる。

＜B_-tree法との相違点＞ B_-tree法又はその変形であるB⁺ _-tree法は、既
に述べた様に、木構造を利用した探索法の応用で
あり、レコードの追加・削除の度に、木構造を再
構成し、木構造の各節の間をポインターで結合・
つなぎ替えを行い、ポインターをたどつていくこ
とにより、レコードをキーの値の順番に読み出せ
るようにしたものである。B_-tree系の方法と本
発明の方法との差は、B_-tree法が、レコード間
の順序をポインターで管理するのに対し、本発明
の方法では、キーの値の順に物理的にレコードを
並べるため、ポインターを持つ必要がないことで
ある。このことにより、本発明では、ポインター
異常によるフアイル構造破壊の発生可能性が極め
て低い。また、B_-tree法では、キー順のレコー
ドをポインターで結合しており、必ずしも各レコ
ードはキーの値の順に物理的に並んでいる訳では
ないので、キー順にレコードを読み出した場合、
フアイルが磁気デイスクなどの場合には、デイス
ク上ランダムなアクセスが発生しアクセス時間が
多くかかるのに対し、本発明では、デイスク上を
シーケンシヤルに読み取れば済むため、キー順で
のレコード・アクセスは極めて効率が良いという
差がある。

次に本発明を具体的な実施例について説明す
る。第１図に本発明の索引付きデータ入出力装置
の構成を示す。第１図において、１，２は、前述
のレコード格納メモリ、とレコード空実管理ビツ
トマツプ・メモリであり、フアイル・デイレクト
リ３には、レコード格納メモリとレコード空実管
理ビツトマツプ・メモリとで構成されるフアイル
１８に関する個有情報（フアイルのサイズ、レコ
ードのサイズ、メモリ上のフアイルの開始アドレ
スなど）が予め定義された情報として記憶されて
いる。制御装置４は、モード・レジスター５で指
定されたモードに従い、フアイル・デイレクトリ
ー３の情報を参照しながら、レコード格納メモリ
１、レコード空実管理ビツトマツプ・メモリ２の
状態を前述の如く、実レコードの配置が、キーの
値の順番に且つ、均一にまばらに分散するように
制御する。モード・レジスター５で指定されるモ
ードとは、フアイルに対するレコードの、登録、
参照、削除、更新のいずれかを行うことを指示す
る制御情報であり、制御装置４は、 (a) 登録（追加）のとき：キー情報記憶バツフ
ア・メモリ６から入力されるキーの値から、レ
コードの追加位置を求め、レコード記憶バツフ
ア・メモリ７から入力されるレコードをフアイ
ルへ登録する。

(b) 参照のとき：索引データ（キー）記憶バツフ
ア・メモリ６から入力されるキーの値と等しい
キーを持つレコードをフアイルから探索し、該
レコードをフアイルから読み出し、レコード記
憶バツフア・メモリ７へ出力する。

(c) 削除のとき：索引データ（キー）記憶バツフ
ア・メモリ６から入力されるキーの値と等しい
キーを持つレコードをフアイルから探索し、該
レコードをフアイルから削除（レコード空実管
理ビツトマツプ・メモリの対応するレコード
空、実管理フラグをオフ（“０”）状態に）す
る。

(d) 更新のとき：索引データ（キー）記憶バツフ
ア・メモリ６から入力されるキーの値と等しい
キーを持つレコードをフアイルから探索し、該
レコードを、レコード記憶バツフア・メモリ７
から入力されるレコードの内容で更新する。

上記における、（）レコードの追加の方法、
および（）レコードの探索の方法、の詳細を第
４，５図に示す。第４図、第５図における、各記
号及び処理名の意味は下記のようなものである。

＜記号＞ RN…求めるレコードのレコード番号（レコー
ド格納メモリ上のアドレスに対応）を格納するレ
ジスター SP…サーチ・ポインター BP…開始ポインター AP…終了ポインター WRN、WRNX レコード番号格納用ワーク−レジスター MP…レコード移動先ポインター IP…レコード追加位置ポインター 以上は全て、第１図の制御装置４における内部
レジスターである。第４図Ａ，Ｂはステツプ101
〜123から成る。

処理ステツプ：(a)＜off−bit−search−fo−
rward from（Ｘ）→Ｙ＞はレコード空実管理ビ
ツトマツプ・メモリ上のＸで指定されたレコード
番号に対応するビツトから始めて、レコード番号
の増加方向へ、off−bit（“０”のもの）をサーチ
し、最初に検出されたoff−bitに対応するレコー
ド番号をＹへ格納する。これは例えば第４図Ａの
ステツプ107、112についての説明である。

処理ステツプ：(b)＜off−bit−search−ba−
ckward from（Ｘ）→Ｙ＞は(a)と同様。但し、レ
コード番号の減少方向へoff−bitをサーチするこ
とを意味する（第４図Ａステツプ105）。

処理ステツプ：(c)＜on−pit−search−fo−
rward from（Ｘ）→Ｙ＞は(a)と同様。但し、レ
コード番号の増加方向へon−bitをサーチする
（第４図Ａステツプ113）。

処理ステツプ：(d)＜on−bit−search−ba−
ckward from（Ｘ）→Ｙ＞は(a)と同様。但し、レ
コード番号の減少方向へ、on−bitをサーチする
（第４図Ａステツプ109）。

処理ステツプ：(e)＜Move from（Ｘ）to（Ｙ）
count（Ｚ）＞はＸで示されるレコードからＺ個の
レコードを、Ｙで示されるレコード位置からＺ個
分のレコード格納領域へ移動する（第４図ステツ
プ117、119）。

処理ステツプ：(f)＜data write to（Ｘ）＞はレ
コード格納メモリ上のＸ番目のレコード格納領域
へレコード記憶バツフア・メモリの内容を書き込
む（第４図Ｂ）。

処理ステツプ：(g)＜bit−set−to（Ｘ）＞はレコ
ード空実管理ビツトマツプ・メモリ上のＸ番目の
ビツトをオン（“１”）にする（第４図Ｂ）。

上記については第５図のステツプ151〜166につ
いても同様である。

ａ，ｂ，ｃ，ｄ各処理の機能説明図を第６図
に、また、処理ｅの機能説明図を第７図に示す。
これら、ａ〜ｇの各処理自体は、メモリに対する
既存のオペレーシヨン又は既存の技術により明ら
かに実現可能なものであり、公知のものであるた
め、その詳細については記載を省略する。なお、
ａ，ｂ，ｃ，ｄにて求めるパターンのビツトがメ
モリ内に存在しない場合には、forwardの時は
（最大レコード番号＋１）を、backwardのとき
は、０をＹに返す。

以下、第４図、第５図に示す、「レコード追加
の方法」、「レコード探索の方法」について説明す
る。

レコードの追加においては、まず、追加しよう
とするレコードのキーと同一の値をもつレコード
の探索（第４図Ａのブロツク101：後述）し、追
加すべきフアイル内のレコード格納位置（BPと
APとで示されるレコード位置の実レコードには
さまれた空き領域）を求める。この時、BPとAP
との間に空き領域が無い場合は、BP又はAPより
連なる実レコード列に隣接する空き領域までの距
離の短かい方向へ実レコード列を移動する（ブロ
ツク104〜120の処理）。この時、実レコード列を
移動する先のレコード格納位置は、ある予め定め
られた空き領域の配分規則Ｒによつて決定するよ
うにする（ブロツク115）。こうして求められた、
レコードを追加可能な空き領域内において、実際
にレコードを追加すべきレコード格納位置は、予
め定められた空き領域の配分規則R´によつて決定
（ブロツク120）し、該領域に追加レコードのデー
タを書き込み、対応するレコード空実管理フラグ
をオン（“１”）とする（ブロツク120〜122の処
理）。

次に、レコードの探索処理においては、BPと
APで囲まれる探索対象レコード領域を、まず全
領域（BP＝０、AP＝（最大レコード番号＋１）
とし（第５図、ブロツク102、103）、該領域を予
め定められた配分規則R″によつて分割するよう
な検索対象レコード番号を求め、その近傍にある
実レコードのキーの値と、求めるキーの値とを比
較することにより、探索対象範囲をせばめていく
（BP、APを更新する：ブロツク104〜115の処
理）。これを、キーの一致するレコードが検出さ
れるか、探索対象レコードの範囲が全て空き領域
となる（キーの値の一致する該当レコードがフア
イル内に存在しない場合）までくり望す。第５図
の処理では該当するレコードが検出できた場合
は、そのレコード番号をRNに、また、該当する
レコードが検出できなかつた場合には、そのレコ
ードが格納されるべき領域が、BPとAPとで示さ
れるようになつている。

なお、ここで使用される配分規則Ｒ，R′，
R″は、少なくとも或る領域の両端を指定する２
つのポインターの値に依存し、２つのポインター
で囲まれる領域をある配分に分割するような領域
内のレコード格納位置レコード番号を導出する関
数である。この関数は、フアイルに格納されるべ
きレコードのキーの値の特性、分散のし方に依存
して任意に定めることのできるものであるが、そ
の目的は、フアイル内レコード格納メモリ上に、
実レコードが一ケ所にかたよることなく、均一に
まばらに散らばつて存在するようにすることにあ
る。

以下、前記の配分規則に具体的に評価関数を適
用した場合について、その特性及び、本発明のフ
アイルにおける実レコード格納状態の遷移一ふる
まいについて説明する。

＜配分規則の具体例＞ 本発明の実施例の１つとして、配分規則を次の
ように定める場合を考える。

MP←Ｒ（WRNX、WRN）：MP←
WRNX＋WRN／２ IP←R′（BP、AP）：IP←BP＋AP／２ SP←R″（BP、AP）：SP←BP＋AP／２ つまり、レコードの追加は、空き領域の中央に
行い、また、探索は、探索範囲を常に２分しなが
ら行つていくこととする。この時の、フアイルへ
のレコードの追加による、フアイル内のレコード
の並びの状態の変化を第８図に示す。但し追加す
るレコードは、以下のキーの値の順に入力される
場合を仮定する。

追加されるキーの順序： 〔80、45、32、23、67、95、21、１、10、55、
71、46、47、17、３、60、85、５、50、35〕 この時の、レコード追加時の移動レコード数を
第９図に示す。第９図から明らかなように、フア
イルへの登録レコード数が少ない、すなわち、ロ
ード比率が低いうちは、殆んどレコードの移動な
くレコードを新たに追加できる。ロード比率が高
くなると場合によつては、移動レコード数の数が
大きくなることが有るため、ロード比率をある程
度のところに抑えて使用すると効率がよいことが
分かる。また、レコードの検索は、２分検索法に
近い方法で行え、効率よく、求めるレコードの探
索を行うことができる。レコードの削除について
は、削除対象レコードを探索した後、探索された
レコードのレコード番号に対応したレコード空実
管理フラグをオフ状態（“０”）とするだけでよ
い。

＜配分規則の具体例＞ 第２の実施例として、配分規則を次のように定
める場合を考える。

MP←Ｒ（WRNX、RNX）： MP←WRNX＋WRN／２ IP←R′（BP、AP）： IP←〔Key−Key（BP）／Key（AP）−Key（BP）（AP−
BP）〕＋ BP SP←R″（BP、AP）： SP←〔Key−Key（BP）／Key（AP）−Key（BP）・（AP
−BP）〕＋ BP 但し、 Key：追加又は探索しようとするキーの値 Key（AP）：APが示すレコードのキーの値 Key（BP）：BPが示すレコードのキーの値 つまり、レコードの追加時におけるレコード追
加位置および、レコード探索時における探索開始
位置は、空き領域または探索範囲領域内の両端の
レコードのキーの値と、追加又は探索しようとす
るレコードのキーの値との比率で領域が分割され
るようなレコード格納位置を選ぶ。但し、フアイ
ルの両端は、キーのとりうる値の最小及び最大値
を予め与えておくものとし、本例では、キーの値
の範囲は１〜100とし、最小値を０、最大値101と
する。第１０図は、以上の条件にて、実施例の
場合と同じ順序で同じキー列を追加していつた場
合のフアイル内レコードの並びの状態の変化を表
わした図であり、第１１図は、その時の移動レコ
ード数との対応を示した図である。この図からも
分かるように、本例のようなキーの特性分布をも
つレコードでは具体例の配分規則とすることに
より、追加時のオーバーヘツド（レコードの移
動）は更に削減され、また、レコードの探索にお
いても、ほとんど１〜２回のキーの照合回数で、
求めるレコードを探索できる。但し、これは、具
体例の配分規則の法が常に秀れた特性を持つて
いる、ということではなく、本例のようなキーの
分散の特性の場合には具体例の方がよい、とい
うことだけにすぎない。すなわち、本発明によれ
ば、レコード追加時のオーバーヘツド（レコード
の移動）の量は、ロード比率と相関があり、ロー
ド比率がある限界値を超えると急激に増加する
（第１２図ａ）。そして、この相関曲線は、フアイ
ルへ格納するレコードのキーの特性により配分規
則を適当に選ぶことにより、ロード比率の限界値
を引き上げること（第１２図ｂ）も、また、全体
の平均のオーバーヘツドを小さくすること（第１
２図ｃ）も可能である。

なお、第１図の構成図において、索引付きデー
タ入出力装置１９を、処理要求９を発行する処理
装置（プロセツサ）とは独立に動作可能なプロセ
ツサとした場合には、レコードの登録処理要求の
あつたレコードデータを一旦、レコード記憶バツ
フアメモリに保持し、要求元に対しては処理完了
信号１０を返し、しかる後、レコード追加登録に
伴うフアイル内レコード移動処理を実施するよう
にすることにより、処理要求に対する応答性を高
めることが可能である。これは、特に分散処理形
態で、フアイル処理を専門に行うフアイル・プロ
セツサや、データベース操作を集中的に実行する
データベースマシンといつた、専用プロセツサ構
成において特に有効である。

本発明の実施例によると、 (1) 索引データ（キー）による、レコードの追加
（登録）、参照、削除、更新を高速に行える。ま
た、ロード比率を抑えることにより、レコード
の追加時にも安定した高レスポンス性能を保証
することができる。

(2) 索引データ（キー）の値の順番に（ソーテイ
ングされた形で）レコードを高速に読み出すこ
とができる。特に、ソーテイングする必要がな
いというだけでなく、フアイル内に物理的に連
続した領域にレコードがキー順に並んでいるの
で、例えば、レコード格納メモリが、磁気デイ
スクのような補助記憶装置の場合にも高速に連
続して読み出すことが可能である。

(3) 従来のキー順フアイルの構成法、例えばＢ木
探索法のような場合と違い、キー順フアイルの
構成要素として、他のデータの所在アドレスを
記憶するような“ポインター”を持たないた
め、フアイルの構造として破壊されにくく、ま
た、破壊されたとしても、局所的なデータ欠損
のレベルにとどまり、フアイル全体のダウンに
至る危険性は極めて少ない。

〔発明の効果〕

本発明によるとフアイルへの入力あるいは出力
を高速におこなうことができる。

【図面の簡単な説明】

第１図は索引付データの出入力装置の概要を示
すブロツク図を、第２図、第３図は本発明の基本
的なデータ構成とその説明図を、第４図Ａ，Ｂ、
第５図はレコードの追加、検索の説明図を、第６
図、第７図は処理ステツプの機能説明図を、第８
図はレコード内のレコードの並びの状態変化図
を、第９図はレコード追加時の移動レコード数、
第１０図、第１１図は第８図、第９図に対応して
いて配分規則を変えた場合を、第１２図はロード
比率と追加時のオーバヘツドの関係を示す。 １……レコード格納メモリ、２……レコード空
実管理ビツトマツプ・メモリ、３……フアイルデ
イレクトリ、４……制御装置、５……処理要求モ
ード・レジスタ、６……キー情報記憶バツフア・
メモリ、７……レコード記憶バツフア・メモリ、
８……フアイル個有情報、９……処理要求信号
（モード）、１０……処理完了信号、１１……キー
情報、１２……レコード・データ、１３……ビツ
トマツプ・アドレス、１４……レコード空実情
報、１５……レコード・アドレス、１６……キー
情報、１７……レコード・データ、１８……フア
イル、１９……索引付きデータ入出力装置。

Claims (1)

1. 【特許請求の範囲】 １ 記憶装置へのデータの入力を管理する方法に
   おいて連続する記憶領域上に記録可能な記憶領域
   単位を複数ケース有し、該記憶単位ごとに記録が
   保持されているか否かを識別管理し、該記録が記
   憶領域上において空実状態が平均的に散在するよ
   うにし、かつ、記録の並びが記録を識別し、かつ
   あらかじめ定められた評価により順序付けされた
   索引情報であるキー情報の値の順序となるように
   各記録を入力配置し格納することを特徴とするデ
   ータの入力管理方法。 ２ 前記特許請求の範囲第１項に記載のデータの
   入力管理方法において、該記憶領域上へ新たな記
   録を追加登録するとき、新たな記録のキー情報の
   値と、既に登録されている記録のキー情報の値と
   を比較し、その値の順序関係より、新たな記録を
   登録すべき空きの記憶領域の範囲を求め、該求め
   られた空きの記憶領域の範囲内に記録入力するこ
   とを特徴とするデータの入力管理方法。 ３ 前記特許請求の範囲第２項記載において、該
   新たな記録を登録すべき記憶領域に空きがない場
   合には、記憶領域上の別の空き領域へ既に登録さ
   れている記録群を、そのキー情報の値の順序が変
   わらないように順次移動させ、新たな記録を登録
   すべき空きの記憶領域を作成し、該新たな記憶領
   域内へ、記憶領域の空実状態が均一的に散在する
   状態となるように新たな記録を追加すべき記憶単
   位を決定し、当該記憶単位へ新たな記録を登録す
   ることを特徴とするデータの入力管理方法。 ４ 前記特許請求の範囲第１項記載において、新
   たな記録を追加する場合にキー情報の値の順序関
   係を保持し、新たな記録を登録すべき空きの記憶
   領域の範囲の直前及び直後に既に登録されている
   記録のキー情報の値と新たな記録のキー情報の値
   との関係により、空き領域をある定められた配分
   規則で分割する様に新たな記録を登録すべき記憶
   単位を決定することを特徴とするデータの入力管
   理方法。 ５ 特許請求の範囲第１〜４項に記載のデータの
   入力管理方法において、該記憶単位毎の１ビツト
   のフラグ情報を、記憶領域中の記憶単位の並びに
   対応した並び順で保持するビツトマツプに記憶
   し、記憶単位に記録が登録されているか否かを該
   ビツトマツプ記憶のフラグの状態（オン／オフ）
   によつて管理し、記録の登録時にはビツトマツプ
   記憶の該当するフラグをオンし、記録の削除時に
   は該当するフラグをオフし、空き又は実の記憶単
   位の検索時には、ビツトマツプ記憶上のフラグを
   走査することにより、空き記憶領域或いは、実の
   記憶領域を求めることを特徴とするデータの入力
   管理方法。 ６ 特許請求の範囲第１項に記載において、新た
   な登録要求のあつた記録を一旦格納し保持する記
   録緩衝領域に登録することを特徴とするデータの
   入力管理方法。