JPH0789335B2 - 索引付順編成ファイルにおけるレコード挿入および参照方法 - Google Patents

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、索引付順編成ファイルに対してキー値によ
る乱アクセスで順に並んだレコードの途中に新たなレコ
ードを挿入する場合、更にはレコード挿入により移動し
たレコードを参照する場合に好適な索引付順編成ファイ
ルにおけるレコード挿入および参照方法に関する。

（従来の技術） 一般にディスクに格納される索引付順編成ファイルは、
第４図（ａ）に示すように、インデックス部11、転置部
（副キーの転置インデックス部）12、およびデータ部13
から成る。データ部13は幾つかのデータブロック14から
成り、各データブロック14は主キー値順（ここでは昇
順）に配置される幾つかのデータレコード15、および各
レコード15毎に用意されるレコード制御ブロック（図示
せず）を含む。データレコード15は主キー値（図では数
値）および副キー値（図では英小文字）を有する。レコ
ード制御ブロックは、対応レコード15のブロック内位置
およびそのレコード長を示す。

次に、転置部12は幾つかの転置ブロック16から成る。こ
の転置ブロック16は幾つかのデータレコードを副キー値
の順にアクセスするためのもので、副キー値をレコード
として持ち、データレコードへのインデックス値を併せ
持つ（図では副キー値だけが示されている）。

またインデックス部11は、主キーのインデックス木を成
す幾つか（ここでは１つ）のインデックスブロック17お
よび副キーのインデックス木を成す幾つか（ここでは１
つ）のインデックスブロック18から成る。まずインデッ
クスブロック17は、１段下のブロック（ここではデータ
ブロック14）の中での最大の主キー値をレコードとして
持ち、そのブロックへのインデックス値を併せ持つ（図
では主キー値だけが示されている）。インデックスブロ
ック17における主キー値の並びはその値順（ここでは昇
順）となっている。次にインデックスブロック18は、１
段下のブロック（ここでは転置ブロック16）の中での最
大の副キー置をレコードとして持ち、そのブロックへの
インデックス値を併せ持つ（図では副キー値だけが示さ
れている）。インデックスブロック18における副キー値
の並びはその値順（ここでは昇順）となっている。

ここで、第４図（ａ）に示した索引付順編成ファイル
に、第４図（ｂ）に示すように主キー値が２、副キー値
がｂの新たなデータレコード25をキー値による乱アクセ
スで挿入する場合の従来方法について説明する。この場
合、レコードの並びは主キー値の昇順となるようにしな
ければならないことから、レコード25の挿入位置は、第
４図（ａ）から明らかなように主キー値が０と４の２つ
のレコード15の間となる。しかし、主キー値が０と４の
２つのレコード15が格納されているデータブロック14内
の空きスペース19が、挿入レコード25の大きさより小さ
い場合には、そのデータブロック14内にレコード25を挿
入することはできない。この場合、第４図（ｂ）に示す
ように新たなデータブロック24をディスク上に生成し、
同ブロック24に元のブロック14からほぼ半数のレコード
（ここでは主キー値が４のレコード15）を移動してブロ
ック14の空きスペースを拡張した後に（即ちブロック分
割を行った後に）、同ブロック14（主キー値が０のレコ
ード15が格納されているブロック）に目的レコード25を
挿入する。この際、ブロック14に挿入したレコード25の
副キー値ｂをもとに各副キーのインデックス木をルート
ブロック（ここではインデックスブロック18）から辿
り、その副キー値ｂのインデックス（のレコード）の追
加先となる転置部12内の転置ブロック16を探す。この副
キー置ｂは、第４図（ａ）の例では、インデックスブロ
ック18の中の最小の副キー値ｅより小さいため、この副
キー値ｅのインデックスを持つ転置ブロック16が、副キ
ー値ｂのインデックスの追加先として求められる。この
転置ブロック16には、副キー値ｅのインデックスの他
に、副キー値a,cのインデックスが存在する。ここで副
キー値ｂと副キー値a,c,eとの大小関係は、ａ＜ｂ＜ｃ
＜ｅであることから、第４図（ｂ）に示すように副キー
値c,eのインデックスが移動され、副キー値ａと副キー
値ｃの間に副キー値ｂのインデックスが追加される。

さて、上記のブロック分割の結果、主キー値が４、副キ
ー値がｇのレコード15の位置が変化する。このため、転
置ブロック16におけるそのレコード15に対するインデッ
クスのポイント先を、第４図（ａ）において矢印P1で示
す位置から、第４図（ｂ）において矢印P2で示す位置、
即ちそのレコード15の移動先（実際には移動後のレコー
ド15に対応するデータブロック24内レコード制御ブロッ
ク）に変更しなければならない。この変更のためには、
上記したレコード（挿入レコード）25の副キー値ｂのイ
ンデックスを追加する場合と同様に、各副キーのインデ
ックス木をルートブロック（ここではインデックスブロ
ック18）から辿り、変更すべきインデックスのレコード
を見付けるという操作が必要となる。しかし、この操作
には、多数のブロックを単位とするディスクアクセスが
必要となるため（一般に、ブロックがディスクアクセス
単位となる）、多大な処理時間を要していた。しかも、
上記の変更処理を行っても、対応するレコード（移動レ
コード）15が参照されない場合には、変更処理に要した
時間が無駄になってしまう。

（発明が解決しようとする課題） 上記したように従来は、索引付順編成ファイルに対する
データレコーダ挿入操作でブロック分割が発生し、以前
からデータブロックに格納されていたレコードの移動が
あると、副キーの転置インデックス部のそのレコード
（移動したデータレコード）に対するインデックスの値
を変更するために副キーのインデックス木をルートブロ
ックから辿る必要があり、多数のブロックのディスクア
クセスを要することから、処理速度が低下するという問
題があった。

したがってこの発明の課題は、索引付順編成ファイルに
対するデータレコード挿入操作でブロック分割が発生
し、以前からデータブロックに格納されていたデータレ
コードの位置が変化して、副キーの転置インデックス部
内に存在するそのレコード（移動レコード）の副キー値
のインデックスのポイント先と一致しなくなった場合に
おける処理速度の低下の防止を図ることである。この発
明の他の課題は、レコード挿入に伴って移動したレコー
ド参照が効率的に行えるようにすることである。

［発明の構成］ （課題を解決するための手段） この発明は、索引付順編成ファイルの構成要素であるデ
ータブロックに格納されている各データレコード毎に用
意されるレコード制御ブロックに、同レコード制御ブロ
ックに対応するデータレコードが新たなデータレコード
の挿入に伴うブロック分割で新たなデータブロックに移
動した場合の移動先を示す移動先情報を設定するための
移動先情報フィールドを設け、データレコードを移動し
て新たなデータレコードを挿入した場合には、移動前レ
コードに対応するレコード制御ブロック内の移動先情報
フィールドに、同レコードの移動先を示す移動先情報を
設定し、レコード挿入に伴うブロック分割で移動したデ
ータレコードの副キー値と併せて副キーの転置インデッ
クス部内に設定されている同レコードへのインデックス
を探して変更する変更処理を省略するようにしたことを
特徴とする。この変更処理は、上記移動レコードを副キ
ー値による乱アクセスで参照した場合に、その参照のた
めに用いられたレコード制御ブロック内の移動先情報フ
ィールドの設定内容に基づいて行われる。

（作用） 上記の構成によれば、レコードの挿入に伴うブロック分
割でデータレコードの移動が発生した場合、その移動先
を示す情報が元のデータブロックの対応レコード制御ブ
ロックの移動先情報フィールドに設定されるので、副キ
ーの転置インデックス部内で上記移動したデータレコー
ドの副キー値と併せて設定されている同レコードへのイ
ンデックスを探して変更する変更処理を省略しても上記
移動したデータレコードを参照することが可能となる。
即ち、ブロック分割に伴うレコード移動時の転置インデ
ックス部の変更処理が省略できるので、この種の変更処
理に伴う処理速度の低下が防止できる。また、上記の変
更処理は、移動レコードを副キー値による乱アクセスで
実際に参照した場合に行われるので、ブロック分割に伴
うレコード移動時に無条件で変更処理を行っていた従来
方法に比べて無駄な変更処理がなくなる。

（実施例） 以下、この発明の一実施例を図面を参照して説明する。
なお、第４図と同一部分には同一符号を付して詳細な説
明を省略する。

まず、図示せぬディスクに、第４図（ａ）に示した索引
付順編成ファイルと同一レコード構成の索引付順編成フ
ァイルが格納されているものとする。但し、この実施例
で用いられる索引付順編成ファイルの要素であるデータ
ブロックの構造（更に具体的に述べるならば、データブ
ロック内のレコード制御ブロックの構造）は、第４図
（ａ）に示した従来の索引付順編成ファイルのそれと異
なる。このデータブロックの構造（更にはレコード制御
ブロックの構造）について、第１図（ａ）を参照して説
明する。

第１図（ａ）において、14′は主キー値が０（副キー値
がｉ）と主キー値が４（副キー値がｇ）の２つのデータ
レコード15を持つデータブロック、31はブロック制御ブ
ロックである。ブロック制御ブロック31は、同ブロック
31が置かれるデータブロック（ここではデータブロック
14′）の空きスペース19の位置並びにサイズを示す情
報、およびデータブロックのみを参照して主キー値の順
にデータレコードをアクセスする場合のデータブロック
の繋がり（チエイン）を示す情報（即ち次のデータブロ
ック並びに前のデータブロックへのポインタ）等が設定
される。ブロック制御ブロック31には、対応データブロ
ックを識別するためのブロック識別子、例えばシーケン
シャルなブロック番号が設定されるブロック番号フィー
ルド32が設けられる。図では、フィールド32には値が10
のブロック番号が設定されている。

33は主キー値が０のレコード15（データブロック14′内
の先頭レコード）に対するレコード制御ブロック、34は
主キー値が４のレコード15（データブロック14′内の２
番目のレコード）に対するレコード制御ブロックであ
る。レコード制御ブロック34は、第１図（ａ）に示すよ
うに対応レコードのサイズ（レコード長）を示す情報を
設定するためのレコード長フィールド41、対応レコード
のデータブロック（ここではデータブロック14′）内位
置を示す情報を設定するためのブロック内位置情報フィ
ールド42、対応レコードが新たなデータレコードの挿入
に伴うブロック分割で新たなデータブロックに移動した
場合の移動先を示す移動先情報を設定するための移動先
情報フィールド43を含んでいる。レコード制御ブロック
33のフォーマットも上記のレコード制御ブロック34と同
様であり、したがって第１図（ａ）では省略してある。

ブロック内位置情報フィールド42に設定される情報は、
対応データブロックのブロック番号（図では10）と対応
レコード制御ブロック（レコード制御ブロック34）のブ
ロック番号である。レコード制御ブロック34のブロック
番号は、対応レコードがデータブロック14′内で何番目
のレコードであるかによって決り、この例では２とな
る。この番号２は、対応レコード制御ブロック34がデー
タブロック14′において後から２番目のブロックである
ことも示す。なお、対応レコードが他のデータブロック
に移動した場合には、ブロック内位置情報フィールド42
には同フィールド42の内容が無効であることを示すNULL
値（ヌル値）が設定される。一方、移動先情報フィール
ド43に設定される情報は、対応レコードの移動先のデー
タブロックのブロック番号と対応レコード制御ブロック
のブロック番号である。なお、対応レコードが他のデー
タブロックに移動されない場合には、移動先情報フィー
ルド43には第１図（ａ）に示すように同フィールド43の
内容が無効であることを示すNULL値（ヌル値）が設定さ
れる。

さて、この実施例では、第１図（ａ）に示したデータブ
ロック14′を、第４図（ａ）に示す主キー値が０（副キ
ー値がｉ）と主キー値が４（副キー値がｇ）の２つのデ
ータレコード15を持つデータブロック14に代えて用いる
ようにしている。したがって、必要があれば第４図
（ａ）において、主キー値が０と４の２つのレコード15
を持つデータブロック14を、第１図（ａ）に示すデータ
ブロック14′に置換えて参照されたい。

ここで、第１図（ａ）において、主キー値が０と４の２
つのレコード15の間に、第１図（ｂ）に示すように主キ
ー値が２、副キー値がｂの新たなデータレコード25を挿
入する必要が発生したものとする。このとき、挿入レコ
ード25のサイズが上記２つのレコード15を持つデータブ
ロック14′の空きスペース19より大きいものとすると、
従来と同様にブロック分割が発生する。即ち、まず第１
図（ｂ）に示すようにブロック番号11の新たなデータブ
ロック24′がディスク上に生成され、同ブロック24′に
元のブロック14′から主キー値が４のレコード15が移動
される。この際、データブロック24′には、移動レコー
ド15に対するレコード制御ブロック35が設定される。こ
のレコード制御ブロック35の内容は、第１図（ａ）に示
すレコード移動前（ブロック分割前）のレコード制御ブ
ロック34と、ブロック内位置情報フィールド42の内容を
除いて同一である。即ちレコード制御ブロック35のフィ
ールド42には、新たなデータブロック24′のブロック番
号11と、レコード制御ブロック35のブロック番号１とが
設定される。

一方、主キー値が４の移動レコード15に対する元のデー
タブロック14′内のレコード制御ブロック34について
は、そのままデータブロック14′に残される。そして、
上記残されたレコード制御ブロック34のブロック内位置
情報フィールド42には、第１図（ｂ）に示すようにNULL
値が設定され、同ブロック34の移動先情報フィールド43
には主キー値が４のレコード15の移動先を示す移動先情
報（ここでは、移動先データブロック24′のブロック番
号11とレコード制御ブロック35のブロック番号１から成
る情報）が設定される。さて、上記のブロック分割に伴
うレコード移動でデータブロック14′の空きスペースが
拡張されると、その空きスペースを利用して第１図
（ｂ）に示すように目的レコード25の挿入が行われ、且
つ同レコード25に対するレコード制御ブロック36が設定
される。

以上のデータレコード25挿入に伴う一連の処理終了後の
索引付順編成ファイルのデータ構造を第２図に示す。但
し、主キーのインデックス木（第４図ではインデックス
ブロック17）については本発明と直接関係しないため省
略してある。第２図において主キー値が８（幅キー値が
ａ）のデータレコード15を持つデータブロック14′は、
第４図（ａ），（ｂ）に示す主キー値が８（副キー値が
ａ）のデータレコード15を持つデータブロック15に対応
し、第２図において主キー値が12と16（副キー値がｃと
ｅ）の２つのデータレコード15を持つデータブロック1
4′は、第４図（ａ），（ｂ）に示す主キー値が12と16
（副キー値がｃとｅ）の２つのデータレコード15を持つ
データブロック14に対応する。また、第２図において、
37,38,39はそれぞれ主キー値が8,12,16のレコード15に
対するレコード制御ブロックであり、そのフォーマット
は前記したレコード制御ブロック34と同一である。

さて、この実施例では、データレコード25の挿入に伴う
一連の処理において、上記のようにブロック分割が発生
してレコードの移動が行われても、従来とは異なって、
転置ブロック16の内容変更、更に具体的に述べるならば
主キー値が４、副キー値がｇの移動レコード15に対する
転置ブロック16内のインデックスのポイント先の変更を
行わないことに注意されたい。このため、第２図におけ
る転置ブロック16内の対応インデックスのポイント先
は、矢印P3で示すように、移動前の主キー値が４のレコ
ード15（に対するレコード制御ブロック34）を指してい
る。このポイント先の変更を行わなくても、以下に述べ
るようにレコード制御ブロック（ここではレコード制御
ブロック34）の移動先情報フィールド43の内容に従っ
て、移動レコード15を参照することは可能である。な
お、この実施例では、移動レコードの参照時に上記のポ
イント先の変更を行うようにしている。

ここで、第２図に示す索引付順編成ファイルを対象とし
て副キーによる乱アクセスでデータレコードを参照する
場合の動作を、副キー値がｇのレコード参照を例に第３
図のフローチャートを用いて説明する。まず、副キーの
インデックス木のルートブロック（第２図ではインデッ
クスブロック18）より、キー値（副キー値）に従って転
置部12の転置ブロック16内の該当インデックスを探す
（ステップS1）。転置部12のインデックスは、そのキー
値（副キー値）を持つデータレコード（に対するレコー
ド制御ブロック）の存在する位置をインデックス値とし
て持っているので、その値から目的レコードの存在する
データブロック（内の対応レコード制御ブロック）を参
照する（ステップS2）。したがって、副キー値がｇであ
るこの例では、第２図から明らかなように矢印P3の示す
データブロック14′（内のレコード制御ブロック34）が
参照される。

次に、上記参照したデータブロック14′内に目的レコー
ド（参照しようとする副キー値がｇのレコード）が存在
するか、或は目的レコードがブロック分割に伴うレコー
ド移動が存在しなくなったかを、データブロック14′内
のレコード制御ブロック34のブロック内位置情報フィー
ルド42（第１図（ｂ）参照）によって調べる（ステップ
S3）。もし、フィールド42にNULL値が設定されていなけ
れば、目的レコードは同フィールド42によって示される
同じデータブロック14′の位置から始まる領域（フィー
ルド41によって示されるレコード長の領域）に存在する
ことから、そのレコードを参照し（ステップS4）、レコ
ード参照処理を終える。

一方、本実施例のようにレコード制御ブロック34のフィ
ールド42にNULL値が設定されていれば、上記参照したデ
ータブロック14′には目的レコードが存在しないことか
ら、データブロック14′内のレコード制御ブロック34の
移動先情報フィールド43から第２図において矢印P4で示
される目的レコードの移動先（に対するレコード制御ブ
ロック35）の位置を調べ、そのデータブロック24′（内
の対応レコード制御ブロック35）を参照する（ステップ
S5）。次に、ステップS5で参照したデータブロック24′
内に目的レコードが存在するか、或は目的レコードがブ
ロック分割に伴うレコード移動で存在しなくなったか
を、データブロック24′内のレコード制御ブロック35の
ブロック内位置情報フィールド42（第１図（ｂ）参照）
によって調べる（ステップS5）。このステップS5を実行
する理由は、ブロック分割によりデータブロック24′に
移動したレコードが、同ブロック24′に対する新たなレ
コード挿入のために更にブロック分割が発生し、再度他
のブロックへ移動している可能性があるからである。し
たがって、データブロック24′内に目的レコードが存在
しない場合には、ステップS5に戻って更に移動先のデー
タブロック（内のレコード制御ブロック）を参照する。
そして、このステップS5と、次のステップS6の判定処理
とを、目的レコードが存在するデータブロックを見つけ
るまで繰返す。

さて、この実施例では、１回目のステップS6の処理で、
データブロック24′内に目的レコード（副キー値がｇの
レコード15）が存在することが検出される。この場合、
転置部12の転置インデックス16の副キー値ｇを持つイン
デックスが、目的レコード15が実際に存在する（データ
ブロック14′内の対応レコード制御ブロック35の）位置
を矢印P5に示す如く直接指すように、インデックスの値
を変更する（ステップS7）。この変更の後は、ステップ
S4に進んで目的レコード15を参照し、レコード参照処理
を終える。以降、この（副キー値がｇの）レコード15に
対するレコード参照（副キー値ｇの乱アクセスによるレ
コード参照）は、転置部12内の対応するインデックスに
より同レコード15が実際に存在する位置が（第２図にお
ける矢印R5のように）指され、したがってインデックス
の値により参照したデータブロックの中に目的レコード
15は存在するので、第３図のフローチャートのステップ
S3からステップS4に分岐し、直ちに目的レコード15が参
照される。

以上はレコード挿入に伴ってブロック分割が起りレコー
ド移動が発生した場合について説明したがこれに限るも
のではない。即ち本発明は、例えば索引付順編成ファイ
ルのデータ更新（モディファイ）時にレコード長が元の
長さより長くなったためにデータブロック内にそのレコ
ードが収まらず、その結果ブロック分割が起きてレコー
ド移動が発生した場合にも応用可能であり、レコード移
動発生時の副キーのインデックス木の転置部の変更処理
を不要とすることができる。

［発明の効果］ 以上詳述したようにこの発明によれば、レコードの挿入
に伴うブロック分割でデータレコードの移動が発生した
場合、その移動先を示す情報が元のデータブロックの対
応レコード制御ブロックの移動先情報フィールドに設定
されるので、副キーの転置インデックス部内で上記移動
したデータレコードの副キー値と併せて設定されている
同レコードへのインデックスを探して変更する変更処理
を省略しても上記移動したデータレコードを参照するこ
とが可能となる。即ちこの発明によれば、ブロック分割
に伴うレコード移動時における転置インデックス部内で
の移動レコードの副キー値のインデックスの変更処理が
省略できるので、この種の変更処理に伴う処理速度の低
下が防止できる。但し、上記の変更処理を行わない状態
で移動レコードを副キー値による乱アクセスで参照しよ
うとすると、元のデータブロックを経由する間接アクセ
スとなるため、そのレコードを１回だけアクセスする場
合には問題とならないが、複数回参照することがある場
合には処理速度の低下を招く。しかしこの発明によれ
ば、上記の変更処理は移動レコードを副キー値による乱
アクセスで実際に参照した場合に行われるので、移動レ
コードに対する２回目以降の参照が高速に行え、しかも
参照されない移動レコードについては上記の変更処理は
行われないため、ブロック分割に伴うレコード移動時に
無条件で変更処理を行っていた従来方法に比べて無駄な
変更処理がなくなる。

【図面の簡単な説明】

第１図乃至第３図はこの発明の一実施例を示すもので、
第１図はデータレコードの移動を伴う場合のレコード挿
入処理を説明するためのデータブロック状態遷移図、第
２図は上記レコード挿入処理後の索引付順編成ファイル
のデータ構造を抜出して示す図、第３図は副キー値の乱
アクセスによるデータレコード参照時の処理手順を示す
フローチャート、第４図はデータレコードの移動を伴う
場合の従来のレコード挿入処理を説明するための索引付
順編成ファイルのデータ構造状態遷移図である。 11……インデックス部、12……転置部（転置インデック
ス部）、13……データ部、14,14′,24,24′……データ
ブロック、15,25……レコード、16……転置ブロック、1
9……空きスペース、31,33〜39……レコード制御ブロッ
ク、42……ブロック内位置情報フィールド、43……移動
先情報フィールド。

Claims (2)

【特許請求の範囲】
1. 【請求項１】索引付順編成ファイルの構成要素であるデ
   ータブロックに格納されている各データレコード毎に用
   意されるレコード制御ブロックに、同レコード制御ブロ
   ックに対応する上記データレコードが新たなデータレコ
   ードの挿入に伴うブロック分割で新たなデータブロック
   に移動した場合の移動先を示す移動先情報を設定するた
   めの移動先情報フィールドを持つ索引付順編成ファイル
   におけるレコード挿入方法であって、 上記データブロックに格納されている上記データレコー
   ドを移動して上記新たなデータレコードを挿入した場合
   には、移動前の上記データレコードに対応する上記レコ
   ード制御ブロック内の上記移動先情報フィールドに、同
   レコードの移動先を示す移動先情報を設定して、 上記ブロック分割により移動した上記データレコード
   が、同レコードに対応し且つ同レコードの移動前の上記
   データブロックに置かれている上記レコード制御ブロッ
   ク内の上記移動先情報フィールドの設定内容に従って参
   照されるようにしたことを特徴とする索引付順編成ファ
   イルにおけるレコード挿入方法。
2. 【請求項２】索引付順編成ファイルの構成要素であるデ
   ータブロックに格納されている各データレコード毎に用
   意されるレコード制御ブロックに、同レコード制御ブロ
   ックに対応する上記データレコードが新たなデータレコ
   ードの挿入に伴うブロック分割で新たなデータブロック
   に移動した場合の移動先を示す移動先情報を設定するた
   めの移動先情報フィールドを持つ索引付順編成ファイル
   におけるレコード挿入および参照方法であって、 上記データブロックに格納されている上記データレコー
   ドを移動して上記新たなデータレコードを挿入した場合
   には、移動前の上記データレコードに対応する上記レコ
   ード制御ブロック内の上記移動先情報フィールドに、同
   レコードの移動先を示す移動先情報を設定して、 上記ブロック分割により移動した上記データレコード
   が、副キー値による乱アクセスで、同レコードに対応し
   且つ同レコードの移動前の上記データブロックに置かれ
   ている上記レコード制御ブロック内の上記移動先情報フ
   ィールドの設定内容に従って参照されるようにし、 この移動レコード参照時には、上記副キーの転置インデ
   ックス部内の対応インデックスを探し、そのインデック
   ス値を、上記参照したレコードの位置を示すように上記
   設定内容に基づいて変更することを特徴とする索引付順
   編成ファイルにおけるレコード挿入および参照方法。