JPS63262735A - ファイル管理システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 索引ファイルの二次インデックスのレコード構造を、　
（副キー）＋（主キー）＋（レコードアドレス）とする
ことにより、副キーによる検索処理時間を短縮するもの
である。

〔産業上の利用分野〕

本発明は、データ処理システムにおけるファイル管理方
式に関するものであり、特に二次インデックスをもつ索
引ファイルのファイル管理方式に関する。

〔従来の技術〕

主キーにより検索可能に構成された索引ファイルのデー
タを、副キーによって検索可能にするためには、従来、
副キーと主キーとを対照させた二次インデックスを設け
、これを用いて副キーを主キーに変換してから索引ファ
イルを検索する必要があった。第５図にその概要を示す
。

第５図において、１は索引ファイル、２は主ファイル、
３は主インデックス部、４はデータ部。

５は二次インデックスファイル、６は二次インデックス
である。

動作は次のように行われる。

■　副キーによりレコードを参照あるいは更新する処理
要求があったとき、まず二次インデックスファイル５の
二次インデックス６を用いて、その副キーに対応する主
キーを求める。なお、主キーは重複のないユニークキー
として設定されるが。

副キーは一般にユニークキーであるとは限らない。

■　次に主ファイル２の主インデツクス部３を用いて、
データ部４における主キーをもつレコードのアドレスを
求める。

■　得られたレコードのアドレスを用いてデータ部４を
アクセスし、目的のレコードの取り出しあるいは更新を
行う。・ このような二次インデックスをもつ索引ファイルではに
二次インデックスのレコード構造が（副キー）＋（主キ
ー）となっている。この場合、主ファイルにデータのレ
コードを追加したり、それから解除を行ったときには、
対応する副キーと主キーの対のレコードを二次インデッ
クスに追加したりあるいはそれから削除する必要がある
が、主ファイル内のページあるいはブロックを分割した
ときなどに生じるレコードの移動に対しては、二次イン
デックスは無関係にできる利点をもつ。

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

従来の（副キー）＋（主キー）のレコード構造をもつ二
次インデックスを用いる索引ファイルでは、副キーでフ
ァイル検索を行う場合、二次インデックスの検索と、主
インデツクスの検索の２段階の前処理を行ってからよう
やくデータ部を検索することが可能になるため、検索処
理に時間がかかるという問題があった。

これに対してはに二次インデックスのレコード構造を、
　（副キー）＋（レコードアドレス）にして、主インデ
ツクスの検索を行わずに直接データ部を検索し、処理時
間を短縮する方式も考えられるが、この場合には、主フ
ァイル内でのレコードの追加、削除のときのみでなく、
上述し、たレコードの移動が行われたときにも、二次イ
ンデックスの更新が必要となり、ファイル管理の負担が
大きくなって処理効率が低下するという問題があった。

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

本発明は、二次インデックスを副キー、主キー。

レコードアドレスの３つで構成し、副キーから主キーお
よびレコードアドレスのいずれも参照できるようにする
。そして基本的な動作では副キーから直接レコードアド
レスを得て、データ部の該当するレコードが迅速に得ら
れるようにする。

さらに本発明では、二次インデックスの更新を一部まと
めて行うことにより、処理を効率化する。

そのため−次インデックスから得た主キーと、データ部
から得たレコードの主キーとを比較し、二次インデック
スの正当性をチェ７クし、二次インデックスにデータフ
ァイルの更新状態が反映されていない場合は、主インデ
ツクスを用いて主ファイルを再検索することを可能にす
る。

第１図に１本発明の原理的構成を例示的手段を用いて示
す。

図において。

８は、索引ファイルであり二次インデックスファイルと
主ファイルとを含む。

９は、二次インデックスファイルである。

１０は、二次インデックスであり、副キーに対応する主
キーおよびデータのレコードアドレスを与える。

１１は、主ファイルである。

１２は、主インデツクス部であり、主キーに対応するデ
ータレコードのページアドレスを与える。

１３は、データ部であり、ページ管理されたレコードに
より構成される。各レコードは主キー。

副キー、データからなる。

１４は、ファイル管理部であり５索引フアイル８の管理
およびアクセス処理を行う。

１５は、二次インデックス検索部であり、入力された副
キーにより二次インデックス１０を検索して、対応する
データのレコードアドレスあるいは主キーを得る処理を
行う。

１６は、デｉり検索部であり、データアドレスによりデ
ータ部１３を検索し、対応するデータレコードの参照、
あるいは追加、削除、変更する処理を行う。

１７は、正当性チェック部であり、データ検索部１６が
検索した結果のデータレコードの主キーと、二次インデ
ックス検索部１５が検索した結果のレコードアドレスに
対応する主キーとを比較し。

データレコードの正当性、すなわち二次インデックス１
０の更新性をチェックする。データレコードが正当でな
い場合には、主インデツクス検索部１８およびデータ検
索部１６に指示し、主インデツクス部１２からページア
ドレスを得て再検索を行わせる。

１８は、主インデツクス検索部であり、主キーにより主
インデツクス部１２を検索して、データアドレスを得る
処理を行う。

１９はインデックス反映処理部であり、データ部１３に
おいてデータレコードの追加、削除、あるいはページの
分割９合併によるレコード移動などのファイル更新が行
われた場合、主インデツクス部１２と二次インデックス
１０にその内容を反映させる処理を行う。ただし、二次
インデックス１０については、その都度反映を行うのは
追加。

削除のあったレコードについてのみとし、ページ分割２
舎併にともない移動を生じたレコードについてはその反
映を一時保留し、その結果として再検索が行われる回数
が所定の回数に達するまで待ってまとめて更新を行う。

〔作用〕

第１図において、■ないし■は、副キーを用いた索引フ
ァイルの検索処理手順を示している。次に■ないし■に
したがって本発明の詳細な説明する。なお９便宜上、デ
ータの参照が行われる場合を中心に説明する。

■　利用者は、副キーを指定して、ファイル管理部工４
にデータの参照処理を要求する。

■　二次インデックス検索部１５は、二次インデックス
１０を参照し、指定された副キーをレコードアドレスに
変換し、データ検索部１６に通知する。

■　データ検索部１６は、レコードアドレスを用いてデ
ータ部１３をアクセスし、該当するデータレコードを読
み出す。

■　正当性チェック部１７は、データ検索部１６がデー
タ部１３から読み出したデータレコードの主キーと、二
次インデンクス検索部１５が二次インデックス１０から
読み出した主キーとを比較し、一致していれば正当とし
、不一致であれば主インデツクス検索部１８とデータ検
索部１６に再検索を指示する。

■　主インデツクス検索部１８は、二次インデックス検
索部１５から出力された主キーを用いて。

主インデツクス部１２から対応するデータのページアド
レスを読み出す。

■　データ検索部１６は、主インデックス検索部１日か
ら出力されたページアドレスを用いてデータ部１３を再
検索し、目的のデータレコードを読み出す。

■　インデックス反映処理部１９は、データ検索部１６
がデータ部１３についてデータレコードの追加あるいは
削除を行ったときそのデータレコードと、さらにそれに
伴いページあるいはブロックの分割、併合が行われた場
合に生じるレコードの移動とを、主インデツクス部１２
と二次インデックス１０に反映させる処理を行う。

なお二次インデックスｌＯに対しては、レコードの移動
を直ちに反映させずに一時保留し、その結果二次インデ
ックス１０と主ファイル１１との間に矛盾が生じて検索
が失敗し、再検索が行われるので、その再検索回数が一
定数に達するまで待ってからまとめて反映処理を行う。

このように１反映処理をまとめて行うことにより。

検索効率の低下を抑制することができる。

〔実施例〕

第２図ないし第４図を用いて本発明の実施例を説明する
。

第２図は、ページ管理された索引ファイルの１構成例を
示し、２１は二次インデックスファイル、２２はインデ
ックス部、２３はルートページ、２４．２４’はリーフ
ページ、２５はデータ部、２６はページ、２７．２７’
は二次インデックスレコード、２日は主ファイル、２９
はインデックス部、３０はルートページ、３１３１′は
リーフページ、３２はデータ部、３３．３３′はページ
、３４．３４’、３４″はデータレコードを表している
。

二次インデックスレコード２７．２７’の構造は、”　
（副キー）＋（主キー）＋（レコードアドレス）”であ
り、主ファイル２８のデータレコード３４．３４’、３
４″の構造は、″　（主キー）＋（副キー）＋（データ
）”となっている。

図示例では、主キーがＡ、Ｂ、Ｃ，・・・、Ｚの値をと
り、副キーは、１０，２０．　・・・、８ｏ。

・・・の値をとっている。

二次インデックスファイル２１のインデックス部２２は
、データ部２５のページ２７．２７’のページアドレス
を、ルートページ２３とリーフページ２４．２４’の２
段階で参照できるように構成されている。たとえばルー
トページ２３は、副キーＫｓが、Ｋｓ≦３０と３０＜Ｋ
ｓ≦５０とのものを切り分けて、それぞれリーフページ
２４．２４’のアドレスを与え、リーフページ２４は、
副キーＫｓがＫｓ≦２０のページとＫｓ＝３０のページ
を切り分けてレコードのページアドレスを与える。

主ファイル２８のインデックス部２９も同様な方法で、
ルートページ３０とリーフページ３１．３１’とを用い
て、２段階で主キーからデータ部３２のページのアドレ
スを与えるように構成されている。

第３図は、第２図に示された索引ファイルの状態におい
て、主キーＹ　ＡＶをもつデータレコードを追加し、そ
の際ページ分割が生じた場合の状態変化を示している。

図示のように、主ファイル２日において、データ部３２
めページ３３が分割されて、３ごと３３となり、それに
伴い、インデックス部２９のリーフページ３１に、主キ
ーマＡマとデータ部のページアドレスとの対応を与える
エントリが追加されている。この場合、二次インデック
スファイル２１に対する反映処理は保留されており、前
述したように、後に再検索回数が一定回数に達したとき
にまとめて実行される。

第３図は、副キーマ１０マを用いた検索処理の例を、フ
ローで示したものである。

次に第４図のフローにより、副キーマ１０マを指定した
場合の検索処理例を説明する。

まず、二次インデックスファイル２１のインデックス部
２２のルートページ２３を読み込み■、副キー’１０マ
を用いてそのエントリを検索し５副キーマ１０マを包含
するり一フページ２４を見出す■。

次に、このリーフページ２４を読み込み■。

副キーマ１０’を用いてそのエントリを検索し。

副キーｖ１０ｖを包含するデータ部２５のページ２６を
見出す■。

次に、このページ２６を読み込み■、副副キーマロ０マ
もつ二次インデックスレコード２７を見出し、主キーマ
Ｂマとレコードアドレス（ｒｉｄ）を得るの。

次に、主ファイル２８のデータ部３２から。

ページ３３を読み込み■、目的のデータレコード３４を
得る［Ｆ］。

ここで二次インデックスレコード２７から得た主キー（
ｖＢマ）とデータレコード３４から得た主キーとを比較
し■、一致していればＦＯＩＩＮＤ（検索成功）となり
、不一致であれば次に主キーマＢマを用いて再検索する
ため■を実行する。

まず主ファイル２８のインデックス部２９から、ルート
ページ３０を読み込み■、エントリを検索して主キーＷ
　Ｂ　Ｙを包含するリーフページ３１を得る■。

次に、リーフページ３１を読み込みの、その中から主キ
ーマＢマをもつデータレコードを包含するデータ部３２
のページ３３を得る［相］。

次に、ページ３３′′を読み込みＯ１主キーＹＢマをも
つ目的のデータレコードを検索する■。

主キーマＢマをもつデータレコードが存在すればＦＯＵ
ＮＤ　　（検索成功）、存在しなければＮＯＴ　Ｆｏｌ
ｌＮＤ　（検索失敗）となる［Ｆ］。

〔発明の効果〕

本発明によれば、二次インデックスに、副キーおよび主
キーとともにデータレコードのアドレスが設定されてい
るため、データレコードの検索を極めて能率的に行うこ
とができ、しかも。

主キーを用いた再検索が容易であることから。

ページの分割、併合に伴うレコード移動が生じてもそれ
を二次インデックスに反映する処理を遅らせ、主ファイ
ルと二次インデックスとの間の矛盾が、ある程度大きく
なった適当なタイミングで実行することも可能にされ、
一層検索処理を効率化することができる。

【図面の簡単な説明】

第１図は本発明の原理的構成図、第２図は本発明の１実
施例による索引ファイルの構成例を示す図、第３図は第
２図に示す索引ファイルにおけるデータレコードの追加
により生じたページ分割の例を示す図、第４図は第２図
の索引ファイルを対象とする検索処理例のフロー図、第
５図は二次インデックスを用いる検索処理の従来方式例
を示す図である。 第１図中。 ｌＯ二二次インデックス １２：主インデツクス部 １３：デーク部 １４：ファイル管理部

Claims (1)

1. 【特許請求の範囲】 二次インデックス（１０）をもつ索引ファイル（８）と
   、ファイル管理部（１４）とをそなえたデータ処理シス
   テムにおいて、 二次インデックス（１０）は、副キーごとに主キーおよ
   びデータのレコードアドレスを対応づけて管理し、 ファイル管理部（１４）は、副キーに基づく検索処理要
   求に対して、その副キーにより二次インデックス（１０
   ）を検索し、対応するデータのレコードアドレスを得て
   直ちにデータのレコードをアクセスする処理を行うこと
   を特徴とする二次インデックスをもつ索引ファイルの管
   理方式。