JPH0535554A - フアイル処理装置 - Google Patents

Abstract

(57)【要約】 【目的】 追加レコードを空領域に挿入する際に、可能
な限りキー順あるいはそれに近い状態となる様な空領域
を選んで追加レコードを挿入する。 【構成】 磁気ディスク装置１２にはキー順に配列され
た複数レコードから成るファイルが記憶されている。Ｃ
ＰＵ１１はレコードを追加する際、追加レコードのキー
とファイル内レコードのキーとを比較し、キー配列上追
加レコードのキーに近いキーを持ったレコードを検索す
る。次で、ＣＰＵ１１はこの検索レコードの記憶位置に
近いファイル内の空領域を検索し、この空領域に追加レ
コードを書き込む。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明はオフィスコンピュー
タ、情報処理システム等のファイル処理装置に関する。

【０００２】

【従来の技術】従来、オフィスコンピュータ等のファイ
ル処理装置において、ファイル内からレコード削除が行
われると、削除されたレコードの格納部分は空領域とな
る。この空領域は新しいレコードの追加により再利用さ
れる。いま、図５に示す如く、ファイル内の各レコード
はキー「１００１」、「１００３」……を持ち、キー順
に昇順配列されている場合、レコード番号「２」、
「４」、「５」、「８」に対応する各領域が空領域とな
っている。ここで、新しい追加レコードが入力される
と、ファイル内を検索し、空領域が有れば最初に検索し
た空領域に追加レコードを書き込む。したがって、例え
ば「１００８」、「１００５」、「１００４」、「１０
０２」のキーを持ったレコードが順次入力されると、フ
ァイル内容は図６に示す如く、レコード番号「２」の空
領域に「１００８」のキーを持ったレコードが書き込ま
れ、……レコード番号「８」の空領域に「１００２」の
キーを持ったレコードが書き込まれる。

【０００３】

【発明が解決しようとする課題】ところで、ファイル内
の全レコードをキー順（昇順）に読み出す場合、レコー
ドアクセスはレコード番号で「１→８→３→５→４→６
→７→２→９」の順序となり、レコード番号「１→２→
３……→９」の様に正順にアクセスする場合に比べて次
レコードへのポジショニングに時間を要する。即ち、全
レコードを昇順に読み出す場合、図６の例では次レコー
ドへの移動ステップ数は合計３０ステップとなり、レコ
ード番号「１」から「９」まで正順にアクセスする場合
の合計ステップ数「８」に比べて４倍近くの時間を要す
ることになる。これはレコード追加時に最初の空領域か
ら追加レコードを順に書き込んでゆく為、当初、昇順配
列されていた各レコードがキー順とは関係せずにランダ
ムなレコード配列となってしまうことに起因する。そこ
で、レコード追加が行われる毎にファイル内容を再編成
し、昇順にレコードを配列し直しておけば、全レコード
を昇順に読み出す場合、高速読み出しが可能となるが、
今度はソートにかなりの時間が消費されてしまうという
新たな問題を生ずる。してみれば、追加レコードを空領
域に挿入する際、可能な限りキー順あるいはそれに近い
状態となる様な空領域を選んで追加レコードを挿入でき
れば、ファイル内容をキー順にソートしておかなくとも
全レコードをキー順に読み出す際、その高速化を図るこ
とが可能となることは明らかである。この発明の課題
は、追加レコードを空領域に挿入する際に、可能な限り
キー順あるいはそれに近い状態となる様な空領域を選ん
で追加レコードを挿入できるようにすることである。

【０００４】

【課題を解決するための手段】この発明の手段は次の通
りである。ファイル記憶手段１（図１の機能ブロック図
を参照、以下同じ）はキー順に配列された複数レコード
から成るファイルを記憶するディスク装置等である。第
１の検索手段２はファイル記憶手段１にレコードを追加
する際、追加レコードのキーとファイル内レコードとの
キーとを比較し、キー配列上追加レコードのキーに近い
キーを持ったレコードを検索する。例えば、キーが一連
の数値列データである場合、キー順に配列された複数レ
コードのうち追加レコードのキーよりも値が小さいキー
を持ったレコードを検索する。第２の検索手段３は第１
の検索手段２によって検索されたレコードの記憶位置に
近いファイル内の空領域を検索する。レコード追加手段
４は第２の検索手段３によって検索された空領域に追加
レコードを書き込む。

【０００５】

【作用】この発明の手段の作用は次の通りである。い
ま、図５に示すファイルに対してレコードを追加するも
のとする。ここで、キー「１００８」を持ったレコード
を追加する際、第１の検索手段２は追加レコードのキー
とファイル内レコードのキーとを比較しキー配列上追加
レコードのキーに近いキーを持ったレコードを検索す
る。この場合、例えば追加レコードのキー「１００８」
よりも小さいキー「１００７」を持ったレコードが検索
される。すると、第２の検索手段３はこのレコードの記
憶位置に近い空領域を検索する。この場合、レコード番
号「８」の空領域が検索される為、レコード追加手段４
はキー「１００８」の追加レコードをこの空領域に書き
込む。したがって、追加レコードを空領域に挿入する際
に、可能な限りキー順あるいはそれに近い状態となる様
な空領域を選んで追加レコードを挿入することができ
る。

【０００６】

【実施例】以下、図２〜図４を参照して一実施例を説明
する。図２はファイル処理装置のブロック構成図であ
る。ＣＰＵ１１は各種プログラムにしたがってこのファ
イル処理装置の全体動作を制御するもので、磁気ディス
ク装置１２内のファイルはディスク制御部１３を介して
ＲＡＭ１４に読み出され、またＲＡＭ１４内のファイル
はディスク制御部１３を介して磁気ディスク装置１２に
登録される。ここで、磁気ディスク装置１２からＲＡＭ
１４に読み出されたフアイルに対してレコード削除をキ
ー入力部１５から指定すると、ＣＰＵ１１は指定レコー
ドをＲＡＭ１４から削除する為、そのレコード格納域は
空領域となる。ＣＰＵ１１はキー入力部１５から新たな
レコードを追加入力すると、ファイル内の空領域を選択
してその空領域に追加レコードを書き込むが、空領域の
選択は一定の規則にしたがって行われる。

【０００７】次に、本実施例の動作を説明する。図３は
レコード追加時の動作を示したフローチャートである。
先ず、キー入力部１５から追加すべきレコードを入力す
る（ステップＳ１）。ＣＰＵ１１は予め指定された更新
対象のファイルを磁気ディスク装置１２からディスク制
御部１３を介してＲＡＭ１４に読み出す（ステップＳ
２）。

【０００８】この状態において、ＣＰＵ１１は先ず追加
レコードとして入力されたレコードと同じキーを持った
レコードがファイル内に存在するか否かをチェックする
（ステップＳ３）。ここで、同一キーを持ったレコード
がファイル内に既に存在していれば重複レコードとなる
為にエラー終了となるが、存在していなければステップ
Ｓ４に進み、ファイル内に空領域が存在するか否かをチ
ェックする。ここで、空領域とはレコード削除によって
形成された領域であり、ファイル内に空領域が無けれ
ば、ステップＳ９に進み、ファイルの最終書き込み位置
から追加レコードを書き込み、ファイルの後に拡張追加
を行い、処理終了となる。

【０００９】一方、ファイル内に空領域が１つでも存在
していれば、追加レコードのキーとファイル内のキーと
を比較し、追加レコードのキーよりも小さい値のキーを
持ったレコードを検索し、そのレコード格納領域に対応
するレコード番号を求める（ステップＳ５）。ここで、
図５に示すファイルに対してキー「１００８」のレコー
ドを追加する場合、追加レコードのキーよりも小さい
「１００７」のキーを持ったレコードが検索され、その
レコード番号「７」が求められる。次に、このレコード
番号より大きいレコード番号の空領域を検索し、そのレ
コード番号を求める（ステップＳ６）。いまステップＳ
５で求められたレコード番号「７」より大きい空領域の
レコード番号は図５に示す如く「８」となる。なお、ス
テップＳ６の条件を満足する空領域がファイル内に存在
しない場合にはステップＳ７でそのことが検出されてス
テップＳ９に進み、ファイルの後に追加レコードが書き
込まれる。一方、ステップＳ６の条件を満足する空領域
がファイル内に存在していれば、その空領域に追加レコ
ードを書き込む（ステップＳ８）。したがって、この場
合、レコード番号「８」の空領域にキー「１００８」を
持った追加レコードが書き込まれることになる。

【００１０】次に、「１００５」のキーを持ったレコー
ドを追加入力すると、上述の場合と同様に、追加レコー
ドのキーよりも小さいキーを持ったレコードを検索し、
そのレコード番号「３」を求める（ステップＳ５）。次
でこのレコード番号「３」よりも大きいレコード番号の
空領域を検索し、この空領域のレコード番号「４」を求
める（ステップＳ６）。このようにして空領域が決定さ
れると、このレコード番号「４」の空領域にキー「１０
０５」の追加レコードが書き込まれる。

【００１１】以下、同様に、キー「１００４」、「１０
０２」を持ったレコードをこの順序で追加入力すると、
図５に示すファイルは図４に示すファイル構成となり、
レコード番号「４」、「５」内のレコードを除き、ファ
イル内の各レコードは昇順配置されたものとなる。

【００１２】この結果、図４に示す如く、次レコードへ
の移動ステップ数の合計は１０ステップとなり、従来に
比べて１／３となり、それだけ高速読み出しが可能とな
る。

【００１３】なお、上記実施例は図３のステップＳ５で
追加レコードのキーよりも小さいキーを持ったレコード
を検索し、ステップＳ６でこの検索レコードのレコード
番号よりも大きいレコード番号を持った空領域を検索す
るようにしたが、これとは逆に、先ず、追加レコードの
キーよりも大きいキーを持ったレコードを検索し、次い
でこのレコードが格納されているレコード番号よりも小
さいレコード番号を持った空領域を検索するようにして
もよい。

【００１４】

【発明の効果】この発明によれば、追加レコードを空領
域に挿入する際に、可能な限りキー順あるいはそれに近
い状態となる様な空領域を選んで追加レコードを挿入す
ることができるので、ファイル内容を予めキー順にソー
トしておかなくとも全レコードをキー順に読み出す際、
高速読み出しが可能となる。

【図面の簡単な説明】

【図１】この発明の機能ブロック図。

【図２】実施例を示したファイル処理装置のブロック構
成図。

【図３】レコード追加時の動作を示したフローチャー
ト。

【図４】レコード追加後のファイル内容とこのファイル
から全レコードをキー順に読み出す際の移動ステップ数
を示した図。

【図５】従来例を説明する為の図で、レコードが削除さ
れたファイル内の空領域を示した図。

【図６】図５で示したファイル内の空領域にレコードを
追加した場合のファイル内容を示すと共に、このファイ
ルから全レコードをキー順に読み出す際の移動ステップ
数を示した図。

【符号の説明】

１１ ＣＰＵ １２ 磁気ディスク装置 １３ ディスク制御部 １４ ＲＡＭ １５ キー入力部

Claims (1)

1. 【特許請求の範囲】 【請求項１】キー順に配列された複数レコードから成る
   ファイルを記憶するファイル記憶手段と、 このファイル記憶手段にレコードを追加する際、追加レ
   コードのキーとファイル内レコードのキーとを比較し、
   キー配列上追加レコードのキーに近いキーを持ったレコ
   ードを検索する第１の検索手段と、 この第１の検索手段によって検索されたレコードの記憶
   位置に近いファイル内の空領域を検索する第２の検索手
   段と、 この第２の検索手段によって検索された空領域に追加レ
   コードを書き込むレコード追加手段と、 を具備したことを特徴とするファイル処理装置。