JPS6134626A - 外部分布分類を実行する方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、極めて長大なファイルを外部で分類するため
の、コンピュータで実施可能な分布法に関するものであ
る。

［従来技術］ 分類（ソート）とは、項目をある「順序」に配列する方
法である。対象となるものは、各々が関連したキー値を
有している記録である。分類の目的は、キー値を非減少
類に入力したレコードの順列を決定することである。分
類作業の特徴は、再配列が行なわれる態様、ならびにこ
れが全体として、分類を行なうＣＰＵにとって局所であ
る内部メモリ内で、すなわちデータがＣＰＵのランダム
・アクセス内部（メイン）メモリに整然と適合する個所
で行なわれるのかどうかによって決まる。

「分布（デストリビュージョン）分類」とは、レコード
を隣接した範囲に分け、ひとつの範囲の全てのレコード
が、次の範囲のレコードのキーよりも小さい値のキーを
持っているようにすることである。一方、「組合せ（マ
ージ）分類Ｊとは、２つ以上の大きさ順配列のリス１〜
を組み合わせ、組み合わされたリストの配列も大きさ順
になるようにすることである。２ウエイ・マージ・ソー
トは典型例であって、この場合、対になった項目が比較
され、各部が順序付けられ、ついでこれらの対が組み合
わされ、結果として得られる４重数が順序付けられ、４
重数がソート済みの８重数に組み合わされ、これが組合
せができなくなるまで続けられる。

「外部分類」とは、１次すなわち内部メモリの容量を越
えたデータのファイルに適用される分類技法であって、
分類処理中にＤＡＳＤ　（直接アクセス記憶装置）、テ
ープ及びドラムのような２次記憶装置に依存する。外部
分類の一型式である組合せ分類において、ファイルの各
部は、内部メモリに読み込まれ、内部で順序付けられ、
ついで外部装置すなわち２次記憶装置に再度書き込まれ
る。

「交換−選択」という技法では、順序付けられていない
「入力ファイル」から、１つまたはそれ以上の順序付け
られたリスト（文字列）を含んでいる中間ファイルが作
成される。交換−選択では、さまざまな長さの順序付け
られた文字列が作成されるが、その平均長さは内部メモ
リの容量の２倍となる。米国特許第２９８３９０４号を
参照されたい。「最小組合せハフマン・ツリー」を形成
することにより、文字列の順序付けられた文字列への最
適な組合せを行なうことができる。最小組合せツリーは
、文字列の長さを表すターミナル節点（ノード）によっ
て構成されており、かつ組合せツリーの値ができるだけ
小さくなるように、配列される。

ディスク装置に格納されているデータに使用されるほと
んどの外部分類法は１組合せをベースとするものである
。」二記のごとく、これらには交換−選択を用いて初期
格納文字列を幾つか生成し、ついで文字列が１つだけに
なるまで、組合せを繰り返す必要がある。米国特許第４
２１０９６１号“Ｓｏｒｔｉｎｇ　Ｓｙｓｔｅｍ”には
、典型的な組合せベースの外部分類法が記載されている
。

一３＝ 一方、連想記憶装置が、分類及び探索の両適用業務に使
用されている。Ｃｈａｎｇ　ｅｔ　ａｌ、′Ａｓ５ｏｃ
ｉａｔｉｖｅ　５ｅａｒｃｈ　Ｂｕｂｂｌｅ　Ｄｅｖｉ
ｃｅｓ　ｆｏｒＣｏｎｔｅｎｔ　Ａｄｄｒｅｓｓａｂｌ
ｅ　Ｍｅｍｏｒｉｅｓ”、１８、ＩＢＭＴｅｃｈｎｉｃ
ａｌ　Ｄｉ、ｓｃｌ、ｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ、
　ｐｐ、　５９８−６０２、Ｊｕｌ、ｙ　　１９７５に
は、言葉及びビットごとに内容アドレス可能なメモリと
して磁気バブル・メモリ装置を挙げている。また、米国
特許第４１６８５３５号”Ｎｏｎ−Ｖｏｌａｔｉｌｅ　
Ｂｕｂｂｌｅ　ＤｏｍａｉｎＭｅｍｏｒｙ　Ｓｙｓｔｅ
ｍ”には、複数の小／大ループ・ビット・ストレージ・
アレイが記載されている。同様に、Ｄｏｒｔｙ　ａｔ　
ａｌ、”Ｍａｇｎｅｔｉｃ　Ｂｕｂｂｌｅ　Ｍｅｍｏｒ
ｙＡｒｃｈｊｌ：ｅｃｔｕｒｅｓ　ｆｏｒ　Ｓｕｐｐｏ
ｒｔｉｎｇ　ＡｓｓｏｃｊａｔｊｖｅＳｅａｒｃｈｊｎ
ｇ　ｏｆ　Ｒｅ１ａｔｊｏｎａｌ　Ｄａｔａｂａｓｅｓ
”２９、ＩＥＥ　Ｅ　Ｔｒａｎｓａｃｔｊｏｎｓ　ｏｎ
　Ｃｏｍｐｕｔｅｒｓ、　ｐｐ、　９５７−９７０、Ｎ
ｏｖｅｍｂｅｒ　ｌ　９８０は、磁気バブル・メモリの
パラレル・アーキテクチャを実質的に拡張し、リレーシ
ョナル・データベースにおける連想探索をサポートする
ものである。Ｃ，Ｓ、　Ｌｊ、ｎ、“ＳＯｒｔｉｎｇ　
ｕｊｔｈ　Ａｓ５ｏｃｉａｔｉｖｅ　５ｅｃｏｎｄａｒ
ｙ　Ｓｔｏｒａｇｅ　Ｄｅｖｉｃｅｓ”、Ｐｒｏｃｅｅ
ｄｉｎｇｓ　ｏｆ　ＡＦＩＰＳ＋　Ｎａｔｉｏｎａｌ　
　　　Ｃｏｍρｕｔｅｒ　Ｃｏｎｆｅｒｅｎｃｅ、　　
１９７７、ｐｐ、６９１−６９５には、キーのヒストグ
ラムを用いた分布分類と、ヘッド・パー・トラック・デ
ィスクにおける連想探索を実行するための、コンピュー
タで実施可能な方法が記載されている。この方法を操作
できるのは、キー値が平均して分布している場合だけで
ある。

［発明が解決しようとする問題点］ 上記のような従来の外部分類法は組合せ（マージ）を基
本とするものであって、交換−選択を用い初期格納文字
列を幾つか生成した後、文字列が唯１つになるまで組合
せ（マージ）を繰返す必要があった。このため分類に長
時間を要し、又長大なファイルには適用困難であった。

［問題点を解決するための手段］ 本発明の目的は、２次記憶装置によって連想アクセスさ
れる極めて長大なファイルに適用でき、分類機能の稼働
時間を大幅に削減する、外部分類法を考案するところに
ある。

上記の目的は、分布分類を実行することによって実現さ
れる。再配列されるデータは、連想２次記憶装置でアク
セスできる、キー登付けて格納されたレコードを包含し
ている。本発明の方法は、所定数のキーのランダム・サ
ンプリングとサンプリングされたキーの内部分類を利用
するものであり、キー値の範囲内のキーのヒストグラム
を作成し、密度の低い隣接した範囲を組み合わせること
によって、レコードの同一サイズで各々がＣＰＵのメイ
ン・メモリに適合している区画を単一のパスに形成し、
キーがある＠凹円にある全てのレコードを連想検索し、
検索されたレコードを内部で分類するものである。

本方法は、キーの順序や、キー値の分布に関係なく、極
めて高速に適用できるものである。サンプリングされた
キーの内部分類の後、格納された順序でキーを指示（ポ
イント）する順次ポインタ・リストが構成される。これ
に関連して、キーのヒストグラムとキーの範囲を作成し
てレコードの区画を形成することには、各キーに対して
ポインタ・リストで内部メモリの２進探索を行ない、キ
ーに関連した範囲を確認することが含まれている。本分
布法を有利に最適化できるのは、連想記憶装置に関して
であって、従来の単なるＤＡＳＤに関してではない。

［実施例］ 本発明の方法は、少なくとも１つのＣＰＵを包含してお
りその各々が内部メモリ、入出力チャネル、制御装置、
直接アクセス記憶装置、及びこれらに接続されたその他
の入出力装置を持つコンピュータ・システムで実行可能
である。かかるシステムは、“Ｄａｔａ　Ｐｒｏｃｅｓ
ｓｉｎｇ　Ｓｙｓｔｅｍ”なる名称の米国特許第３４０
０３７１号に記載されている。

該明細書記載のシステムは、資源として、コンピュータ
・システムまたはこのシステムで稼働するオペレーティ
ング・システムのいず九かの、処理の実行に必要とされ
る機構の全てを包含している。

典型的な資源は、内部メモリ、入出力装置、ＣＰＵ、デ
ータ・セット、及び制御または処理プログラムを含んで
いる。

機能のセットとしての「分類」を、任意の実行適用業務
処理、またはデータベース管理システムによって呼び出
すことができる。実行機能が、ファイル名で分類を呼び
出すのが、典型的なものである。オペレーティング・シ
ステムがファイルの位置を確認し、これが内部メモリに
適合しない場合には、「外部分類」機能が呼び出される
。

本発明の方法には、連想２次記憶装置が必要である。こ
の装置は、ロジック・パー・トラック機能を有する大形
ＤＡＳＤ、または磁気バブル・メモリ（ＭＢＭ）のいず
れかによって達成される。

本方法を、３つのフェーズ、すなわち（１）サンプル・
フェーズ、（２）範ＦＨＩ（バケツ１−）形成フェーズ
、及び（３）内部分類フェーズを参照して説明する。

サンプル・フェーズにおいては、所定数のキー値がラン
ダムにサンプリングされ、サンプリングされたキーが内
部で分類される。範囲形成フェーズにおいては、ファイ
ルの単一パスで、分類されたサンプルによる定義に従っ
て、各範囲に幾つのレコードが属しているかのカウント
が取られる。このヒストグラムを使用して、隣接する範
囲が組み合わされ、各範囲がほぼ内部メモリに適合する
レコード数を含んでいるような、大きい範囲が形成され
る。最後に、増加キー値順の各範囲に対する内部分類フ
ェーズにおいては、その範囲内にキー値がある全てのレ
コードを内部メモリで検索するために、ファイルの連想
探索が行なわれる。次いで、レコードが内部分類され、
出力ファイルに付加される。

時間／空間効率を改善する修正を加えた方法の分析、連
想２次記憶装置としての磁気バブル・メモリの使用、及
び内部分類フェーズの有効性の改善についても、詳細に
説明する。

本明細書においては、まず各レコードがＲバイトの固定
長を有しており、一方、キー・フィールドがＫ（Ｒバイ
トからなるものと、想定する。ＣＰＵはＭバイトの内部
メモリ・サイズを有しており、分類されるファイルはＮ
レコードからなるものとする。さらに、内部で分類でき
るレコード数Ｆは、はぼＭ／Ｒであるものとする。最後
に、すンプリングされたキーの数Ｓは、はぼＭ／にであ
るとする。

サンプル・フェーズ ８個（ただし、ＳはほぼＭ／にである）のキーのサンプ
ルは、ランダム・サンプリング法を用いて取られる。必
要な内部メモリの量Ｍの決定も行なうＳの値の選択は、
本方法の中核をなすものであり、これについて以下で説
明する。内部メモリに格納されるこのサンプルは、ＡＶ
ＬまたはＲＢツリーのような平衡ツリーを使用して、格
納される。Ｄ、　Ｅ、　Ｋｎｕｔｈ、”Ｔｈｅ　Ａｒｔ
　ｏｆ　ＣｏｍｐｕｔｅｒＰｒｏｇｒａｍｍｉ　ｎｇ”
、Ｖｏｌ、ｕｍｅ３　：　“Ｓｏｒｔｉｎｇ　ａｎｄＳ
ｅａｒｃｈｉｎｇ”、　Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ
、１９７３を参照されたい。平衡ツリーによる分類によ
って、分類時間がサンプリングと部分的に重複してもよ
いことになる。完全を期すため、「ツリー」はサイクル
を持たない連結グラフであることが望ましい。

さらに、「有向ツリー］はサイクル及び代替経路を何ら
含まない有向グラフである。有向ツリーは、子孫のセッ
トが他の全ての節点（ノード）からなっている「−意の
節点（ルート）」を有している。

本発明において、平衡ツリーの各節点には、キーのため
の記憶スペース、ならびに分類のための２つのポインタ
が必要である。ちなみに、祖先子孫という述語が、節点
の関係を述べるのに使用されている。それゆえ、左側の
子孫のキー値が、親のキー値以下である、ということが
できる。同様にして、右側の子孫のキー値は、親のキー
値以上となる。キー及びポインタの平衡ツリー構成の例
を、第１図に示す。サンプル・フェーズの最後の部分で
は、昇順のツリーのキーに向けられるポインタの順次リ
ストを作成するために、平衡ツリーの順を追った横断が
必要である。第１図の平衡ツリーに対応したポインタの
リストを第２図に示す。

上述の通り、このステップには、８個のキーのランダム
・サンプリングとサンプリングされたキーの内部分類が
含まれている。磁気バブル・メモリの形の連想記憶装置
においては、各レコードはＭＢＭのランダム・アレイに
格納される。第３図にアレイを示すが、これについて以
下で説明する。

サンプリングは、レコードがＭＢＭに書き込まれている
間に行なわれる。入力ファイルのレコードがＭＢＭに既
に常駐している場合には、これらはランダム・アレイに
格納されているものとみなされる。常駐していない場合
には、これらをアレイ内でランダムに暗号化しなければ
ならない。

かかる装置におけるサンプリングは、次のようにして行
なわれる。

まず、各アレイからサンプルとして選択されるレコード
数が、多項分布に基づいてランダムに選ばれる。独立多
項ランダム変数の生成方法は、Ｄ、　Ｅ、　Ｋｎｕｔｈ
、”Ｔｈｅ　Ａｒｔ　ｏｆ　ＣｏｍｐｕｔｅｒＰｒｏｇ
ｒａｍｍｉｎｇ”、Ｖｏｌｕｍｅ　２：“Ｓｅｍｉｎｕ
ｍｅｒｉｃａｌＡｌｇｏｒｉｓｍｓ”、Ａｄｄｉｔｉｏ
ｓｏｎ−Ｗａｓｌｅｙ、２ｎｄ　ｅｄｉｔｉｏｎ。

１９８１に記載されている。次いで、順序ランダム・サ
ンプリング法を使用して、各アレイから所望数のキーを
選択する。これに関しては、　Ｊ、　Ｓ。

Ｖｉｔｔｅｒ、　”Ｆａｓｔｅｒ　Ｍｅｔｈｏｄ　ｆｏ
ｒ　Ｒａｎｄｏｍ　Ｓａｍｐｌｉｎｇ”、Ｔｅｃｈｎｊ
ｃａｌ　Ｒｅｐｏｒｔ　Ｃ５−８２−２１、Ｂｒｏｗｎ
　Ｕｎｉｖｅｒｓｉｔｙ。

Ａｕｇｕｓｔ　１９８２を参照されたい。サンプリング
され＝１２− たキー値は、ついで内部メモリに読み込まれ、上述のよ
うに、平衡ツリーに挿入される。

（パケット　多　フェーズ このフェーズは、計算サブフェーズと結合サブフェーズ
とに分けられる。サンプル・フェーズで分類されたサン
プリングされたキー値は、ファイルをＳ＋１の範囲の区
画に分けるのに役立つ。この場合、分類されたキー値は
、Ｘｌ、Ｘ２・・・・、ＸＳと表される。また、ｘｏは
−のにセットされ、Ｘ８４１は＋のにセットされる。１
からＳ＋１までの閉区間の各値ｉに対し、ｉ番目の範囲
は、キー値が半閉区間ｘト、ないしＸ−にあるレコード
のセットになるように定義される。

各範囲は標準偏差が約Ｎ／Ｓの平均Ｎ／Ｓのレコードを
含んでいる。Ｓの値は、内部メモリに入れることのでき
るレコード数ＦよりもＮ／Ｓがはるかに小さくなるよう
に選択される。これについては、以下で検討する。

キーの格納順序を、サンプル・フェーズの最期の段階で
作成された順次ポインタ・リストによって表わすことが
できる。

重要なのは、計数サブフェーズが各キーを連想記憶装置
で処理すること、及びフイボナツチ探索または等２進探
索のいずれかを、ポインタ・リストに行なって、小さい
範囲のどれがキーを含んでいるかを確認するとからなっ
ていることである。

この範囲のカウントは、１．ずつ増加させられる。

平衡ツリーのポインタ・フィールドがもはや必要ないの
であるから、範囲の上限を画定するキーのポインタ・フ
ィールドのツリーに範囲のカウントを格納できる。別の
記憶位置を必要とする最高順位の範囲のカウントの場合
を除き、これがあてはまる。

計数サブシステムのステップの順序を、第１表のパスカ
ル疑似コードを参照して説明する。

１表　範　ン　フェーズの　　サブフェーズ（Ｉｎｉｔ
ｊａｌｉｚｅ　ｔｈｅ　Ｃｏｕｎｔｓ）ｆｏｒ　ｉ：＝
１　ｔｏ　Ｓ＋１　ｄｏ　Ｐ［ｉｌ、ｃｏｕｎｔ：＝Ｏ
；（Ｐｒｏｃｅｓｓ　ｅａｃｈ　ｋｅｙ　ａｎｄ　１ｎ
ｃｒｅ＋ｎｅｎｔ　ｉｔｓ　ｒａｎｇｅ　ｃｃ＋ｕｎｔ
）ｆｏｒ　ａａｃｈ　ｋｅｙ　ｉｎ　ｔｈｅ　ｆｉｌｅ
　ｄ。

ｅｇｉｎ Ｐｅｒｆｏｒｍ　ａ　ｂｉｎａｒｙ　５ｅａｒｃｈ　ｏ
ｎ　ｔｈｅ　ｐｏｉｎｔｅｒ　ｕｓｔ　Ｐ　ｉｎ　ｏｒ
ｄｅｒ　ｔｏ　ｆｉｎｄｔｈｅ　ｖａｌｕｅ　ｉ　５ｕ
ｃｈ　ｔｈａｔ　Ｐ［ｉ−１］、ｋｅｙ＜“ｋｅｙ　ｖ
ａｌ、ｕｅ”＜Ｐ［ｉｌ、ｋｅｙ；ｉｆ　Ｐ［ｉｌ、ｃ
ｏｕｎｔ＜Ｖ　ｔｈｅｎ　Ｐ口］、ｃｏｕｎｔ：＝Ｐ［
ｉｌ、ｃｏｕｎｔ＋１ｅｎｄ； この場合、サンプル・フェーズの最期の段階で作成され
たポインタ・リストはＰで表される。Ｐの各要素は、キ
ー・フィールドとカウント・フィールドを有するレコー
ドのアドレスである。１とＳ＋１との間の各ｉに対して
、Ｐ　［ｉｌキーは格納された順序のｉ番目のサンプリ
ングされたキーである。値がＰ　［Ｓ＋１］のキーは、
＋ωであるとみなされ、キーが取り得る最大値よりも大
きな任意の数である。各１に対する、Ｐ　［ｉｌに格納
できる最大値Ｖは、Ｆよりも大きく、これは内部分類フ
ェーズ中に内部メモリに適合できるレコード数である。

係数サブフェーズの目的は、１とＳ＋１との間の各ｉに
対するＰ　［ｉ］カカラトの値を、レコード数が多くで
もＶである場合には、キー値が区間（Ｐ［１−１１キー
〈キー値≦Ｐ［ｉコキー）にあるレコード数に、それ以
外の場合には、値Ｖにセットすることである。

結合サブフェーズにおいて、隣接する範囲がまとめられ
、より大きな範囲が形成される。各グルーピングは、で
きるだけ多くの小さい範囲を結合し、結果として得られ
る結合された範囲が多くてもＦ個のレコードを含むよう
にする。結果として得られる各範囲は、はとんどの場合
、はぼＦに等しくなる。ちなみに、Ｆ個を越えるレコー
ドを含んでいるレコードを、「オーバーフロー範囲」と
呼ぶ。その後、オーバーフロー範の平均値と標準偏差が
１未満であることが、確立される。また、＝１６− 範囲に対する区画を画定するキーが、内部メモリにスペ
ースがなければ、公知のディスクまたはテープに順次出
力される。オーバーフロー範囲の場合、カウントまたは
特別なマーカが、範囲の上限を画定するキーと共に出力
される。

結合サブフェーズを実行する方法を、第■表のパスカル
言語疑似コード順序を参照して説明する。

■表　　　形　フェーズの　ムサブフエーズｅｎｄ： このパスカル類似の順序において、１とＳとの間の各ｊ
に対する値Ｐ　［ｉｌは、格納された順序のサンプリン
グされたキー値である。Ｐ［０］キー：＝−ω及びＰ　
［Ｓ＋１］キー＝十（１）とみなされるが、これらはキ
ーが取り得るあらゆる値よりも小さく、また大きい数で
ある。各ｉに対するＰ［ｉ］カカラトに格納できる最大
数を、■で表す。

１とＳ＋１との間のｊに対する値Ｐ　［ｉｌのカウント
は、■の最大数、及びキー値が（Ｐ［ｉ−１］キー〈キ
ー値≦Ｐ［ｉ］キー）にあるレコード数である。■の値
はＦよりも大きく、これは内部分類フェーズ中に内部メ
モリに適合できるレコード数である。プログラミングを
簡単にするために、特別なカウント・フィールドＰ　［
Ｓ＋２］カウントがあるものとする。

結合フェーズの出力は、結合された範囲の終点を画定す
るキー値のリストである。

レコードが固定長ではなく、可変長である場合には、本
方法を次のようにして、変更することができる。係数サ
ブフェーズにおいて、各範囲に対するカウントは、この
範囲内のレコード数ではなく、この範囲内のレコードが
占める全スペースをカウントする。結合サブフェーズに
おいては、できるだけ多くの隣接範囲が結合され、結果
として得られる範囲の各々のレコードが内部メモリに適
合できるようにする。

血皿分兼λ玉ニス このフェーズにおいては、範囲を画定するキーが順次処
理される。各範囲に対し、その内部のレコードが想連探
索によって検索され、分類され、次いで出力ファイルに
付加される。範囲がオーバーフロー範囲になければ、そ
のレコードの全ては内部メモリに適合するので、内部で
分類することができる。この場合、範囲内のレコードの
分類に、交換選択を使用するが、これは各範囲を再初期
化する必要がないからである。範囲内のレコードが２次
記憶装置から検索されれば、次の範囲のレコードの検索
が始まる。これは、最初の範囲の全てのキー値が２番目
の範囲の全てのキー値以下であること、ならびに範囲内
のレコードが交換選択ツリーに適合できることに依存す
るものである。範囲がオーバーフロー範囲であるという
まれな場合には、本発明方法を再帰的に適用するか、あ
るいは公知の分類組合せを用いるかのいずれかによって
、範囲の分類を行なうことができる。上記のように、か
かるオーバーフロー範囲の数は、はとんど常に１未満で
ある。

サンプル・す４ヌ唱Ｊ１ぴ閏１し仙艷ｕ」」１仁スｙ□
の選択 サンプリングされたキーの数Ｓは、平均数及びオーバー
フロー範囲の数の標準偏差が１未満でなければならない
という目的に従って、必要な内部メモリの量を最小限の
ものにするように、選択される。Ｍ及びＳの値は、次の
式によって関連付けられる。

（］、）　　Ｓ＝　（Ｍ−２Ｂ）／　（Ｋ＋３Ｐ）Ｍ及
びＳの値を、２つの変数Ｍ及びｒ（ただし、ｒ＝Ｅ　（
Ｓ＋１）（Ｎ＋１）である）の２つの式を解くことによ
って、計算できる。上記の目的を達成できることを保証
する最初の式は、次のとおりである。

ただし、Ｂ及びＢ′は人出力バツファのサイズであり、
Ｐはポインタ・フィールド当りのバイト数である。２番
目の式は、次のとおりである。

（３）　　（Ｍ−２Ｂ＋に＋３Ｐ）（Ｍ−２（Ｂ＋Ｂ’
））＝ｒ（Ｎ＋１）（Ｒ＋Ｐ）（Ｋ＋３Ｐ）この式はサ
ンプリングされたキーＳを内部に格納できることを保証
するものである。これら２つの式を解いて得られるＭの
概算値は、次のとおりである。

上記で計算したＭの値よりも多い内部メモリが利用でき
る、たとえばｋＭバイトの内部メモリを利用できるので
あれば、分類の総時間は、大体係数にだけ減少する。

磁気バブル・メモリに実施した連想２次記ｍ連想２次記
憶装置は、次の形式（プログラム言語）の連想探索また
は範囲照会と呼ばれる照会を処理する。

Ｇｊｖｅｎ　ｖａｌｕｅｓ　ａ　ａｎｄ　ｂ＋ｒｅｔｒ
ｊｅｖｅ　ａ］、１　ｒｅｃｏｒｄｓｓｕｃｈ　ｔｈａ
ｔ　ａ“ｋｅｙ　ｖａｌｕｅ”≦ｂこの照会は、本方法
の内部分類フェーズ中に、各範囲に対し１回行なわれる
。これは実行時間の大幅な削減をもたらす。データベー
ス適用業務における連想２次記憶装置への磁気バブル・
メモリの使用法の詳細は、前出のＣｈａｎ、　Ｄｏｔｙ
及びＬｉｎの参照文献に記載されている。

第３図は、数レベルの階層を形成する複数個のカートを
包含する磁気バブル・メモリ（ＭＢＭ）２次記憶装置を
示すものである。最高レベルにおいて、メモリは数百メ
ガバイトの容量を有する幾つかのボックスからなってい
る。ボックスをボードに区分できるが、このボードは数
個のチップを含む数個のモジュールを含んでいる。キー
となる記憶装置をアレイと呼ぶ。第３図は幾っがのアレ
ス１５．１７．１９を示す。各アレイは複数の磁気バブ
ル・ループ２１．２３．２５．２７を有する。各アレイ
は大きな記憶容量を持つことが望まれる。アレイにはＲ
ＡＭバッファ３が組合わされている。バッファ３は幾つ
かの磁気バブル・アレイに対して読み又は書きバッファ
として働らく。

約２０００ビツトのＲＡＭが各１メガビツトのアレイに
使用される。アレイ１５または１７または１９から、Ｒ
ＡＭバッファ３へ各レコードを転送することによって、
連想探索が行なわれる。ＲＡＭ３に結合しているマイク
ロプロセッサ３３は、パス２からパス１へ、キー値が範
囲紹介を満たす全てのレコードを選択し、転送する。ア
レイ１５を、たとえは、ＲＡＭ３に結合しているパス３
０及び３２は、１メガバイト／秒の速度で駆動される。

以下で説明するように、アレイ１５がデータを、この速
度でループからＲ２Ｈへ放出できると仮定すると、アレ
イの全ての内容を、１秒で探索できることになる。全て
のアレイを平行して探索できるので、連想探索当りの全
時間が１秒となり、有利である。

典型的な１メガビツトのアレイ１５は、最大１０００個
の同期した小ループ２１．２３．２５．２７からなって
いる。各ループは、変動磁場に応じてループを回転する
１０００ビツトを表すようにコーディングされた磁気バ
ブルを含んでいる。

この場合、レコードは小ループに格納される。すなわち
、レコードのビットは、ループの同一相対位置に、それ
ぞれ１ビツト／ループで格納さる。

１０００ビツトを越えるビットを含んでいるレコードは
、これらを幾つかのアレイに拡張するか、あるいは隣接
する１０００ビツト・セクションに区分するかして、格
納される。いずれの場合においても、セクション中の各
ビットは、同一相対位置の別個の小ループに格納される
。

必要に応じ、レコードが幾つかのアレイに拡張されると
仮定すると、レコードの全てのビットは、同期して、ル
ープ内の同一点に同時に到達することになる。小ループ
の各読取りアクセスは、非破壊性のものとみなされる。

読取りは、各ビットを複写し、複写ビットを１０００ル
ープ読取リバツフアにロードすることによって、行なわ
れる。読取りシフト・レジスタＲ８Ｒ２９が空で、利用
できる場合、ビットをＲ２Ｈにロードできる。次いて、
ビットは順次、読取りヘッド９によってシフトされる。

書込み操作は、書込みシフト・レジスタＷＳＲ３１を使
用して、同様な方法で行なわれる。

小ループの循環に必要な時間は、］、　ＯＯＯビットを
読取りヘッドによってＲ２Ｈへ移動するのにかかる時間
に等しい。これは約０．００１秒である。シフトがＲ８
Ｒで完了すると、１０００ループ読取リバツフアには、
次のレコードをロードする時間ができる。それゆえ、フ
ァイル全体を、１０００ＸＯ，０Ｏ１＝１秒でＲ８Ｒに
ロードし、読み取ることができる。これは１メガビツト
をアレイ１５からＲＡＭ３に転送するのにかかる時間に
対応している。連想探索当りの時間は、従って、１−秒
となる。

１５及び１７のような２つのアレイが、単一の読取りパ
ス３０を共有している場合には、連想探索時間は、１秒
ではなく、２秒となる。１〜２秒程度の連想探索が、分
類性能には極めて適切なものであることがわかった。以
下で説明するマーキング技術を使用して、有効連想探索
時間を数分の一秒まで短縮することができる。

作菊４ヒする修正 実行時間、及び本発明の外部分布分類法を支援するのに
必要な内部メモリの大きさの両面での経済性を達成でき
る。本方法は大まかに３つのステップを行なうものであ
る。これらのステップとは、（１）８個のキーのランダ
ム・サンプリング及び８個のサンプリングされたキーの
内部分類、（２）各々が内部ＣＰＵメモリに適合でき、
キー値の範囲を構成できるレコードの等サイズの区画を
単一パスに形成すること、（３）キーが範囲内にあるレ
コードの全ての連想検索を行ない、これらのレコードを
内部で分類することである。

キーの一様分布を想定する ランダム・サンプリング及びサンプリングされたキーの
内部分類ステップにおいて、キーが一様に分布している
場合に生じる高速分割によって、速度を上げることがで
きる。これは、内部メモリの所定部分に、次の処理を行
なうことによって達成される。まず、キーが取ることの
できる２５６にの範囲を、はぼｃ　Ｎ　Ｒ／　Ｍの等し
いサイズの区間に分割する。ただし、Ｃはｃ　＞　１の
定数である。各キーが処理されると、該当する区間のカ
ウンタが増加させられる。各キーの最初の数バイトが一
様に近い区画をもたらすのであれば、範囲形成フェーズ
のファイルへのパスを省略し、一様な区間のカウントで
置き換えることができる。

五皿分１Ｙ援助するマーキング技 キー値が範囲内にある全てのレコードを連想検索し、こ
れらのレコードを内部で分類するステップにおいて、上
記した探索には、１〜２秒が必要であった。しかしなが
ら、磁気バブル・メモリ連想記憶をＣＰＵに結合してい
る経路は、Ｍバイト（内部メモリへの１回のロード）の
転送にかかる時間を上記のほんの数分の１に減らすこと
ができる。ファイル内のＮＲ／Ｍのレコードごとにほぼ
１つのレコードが、所定の範囲に属することがわかって
いる。従って、所定の範囲内のレコードの全体的な検索
のほとんどには、範囲照会を満たさないレコードの処理
が含まれる。レコードのほとんどを検索することを回避
することにより、検索の速度を上げることができる。Ｍ
ＢＭに格納されており、かつ「マーク・ビット」として
使用されるレコード当り１個の特別ビットを使用するこ
とが、有利である。レコードには、マークを付けても、
付けなくでもよい。連想記憶アーキテクチャを変更し、
マークの付けられたレコードだけが大ループから読取り
シフト・レジスタ２９に転送されるようにしなければな
らない。キー値の所定範囲内のキーを得るための照会の
プログラム言語は、次の形を取る。

Ｇｉｖｅｎ　ｖａｌｕｅｓ　ａ　ａｎｄ　ｂ　ｒｅｔｒ
ｉｅｖｅ　ａｌｌ　ｍａｒｋｅｄｒｅｃｏｒｄｓ　ｉｎ
　ｔｈｅ　ｓｅｍｉ−ｃｌｏｓｅｄ　ｒａｎｇｅ　ａ“
ｋｅｙｖａｌｕｅ”≦ｂ。

説明のため、ファイルをに個のほぼ等しいサイズの領域
に分割するに一１個の順序付けられたキー値があるもの
と想定する。Ｋ−１個の順序付けられたキー値は、範囲
形成フェーズの結合サブフェーズ中に得られる。内部分
類フェーズを、Ｋ個の連続したサブフェーズに分けるこ
とができる。

この場合、ｉ番目のサブフェースは、Ｋ−１個の隣接キ
ー値によって形成されたｉ番目の領域内にある書く各範
囲の検索及び分類を含んでいる。ｉ番目のサブフェース
の始まりで、ｉ番目の領域の全てのレコードにマークが
付けられ、その他の全てのレコードにマークが付れられ
ていなければ、１回でほぼＮ／に個のレコードにマーク
が付けられ、従って各範囲検索で処理されるレコードの
数は、係数にだけ減少する事になる。Ｋ回の処理ステッ
プの各々では、１回の完全な連想探索が必要となる。総
処理時間は、無視できるものである。

各連想探索中に、範囲照会を満たす全てのレコードのマ
ークの付いたビットがオフにされるのであれば、さらに
改良を行なうことができる。それゆえ、各サブフェーズ
の始めで、ぼぼＮ／にのレコードにマークが付けられる
が、マークの付けられたレコードの数は、サブフェーズ
の終りでゼロになるまで、直線的に減少することになる
。これを第４図に示す。しかしながら、各連想探索で処
理されるレコードの平均数は、約Ｎ／（２Ｋ）となる。

なお、範囲照会を、２つの比較ではなく、１つの比較し
か要求しない下記の照会に書き換えることができる。

Ｇｉｖｅｎ　　ｖａｌｕｅｓ　　ｂ、ｒｅｔｒｉｅｖｅ
　　ａｎｄ　　ｕｎｍａｒｋ　　ａｌｌｍａｒｋｅｄ　
ｒｅｃｏｒｄｓ　　５ｕｃｈ　ｔｈａｔ　“ｋ　ｅ　ｙ
　ｖ　ａ　］、　ｕ　ｅ　”≦ｂ＋この形式の照会は、
範囲（ａ　“ｋｅｙ　ｖａｌ、ｕｅ”≦ｂ）が処理され
ている間に、ａ以下のキー値を有するキー値からマーク
が取り除かれるのであるから、以前の照会と等価である
。

［発明の効果コ 本発明の好ましい実施例を説明したが、各種の改変を本
発明の原理に従って行ない得ることを理解されたい。例
えば、経験上、ＲＡＭ３が余分のマークの付いたビット
のための、あるいはアドレスの待ち行列を形成するため
の余分の記憶域を有していることが好ましいことがわか
っている。さらに、入力ファイルの各論理レコードが、
幾つかの物理レコードにおよぶように、ＭＢＭに極めて
小さい論理レコードを置くか、あるいは各物理レコード
が複数の論理レコードを含むように、極めて大きい物理
レコードを置くかのいずれかによつて、ＭＢＭ連想記憶
の記憶域の利用度を最大限のものにできる。上記のマー
キング技術は、物理レコードのサイズが、論理レコード
のサイズに比較して小さい場合に、より効率がよくなる
。

連想探索当りの時間、及び格納されている各範囲に対す
る最終出力時間が十分短いものであれば、内部分類フェ
ーズの稼働時間は、ＣＰＵ時間によって支配され、入出
力時間によっては支配されない。この場合、内部メモリ
にほぼ２倍のスペースを割り振り、これを２つに分割す
ることによって、内部分類フェーズをはるかに高速にで
きる。内部メモリの容量は、Ｍ’＝２　（Ｍ−２（Ｂ＋
Ｂ’　）　）に増加する。ただし、Ｍは以前の内部メモ
リの容量である。

各範囲の内部範囲が、動的なものではなく、静的なもの
なのであるから、交換選択の代りに、交換選択のほぼ２
倍の速度であるクイックソートやラデイツクスのような
静的内部分類法を使用できることに留意されたい。内部
分類フェーズに対するＣＰＵ時間は約５０パーセント削
減される。

現在、大規模なデータベースがＤＡＳＤにラン＝３２− ダム・アクセス方式で格納されており、これは探索時間
を速くするために、ハツシュ及び索引手法を使用してい
る。上述のＭＢＭ技術により、データベースをＭＢＭに
格納でき、より高速なランダム・アクセスの利点を利用
できる。同じハツシュ及び索引手法を使用できる。この
方式のデータベース・システムは、ＤＡＳＤに格納され
ているデータベース・システムよりもはるかに高速で１
−ランザクジョンを処理することができる。

さらに、ＭＢＭに格納されているデータベースは一般の
リレーショナル・データベース照会を、連想探索を行な
うことにより１秒車位で、迅速に実行できる。これはデ
ータベースがＤＡＳＤに格納されている場合には、達成
できなかったことである。換言すれば、ＭＢＭをランダ
ム・アクセス装置、あるいは連想装置のいずれかとして
、現在のトランザクションまたは照会にいずれか効率の
よい方を使用できる。分類法は、リレーショナル・デー
タベースの一般的な操作のひとつとして検討できるもの
である。

【図面の簡単な説明】

第１図は、サンプル・フェーズ中に作成された必要なポ
インタを含む、分類されサンプリングされたキーの平衡
ツリーの図である。 第２図は、サンプル・フェーズ中に作成されたポインタ
・リストの図である。 第３図は、本発明方法の連想探索を実行するための典型
的な連想記憶カードの図である。 第４図は、実施されるマーキング技術の図である。 ３・・・・ＲＡＭバッファ、５・・・・エラー・コード
・テスト、９・・・・読取り、１１・・・・書込み、１
５．１７．１９・・・・アレイ。 出願人　　　インターナショナル・ビジネス・マシーン
ズ・コーポレーション

Claims (1)

1. 【特許請求の範囲】 利用可能な内部メモリを有するＣＰＵにより、連想２次
   記憶装置からアクセスされるキー付きのレコードを含ん
   だデータを再配列するため外部分布分類を実行する方法
   であって、 Ｓ個のキーのランダム・サンプリングを行い、サンプリ
   ングされたキーをＣＰＵ内で内部分類するステップと、 キーのヒストグラムとキー値の範囲を得ることによって
   、単一パスに等しいサイズの区画を形成し、各区画がＣ
   ＰＵの内部メモリに適合するように隣接する密度の小さ
   い範囲を結合して大きい範囲を形成するステップと、 キーが区画の範囲内にあるすべてのレコードを連想検索
   し、該レコードを内部分類するステップと、 より成る外部分布分類を実行する方法。