JPH04109333A - 分割法を用いたソートの境界値選定方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、入力ファイルから処理対象となるキーを含む
レコード群を所定量単位で入力バッファに読込み、ソー
ト処理を施して出力ファイルを作成するデータ処理機構
に用いられる分割法を用いたソートの境界値選定方式に
関する。

（従来の技術） 乱順に並んでいるレコード群をキーと呼ばれるレコード
上の対象領域に関して、何がの意味で昇順または降順に
並べかえる方法の一つに、分割法がある。

この分割法は、境界値と呼ばれる値をもとにして、乱順
なレコードをキーにもとづき並べ直すことを特徴として
いる。つまり、境界値より小さいキーをもつレコードを
左側分割部分に、境界値以上のキーをもつレコードを右
側分割部分にする。

これにより分割部分が二ってき、この分割部分それぞれ
に対して境界値を選択し、これをもとに再度レコードの
並べ直しを実行する。これを繰り返せば一本の整列化さ
れたレコード群ができあがる。

従来、分割法を用いるソート処理に於いては、分割対象
となるレコード群からランダムに１個又は複数個のレコ
ードを選択し、そのレコードをもとに境界値を選定して
いた。即ち、処理対象キーを含むレコードを１つ選んで
境界値を決める場合は、乱数を発生させて、対象レコー
ド群の先頭から数えた上記乱数値のレコードを境界値と
する。

又、複数個のレコードを選択して境界値を決める場合は
、対象レコード群の先頭から異なるキーをもつレコード
を２つ選び、そのうちの値の大きいレコードを境界値と
する。又は、乱数を３つ発生させて、その３つの乱数値
を対象レコード群の先頭からの順次番号として選出し、
その選出したレコードのキーの中央値（中間の値）を境
界値とする。

上記した従来の境界値選択方法には以下のような問題点
があった。

即ち、上記した従来の各境界値選択方法は、いずれもレ
コード群からランダムに１個又は複数個のレコードを選
択して、そのレコードから境界値を選定するため、実際
の処理に於いて最善の境界値である中央値を選ぶことか
困難である。又、最悪のケースでは、分割内の最大値又
は最小値を選んでしまう場合もあり、分割の効率か悪く
なる。

これによってソート全体の速度か遅くなる。

（発明が解決しようとする課題） 上述したように従来の各境界値選択方法は、いずれもレ
コード群からランダムに１個又は複数個のレコードを選
択して、そのレコードから境界値を選定するため、実際
の処理に於いて最善の境界値である中央値を選ぶことが
困難であり、最悪のケースでは、分割内の最大値又は最
小値を選んでしまう場合もあり、従って分割処理の効率
低下を招き、能率のよい高速のソー（・処理が期待でき
ないという問題を有していた。

本発明は上記実情に鑑みなされたもので、分割法を用い
たソート処理の際の境界値を、各分割部分のレコード群
のキーの平均値により選択することにより、選択される
境界値を実際の処理の最善の境界値である中央値に近付
は収束化して、効率の良い分割処理を実現でき、ソート
処理時間を短縮できる、分割法を用いたソートの境界値
選定方式を提供することを目的とする。

［発明の構成］ （課題を解決するための手段及び作用）本発明は、入力
ファイルから処理対象となるキーを含むレコード群を設
定単位で人カッく・ソファに読込め、分割法を用いたソ
ート処理を施して出力ファイルを作成するデータ処理機
構に於いて、上記入力バッファに最初に読込まれたレコ
ード群から無作為に少なくとも３つのキーを抽出し、そ
の各キー値のうち中間の値を第１回分割用の境界値とし
て選択する手段と、上記選択された境界値に従い上記入
力バッファに格納されたレコード群を分割し、その分割
したレコード群それぞれの処理対象キーの最大値及び最
小値を抽出する手段と、上記分割したレコード群それぞ
れの処理対象キーの最大値及び最小値から第２回分割用
の境界値を得る手段と、同手段で得た境界値をもとに対
応する分割レコード群それぞれを分割し、その分割した
レコード群それぞれの処理対象キーの最大値及び最小値
を抽出する手段とを有して、上記最大値及び最小値から
得た分割用境界値に従う処理を所定回数繰り返し実行し
、最終的に昇順又は降順のファイルを得る構成としたも
ので、これにより分割法によるソート処理に於いて、選
択される境界値を実際の処理の最善の境界値である中央
値に近付けて、効率の良い分割処理が実現でき、ソート
処理を高速化できる。

（実施例） 本発明の！実施例に於ける具体的な構成及び動作を図面
を参照して説明するに際し、本発明の詳細な説明する。

本発明は、分割処理および境界値選択を実行する処理装
置と、入…カバッファ部、レコード格納領域、分割情報
格納領域及び境界値選択情報格納領域等を設けた主記憶
とを有して、各分割部分の最大値と最小値を境界値選択
情報として記録し、これを利用して境界を作成すること
により、効率のよい分割処理を可能にし、高速なソーテ
ィング処理を実現する。

即ち、入力ファイルの物理ブロックの整数倍で入力バッ
ファに最初に読み込まれたレコード群からランダムに３
つレコードを選択し、それらのレコードのキーの中間の
値を第１回分割の境界値とする。この境界値をもとに、
入力バッファからレコード格納領域にレコードを移動す
るときに分割処理を実行し、境界値より小さいキーをも
つレコードを左分割部分、大きいか等しいキーをもつレ
コードを右分割部分とする。この分割処理と同時に左右
それぞれの分割部分の最大値キー、最小値キーをもつ対
象レコードのレコード格納領域内のアドレスを境界値選
択情報として記録する。第１回分割処理は（レコード格
納領域が一杯か処理対象レコードがなくなるまで継続す
る。次に、各分割部分の最大値キー、最小値キーを平均
して境界値を算出し、この境界値をもとに分割処理を繰
り返す。このとき、左右分割部分の各々に対し、その中
の最大値キー、最小値キーを選■して、対象レコードの
レコード格納領域内のアドレスを境界値選択情報とし、
又、対象分割の情報を分割情報格納領域内に記録して、
レコード群との結合を図る。この処理を反復実行するこ
とにより全体の整列化が終了する。

このように、分割処理をするときに必要な境界値を中央
値に近い値になるように作成（算出）することにより、
分割処理効率を大幅に向上でき、高速に整列化処理でき
るとともに、主記憶領域を効率良く利用することができ
る。

以下に図面を参照して本発明の一実施例を説明する。

第１図は本発明の一実施例に於けるシステム構成と分割
・整列化処理のレコードの流れを示すシステムブロック
図である。

第１図に於いて、１は入力ファイルであり、整列化対象
のレコード群が格納されている。２乃至６はそれぞれ主
記憶（ＭＭ）内に設けられた構成要素である。このうち
、２は主記憶（ＭＭ）内のプログラム格納領域に格納さ
れた分割処理プログラムであり、第３図のフローチャー
トに示す分割処理と境界値選択処理を実行して整列化を
司るソフトウェアである。３は入力バッファであり、入
力ファイルｌから物理ブロックの整数倍単位で読み込ま
れたレコード群を一時的に保存しておく領域である。４
は境界値／分割情報格納領域であり、境界値選択に必要
な情報（実メモリ上の左右分割部分の先頭アドレス、分
割内のレコードの数、分割内の最大値・最小値のアドレ
ス等）とレコード格納領域５内の分割処理情報が格納さ
れている。

５はレコード格納領域であり、分割情報及び境界値情報
とリンクのとれたレコード群が格納されている。６は出
力バッファであり、出力ファイル７に物理ブロックの整
数倍で書き込むためのレコード群を一時的に保存してお
く。７は出力ファイルであり、ソートされたレコード群
を格納するために使用される。

第２図は上記実施例に於ける境界値及び分割情報格納領
域の一つのセルを示す図でる。

第２図に於いて、境界値／分割情報格納領域４は主記憶
（ＭＭ）上に存在し、レコード格納領域５内の各分割毎
の分割情報及び境界値選択情報群が格納されている。２
１は左分割制御領域であり、左分割部分のレコード格納
領域５内の先頭アドレスや分割内レコード数等が記録さ
れている。２２は左分割部分内キーアドレス格納領域で
あり、左分割部分内で最大のキー値をもつレコードのレ
コード格納領域５内のアドレスが記録される。２３は左
分割部分内キーアドレス格納領域であり、左分割部分内
で最小のキー値をもつレコード格納領域５内のアドレス
が記録される。２４は右分割制御領域であり、右分割部
分のレコード格納領域５内の先頭アドレスや分割内レコ
ード数等が記録される。

２５は右分割最大キーアドレス格納領域であり、右分割
部分内で最大のキー値をもつレコードのレコード格納領
域５内のアドレスが記録される。

２６は右分割内最小キーアドレス格納領域であり、右分
割部分内で最小のキー値をもつレコードのレコード格納
領域５内のアドレスが記録される。

第３図は本発明の一実施例に於ける分割処理、境界値選
択処理を示すフローチャートある。第３図に於いて、Ｓ
ｌはデータを入力するステップであり、非同期処理によ
り入力ファイルｌから入力バッファ３ヘデータの入力を
実行する。Ｓ２は第１回目の境界値を選択するステップ
であり、最初に入力されたレコード群からランダムに３
つのレコードを選びキー値の中間を境界値にする。Ｓ３
は第１回分割処理を実行をするステップであり、選択し
た境界値をもとに分割処理及び各分割内の最大値、最小
値をもつレコードの選択処理を実行する。Ｓ４は境界値
選出処理を実行するステップであり、各分割内の最大キ
ー値と最小キー値の平均をとり境界値とする処理を実行
する。Ｓ５は分割処理、最大／最小キー選出処理を実行
するステップであり、各分割部分を境界値をもとに分割
処理し、同時に最大／最小キー値をもつレコードを選出
する処理を実行する。

第４図及び第５図はそれぞれ本発明の実施例に於ける動
作説明図である。第４図に於いて、２１ａ　。

２１ｂはそれぞれ第２図に示す左分割制御領域２１内に
設けられるもので、２１ａは左分割の先頭アドレス（Ｌ
ＳＡ）を格納する左分割先頭アドレス格納領域、２１ｂ
は左分割内のレコード数（ＬＲＮ）を格納する左分割内
レコード数格納領域、２２は左分割内の最大キー値をも
つレコードのアドレス（ＬＭＫ）を格納する左分割内最
大キーアドレス格納領域、２３は左分割内の最小キーア
ドレス（ＬＬＫ）を格納する左分割内最小キーアドレス
格納領域、２４ａは第２図に示す右分割制御領域２４内
に設けられる、右分割の先頭アドレス（ＲＳ　Ａ）を格
納する右分割先頭アドレス格納領域、２４ｂは右分割内
のレコード数（ＲＲＮ）を格納する右分割内レコード数
格納領域、２５は右分割内の最大キー値をもつレコード
のアドレス（ＲＭＫ）を格納する右分割部分内キーアド
レス格納領域、２６は右分割内の最小キーアドレス（Ｒ
Ｌ　Ｋ）を格納する右分割内最小キーアドレス格納領域
である。

ここで上記第１図乃至第５図を参照して本発明の一実施
例に於ける動作を説明する。

第１図は、本発明の一実施例に於ける構成要素、及び処
理対象となる入力ファイルのレコード群を分割・整列化
して順序列（出力ファイル）を作成するだめのレコード
の流れを示している。

分割処理及び境界値選択のために割当てた主記憶（ＭＭ
）上に、第１図に示すように、入力バッファ３、境界値
／分割情報格納領域４、レコード格納領域５、出力バッ
ファ６等を設ける。

先ず、入力ファイル■から非同期処理により処理対象と
なる最初のレコード群が入力バッフ７３に読み込まれる
（第３図ステップＳ１．）。この入力バッファ３に読み
込まれたレコード群から、ランダムに３つレコードを選
択し、この中の中間値を第１回分割処理用の境界値とし
て選択する（第３図ステップＳ２．Ｓ３）。

入力バッファ３に読み込んだレコード群をレコード単位
でレコード格納領域５に移動する毎に、そのレコードを
先に選んだ上記境界値と比較して、大小を決定すると同
時に、左分割（境界値より小）内の最大キー値／最小キ
ー値と右分割（境界値より大きいか等しい）内の最大キ
ー値／最小キー値を決定していく　（第３図ステップＳ
４）。この動作を制御するのが第２図に示される境界値
／分割情報格納領域４の各情報群である。

この第１回分割処理は、レコード格納領域５が一杯にな
るか又は入力レコードがなくなるまで反復実行される（
第３図ステップＳ５）。

次に、左分割内の最大キー値と最小キー値の平均を計算
して、左分割部分を分割処理するための境界値を選出す
る（第３図ステップ５ｋｉ）。

次に、この境界値をもとに、分割処理が実行されて、左
分割、右分割ができあがるとともに、左右分割それぞれ
の最大キー値、最小キー値が選出される（第３図ステッ
プＳ７）。

この結果、第２図のレコード格納領域５内に示すような
データ構造の左及び右の分割部分が主記憶上に多数作成
される。

前述の一連の動作を繰り返すことにより、１本の順序列
が作成される（第３図ステップＳ８゜Ｓ９）。

このように、分割処理をするときに、必要な境界値を中
央値に近い値になるように作成（選定）して、その境界
値によりレコードを分割処理することにより、分割処理
効率を大幅に向上でき、高速に整列化処理できる。

尚、上記実施例では第１回分割用の境界値選択を３つの
キー抽出により行なったが、これに限定されるものでは
なく、３つ以上の複数個の抽出キーから第１回分割用の
境界値を選択する構成であってもよい。

［発明の効果］ 以」二詳記したように本発明による分割法を用いたソー
トの境界値選定方式によれば、入力ファイルから処理対
象となるキーを含むレコード群を設定単位で入力バッフ
ァに読込み、分割法を用いたソート処理を施して出力フ
ァイルを作成するデータ処理機構に於いて、上記入力バ
ッファに最初に読込まれたレコード群から無作為に少な
くとも３つのキーを抽出し、その各キー値のうち中間の
値を第１回分割用の境界値として選択する手段と、上記
選択された境界値に従い上記入力バッファに格納された
レコード群を分割し、その分割したレコード群それぞれ
の処理対象キーの最大値及び最小値を抽出する手段と、
上記分割したレコード群それぞれの処理対象キーの最大
値及び最小値から第２回分割用の境界値を得る手段と、
同手段で得た境界値をもとに対応する分割レコード群そ
れぞれを分割し、その分割したレコード群それぞれの処
理対象キーの最大値及び最小値を抽出する手段とを有し
てなる構成としたことにより、分割法によるソート処理
に於いて、選択される境界値を実際の処理の最善の境界
値である中央値に近付けて、効率の良い分割処理が実現
でき、ソート処理を高速化できる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図は
上記実施例に於ける境界値及び分割情報格納領域の一つ
のセル構造を示す図、第３図は本発明の一実施例に於け
る分割処理、境界値選択処理を示すフローチャート、第
４図及び第５図はそれぞれ本発明の一実施例に於ける動
作説明図である。 ｌ・・・入力ファイル、２・・・分割処理プログラム、
３・・・入力バッファ、４・・・境界値／分割情報格納
領域、５・・・レコード格納領域、６・・・出力バッフ
ァ、７・・・出力ファイル、２１・・・左分割制御領域
、２２・・・左分割内最大キーアドレス格納領域、２３
・・・左分割内最小キーアドレス格納領域、２４・・・
右分割制御領域、２５・・・右分割最大キーアドレス格
納領域、２６・・・右分割内最小キーアドレス格納領域
、ＭＭ・・・主記憶。 出願人代理人　弁理士　鈴江武彦 第 図

Claims (1)

【特許請求の範囲】
1. 入力ファイルから処理対象となるキーを含むレコード群
   を設定単位で入力バッファに読込み、分割法を用いたソ
   ート処理を施して出力ファイルを作成するデータ処理機
   構に於いて、上記入力バッファに最初に読込まれたレコ
   ード群から無作為に少なくとも３つのキーを抽出し、そ
   の各キー値のうち中間の値を第１回分割用の境界値とし
   て選択する手段と、上記選択された境界値に従い上記入
   力バッファに格納されたレコード群を分割する手段、及
   び分割したレコード群それぞれの処理対象キーの最大値
   及び最小値を抽出する手段と、上記分割したレコード群
   それぞれの処理対象キーの最大値及び最小値から第２回
   分割用の境界値を得る手段と、同手段で得た境界値をも
   とに対応する分割レコード群それぞれを分割する手段、
   及びその分割したレコード群それぞれの処理対象キーの
   最大値及び最小値を抽出する手段とを具備してなること
   を特徴とする分割法を用いたソートの境界値選定方式。