JPH0199125A - リンク分類方式 - Google Patents
リンク分類方式Info
- Publication number
- JPH0199125A JPH0199125A JP25806887A JP25806887A JPH0199125A JP H0199125 A JPH0199125 A JP H0199125A JP 25806887 A JP25806887 A JP 25806887A JP 25806887 A JP25806887 A JP 25806887A JP H0199125 A JPH0199125 A JP H0199125A
- Authority
- JP
- Japan
- Prior art keywords
- string
- strings
- phase
- key
- directory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 230000001174 ascending effect Effects 0.000 claims abstract description 5
- 238000000034 method Methods 0.000 claims description 15
- 230000003247 decreasing effect Effects 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 8
- 230000000694 effects Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（産業上の利用分野）
本発明は電子計算機による事務データ処理の分間作業に
関し、特に、外部記憶装置として磁気ディスク装置を使
用して大容量データを分類する方式に関する。
関し、特に、外部記憶装置として磁気ディスク装置を使
用して大容量データを分類する方式に関する。
（従来の技術）
従来、外部記憶装置として磁気ディスク装置を使用して
大容量データを分類する方式は、第４図に示すように、
以下の３つのフェーズからなる。
大容量データを分類する方式は、第４図に示すように、
以下の３つのフェーズからなる。
（１）グリソートフェーズ
（２）マージフェーズ
（３）ラストパスフェーズ
ブリソートフェーズでは、入力ファイルからデータ・レ
コードが読込まれ、順番に組分けされ、順序づけられた
組、即ちストリングとして磁気ディスク装置へ出力され
る。マージフェーズでは、これらのストリングの数がラ
ストパスのマージオーダ以下になるまで、ストリングが
マージされる。
コードが読込まれ、順番に組分けされ、順序づけられた
組、即ちストリングとして磁気ディスク装置へ出力され
る。マージフェーズでは、これらのストリングの数がラ
ストパスのマージオーダ以下になるまで、ストリングが
マージされる。
即ち組合されてより大きなストリングが作成される。ま
た、ラストパスフェーズでは、マージフェーズでマージ
されてできあがった幾つかのストリングを１本のストリ
ングに作成して出力ファイルへ書込む。
た、ラストパスフェーズでは、マージフェーズでマージ
されてできあがった幾つかのストリングを１本のストリ
ングに作成して出力ファイルへ書込む。
（発明が解決しようとする問題点）
上述した従来の分類方式は、ストリングの数がラストバ
スのマージオーダより大きい場合に、磁気ディスク装置
に格納されたストリングを物理的に読出してマージする
という方式を採っている。
スのマージオーダより大きい場合に、磁気ディスク装置
に格納されたストリングを物理的に読出してマージする
という方式を採っている。
つまり、マージフェーズにおいて、ストリングを比較し
た後にレコード全体を移動させるので、時間がかかって
いる。
た後にレコード全体を移動させるので、時間がかかって
いる。
一方、磁気ディスク装置は、レコードキーとレコードの
格納場所とに何らかの関連性を持たせて各レコードを格
納することにより、レコードキー操作でレコードを論理
的に並べることができるという性質を備えており、ラン
ダムアクセスに適している。
格納場所とに何らかの関連性を持たせて各レコードを格
納することにより、レコードキー操作でレコードを論理
的に並べることができるという性質を備えており、ラン
ダムアクセスに適している。
ところが、従来の分類方式は、このような磁気ディスク
装置の性質を全く生かしていないという問題点があった
。
装置の性質を全く生かしていないという問題点があった
。
（問題点を解決するための手段）
従来の問題点を解決するために本発明が提供するリンク
分類方式は、電子装置の外部記憶装置として磁気ディス
ク装置を使用し、入力ファイルから読込まれたレコード
から複数のストリング舎作成して前記磁気ディスク装置
へ出力し、これらのストリングを物理的に入替えてマー
ジすることにより大容量データを分類する方式であって
、前記ストリングが作成されて前記磁気ディスク装置へ
出力されると同時に、前記ストリングのそれぞれが出力
される前記磁気ディスク装置上の位置とそのストリング
の第１レコードのキー及び最終レコードのキーとを内部
記憶装置へ出力することによりストリングディレクトリ
を作成する手段と、前記マージを行う前に、前記ストリ
ングディレクトリ作成手段により作成されたストリング
ディレクトリを第１レコードのキーの昇順に並び替え、
並び替えた後の先頭のストリングディレクトリの最終レ
コードのキーと以降のストリングディレクトリの第１レ
コードのキーとを比較し、後者の方が大きい場合に両方
のストリングディレクトリをリンクし、この比較処理を
全てのストリングディレクトリについて行うことにより
、前記ストリングを論理的にマージする手段とを備えて
いることを特徴とする。
分類方式は、電子装置の外部記憶装置として磁気ディス
ク装置を使用し、入力ファイルから読込まれたレコード
から複数のストリング舎作成して前記磁気ディスク装置
へ出力し、これらのストリングを物理的に入替えてマー
ジすることにより大容量データを分類する方式であって
、前記ストリングが作成されて前記磁気ディスク装置へ
出力されると同時に、前記ストリングのそれぞれが出力
される前記磁気ディスク装置上の位置とそのストリング
の第１レコードのキー及び最終レコードのキーとを内部
記憶装置へ出力することによりストリングディレクトリ
を作成する手段と、前記マージを行う前に、前記ストリ
ングディレクトリ作成手段により作成されたストリング
ディレクトリを第１レコードのキーの昇順に並び替え、
並び替えた後の先頭のストリングディレクトリの最終レ
コードのキーと以降のストリングディレクトリの第１レ
コードのキーとを比較し、後者の方が大きい場合に両方
のストリングディレクトリをリンクし、この比較処理を
全てのストリングディレクトリについて行うことにより
、前記ストリングを論理的にマージする手段とを備えて
いることを特徴とする。
（実施例）
以下、本発明の一実施例について図面を参照して説明す
る。
る。
第１図は本発明の一実施例のリンク分類方式を用いて大
容量データを分類する場合のデータの流れを示す図、第
２図はストリングディレクトリのフォーマット例を示す
図、第３図はリンク例を示す図である。
容量データを分類する場合のデータの流れを示す図、第
２図はストリングディレクトリのフォーマット例を示す
図、第３図はリンク例を示す図である。
本実施例のリンク分類方式は、第１図に示すように、以
下の４つのフェーズからなる。
下の４つのフェーズからなる。
（１）ブリソートフェーズ
（２）リンクフェーズ
（３）マージフェーズ
（４）ラストパスフェーズ
グリソートフェーズでは、従来と同様に、入力ファイル
からデータ・レコードが読込まれ、ストリングが作成さ
れて磁気ディスク装置へ出力されるが、このとき同時に
、ストリングディレクトリが作成されて内部記憶装置に
格納される。このストリングディレクトリは、第２図に
示すように、ストリングが格納されているディスクアド
レスと、ストリングの第１レコードのキーと、最終レコ
ードのキーとからなる。
からデータ・レコードが読込まれ、ストリングが作成さ
れて磁気ディスク装置へ出力されるが、このとき同時に
、ストリングディレクトリが作成されて内部記憶装置に
格納される。このストリングディレクトリは、第２図に
示すように、ストリングが格納されているディスクアド
レスと、ストリングの第１レコードのキーと、最終レコ
ードのキーとからなる。
リンクフェーズでは、プリソートフェーズで作成された
ストリングディレクトリを操作することにより、ストリ
ングを論理的にマージする。このリンクは、まず、プリ
ソートフェーズで作成した複数個のストリングディレク
トリを第１キーが大きいものから昇順に並び替える０次
に、１番目のストリングディレクトリの最終キーと２番
目のストリングディレクトリの第１キーを比較し、後者
の方が大きいときにこれらの２つのストリングディレク
トリをリンクすることにより、ストリングを論理的にマ
ージする。３番目以降のストリングディレクトリについ
ても同様の比較を行ってリンクしていく、この作業を全
てのストリングディレクトリについて行うことにより、
ストリングを物理的にマージさせることなく論理的にマ
ージさせてストリングの数を減らす。
ストリングディレクトリを操作することにより、ストリ
ングを論理的にマージする。このリンクは、まず、プリ
ソートフェーズで作成した複数個のストリングディレク
トリを第１キーが大きいものから昇順に並び替える０次
に、１番目のストリングディレクトリの最終キーと２番
目のストリングディレクトリの第１キーを比較し、後者
の方が大きいときにこれらの２つのストリングディレク
トリをリンクすることにより、ストリングを論理的にマ
ージする。３番目以降のストリングディレクトリについ
ても同様の比較を行ってリンクしていく、この作業を全
てのストリングディレクトリについて行うことにより、
ストリングを物理的にマージさせることなく論理的にマ
ージさせてストリングの数を減らす。
例えば第３図に示すように、ディスクアドレス″Ａ ｌ
’Ｔ〜“Ｅ″を持つ５つのストリングディレクトリをリ
ンクする場合に、これらのストリングディレクトリを第
１キーが大きいものから昇順に並び替えると、’Ｅ’
、”Ｂ” 、”Ｄ″ ＩＩ ＣＨ９“Ａ ＩＴとなる
０次に、“Ｅ”の最終キーと“Ｂ″の第１キーを比較し
て後者の方が大きいので、両者をリンクする。これによ
り、“Ｅ−Ｂ”。
’Ｔ〜“Ｅ″を持つ５つのストリングディレクトリをリ
ンクする場合に、これらのストリングディレクトリを第
１キーが大きいものから昇順に並び替えると、’Ｅ’
、”Ｂ” 、”Ｄ″ ＩＩ ＣＨ９“Ａ ＩＴとなる
０次に、“Ｅ”の最終キーと“Ｂ″の第１キーを比較し
て後者の方が大きいので、両者をリンクする。これによ
り、“Ｅ−Ｂ”。
“Ｄ″ ＭＣ″ Ｍ Ａ Ｒの４つのストリングに
マージされたこととなる０次に、“Ｅ−Ｂ″の最終キー
と“Ｄ”の第１キーとを比較するが、前者の方が大きい
ので、両者をリンクしない、同様にして、”Ｅ−Ｂ″と
“Ａ″とをリンクし、“Ｄ”と“Ｃ″とをリンクする。
マージされたこととなる０次に、“Ｅ−Ｂ″の最終キー
と“Ｄ”の第１キーとを比較するが、前者の方が大きい
ので、両者をリンクしない、同様にして、”Ｅ−Ｂ″と
“Ａ″とをリンクし、“Ｄ”と“Ｃ″とをリンクする。
つまり、５つのストリングから物理的にストリングをマ
ージすることなく、ストリングディレクトリを操作する
ことにより、“Ｅ−Ｂ−Ａ″と“Ｄ−Ｃ″という２つの
ストリングが作成されることとなる。
ージすることなく、ストリングディレクトリを操作する
ことにより、“Ｅ−Ｂ−Ａ″と“Ｄ−Ｃ″という２つの
ストリングが作成されることとなる。
マージフェーズでは、リンクフェーズで論理的にリンク
されたストリングの数がラストバスのマージζ−ダ以下
になるまで、ストリングを物理的にマージする。
されたストリングの数がラストバスのマージζ−ダ以下
になるまで、ストリングを物理的にマージする。
また、ラストバスフェーズでは、マージフェーズでマー
ジされてできあがった幾つかのストリングを１本のスト
リングに作成して出力ファイルへ書込む。
ジされてできあがった幾つかのストリングを１本のスト
リングに作成して出力ファイルへ書込む。
（発明の効果）
以上に説明したように本発明は、外部記憶装置として磁
気ディスク装置を使用して大容量データを分類する場合
に、従来はマージフェーズにおいて、ストリングの数が
ラストバスオーダ以下になるまで物理的にマージを行つ
−ていたのを、マージフェーズの前に、ストリングディ
レクトリを操作することにより、ストリングを物理的に
移動させずにマージする。従って、マージフェーズに至
る前に論理的にストリングをマージしてストリングの数
を減らすことができるので、場合によってはストリング
の数がラストバスオーダ以下になって、マージフェーズ
をバイパスすることも可能になる。
気ディスク装置を使用して大容量データを分類する場合
に、従来はマージフェーズにおいて、ストリングの数が
ラストバスオーダ以下になるまで物理的にマージを行つ
−ていたのを、マージフェーズの前に、ストリングディ
レクトリを操作することにより、ストリングを物理的に
移動させずにマージする。従って、マージフェーズに至
る前に論理的にストリングをマージしてストリングの数
を減らすことができるので、場合によってはストリング
の数がラストバスオーダ以下になって、マージフェーズ
をバイパスすることも可能になる。
これは、従来の分類方式においてマージフェーズが占め
る処理時間が非常に大きいことを考えると、有効な分類
方式といえる。
る処理時間が非常に大きいことを考えると、有効な分類
方式といえる。
第１図は本発明の一実施例のリンク分類方式を用いて大
容量データを分類する場合のデータの流れを示す図、第
２図はストリングディレクトリのフォーマット例を示す
図、第３図はリンク例を示す図、第４図は従来の分類方
式で大容量データを分類する場合のデータの流れを示す
図である。
容量データを分類する場合のデータの流れを示す図、第
２図はストリングディレクトリのフォーマット例を示す
図、第３図はリンク例を示す図、第４図は従来の分類方
式で大容量データを分類する場合のデータの流れを示す
図である。
Claims (1)
- 【特許請求の範囲】 電子装置の外部記憶装置として磁気ディスク装置を使用
し、入力ファイルから読込まれたレコードから複数のス
トリングを作成して前記磁気ディスク装置へ出力し、こ
れらのストリングを物理的に入替えてマージすることに
より大容量データを分類する方式において、 前記ストリングが作成されて前記磁気ディスク装置へ出
力されると同時に、前記ストリングのそれぞれが出力さ
れる前記磁気ディスク装置上の位置とそのストリングの
第１レコードのキー及び最終レコードのキーとを内部記
憶装置へ出力することによりストリングディレクトリを
作成する手段と、 前記マージを行う前に、前記ストリングディレクトリ作
成手段により作成されたストリングディレクトリを第１
レコードのキーの昇順に並び替え、並び替えた後の先頭
のストリングディレクトリの最終レコードのキーと以降
のストリングディレクトリの第１レコードのキーとを比
較し、後者の方が大きい場合に両方のストリングディレ
クトリをリンクし、この比較処理を全てのストリングデ
ィレクトリについて行うことにより、前記ストリングを
論理的にマージする手段とを備えていることを特徴とす
るリンク分類方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25806887A JPH0199125A (ja) | 1987-10-12 | 1987-10-12 | リンク分類方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25806887A JPH0199125A (ja) | 1987-10-12 | 1987-10-12 | リンク分類方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0199125A true JPH0199125A (ja) | 1989-04-18 |
Family
ID=17315084
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP25806887A Pending JPH0199125A (ja) | 1987-10-12 | 1987-10-12 | リンク分類方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0199125A (ja) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60168232A (ja) * | 1984-02-10 | 1985-08-31 | Nec Corp | 密度解析分類方式 |
-
1987
- 1987-10-12 JP JP25806887A patent/JPH0199125A/ja active Pending
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60168232A (ja) * | 1984-02-10 | 1985-08-31 | Nec Corp | 密度解析分類方式 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4514826A (en) | Relational algebra engine | |
| US4817036A (en) | Computer system and method for data base indexing and information retrieval | |
| US5117495A (en) | Method of sorting data records | |
| JPH02178730A (ja) | 分割法を用いた内部ソート方式 | |
| US6424970B1 (en) | Sorting system and method executed by plural computers for sorting and distributing data to selected output nodes | |
| JP3515810B2 (ja) | ソート処理方法および装置 | |
| JPS6172333A (ja) | 複数ファイルのマージ方法 | |
| JPH0581337A (ja) | データ処理装置 | |
| JP2923952B2 (ja) | マージ処理方法 | |
| JPH0267648A (ja) | ツリー構造データベースのレコード追加方式 | |
| JPS62287350A (ja) | インデツクス一括更新方式 | |
| JPH04178726A (ja) | 大容量データ分類処理方式 | |
| JP2926803B2 (ja) | ソート処理方法 | |
| JPS6134626A (ja) | 外部分布分類を実行する方法 | |
| JP3293544B2 (ja) | 補助記憶装置を用いたソート方式 | |
| JPH0436415B2 (ja) | ||
| JPS6266326A (ja) | 日本語デ−タ整列処理方式 | |
| JPH0291725A (ja) | 併合処理方式 | |
| JPH02222044A (ja) | データ処理装置 | |
| JPH03259329A (ja) | 大容量データのキー相対アドレス分類方式 | |
| JPH0145648B2 (ja) | ||
| JPH0298729A (ja) | データ分類入力方法 | |
| JPH0324617A (ja) | データ処理方式 | |
| JPS60168232A (ja) | 密度解析分類方式 | |
| JPH02208751A (ja) | データ保存方式 |