JP2501430B2 - デイジタル式情報記憶検索装及び方法 - Google Patents

Description

【発明の詳細な説明】 本発明はディジタル情報の記憶ディスクに記憶された
情報の検索、特に情報記憶ディスクに記憶されたユーザ
データを迅速かつ効率的に検索するディジタル式情報記
憶検索装置及び方法に関するものである。

磁気テープ駆動装置等の情報記憶装置を用いる場合、
記憶したデータを系列的に読出すので、索引法を改善す
る必要性は非常に少ない。しかしながら、ランダムアク
セス情報記憶ディスクが発展するにつれ、ユーザ情報の
特定のブロックを検索するために、効率的な索引付けに
対する需要が増加している。また、ディジタルデータ
は、従来、情報記憶ディスクに一層稠密に書込まれるた
めに、特定のユーザデータを迅速かつ効率的に検索し、
読み出す索引検索装置を開発することはむしろ一層困難
になっている。

この問題に対する初期の解答はディスクデータを索引
付けする方法で与えられた。即ち、求める特定のデータ
グループを見出すために、若干効率良く索引を検索でき
かつ更に大きなデータグループを独自に識別する手短な
一般にキーと呼ばれる操作手段がユーザデータに与えら
れた。ユーザデータのヘッダ部分に或る独自の識別キー
（検索キーidentifier）を付与しかつ個別メモリにその
識別キーを分類するか又はユーザデータの或る独自の特
性を取りその値をキーとして用いるかのいずれかにより
一般に検索する。磁気ディスクに記憶されるデータはホ
スト中央処理ユニットに転送され、特定のデータブロッ
クのプラッタの内容と場所を示す拡張索引が与えられ
る。IBMカウントキー方式のように、この方法の初期の
例では、データ記憶と効率的な検索の問題をある程度解
決できた。

しかしながら、ディスク面上にデータが更に稠密に書
込まれ、ディスク面上でより多くの場所が索引に必要と
なるため、更に効率のよいディスク索引システムが必要
となることは明かである。ユーザには記憶されたデータ
に迅速にアクセスすることを常に要求される。索引が広
範な程、特定のユーザデータの組の検索に必要な検索時
間が長くなる。ディスク面にデータがより稠密に書込ま
れる程、検索時間は増加し、システムの効用が対応して
減少する。また、１つ以上のキー索引法に基づいて特定
の組のデータ用の所与のデータベースをユーザが検索す
る必要性が生じる。このために、求めるデータを最初に
索引する方法以外の「分類」法に基づいて、前記データ
を一層効率的に検索できる効率的で時間短縮できる多重
キーシステムが必要となる。例えば、ソーシャルセキュ
リティナンバ（social security number）に関してデー
タを分類索引する場合、アドレス又はエージ（age）に
より行う効率的な検索は最も困難になる。使用されるこ
のシステムは一般に単一の識別キー及び索引に対する分
類法を有する。

更に最近は、取り外し可能な記憶媒体を有する記憶装
置の開発も進展し、ディスク面に記憶されたデータを効
率的に索引する検索装置の必要性が一層高まってる。デ
ィスクの記憶されたデータに効率的にアクセスするに
は、ディスクが完全な索引を具備しなければならず、ま
た多数の記録用ディスクを使用せずに記録用ディスクの
単一のプラッタに多量の情報を記録する傾向に記憶装置
が開発されるので、効率的な索引システムに対する必要
性が増大している。

特に重要な事は、ライトワンスオンリー（write once
only）機能を有する光学媒体が開発されたため、従来
の索引検索法が不適切になっている。消去可能な磁気デ
ィスクではデータは代替可能であり、容易に再配列可能
である。特に、データが特定のシーケンスを持ち、その
データに挿入すべき新しいデータが与えられると、適切
な位置に新しいエントリを配置するデータを再記憶する
ことが比較的容易になる。また、プラッタ面（ディスク
面）の欠陥によりデータの記憶が妨害されても、そのデ
ータを他の場所に記憶でき、また記憶されたポインタ
（アドレスを収容するレジスタ）が新しい記憶場所に導
かれ、ホスト中央処理ユニットがプラッタ面の所定の記
憶位置にデータを記憶したものとして取り扱うことがで
きる。これらの方法は消去不可能な記憶媒体を用いた場
合は実施不能となる。従って、データを書込み、そのデ
ータを索引付けしかつ検索する新しい方法を開発しなけ
ればならない。かくて、記録用ディスクの情報を記録す
る重要なプラッタ面の全記憶容量を消尽しておらず、書
き込み可能な残り容量を含む情報記憶ディスクの全てに
対しての効率の良い索引検索装置が必要となる。更に、
索引付けのためにるプラッタ記憶容量を増加せずに、多
重分類索引方式に基づいて単一のプラッタ面のより多量
のデータにユーザが効率的にアクセスできる手段が必要
となる。また、「ライトワンスオンリ（write once onl
y）（一度だけ書込める）」ディスクに対し、少なくと
も消去可能媒体と同様に効率良く書込み、索引付けし、
検索できるシステムが要求される。更に最後に、取り外
し可能な記憶媒体を有する記憶装置に対する索引（イン
デックス）をサポートし得るシステムが必要となる。

従って、本発明の目的は、検索結果を用いて各ユーザ
バンド内で空いているユーザブロックに新しいデータの
書き込みが可能なディジタル式情報記憶検索装置及び方
法を提供することを目的とする。

本発明によるディジタル式情報記憶検索では、索引レ
ジスタ（23）を備えたランダムアクセスメモリ及びマイ
クロプロセッサ（７）を有する記憶装置（６）と、ホス
ト中央処理ユニット（１）とを含む情報記録システム内
に、索引バンド（11）と複数のユーザバンド（12）とを
備えた情報記録ディスク（９）が配置される。異なるビ
ット数長さの複数種類のキー値を、物理的ID（18）と共
にユーザデータブロック（14）のヘッダ（16）内に直列
に配置し、情報記録ディスク（９）にキー値を有するユ
ーザデータブロック（14）内に既に記録された又は記録
すべきユーザデータ（17）をデジタル方式で索引付けし
かつ検索する。

このディジタル式情報記憶検索では、まず、ホスト中
央処理ユニット（１）からの指令を検出し、ユーザバン
ド（12）内を検索するために書き込むべきユーザデータ
ブロック（14）に対するキー値が、ユーザバンド（12）
内に予め記憶されたユーザデータブロック（14）に対応
する最低のキー値より小さいか否かを決定する。このよ
うに、ホスト中央処理ユニット（１）の指令を検出し、
ユーザデータブロック（14）を書き込むための予め指定
されたユーザバンド（12）の有効性（アベイラビリテ
ィ）が決定される。次に、書き込むべきユーザデータブ
ロック（14）に対するホスト中央処理ユニット（１）か
らのキー値が、ユーザバンド（12）内に予め記憶された
ユーザデータブロック（14）に対応する最低のキー値よ
り小さいとき、誤り指令を発生する。続いて、ユーザバ
ンド（12）内に予め記憶されたユーザデータブロック
（14）に対応する最低のキー値より大きなキー値を、書
き込むべきユーザデータブロック（14）が有する場合、
ホスト中央処理ユニット（１）からの指令に従い指定さ
れた索引バンド（11）に最低のユーザキーを書き込む。
各ユーザバンド（12）に対する予め記憶された最低のキ
ー値を索引レジスタ（23）に入力する。

ターゲットキー値を有するユーザデータブロック（1
4）の読出しが必要な検索時に、ポインタテーブル（2
7、28、29）内で索引レジスタ（23）に入力された前記
キー値のうち同一種類のキー値を小さい値から大きい値
に順に分類する。また、ターゲットキー値より小さいか
又はこれに等しい前記ターゲットキー値に最も近いキー
値を有する単一のユーザバンド（12）を探索するまで、
ポインタテーブル（27、28、29）内で上方又は下方にポ
インタテーブル（27、28、29）内で分類された前記キー
値の中央値とホスト中央処理ユニット（１）からの指令
による最低のユーザキーのターゲットキー値とを比較す
る。ターゲットキー値より小さいか又はこれに等しい最
高のキー値を有する単一のユーザバンド（12）を探索す
るとき、ポインタテーブル（27、28、29）内で上方又は
下方に移動するプロトコルを使用する。最後に、ターゲ
ットキー値を有する識別したユーザデータブロック（1
4）を含む単一のユーザバンド（12）を検出しかつその
存在をホスト中央処理ユニット（１）に知らせる。

本発明の好適実施例では、同心状の索引バンド（11）
及びユーザバンド（12）がディスク（９）に形成され、
各ユーザバンド（12）はその中に複数のユーザトラック
（13）を持ち、各ユーザトラック（13）はその上に複数
のユーザデータブロック（14）を有する。記憶すべきホ
スト中央処理ユニット（１）内のデータは、通常ユーザ
データブロック（14）内に構成される。ユーザデータの
ブロックをホスト中央処理ユニット（１）から記憶装置
（６）に転送する前に、ユーザはデータの検索に用いる
キー値又は複数のキー値の１組を識別する。

本発明では、所与のユーザバンド（12）に対する記憶
装置（６）への制約条件（プロトコル）を要求し、ユー
ザデータブロック（14）に対するキー値がユーザバンド
（12）内に予め記憶されたキー値より小さい場合、情報
の如何なる新しいユーザデータブロック（14）もユーザ
バンド（12）に記憶されない。ユーザバンド（12）内に
予め記憶されたキー値より小さいキー値を有するユーザ
データブロック（14）を記憶すると、ディスク（９）上
の既存のユーザデータブロック（14）を消去することに
なるからである。

ディスク（９）のユーザバンド（12）にデータが記憶
されると、記憶装置（６）は、ユーザデータブロック
（14）に対するキー値を索引バンド（11）に書込まれた
キー値と比較し、ユーザデータブロック（14）に対する
最低キー値を識別し、その値がより低い値の場合、誤り
指令を発生して、ディスク（９）への記憶を行わず、単
に記憶装置（６）内に記憶する。従って、索引バンド
（11）の最後のエントリは任意のユーザバンド（12）に
記憶された最低キー値を示す。最低のキー値を示す最後
のエントリが索引バンド（11）に書き込まれると、記憶
装置（６）のランダムアクセスメモリに配置された索引
レジスタ（23）に記入される。索引レジスタ（23）は、
ディスク（９）面上のユーザバンド（12）の物理的番号
であるバンドアドレス（Ａ〜Ｇ）によって構成され、索
引レジスタ（23）の内容はユーザバンド（12）上の最低
キー値を含む。

記憶装置（６）のランダムアクセスメモリは、記憶装
置（６）のユーザが指示する各ユーザキーに用いられる
ポインタテーブルレジスタ（27、28、29）を備えてい
る。ポインタテーブルレジスタ（27、28、29）内のキー
は、ユーザにより索引レジスタ（25）内で指令された特
定のユーザキーにより決定され、シーケンスで索引バン
ド（11）のバンドアドレス（Ａ〜Ｇ）の内容によって分
類される。例えば、第１のユーザキーが索引レジスタ
（23）の最初の５つのエントリに基づく場合、第１のポ
インタテーブル（27）は初めの５つのエントリのみを用
いてシーケンスに分類され、一方第２のユーザキーが索
引レジスタ（23）の最後の２つのエントリに基づく場
合、第２のポインタテーブル（29）は最後の２つのエン
トリの順に分類される。

検索の際に、ユーザはターゲットキー、即ち、配置す
べきデータに関するキーを識別する。このキーは求める
特定のユーザデータブロック（14）のヘッダ（16）内に
与えられる。この値は、キー開始レジスタ（34）に記憶
された情報と、キーの長さレジスタ（35）及び選択ポイ
ンタテーブル（33）と共に、ターゲットキーレジスタ
（32）に記憶される。検索を実施するために、ユーザ
は、選択ポインタテーブル（33）の用い方と、キー開始
位置を示すキー開始レジスタ（34）と読取られるべきキ
ーの長さを決定するキー長さレジスタ（35）とに関する
命令を記憶装置（６）に送出する。次に、探索動作が開
始される。記憶装置（６）は指示された選択ポインタテ
ーブル（33）を探索し、索引レジスタ（25）の中間位置
から中間値を最初に選択し、次に索引レジスタ（25）に
含まれる適切なキー値を読取る。続いて、記憶装置
（６）はターゲットキー値を索引レジスタ（25）から読
取られたキー値と比較し、また、好適実施例では、その
後、ターゲットキーより小さな最大キーが配置されるま
で、ポインタテーブル（27、28、29）と前後して２進探
索を実施することができる。この時点で記憶装置（６）
は、データが存在する場合にそれが配置されるポインタ
テーブル（27、28、29）から識別されるユーザバンド
（12）に読み書きヘッドを移動することができる。

本実施例では、記憶装置（６）の一部である情報記憶
ディスク（９）のユーザデータ（17）を索引付けし検索
することができる。ディスク（９）は複数のユーザバン
ド（12）と索引バンド（11）とを有し、ユーザバンド
（12）は複数のデータトラックロケーションを備えてい
る。記憶装置（６）は、マイクロプロセッサ（７）及び
ランダムアクセスメモリを有する。

第１図に示すように、本発明の好適実施例では記憶す
べきデータは、ホスト中央処理ユニット１のチャネルイ
ンタフェースバッファ２に先ず記憶され、前記データは
ディジタル式情報記憶検索装置の制御装置３に転送すべ
きユーザデータブロック14を構成する。好適実施例で
は、7904バイトの情報はユーザデータの単一ブロックか
らなる。構成されたユーザデータブロック又は複数のユ
ーザデータブロックは、制御装置３に転送され、バッフ
ァ４に記憶された後、マイクロプロセッサ５により記憶
装置６のマイクロプロセッサ７により記憶装置６のバッ
ファ８を通過可能となり、更に記憶装置６のディスク９
に転送されて記憶される。図示しないが、記憶装置６
は、索引キーを記憶する索引記憶手段、索引記憶手段を
分類するソート手段及び索引記憶手段を検索するサーチ
手段を備える。

ディスク９のフォーマットは、第２図に略示するよう
に、粗調−微調サーボ検索動作によりユーザバンド12の
位置を検出するクロック信号を発生するための複数本の
同心トラック10を有する。好適実施例では、ディスク９
は１つの索引バンド11と714本のユーザバンド12とを持
ち、各ユーザバンド12は、第３図に示すように、48個の
ユーザデータトラック13を有する。好適実施例では、各
ユーザトラック13は最大15個のユーザデータブロック14
を記憶できる。ディスク９の索引バンド11は記憶装置６
のデータ索引機能に用いられる。

好適実施例では、ディスク９は取り外し可能、消去不
能な記憶媒体であり、またライトワンスオンリ機能のた
めに、実際の書込み前ではディスク９面上のデータの物
理的記憶場所は不明であり、ディスク９に対する完全な
索引エントリをディスク９上に配置することが必要とな
る。従って、新しい記憶装置６に配置するとき、ディス
ク９の内容を読出し、索引付けしかつ検索することがで
きる。

書式配置（フォーマッテイング）の条件により、記憶
装置６のプロトコルは、ユーザバンド12に対するユーザ
データ17を増大するキー番号順に記憶することを要求す
る。従って、所与のユーザバンド12には、以前に記憶さ
れたユーザデータブロック14のキー値以下のキー値を有
するデータのユーザデータブロック14は何ら記憶されな
い。従って、記憶されたユーザバンド12に対して、第２
のユーザデータブロック14は第１のユーザデータブロッ
ク14より大きなキー値を常に持ち、第３のユーザデータ
ブロック14は第２のユーザデータブロック14より大き
く、以下同様に与えられる。しかしながら、ユーザバン
ド12自身を系列的に記憶する必要はない。記憶装置６に
記憶する通常の順序は外径から内径へと進むが、ユーザ
の指示により記憶可能なユーザバンド12にデータが記憶
される。記憶すべき新しいユーザデータ17のユーザデー
タブロック14が所定のユーザバンド12に予め記憶された
キー値以下のキー値を持つ場合、記憶装置６は、記憶す
べきユーザデータブロック14のキー値に等しいか又はそ
れ以下の索引キーを割り当てて、別の新しいユーザバン
ド12に前記新しいユーザデータ17を配置する。

第４図に示すように、ホスト中央処理ユニット１は動
作時に包括キー15をユーザデータブロック14のヘッダ16
に配置する。ヘッダ16へのキーの使用は公知であり、IB
Mキーカウント方式がその１例である。しかしながら、
包括キー15には、複数の可変長の特定のユーザキーが配
置され、複数のユーザ指令キーに対する索引付け及び検
索を実施できる。データが記憶装置６に伝送されると、
記憶装置６は記憶前にユーザデータブロック14の始めに
物理的ID（PID）18を配置する。好適実施例では、記憶
装置６にデータを光学的に書込む時、データはライトワ
ンスオンリー容量であり、また、実際の書込み動作前で
は、ユーザデータ17をディスク９に物理的に配置する位
置をホスト中央処理ユニット１が認識できないために、
物理的ID（PID）18が必要となる。包括キー15はホスト
中央処理ユニット１により指定され、ユーザデータに対
するユーザバンド12の位置を決定すると共に、ユーザバ
ンド12内のユーザデータブロック14の位置を決定する。
包括キー15はユーザバンド12、ユーザデータトラック13
及びユーザデータブロック14をユーザバンド12内に系列
化する物理的ID（PID）18を含む。包括キー15は情報ユ
ーザデータブロック14をどのユーザバンド12に記憶すべ
きか及びデータを表示するユーザバンド12のどのユーザ
データブロック14を表すかをシーケンスで指示する。PI
D18はユーザバンド12、ユーザデータトラック13及びユ
ーザデータブロック14をユーザバンド12内に系列化し、
各ユーザデータ17が物理的にディスク９に記憶される。

第４図に示すように、記憶装置６がデータを記憶する
記憶装置６のディスク９面上に特定の記憶場所を決定し
た後、その記憶場所のPID18がディスク９に記憶され、
これに包括キー15が伴い、その後ユーザデータ17が伴
う。この例では、説明のためディジタル数字とα文字を
用いる。記憶されるデータは例えばASCII符号化方式に
よる２進数で与えられる。

第５図の表は、本発明の完全な機能を説明するため
に、記憶すべき複数のユーザデータブロック14の代表的
な組に用いられる包括キー15を示す。例えばユーザデー
タブロック14は３個の個別のユーザにより表わされる。
第１のキーは、ホスト中央処理ユニット１により与えら
れて所与のユーザデータブロック14をどのユーザバンド
12に記憶すべきかを指示し、またユーザバンド12内のユ
ーザデータブロック14の位置をシーケンスで指示する論
理ID（LID）キー19である。混乱を避けるため、キー値
は引用するが参照番号を省略する。例えば、第１エント
リに対して、LIDキー値00501は第５ユーザバンド12の第
１ユーザデータブロック14にデータを記憶すべきことこ
とを示す。エントリ２はLIDキー値00406を有するユーザ
データ17を第４ユーザバンド12の第６ユーザデータブロ
ック14に記憶すべきことを示す。第５図に例示するユー
ザキー１はユーザデータブロック14の検索時にユーザに
有用なユーザデータ17の値を単に例示し、ユーザキー２
は所与のユーザデータブロック14の検索時に有用なユー
ザデータ17の他の値を示す。項目を系列化する第５図の
順序はデータを記憶し得るシーケンスをランダムに説明
している。

第６図は、LIDキー19の値によりデータをディスク９
に記憶すべきシーケンスを形成するバンドアドレスＡ〜
Ｇのユーザバンド12を表示するディスク９にデータを記
憶する状態を示す。即ち、項目１が記憶され、続いて項
目２、項目３、項目４と最後の項目30が記憶されるまで
続けられる。ユーザバンド12による記憶を示す第６図は
第５図の表との比較から理解されるように、ディスク９
にデータを記憶すシーケンスと順序を示す。

新しいファイルが開かれデータが記憶されるとき、記
憶装置６は索引バンド11にPID18と包括キー15を記憶す
る。好適実施例では、索引バンド11は所与のユーザバン
ド12に対する最低キー値のみをリストする。索引バンド
11に記憶される第１のキーは索引バンド11に対する最低
キー値である。ユーザが所与の索引バンド11に以前に記
憶された情報の削除を決定して、割り当てられた新しい
キー番号と共に、その索引バンド11に新たな組のデータ
を記憶させれば、この新しいキー番号は以前に記憶され
たが削除されたキー値より小さくてもよい。

第7a図は項目１〜30に与えられたデータに対する索引
バンド11に記憶された値22のリストを示す。第7b図に示
すように、索引バンド11に転送されるデータは、記憶装
置６のランダムアクセスメモリの索引レジスタ23に読み
取られる。好適実施例では、索引アドレス24はデータを
記憶するユーザバンド12のバンドアドレスＡ〜Ｇであ
り、個別の索引レジスタ25は索引バンド11のユーザバン
ド12に対して記憶されるユーザデータブロック14から得
られる全包括キー15のキー値を記憶する。好適実施例で
は、索引レジスタ25にはディスク９上に書込まれるデー
タ順にキー値が記憶される。従って、第7b図に示すよう
に、第２のレジスタ25は内容00401 030 71を持つバンド
アドレスＤを有し、最後のエントリに一番近いレジスタ
25は内容00301 430 61のバンドアドレスＣを有する。

これを達成するために、索引レジスタ25の内容及びユ
ーザバンド12に関係するキー値に基づいて分類されたバ
ンドアドレスＡ〜Ｇを有する第８図に示す３個１組のポ
インタテーブル27、28、29が確立される。説明のため
に、本実施例では３つのポインタテーブル27、28、29を
使用する。ユーザデータ17を識別するために単一キーを
使用する場合、索引付けしかつ検索のために単にLIDキ
ー19の上昇するシーケンスに索引レジスタ25を配列する
ことができる。しかしながら、索引付けしかつ検索する
ためにユーザデータを多様に分類する能力を与える包括
キー15と共に、異なる改良された方法を実施できる。索
引キーを分類し、個々のキーの各組に対する異なる索引
レジスタ25で予備的に分類するため、付加的な組の索引
レジスタ25を用いて、多重のキーを有効に使用すること
ができる。

先ず、第7c図は、索引レジスタ25内に位置が存在する
場合と同じ個数の索引レジスタ25内の位置を有する索引
順序表26を構成する位置１、位置６及び位置９を示す。
索引順序表26での各個別位置の値は所与のキーに対する
分類すべき位置を表わす。例えば、位置１はLIDキー１
を分類するための索引順序表26内の第１位置で開始し、
ユーザキー２に対して索引順序表26内の位置６から分類
を開始し、またユーザキー３に対して索引順序表26内の
位置９から分類を開始すべきことを示す。

第8a図に示すように、位置１から始まるLIDキー19に
対する分類が最低キー値であるLID値0101 105 51（バン
ドアドレスＡに記憶される）であり、最高キー値0701 5
60 31（バンドアドレスＧに記憶される）であるから、
索引順序表26が昇順にリストされ、ポインタテーブル１
（27）のLIDキー19の分類は第7c図の位置１で開始す
る。第8d図に示すように、LIDキー19に対するポインタ
テーブル１はLIDキー19の値の順序を表わすバンドアド
レスＡからＧのシーケンスを構成して配列される。第7c
図に示すように、第２ユーザIDの分類は位置６で始ま
り、ポインタテーブル２（28）に対する分類はバンドア
ドレスＤに示すように第１の値03071であり、また最高
値はバンドアドレスＥに示すように62521である。従っ
て、第8b図に示すように、ポインタテーブル２は第１値
がバンドアドレスＤで最終値がバンドアドレスＥである
シーケンスを形成して配列される。第7c図に示すよう
に、ポインタテーブル３に対する分類は索引順序表26か
らの位置９の値で始まるユーザキー２に基づいて与えら
れ、第１の値はバンドアドレスＢに関する11であり、最
後の値はバンドアドレスＤからの71である。従って、第
8c図に示すように、ポインタテーブル３の索引レジスタ
25の初めの値をバンドアドレスＢで表わし、ポインタテ
ーブル３の最後の値をバンドアドレスＤで示す。

検索レジスタ25を設定すると、ユーザは拡張索引及び
迅速なバンド検索機能を用いてディスク９上のユーザデ
ータ17のユーザデータブロック14を検索することができ
る。例えば、第５図からのLID値00304、第１ユーザキー
値460及び第２ユーザキー値64を有するユーザデータの
リストの項目12に対して検索が実施される。第９図は、
ディスク９から読出すべきユーザデータに対するターゲ
ットキー値を示す。第9a図に示すように、包括キー15を
用いて索引付けしかつ検索を実施するために、ターゲッ
トキーレジスタ32、選択ポインタテーブルレジスタ33、
キー開始レジスタ34及びキー長さレジスタ35が記憶装置
６のランダムアクセスメモリに配置される。ターゲット
キーレジスタ32は、索引の結果を迅速なユーザバンドの
検索キーと比較するため、検索すべきターゲットキーの
値を保持する。選択ポインタテーブルレジスタ33は検索
する特定のポインタテーブルに対する値を保持する。キ
ー開始レジスタ34は、索引レジスタ25内の第１値の位
置、検索用のキー値を選択する索引レジスタ25内の位置
の値を保持する。

例えば、項目12に対する３個のキー値１、２、３の全
てが与えられる。第9b図に示すようにLIDキー19を用い
て検索する際には、ターゲットキーレジスタ内にターゲ
ットキー値をセットし、LIDキー19を用いた検索を表わ
す１に選択ポインタテーブル33をセットし、索引レジス
タ25内でLIDキー19が開始される位置である１にキー開
始レジスタ34を配置し、またキー長さレジスタ35は第１
位置から始まる全索引レジスタ25内の位置の個数を表わ
す値10を有する。ターゲットキーレジスタ32〜キー長さ
レジスタ35が所定通り全て入力されると、検索開始が可
能となる。

動作時に記憶装置６はポインタテーブル１（27）から
中間値を選択する。この場合、第10図に示す中間値はＤ
である。次に、記憶装置６はバンドアドレスＤに行き、
バンドアドレスＤに対するキー値である索引レジスタ25
の内容を読み出す。次に記憶装置６は、検索基準として
用いるターゲットキー値と選択されたキー値とを比較
し、ターゲットキー値以下か、それに等しい最大キーを
索引内に見出す。

好適実施例では、この基準を用いて、２進探索がポイ
ンタテーブル１（27）で実施される。例えば、LIDキー1
9の場合、選択されたバンドアドレスはＤである。バン
ドアドレスＤにおける索引レジスタ25の内容が読出さ
れ、ターゲットキー値と比較される。この場合、00401
030 71は00304 460 64以上であり、またポインタテーブ
ル１（27）が増加するシーケンスで与えられるので、記
憶装置６は、第１エントリ値0010110551と中間値004010
371との間のポインタテーブル１（27）の値を選択し、
ポインタテーブル１（27）内を上に向けて移動する。第
10図に示すように、バンドアドレスＢが選択され、また
バンドアドレスＢの内容及び索引レジスタ25が読み出さ
れる。この場合、00201 300 11はターゲットキー値0030
4 460 64以下である。しかしながら、記憶装置６は、な
おターゲットキー値以下のより大きなキー値が索引レジ
スタ25内に存在するか否かを見なければならない。従っ
て、記憶装置６はポインタテーブル１（27）内を下方の
値Ｃに移動する。記憶装置６は、該当する索引レジスタ
に移行し、バンドアドレスＣの索引レジスタ25の内容を
読取り、ターゲットキー値よりは小さいがバンドアドレ
スＢからの内容よりは大きい値00301 430 61を見出す。
バンドアドレスＤの内容は既に検索され比較されるの
で、記憶装置６はデータが存在すればバンドアドレスＣ
に配置されることを検知する。

第１のユーザキーを用いて検索する場合、第9c図に示
すように、選択ポインタテーブル２は、第２のポインタ
テーブルを検索に用いるべきことを示す値２にセットさ
れる。キー開始レジスタ34は６にセットされ、これによ
り索引レジスタ23を通しての検索が位置６で開始され、
位置６からのターゲットキー値と比較される。キー長さ
レジスタ35は、検索すべきキー値を見出すために索引レ
ジスタ内の５桁を位置６から読取るべきことを示す値05
にセットされる。

動作時、記憶装置は、第11図に示すように、ポインタ
テーブル２の中間値Ｂを選択する。次に記憶装置６は、
位置６で位置10を通して始まる中間値Ｂに関する索引レ
ジスタ25の内容30011を読取りこれをターゲットキー値4
60 64と比較する。選択された索引値はターゲット値よ
り小さいので、記憶装置６は選択ポインタテーブル２内
で下に移動し、バンドアドレスＧを選択し、ターゲット
キー値より大きなバンドアドレスＧの内容56031を索引
レジスタ25内で読出す。従って記憶装置６は索引レジス
タ25内でターゲットキー値より小さな値430 61を有する
バンドアドレスＣまでテーブル内を上に移動する。しか
しながら、バンドアドレスＧは既に検索されたので、記
憶装置６は、データが存在する場合それがバンドアドレ
スＣに配置されることを知る。

第9d図に示すように、第３のユーザキーを用い検索を
実施すると、ターゲットキーレジスタ32を64にセット
し、ターゲットポインタテーブル33を３にセットし、キ
ー開始レジスタ34を９にセットし、またキー長さレジス
タ35を02にセットする。第12図に示すように、動作時、
記憶装置６はポインタテーブル値Ｆを選択し、索引レジ
スタ25の内容を41として読取る。この値はターゲットキ
ー値64に比べられ、ターゲットキー値64は索引値41より
大きいので、記憶装置６は第３ポインタテーブル29のバ
ンドアドレスＣまで移動する。次に記憶装置６はバンド
アドレスＣでの索引レジスタ25の内容をターゲットキー
値64と比較する。索引レジスタ25の値61はターゲットキ
ー値64より小さい。記憶装置６はターゲットキー値64よ
り小さい最大のキー値を探し、そこでバンドアドレスＡ
まで移動し、64より小さいバンドアドレスＡの内容51を
読取るが、バンドアドレスＣの値61がバンドアドレスＡ
の値51より大きいので、記憶装置６はターゲットキー値
64より小さな最大キーとしてバンドアドレスＣを選択
し、データが存在する場合、そのデータがバンドアドレ
スＣにあることをホスト中央処理ユニット１に通知す
る。

従って、検索に用いる選択されたキーの値とは無関係
に、所望のデータの記憶場所として同一のバンドアドレ
スを識別することができる。包括キー15の利点は、前記
データを識別する複数個の異なるユーザキーを用いてユ
ーザが所与のデータブロックを検索できる点にもある。
例えば、ユーザキー１はソーシャルセキュリティ番号
（social security number）でもよく、一方ユーザキー
２は異なる識別パラメータを用いた所与のデータの組の
迅速な索引付けしかつ検索を許容するシティ（city）又
はステート（state）の記憶場所でもよい。

データが存在するバンドアドレスを識別すると、記憶
装置６は迅速なバンドアドレス検索を開始して所望の情
報の特定のユーザデータブロック14を見出すことができ
る。好適実施例では、バンド上の全720ユーザブロック
に対しバンド当り48個のユーザデータトラックが存在
し、ユーザデータトラック当り15データブロックが存在
する。従って全ユーザバンドを個別に横切る各ユーザデ
ータブロックでのヘッダ情報の読取りは時間がかかり、
効率の悪いことが理解されよう。記憶装置６は、１に等
しい低い境界値を第１の値として動作時にセットし、ま
た48に等しい高い境界値として第２の値をセットする
（これによりそのバンドの48ユーザデータトラックの全
部がカバーされる）。次に中央値（median）が計算さ
れ、記憶装置６は読み書きヘッドをその中央値ユーザデ
ータトラックに送出する。

次に、記憶装置６は、ユーザデータブロック14に対す
る包括キー15を含むヘッダ情報を読出し、ターゲットキ
ー値と読出された値を比較する。読出された値＋１がタ
ーゲットキー値より大きいと、低い境界値は読み書きヘ
ッドがトラッキング中のユーザデータトラック番号に等
しくセットされる。逆に、読出された値＋１がターゲッ
トキー値以下か１に等しい時は、読み書きヘッドが探索
しているユーザデータトラックの値に等しくより高い境
界値がセットされる。いずれの場合も、記憶装置６はそ
の時点で新しい中央値を再計算し、そのユーザデータト
ラック上の任意のユーザデータブロック14のヘッダ情報
を読み取られたキー値をターゲットキー値に比較でき
る。記憶装置６が下部境界ユーザデータトラックの始点
から上部境界ユーザデータトラックの終点まで各ユーザ
データブロック14のヘッダ情報を読出して、下部境界ユ
ーザデータトラック又は上部境界ユーザデータトラック
の一方に達するまで前記の過程を続行し、その間の到る
所でデータデータブロック14が検索される。例えば第６
図に示すように、バンドアドレスＣには６個のデータデ
ータブロック14が書込まれることがわかる。記憶装置６
は所望のバンドアドレス、例えばバンドアドレスＣに記
憶装置６の読み書きヘッドを送出する。

バンドアドレスＣを用いた第13図に示す例では、説明
のために第１ユーザキー46064を用い、上限及び下限の
間で中央値が計算され、また第１ブロックが読出され
る。この場合、ユーザブロック番号29は、この値がター
ゲットキー値以上であるので、48066として読み出さ
れ、上限がこの新しいユーザデータブロックにされ、こ
の新しい上限の間に見出された中央値と共にユーザデー
タブロック29が上限にされ、ユーザデータブロック29と
ユーザデータブロック８の間で中央値が計算される。ユ
ーザデータブロック10が読出され、第２ブロックはキー
値44062を示す。この値はターゲットキー値46064以下な
ので、記憶装置６はユーザデータブロック10に等しい下
限値をセットし、ユーザデータブロック29とユーザデー
タブロック10の間で中央値を見出す。ユーザデータブロ
ック23で読出し可能な第１ブロックが読出され、47065
を見出す。この値はターゲットキー値46064より大きい
ので、上限はユーザデータブロック23にセットされ、ま
たユーザデータブロック10とユーザデータブロック23と
の間の中央値はユーザデータブロック11として見出され
る。ユーザデータブロック11は値が45063の読出し可能
の第１ブロックとして読出され、この値はターゲットキ
ー値46064以下である。次に記憶装置６はユーザデータ
ブロック12からのキーを読出す。この時点で、記憶装置
６は、ユーザデータブロック23上の位置で47065を読出
し、ユーザデータブロック11上の位置で45063を読出
し、ターゲットキー値がディスク９上にあるかどうかを
通知し、また記憶装置６は、求める情報が存在すると
き、２つのユーザデータブロック11、23域内にあり、こ
れによりターゲットキー値より大きいか等しい最低値の
キーを有するユーザデータブロックを見出すまで45063
を読み出すユーザデータブロック11の後の内向きのユー
ザデータブロック毎の読出しを開始する。この時点で記
憶装置６は、配置動作が完了し、求めるデータが読み取
り可能であることを示す信号を制御装置３及びホスト中
央処理ユニット１に送出する。

以上に開示された本発明は比較的簡単な２進探索に関
して記憶したが、任意の探索アルゴリズムを用いて本発
明が実施可能であり、また以上に開示する手順が添付し
た特許請求の範囲を何等限定しないことを理解すべきで
ある。

【図面の簡単な説明】

第１図はホスト中央処理ユニット、ホスト中央処理ユニ
ットに接続された制御装置及び制御装置により操作され
る情報記憶装置との間の関係を示すブロック図、第２図
はユーザデータトラックがその間に配置される複数のユ
ーザバンドを上に配置させた情報記憶ディスクの概略
図、第３図はユーザデータトラックに記憶された複数の
ユーザデータブロックを示すプラッタ上のユーザバンド
の形態を示す概略図、第４図は物理的IDとユーザ包括キ
ーとを有するブロックヘッダを示す単一ブロック図、第
５図は包括キーを説明のためにLIDキー、ユーザキー１
及びユーザキー２の３種の特定キーに分解した一組の包
括キーを系列化した表、第６図は適切なユーザバンド上
に適切なプロトコルにより記憶されたユーザデータを有
する複数のユーザバンドを持つプラッタ面を示す概略
図、第７図は記憶装置の索引レジスタが各索引バンドの
適切な索引値を保持する状態を示す表、第８図はLIDキ
ー、第１ユーザキー及び第２ユーザキーをポインタテー
ブルに加えるバンドアドレスＡ〜Ｇを示す表、第９図は
選択ポインタテーブル１、選択ポインタテーブル２及び
選択ポインタテーブル３を用いる時のターゲットキーレ
ジスタ、選択ポインタテーブルレジスタ、キー開始レジ
スタ、キーの長さレジスタ及びこれらのレジスタの内容
を示す表、第10図はLIDキー、索引、及び第１ポインタ
テーブルを用いた探索シーケンスを示す表、第11図は索
引及びポインタテーブル番号２を用いた第１ユーザキー
の探索シーケンスを示す表、第12図は索引ユーザキー２
及びポインタテーブル３を用いたユーザキーの探索シー
ケンスを示す表、第13図は配置すべき特定のユーザデー
タトラックとブロック上にデータを与える連続する２進
探索場所を示すユーザデータトラックＣの略図である。 １……ホスト中央処理ユニット、2,4,8……バッファ、
３……制御装置、5,7……マイクロプロセッサ、６……
記憶装置、９……ディスク、10……ユーザデータトラッ
ク、11,12……ユーザバンド、13……ユーザデータトラ
ック、14……ユーザデータブロック、15……包括キー、
16……ヘッダ、17……ユーザデータ、18……PID、19…
…PIDキー、22……エントリ、24……索引アドレス、25
……レジスタ

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭57−193837（ＪＰ，Ａ) 特開 昭56−22172（ＪＰ，Ａ)

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】索引レジスタ（23）を備えたランダムアク
   セスメモリ及びマイクロプロセッサ（７）を有する記憶
   装置（６）と、ホスト中央処理ユニット（１）とを含む
   情報記録システム内に、索引バンド（11）と複数のユー
   ザバンド（12）とを備えた情報記録ディスク（９）を配
   置し、異なるビット数長さの複数種類のキー値を、物理
   的ID（18）と共にユーザデータブロック（14）のヘッダ
   （16）内に直列に配置し、情報記録ディスク（９）にキ
   ー値を有するユーザデータブロック（14）内に既に記録
   された又は記録すべきユーザデータ（17）をデジタル方
   式で索引付けしかつ検索する装置において、 ホスト中央処理ユニット（１）からの指令を検出し、ユ
   ーザバンド（12）内を検索するために書き込むべきユー
   ザデータブロック（14）に対するキー値が、ユーザバン
   ド（12）内に予め記憶されたユーザデータブロック（1
   4）に対応する最低のキー値より小さいか否かを決定す
   る手段と、 書き込むべきユーザデータブロック（14）に対するホス
   ト中央処理ユニット（１）からのキー値が、ユーザバン
   ド（12）内に予め記憶されたユーザデータブロック（1
   4）に対応する最低のキー値より小さいとき、誤り指令
   を発生する手段と、 ユーザバンド（12）内に予め記憶されたユーザデータブ
   ロック（14）に対応する最低のキー値より大きなキー値
   を、書き込むべきユーザデータブロック（14）が有する
   場合、ホスト中央処理ユニット（１）からの指令に従い
   指定された索引バンド（11）に最低のユーザキーを書き
   込む手段と、 各ユーザバンド（12）に対する予め記憶された最低のキ
   ー値を索引レジスタ（23）に入力する手段と、 ターゲットキー値を有するユーザデータブロック（14）
   の読出しが必要な検索時に、ポインタテーブル（27、2
   8、29）内で索引レジスタ（23）に入力された前記キー
   値のうち同一種類のキー値を小さい値から大きい値に順
   に分類する手段と、 ターゲットキー値より小さいか又はこれに等しい前記タ
   ーゲットキー値に最も近いキー値を有する単一のユーザ
   バンド（12）を探索するまで、ポインタテーブル（27、
   28、29）内で上方又は下方にポインタテーブル（27、2
   8、29）内で分類された前記キー値の中央値とホスト中
   央処理ユニット（１）からの指令による最低のユーザキ
   ーのターゲットキー値とを比較する手段と、 ターゲットキー値を有する識別したユーザデータブロッ
   ク（14）を含む単一のユーザバンド（12）を検出しかつ
   その存在をホスト中央処理ユニット（１）に知らせる手
   段とを含むことを特徴とするディジタル式情報記憶検索
   装置。
2. 【請求項２】索引レジスタ（23）を備えたランダムアク
   セスメモリ及びマイクロプロセッサ（７）を有する記憶
   装置（６）と、ホスト中央処理ユニット（１）とを含む
   情報記録システム内に、索引バンド（11）と複数のユー
   ザバンド（12）とを備えた情報記録ディスク（９）を配
   置し、異なるビット数長さの複数種類のキー値を、物理
   的ID（18）と共にユーザデータブロック（14）のヘッダ
   （16）内に直列に配置し、情報記録ディスク（９）にキ
   ー値を有するユーザデータブロック（14）内に既に記録
   された又は記録すべきユーザデータ（17）をデジタル方
   式で索引付けしかつ検索する方法において、 ホスト中央処理ユニット（１）からの指令を検出し、ユ
   ーザバンド（12）内を検索するために書き込むべきユー
   ザデータブロック（14）に対するキー値が、ユーザバン
   ド（12）内に予め記憶されたユーザデータブロック（1
   4）に対応する最低のキー値より小さいか否かを決定す
   る過程と、 書き込むべきユーザデータブロック（14）に対するホス
   ト中央処理ユニット（１）からのキー値が、ユーザバン
   ド（12）内に予め記憶されたユーザデータブロック（1
   4）に対応する最低のキー値より小さいとき、誤り指令
   を発生する手段と、 ユーザバンド（12）内に予め記憶されたユーザデータブ
   ロック（14）に対応する最低のキー値より大きなキー値
   を、書き込むべきユーザデータブロック（14）が有する
   場合、ホスト中央処理ユニット（１）からの指令に従い
   指定された索引バンド（11）に最低のユーザキーを書き
   込む過程と、 各ユーザバンド（12）に対する予め記憶された最低のキ
   ー値を索引レジスタ（23）に入力する過程と、 ターゲットキー値を有するユーザデータブロック（14）
   の読出しが必要な検索時に、ポインタテーブル（27、2
   8、29）内で索引レジスタ（23）に入力された前記キー
   値のうち同一種類のキー値を小さい値から大きい値に順
   に分類する過程と、 ターゲットキー値より小さいか又はこれに等しい前記タ
   ーゲットキー値に最も近いキー値を有する単一のユーザ
   バンド（12）を探索するまで、ポインタテーブル（27、
   28、29）内で上方又は下方にポインタテーブル（27、2
   8、29）内で分類された前記キー値の中央値とホスト中
   央処理ユニット（１）からの指令による最低のユーザキ
   ーのターゲットキー値とを比較する過程と、 ターゲットキー値を有する識別したユーザデータブロッ
   ク（14）を含む単一のユーザバンド（12）を検出しかつ
   その存在をホスト中央処理ユニット（１）に知らせる過
   程とを含むことを特徴とするディジタル式情報記憶検索
   方法。