JPH02216554A - 索引順編成ファイルの再編成方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、ハードディスクを接続した索引順編成ファイ
ルを有する情報処理システムにおける索引順編成ファイ
ルの再編成方式に関する。

〔従来の技術〕

従来のこの穐の索引順編成ファイルの再編成方式に使用
されている索引順編成ファイルの構造について図面を参
照して説明する。

第８図は、索引順編成ファイルの構造を示す図であり、
索引部１と、データ部２とから構成される。

第９図は、第８図の索引順編成ファイル索引部１の階層
構造を示す図であり、第２レベル索引ブロツクである１
と、第２レベル索引ブロツクである２、３と、最下位レ
ベル索引ブロックである４゜５，６と、データレコード
７．８．９．１０から構成される。

第１０図は、第８図の索引順編成ファイルの削除レコー
ドチエインを示す図であり、削除レコードは、削除レコ
ードであることを示す１６進コード″ＦＦ”コード１と
、次の削除レコードのアドレスを示すポインタ２とから
構成されている。また、最後の削除レコードは、次の削
除レコードのアドレスを示すポインタの場所に削除レコ
ードチエインの最後であることを示す“Ｆ　Ｆ　”コー
ド３が有り、削除レコードであることを示す“ＦＦ”コ
ード１とチエインの最後であることを示す°“ＦＦ”コ
ード３とから構成されている。

第１１図は、第８図の索引順編成ファイルの同一キーレ
コードチエインを示す図であり、同一キーレコードは、
データレコード１とその後に直前の同一キーレコードの
アドレスを示すポインタ２と直後の同一キーレコードの
アドレスを示すポインタ３とから構成されている。

第１２図は、第８図の索引順編成ファイルのレコード追
加時の索引部の索引ブロック分割を示した図であり、追
加前のレコードキー１０，２０゜３０．４０からなる索
引ブロック１と２５の値をもつ追加レコードキー４と、
追加後の索引ブロック２，３とから構成される。

次に、このように構成された索引順編成アイルの構造に
ついて説明する。

第８図を参照すると、索引順編成ファイルは、先頭に索
引部１があり、データ部２はファイルの後ろにある。デ
ータレコードは、ファイルの後ろから順に入力されてい
く。

第９図を参照すると、索引順編成ファイルの索引部は、
階層構造となっている。第ルベルの索引ブロックは、そ
れぞれ第２レベルの索引ブロックの先頭を指すポインタ
と、キー値を持っている。

第２レベルの索引ブロックはそれぞれの第３レベルの索
引ブロックの先頭を指すポインタとキー値を持っている
。１つの索引ブロックに入るキー値とポインタの数は決
まっているので、すべてのキーを網羅できるまで階層は
深くなっていく、最下位レベルの索引ブロックはそれぞ
れのデータレコードを指すポインタとキー値を持ってい
る。ポインタとキー値の組を索引エントリと呼ぶ。

第１０図を参照して削除レコードについて説明する。削
除レコードは、先頭に１６進コード“ＦＦ”が入力され
る。その後ろに、その次の削除レコードを指すポインタ
が入力される０次々に削除レコードをポイン°りで指し
ていき、最後の削除レコードはポインタの場所に１６進
コード“ＦＦ”が入力される。

第１１図を参照して同一キーレコードチエインについて
説明する。同一キーレコードを許すことにしてアロケー
トした場合は、指定したレコード長より、８バイト長い
レコード長でアロケートされる。データレコードの後ろ
に次の同一キーレコードを指すポインタであるＮポイン
タと、前の同一キーレコードを指すポインタであるＰポ
インタが付加される。同一キーを指すポインタは、次々
とチエインされていき、最後の同一キーレコードのＮポ
インタは先頭の同一キーレコードを指す。

先頭の同一キーレコードのＰポインタは、最後の同一キ
ーレコードを指す、同一キーレコードは、このようにチ
エインでつながれている。

第１２図を参照して索引順編成ファイルの索引ブロック
の分割方法を説明する。１つの索引ブロックの中に入る
索引エントリの個数は決まっている。索引エントリは、
キー値の昇順に並んで入る。

本例では、キー値２５を持つデータレコードが追加され
たため、索引エントリもキー値２５の分が追加されると
ころである。この例では、１つの索引ブロックに４つま
でしか索引エントリが入らない為、２５を追加するため
に、２つの索引ブロックに分ける必要があるので、２つ
の索引ブロック２３と２４を作成する。

以上のような特徴をもつ索引順編成ファイルのデータレ
コードから完全な索引順編成ファイルを作成するために
は、データレコードを１件ずつ処理し、レコードの追加
という形で１件ずつキー部を作りなおしていて、また、
１件ずつ同一キーチエイノを張りなおしていた。

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

従来の索引順編成ファイルの再構成処理は、索引順編成
ファイルに削除レコードチエイン、同一キーレコードチ
エイン、同一キーレコードチエインが存在するなめ、デ
ータレコードを１件する処理していて多大な時間がかる
という欠点がある。

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

本発明の索引順編成ファイルの再編成処理方式の構成は
、データ格納ファイルである目的ファイルと、その目的
ファイルをユーザメモリに格納する目的ファイル入出力
制御機構と、ワークファイルサイズを計算するワークフ
ァイルサイズ計算機構と、メモリ上で全レコードから削
除レコードを取り除く削除レコードのアライン制御機構
と、索引順編成ファイルデータレコードからキーを抽出
するキー抽出機構と、抽出されたキーを前記メモリ上で
ソートするキーソート機構と、このキーソート機構によ
り作成されたキーの列を基に前記メモリ上でキーをマー
ジするマージ機構と、ソートされたキーを前記メモリか
ら前記ワークファイルに格納するワークファイル入出力
制御機構と、前記メモリ上で索引順編成ファイルのキー
部を作成するキー部作成機構と、前記メモリ上でデータ
レコードの同一キーチェーンを張る同一キーチェーン張
り機構とを含んで構成されることを特徴とする。

〔実施例〕

次に、本発明について図面を参照して説明する。

第１図は本発明の一実施例を示す構成図であり、ワーク
ファイルサイズ計算機構１、削除レコードアライン機構
２、データレコードからキーを取り、出す機構３、キー
のソート機構４、キーのマージ機構５、キー部作成機構
６、同一キーチェイン張り機構７、ユーザメモリ８、ワ
ークファイル入出力機構９、ワークファイル１である１
２、ワークファイル２である１３、ワークファイル３で
ある１４、目的ファイル入出力機構１０、目的ファイル
１１から構成される。

第２図は、削除レコードのアライン方法を示す図であり
、目的ファイル３、ユーザメモリ中の入力データバッフ
ァ１、出力データバッファ２から構成される。

第３図は、データレコードからキーを取りだし、キーを
ソートする方式を示す図であり、ユーザメモリ中のデー
タレコード入力バッファ１、ソート用バッファ２、ソー
トされたキー用バッファ３、目的ファイｌし４、ワーク
ファイル１である５から構成される。

第４図は、何本かにソートされたキーの列を４本ずつ入
力していき、１本にソートしていくマージ機構方式を示
す図であり、ユーザメモリ中の入力バッファ１である１
、入力バッファ２である２、入力バッファ３である３、
入力バッファ４である４、出力バッファである５、ワー
クファイル１である６から構成される。

第５図は、４本にソートされたキーを１本にソートシ同
一キー情報テーブルを作成する方法を示す図であり、ユ
ーザメモリ中の入力バッファ１であるｌ、入力バッファ
２である２、入力バッファ３である３、入力バッファ４
である４、キー用出力バッファ５、同一キー情報テーブ
ル用バッファ６、ワークファイル１である７、ワークフ
ァイル２である８、ワークファイル３である９から構成
される。

第６図は、ソートされたキーからキー部を作成する方式
を示す図であり、ユーザメモリ中のキー人力バッファで
ある１、キー部作成バッファである２、ワークファイル
２である３、目的ファイルである４から構成される。

第７図は、同一キー情報テーブルから同一キーチエイン
を張っていく方式を示した図であり、ユーザメモリ中の
データレコードバッファである１、同一キー情報テーブ
ルバッファである２、目的ファイルである３、ワークフ
ァイル３である４がら構成される。

次に、このように構成された本実施例の索引順編成ファ
イルの再編成方式の動作について説明する。

まず、第１図のワークファイルサイズ計算制御機構につ
いて説明する。

ワークファイルラベルにそのファイルのレコード長、レ
コード件数、キー長が書かれているので、その値を元に
してワークファイルサイズを計算する。計算して求めた
サイズのテンポラリファイルがディスク上にとれない場
合は、本発明の処理を行うことが不可能なので、その旨
通知して処理を中断する。

索引順編成ファイルの再構成において、第１０図に示す
ような削除レコードチエインを張る作業を行うと多大な
時間がかかるため、第２図に示すようにユーザメモリを
利用して削除レコードをアラインする。

第２図に示すアライン方法を説明すると、ユーザメモリ
のすべての領域を入力バッファ領域２１と、出力バッフ
ァ領域２２とに、２分割してしまい、目的ファイル１０
から入力バッファ領域２１にデータレコードを読み切れ
るだけ一度に読んでしまう、そして、１件ずつデータレ
コードが削除レコードであるか否かを判断しながら、削
除レコードでなければ出力バッファ領域２２にデータレ
コードを移す、出力バッファ２２の最後までデータレコ
ードが入ったなら、それを−度に目的ファイル１０に書
き込む、このようにして、少ない入出力回数で高速に削
除レコードのアラインを行う。

次に、キーのソート機構を第３図を参照しながら説明す
る。目的ファイル４からデータレコードをデータレコー
ド入力バッファ３１に読み込めるだけ読み込み、そのデ
ータレコードからキーを取り出し、それにデータレコー
ドのアドレスを付加してソート用バッファ３２に入れる
。ソート用バッファ３２中では、トーナメント方式で昇
順にソートしていき、一番手さいものをソートされたキ
ー用バッファ３３に入れていき、バッファすべてが埋ま
った時点でワークファイル１である１１に出力する。同
様の作業を続け、ワークファイル１である１１にすべて
のキーをはき出す。

次に、第４図を参照しながら、ソートされたキーのマー
ジ機構を説明する。

キーのソート機構によりソートされたキーの列の何本か
が、ワークファイル１である１１に作成されている。こ
のうち４本を入力バッファ１゜２．３．４である４１，
４２．４３．４４にそれぞれ入力する。そして、入カバ
ツファエ、２゜３．４である４１．４２．４３．４４か
らそれぞれ１件ずつ一番手さいものを取りだし、４つの
中で一番手さなキーを出力バッファ４５に入れる。

同様の作業を繰り返して出力バッファ４５すべてが埋ま
ったら、ワークファイル１である１１に出力する。この
ようにして、４本を１本にソートしてしまう。

なお、この実施例では、４本として例をあげたが、これ
は、４本に限らず複数であればよい。

次に、第５図を参照して同一キーアドレス情報テーブル
を作成する方法を説明する。マージ機構により、ワーク
ファイル１である１１には４本にソートされたキーが入
っている。ワークファイル１である１１から入力バッフ
ァ１，２．３．４である５１．５２，５３．５４にそれ
ぞれソートされたキーの列４本を１本ずつ入力する。４
本のキーの列からそれぞれ１つずつ一番手さいキーを取
りだし、その４つの中から一番手さいキーをキー用出力
バッファ５５に入れる。同様の作業を繰り返す、その際
キーが同じ値のものがあったなら、その同一キーの情報
を同一キー情報テーブルに入れる。同一キー情報テーブ
ルは、同一キー情報テーブル用バッファ５６に入れてい
き、バッファがすべて埋まったら、ワークファイル２で
ある１２に出力する。この′とき、キー数をカウントし
ておく。

次に、第６図を参照してキー部を作成する方式を説明す
る。ワークファイルに出力されたキー数から、索引ブロ
ックがいくつ必要か求める事が出来る。そこから索引ブ
ロックの階層数を求める事ができ、各索引ブロックが物
理的にファイル上のどこに書かれるかのアドレスを計算
で求める事が出来る。そのキー部をメモリ上で展開して
、それを、第６図のキー部作成バッファ６２に作成する
、ユーザメモリで、キー部作成バッファ６２以外は、キ
ー人力バッファ６１として使用する。ワークファイル１
２から入力バッファいっばいを使って、−度に読めるだ
け多くのキーを入力する。

そのキーを階層構造になるようにキー部作成バッファ６
２のあらかじめ計算された場所に移す、このようにして
、メモリ上で物理的にキー部を作成して、索引順編成フ
ァイルには、完成されたキー部を一度に出力する。

以上の方法で少ない入出力回数でキー部を作成すること
が出来る。

第７図を参照して同一キーチエインを張る方法について
説明する。ユーザメモリは、データレコードバッファ７
１と同一キー情報テーブルバッファ７２の２つに分ける
。目的ファイル１２からデータレコードバッファ７１に
一度に読めるだけ読み込む、また、ワークファイル３で
ある１３から、同一キー情報テーブルバッファ７２に一
度に読めるだけ読み込む、同一キー情報テーブルを参照
してデータレコードバッファ中にあるデータレコードの
同一キーのアドレスを書き込んでいく。

現在ある同一キー情報テーブルから現在あるデータレコ
ードに同一キーアドレスを書き込める分書き込んだら、
データレコードをデータレコードバッファ７１の分、目
的ファイル１２の元あった場所に出力する。そして、次
のデータレコードを、再び、データレコードバッファ７
１に読めるだけ一度に入力し、同様に、同一キー情報テ
ーブルを参照しながら同一キーアドレスを書き込んでい
く、データレコードの最後まで進んだら次の同一キー情
報テーブルを入力し、データレコードは、再び、目的フ
ァイルの最初から入力して同一キーアドレスを書き込ん
でいく、同様の動作を繰り返し、同一キーアドレステー
ブルを最後まで参照し、かつ、データレコードを最後ま
で書き込んだ時点で完全な同一キーチエインが張られる
事になる。なお、同一キーが存在しない場合は、この作
業を行わない。

〔発明の効果〕

以上説明したように本発明は、物理的にメモリ上で索引
順編成ファイルを作成することにより、少ない入出力回
数で高速に索引順編成ファイルを再編成することができ
るという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の索引順編成ファイル再編成
方式の構成図、第２図は削除レコードのアライン方法を
示した図、第３図はデータレコードからキーを取り出し
キーをソートする方式を示す図、第４図はキーのマージ
機構を示す図、第５図は同一キーアドレス情報テーブル
を作成する方法を示す図、第６図はキー部を作成すると
きの構成図、第７図は同一キーチエインを張る方法を示
す図、第８図は索引順編成ファイルの構成図、第９図は
索引部の階層構造を示した図、第１０図は索引順編成フ
ァイルの削除レコードチエインを示す図、第１１図は索
引順編成ファイルの同一キーレコードチエインを示す図
、第１２図は索引順編成ファイルのレコード追加時の索
引部の索引ブロック分割を示す図である。 １・・・ワークファイルサイズ計算機構、２・・・削除
レコードアライン機構、３・・・データレコードがらキ
ーを取り出す機構、４・・・キーのソート機構、５・・
・キーのマージ機構、６・・・キー部作成機構、７・・
・同一キーチェイン張り機構、８・・・ユーザメモリ、
９・・・ワークファイル入出力機構、１０・・・目的フ
ァイル入出力機構、１１・・・目的ファイル、１２・・
・ワークファイル１．１３・・・ワークファイル２．１
４・・・ワークファイル３゜

Claims (1)

【特許請求の範囲】
1. データ格納ファイルである目的ファイルと、その目的フ
   ァイルをユーザメモリに格納する目的ファイル入出力制
   御機構と、ワークファイルサイズを計算するワークファ
   イルサイズ計算機構と、メモリ上で全レコードから削除
   レコードを取り除く削除レコードのアライン制御機構と
   、索引順編成ファイルデータレコードからキーを抽出す
   るキー抽出機構と、抽出されたキーを前記メモリ上でソ
   ートするキーソート機構と、このキーソート機構により
   作成されたキーの列を基に前記メモリ上でキーをマージ
   するマージ機構と、ソートされたキーを前記メモリから
   前記ワークファイルに格納するワークファイル入出力制
   御機構と、前記メモリ上で索引順編成ファイルのキー部
   を作成するキー部作成機構と、前記メモリ上でデータレ
   コードの同一キーチェーンを張る同一キーチェーン張り
   機構とを含むことを特徴とする索引順編成ファイルの再
   編成方式。