JP2770855B2 - ディジタル式情報記憶検索方法及びその装置 - Google Patents
ディジタル式情報記憶検索方法及びその装置Info
- Publication number
- JP2770855B2 JP2770855B2 JP59219403A JP21940384A JP2770855B2 JP 2770855 B2 JP2770855 B2 JP 2770855B2 JP 59219403 A JP59219403 A JP 59219403A JP 21940384 A JP21940384 A JP 21940384A JP 2770855 B2 JP2770855 B2 JP 2770855B2
- Authority
- JP
- Japan
- Prior art keywords
- user
- key
- user data
- band
- index
- 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.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9017—Indexing; Data structures therefor; Storage structures using directory or table look-up
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99937—Sorting
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Indexing, Searching, Synchronizing, And The Amount Of Synchronization Travel Of Record Carriers (AREA)
Description
【発明の詳細な説明】
本発明はディジタル情報の記憶ディスクに記憶された
情報の検索、特に情報記録ディスクに記憶されたユーザ
データを迅速かつ効率的に記録しかつ検索するディジタ
ル式情報記憶検索方法及びその装置に関するものであ
る。 また、本発明はホスト中央処理ユニットによって記録
媒体上にディジタルデータを記録し、多様性のあるキー
を使用して、ディジタルデータを迅速な方法で任意に検
索できる情報記憶検索技術に関連する。 磁気テープ駆動装置等の情報記憶装置を用いる場合、
記憶したデータを系列的に読出すので、索引法を改善す
る必要性は非常に少ない。しかしながら、ランダムアク
セス情報記録ディスクが発展するにつれ、ユーザ情報の
特定のブロックを検索するために、効率的な索引付けに
対する需要が増加している。また、ディジタルデータ
は、従来、情報記録ディスクに一層稠密に書込まれるた
めに、特定のユーザデータを迅速かつ効率的に検索し、
読み出す索引検索装置を開発することはむしろ一層困難
になっている。 この問題に対する初期の解答はディスクデータを索引
付けする方法で与えられた。即ち、求める特定のデータ
グループを見出すために、若干効率良く索引を検索でき
かつ更に大きなデータグループを独自に識別する手短な
一般にキーと呼ばれる操作手段がユーザデータに与えら
れた。ユーザデータのヘッダ部分に或る独自の識別キー
(検索キーidentifier)を付与しかつ個別メモリにその
識別キーを分類するか又はユーザデータの或る独自の特
性を取りその値をキーとして用いるかのいずれかにより
一般に検索する。磁気ディスクに記憶されるデータはホ
スト中央処理ユニットに転送され、特定のデータブロッ
クのプラッタの内容と場所を示す拡張索引が与えられ
る。IBMカウントキー方式のように、この方法の初期の
例では、データ記憶と効率的な検索の問題をある程度解
決できた。 しかしながら、ディスク面上にデータが更に稠密に書
込まれ、ディスク面上でより多くの場所が索引に必要と
なるため、更に効率のよいディスク索引システムが必要
となることは明らかである。ユーザには記憶されたデー
タに迅速にアクセスすることを常に要求される。索引が
広範な程、特定のユーザデータの組の検索に必要な検索
時間が長くなる。ディスク面にデータがより稠密に書込
まれる程、検索時間は増加し、システムの効用が対応し
て減少する。また、1つ以上のキー索引法に基づいて特
定の組のデータ用の所与のデータベースをユーザが検索
する必要性が生じる。このために、求めるデータを最初
に索引付けする方法以外の「分類」法に基づいて、前記
データを一層効率的に検索できる効率的で時間短縮でき
る多重キーシステムが必要となる。例えば、ソーシャル
セキュリティナンバ(social security number)に関し
てデータを分類索引付けする場合、アドレス又はエージ
(age)により行う効率的な検索は最も困難になる。使
用されるこのシステムは一般に単一の識別キー及び索引
に対する分類法を有する。 更に最近は、取り外し可能な記憶媒体を有する記憶装
置の開発も進展し、ディスク面に記憶されたデータを効
率的に索引付けする検索装置の必要性が一層高まって
る。ディスクに記憶されたデータに効率的にアクセスす
るには、ディスクが完全な索引を具備しなければなら
ず、また多数の記録用ディスクを使用せずに記録用ディ
スクの単一のプラッタに多量の情報を記録する傾向に記
憶装置が開発されるので、効率的な索引システムに対す
る必要性が増大している。 特に重要な事は、ライトワンスオンリー(write once
only)機能を有する光学媒体が開発されたため、従来
の索引検索法が不適切になっている。消去可能な磁気デ
ィスクではデータは代替可能であり、容易に再配列可能
である。特に、データが特定のシーケンスを持ち、その
データに挿入すべき新しいデータが与えられると、適切
な位置に新しいエントリを配置するデータを再記憶する
ことが比較的容易になる。また、プラッタ面(ディスク
面)の欠陥によりデータの記憶が妨害されても、そのデ
ータを他の場所に記憶でき、また記憶されたポインタ
(アドレスを収容するレジスタ)が新しい記憶場所に導
かれ、ホスト中央処理ユニットがプラッタ面の所定の記
憶位置にデータを記憶したものとして取り扱うことがで
きる。これらの方法は消去不可能な記憶媒体を用いた場
合は実施不能となる。従って、データを書込み、そのデ
ータを索引付けしかつ検索する新しい方法を開発しなけ
ればならない。かくて、記録用ディスクの情報を記録す
る重要なプラッタ面の全記憶容量を消尽しておらず、書
き込み可能な残り容量を含む情報記録ディスクの全てに
対して効率の良い索引検索装置が必要となる。更に、索
引付けのためにるプラッタ記憶容量を増加せずに、多重
分類索引方式に基づいて単一のプラッタ面のより多量の
データにユーザが効率的にアクセスできる手段が必要と
なる。また、「ライトワンスオンリー(write once onl
y)(一度だけ書込める)」ディスクに対し、少なくと
も消去可能媒体と同様に効率良く書込み、索引付けし、
検索できるシステムが要求される。更に最後に、取り外
し可能な記憶媒体を有する記憶装置に対する索引(イン
デックス)をサポートし得るシステムが必要となる。 そこで、本発明は情報記録ディスクに記憶されたユー
ザデータを迅速かつ効率的に検索するディジタル式情報
記憶検索方法及びその装置を提供することを目的とす
る。 ユーザデータを検索する本発明によるディジタル式情
報記憶検索方法は、ホスト中央処理ユニット(1)及び
記憶装置(6)を有する情報記録システム内に配置され
かつ索引バンド(11)及び複数のユーザバンド(12)を
有する情報記録ディスク(9)のブロックフォーマット
に記録されたユーザデータを検索するために使用され
る。情報記録ディスク(9)の各ユーザバンド(12)は
各ユーザデータブロック(14)を記録する複数のユーザ
データトラック(13)を有する。このディジタル式情報
記憶検索方法は、ユーザデータを書き込むべきユーザバ
ンド(12)の位置を索引付けすると共にユーザバンド
(12)のユーザデータブロック(14)の位置を決定する
論理IDキー(19)及びユーザデータブロック(14)に対
する複数のユーザキー(20、21)を含む包括キー(15)
をホスト中央処理ユニット(1)において記録すべきユ
ーザデータブロック(14)に割り当てる過程と、索引を
記憶する索引記憶手段、索引記憶手段に記憶された索引
を分類するソート手段及び索引記憶手段に記憶された索
引を検索するサーチ手段を備えた記憶装置(6)に、ユ
ーザバンド(12)、ユーザデータトラック(13)及びユ
ーザデータブロック(14)をユーザバンド(12)内に系
列化する物理的ID(18)及び包括キー(15)を有するヘ
ッダ(16)を有するユーザデータブロック(14)を転送
する過程と、ホスト中央処理ユニット(1)によって指
定された情報記録ディスク(9)上のユーザデータ位置
内に包括キー(15)と共にユーザデータブロック(14)
を書き込む過程と、ユーザデータブロック(14)を記録
するユーザバンド(12)の位置及び包括キー(15)を情
報記録ディスク(9)上の所定の位置に記録する過程
と、ターゲットキーにより識別される所定のユーザデー
タブロック(14)に対する検索基礎となる包括キー(1
5)内の論理IDキー(19)又は複数のユーザキー(20、2
1)の一つをターゲットキーとして選択する過程と、タ
ーゲットキーを記憶装置(6)に転送する過程と、ター
ゲットキーの値に基づく連続する順序で記憶装置(6)
に設けられたマイクロプロセッサにより索引記憶手段に
記憶された索引を分類する過程と、マイクロプロセッサ
によりターゲットキーに対して分類された索引記憶手段
を検索して、求められるユーザデータに関連する特定の
論理IDキー(19)又はユーザキー(20、21)が存在する
情報記録ディスク(9)上の位置を決定する過程とを含
む。 情報記録ディスク(9)のブロックフォーマットに記
録されたユーザデータを検索する本発明によるディジタ
ル式情報記憶検索装置は、ユーザデータを書き込むべき
ユーザバンド(12)の位置を索引付けすると共にユーザ
バンド(12)のユーザデータブロック(14)の位置を決
定する論理IDキー(19)及びユーザデータブロック(1
4)に対する複数のユーザキー(20、21)を含む包括キ
ー(15)を登録すべきユーザデータブロック(14)に割
り当てるホスト中央処理ユニット(1)と、索引を記憶
するランダムアクセスメモリを有する索引記憶手段及び
索引記憶手段に記憶された索引を分類すると共に索引記
憶手段に記憶された索引を検索するマイクロプロセッサ
を備えた記憶装置(6)に、ユーザバンド(12)、ユー
ザデータトラック(13)及びユーザデータブロック(1
4)をユーザバンド(12)内に系列化する物理的ID(PI
D)(18)及び包括キー(15)を含むヘッダ(16)を有
するユーザデータブロック(14)をホスト中央処理ユニ
ット(1)から転送する制御装置(3)と、ホスト中央
処理ユニット(1)によって指定された情報記録ディス
ク(9)のユーザデータ位置にユーザデータブロック
(14)を包括キー(15)と共に書き込む手段と、ユーザ
データブロック(14)を記録するユーザバンド(12)の
位置及び包括キー(15)を情報記録ディスク(9)上の
所定の位置に記録する手段とを備えている。ターゲット
キーとして論理IDキー(19)又はユーザキー(20、21)
の一つをホスト中央処理ユニット(1)によりユーザデ
ータの検索基礎となる包括キー(15)内で選択し、ユー
ザデータ内で検索すべき選択されたターゲットキーを記
憶装置(6)に転送し、検索に対して選択されたターゲ
ットキーの値に基づ連続する順序で索引記憶手段に記憶
された索引を分類し、ターゲットキーに対して分類され
た索引記憶手段をユーザデータ内で検索して、求められ
るユーザデータに関連する特定の論理IDキー(19)又は
ユーザキー(20、21)が存在する情報記録ディスク
(9)上の位置を決定する。 本発明によれば、ヘッダは論理IDキー(19)と複数の
ユーザキー(20、21)からなる包括キー(15)を含み、
論理IDキー(19)はデータを書き込むべきユーザバンド
(12)の位置を索引付けすると共に、各ユーザバンド
(12)でのユーザデータブロック(14)の位置を決定す
る。複数のユーザキー(20、21)はユーザデータブロッ
ク(14)の所望のキーを含む。包括キー(15)はディス
ク(9)の周囲の索引バンド(11)に記録されるため、
索引バンド(11)を検索するときに、所望のユーザキー
(20、21)が存在したときに、そのユーザキー(20、2
1)がどのユーザバンド(12)の何番目に対応するかを
直ちに検索することができる。従って、索引バンド(1
1)を検索して必要なユーザキー(20、21)が存在した
ときに、包括キー(15)の内容から対応するユーザバン
ド(12)を検索しかつそのユーザバンド(12)内のデー
タの位置を知り、直ちに対応するユーザデータブロック
(14)から必要な情報を読み出すことができる。これに
より、無関係なユーザバンド(12)及びユーザデータブ
ロック(14)を検索する必要がないので、ユーザデータ
を迅速かつ効率的に検索することができる。 また、ライトワンスオンリー機能を有する光学媒体を
使用するとき、索引バンド(11)を検索することによ
り、未書き込みのユーザバンド(12)及びユーザデータ
ブロック(14)を直ちに検索して、そこに新たな情報を
書き込むことができる。このため、ライトワンスオンリ
ー機能を有する光学媒体に対しても、未書き込みのユー
ザデータブロック(14)を使用して、消去可能媒体と同
様に効率良く書込み、索引付けし、検索することが可能
となる。この場合に、複数のユーザキー(20、21)を使
用できるので、ユーザが複数個の独自のユーザキー(2
0、21)を使用してユーザデータを迅速かつ効率的に検
索できる。このように、本発明によれば、包括キー(1
5)を使用してディジタル式情報記憶ディスクに記憶さ
れたユーザ情報を迅速かつ効率的に検索するディジタル
式情報記憶検索方法及びその装置が得られる。 包括キー(15)はホスト中央処理ユニット(1)によ
り指定され、ユーザデータに対するユーザバンド(12)
の位置を決定すると共に、ユーザバンド(12)内のユー
ザデータブロック(14)位置を決定する論理IDキー(1
9)を含む。ユーザブロックを記録するために、ヘッダ
はユーザバンド(12)、ユーザデータトラック(13)及
びユーザデータブロック(14)をユーザバンド(12)内
に系列化(リスト化)する物理的ID(PID)(18)を含
む。包括キー(15)はデータ(情報)を記録すべきユー
ザバンド(12)及びユーザバンド(12)中のユーザデー
タを表示するユーザデータブロック(14)を所定の順序
で指示する。 データを効率的に記録するために、情報はブロックと
呼ばれるデータグループに分類され、包括キー(15)
は、記録すべきデータのユーザデータブロック(14)の
ヘッダ内に配置される。ユーザはユーザキー(20、21)
に対して一定長の1組の記憶用フィールドを定義し、各
記憶用フィールド内には、ユーザデータブロック(14)
に対する独自の識別キーとしてのユーザキー(20、21)
を配置する。 動作時に、ホスト中央処理ユニット(1)(CPU)に
より記録すべきユーザデータのブロックを構成した後、
独自のキー識別子としてユーザキー(20、21)を選択す
る。ユーザキー(20、21)は、ユーザデータブロック
(14)のヘッダ内に包括キー(15)の一部として配置さ
れる。この情報は、制御装置を通して処理され、ディス
ク(9)に記憶される記憶装置(6)に転送される。好
適実施例では、ユーザはディスク(9)面の所定のユー
ザバンド(12)に記録するユーザデータブロック(14)
を検索動作により効率的に検索できる。好適実施例で
は、ディスク(9)のフォーマットは716本のユーザバ
ンド(12)からなり、その1つは索引バンド(11)とし
て用いられ、各ユーザバンド(12)は48本のユーザデー
タトラック(13)を持ち、各ユーザデータトラック(1
3)は最大15個のユーザデータブロック(14)の記録用
空間を有する。 ディスク(9)面に情報を記録する時は、ヘッダに関
する情報はディスク(9)の索引バンド(11)上に記録
されると共に、記憶装置(6)のランダムアクセスメモ
リに記憶される。ユーザバンド(12)内にユーザデータ
ブロック(14)を順次記録することが本発明の実施にと
って必須であるが、ユーザバンド(12)自身を連続的に
記録する必要はない。索引レジスタのアドレスはユーザ
バンド(12)の番号であり、そのレジスタにはユーザキ
ー(20、21)の完全な組(即ち、完全な包括キー(1
5))が配置される。各ユーザキー(20、21)に対して
与えられるポインタテーブルには、ポインタテーブルに
より与えられるユーザキー(20、21)の値に基づいて系
列的に分類される索引アドレスが配置される。例えば、
第2のレジスタの5つの位置がユーザキー(20、21)1
を表すと、ポインタテーブル2はユーザキー(20、21)
に対して適切なシーケンスで分類される。包括キー(1
5)を用いて検索するために、ユーザは検索すべき適切
なキーとして配置すべきターゲットキーを付与して、記
憶装置(6)を指令する。 好適実施例の詳細な説明 第1図に示すように、本発明の好適実施例では記憶す
べきデータは、ホスト中央処理ユニット1のチャネルイ
ンタフェースバッファ2に先ず記憶され、前記データは
ディジタル式情報記憶検索装置の制御装置3に転送すべ
きユーザデータブロック14を構成する。好適実施例で
は、7904バイトの情報はユーザデータの単一ブロックか
らなる。構成されたユーザデータブロック又は複数のユ
ーザデータブロックは、制御装置3に転送され、バッフ
ァ4に記憶された後、マイクロプロセツサ5により記憶
装置6に転送される。記憶装置6に転送された記憶すべ
きデータは、記憶装置6のマイクロプロセツサ7により
記憶装置6のバッファ8を通過可能となり、更に記憶装
置6のディスク9に転送されて記憶される。図示しない
が、記憶装置6は、索引キーを記憶する索引記憶手段、
索引記憶手段を分類するソート手段及び索引記憶手段を
検索するサーチ手段を備える。 ディスク9のフォーマットは、第2図に略示するよう
に、粗調−微調サーボ検索動作によりユーザバンド12の
位置を検出するクロック信号を発生するための複数本の
同心トラック10を有する。好適実施例では、ディスク9
は1つの索引バンド11と714本のユーザバンド12とを持
ち、各ユーザバンド12は、第3図に示すように、48個の
ユーザデータトラック13を有する。好適実施例では、各
ユーザトラック13は最大15個のユーザデータブロック14
を記憶できる。ディスク9の索引バンド11は記憶装置6
のデータ索引機能に用いられる。 好適実施例では、ディスク9は取り外し可能、消去不
能な記憶媒体であり、またライトワンスオンリー機能の
ために、実際の書込み前ではディスク9面上のデータの
物理的記憶場所は不明であり、ディスク9に対する完全
な索引エントリをディスク9上に配置することが必要と
なる。従って、新しい記憶装置6に配置するとき、ディ
スク9の内容を読出し、索引付けしかつ検索することが
できる。 書式配置(フォーマッティング)の条件により、記憶
装置6のプロトコルは、ユーザバンド12に対するユーザ
データ17を増大するキー番号順に記憶することを要求す
る。従って、所与のユーザバンド12には、以前に記憶さ
れたユーザデータブロック14のキー値以下のキー値を有
するデータのユーザデータブロック14は何ら記憶されな
い。従って、記憶されたユーザバンド12に対して、第2
のユーザデータブロック14は第1のユーザデータブロッ
ク14より大きなキー値を常に持ち、第3のユーザデータ
ブロック14は第2のユーザデータブロック14より大き
く、以下同様に与えられる。しかしながら、ユーザバン
ド12自身を系列的に記憶する必要はない。記憶装置6に
記憶する通常の順序は外径から内径へと進むが、ユーザ
の指示により記憶可能なユーザバンド12にデータが記憶
される。記憶すべき新しいユーザデータ17のユーザデー
タブロック14が所定のユーザバンド12に予め記憶された
キー値以下のキー値を持つ場合、記憶装置6は、記憶す
べきユーザデータブロック14のキー値に等しいか又はそ
れ以下の索引キーを割り当てて、別の新しいユーザバン
ド12に前記新しいユーザデータ17を配置する。 第4図に示すように、ホスト中央処理ユニット1は動
作時に包括キー15をユーザデータブロック14のヘッダ16
に配置する。ヘッダ16へのキーの使用は公知であり、IB
Mキーカウント方式がその1例である。しかしながら、
包括キー15には、複数の可変長の特定のユーザキーが配
置され、複数のユーザ指定キーに対する索引付け及び検
索を実施できる。データが記憶装置6に伝送されると、
記憶装置6は記憶前にユーザデータブロック14の始めに
物理的ID(PID)18を配置する。好適実施例では、記憶
装置6にデータを光学的に書込む時、データはライトワ
ンスオンリー容量であり、また、実際の書込み動作前で
は、ユーザデータ17をディスク9に物理的に配置する位
置をホスト中央処理ユニット1が認識できないために、
物理的ID(PID)18が必要となる。包括キー15はホスト
中央処理ユニット1により指定され、ユーザデータに対
するユーザバンド12の位置を決定すると共に、ユーザバ
ンド12内のユーザデータブロック14の位置を決定する。
包括キー15はユーザバンド12、ユーザデータトラック13
及びユーザデータブロック14をユーザバンド12内に系列
化する物理的ID(PID)18を含む。包括キー15は情報ユ
ーザデータブロック14をどのユーザバンド12に記憶すべ
きか及びデータを表示するユーザバンド12のどのユーザ
データブロック14を表すかをシーケンスで指示する。PI
D18はユーザバンド12、ユーザデータトラック13及びユ
ーザデータブロック14をユーザバンド12内に系列化し、
各ユーザデータ17が物理的にディスク9に記憶される。 第4図に示すように、記憶装置6がデータを記憶する
記憶装置6のディスク9面上に特定の記憶場所を決定し
た後、その記憶場所のPID18がディスク9に記憶され、
これに包括キー15が伴い、その後ユーザデータ17が伴
う。この例では、説明のためディジタル数字とα文字を
用いる。記憶されるデータは例えばASCII符号化方式に
よる2進数で与えられる。 第5図の表は、本発明の完全な機能を説明するため
に、記憶すべき複数のユーザデータブロック14の代表的
な組に用いられる包括キー15を示す。例えばユーザデー
タブロック14は3個の個別のユーザキーにより表され
る。第1のキーは、ホスト中央処理ユニット1により与
えられて所定のユーザデータブロック14をどのユーザバ
ンド12に記憶すべきかを指示し、またユーザバンド12内
のユーザデータブロック14の位置をシーケンスで指示す
る論理ID(LID)キー19である。 論理IDキー19は、ホスト中央処理ユニット1が作成す
るデータブロックに対してホスト中央処理ユニット1に
よって設定される。論理IDキー19はデータブロックを書
き込むべきユーザバンド12と、ユーザバンド12内のデー
タブロックを位置決めするシーケンスとを決定する合成
された情報を含む。 例えば、第1LIDキーエントリ「00501」が「データブ
ロックをユーザバンド5内に書き込むべきこと」及び
「データブロックがユーザバンド5のエントリ1にある
べきこと」を示し、第6図のユーザバンドE(第5番目
のユーザバンド)を参照すると、ここで、エントリ順序
は「00501」、「00502」、「00503」である。論理IDキ
ー19は単一であり、同一ディスク上では反復できないこ
とに注意すべきである。 20及び21で示すユーザキー1と2も、同一ディスク上
で反復できない。しかしながら、ユーザキー1及び2は
所望のキー値を選択できる。同一のディスクを通じてそ
の分野に適合して同一の限定された英符号を適用するこ
とを条件として、いかなる英符号もユーザキーの分野に
適用できる。例えば、社会保険番号(ソシャルセキュリ
ティナンバー)を常にユーザー1として使用し、誕生日
を常時ユーザキー2等として使用でき、異なるディスク
に対して異なる基準を使用することも可能である。その
結果、異なる全ての包括キー15はディスク9の日付情報
ブロックを記憶するために使用できる。混乱を避けるた
め、キー値は引用するが参照番号を省略する。例えば、
エントリ1に対して、LIDキー値00501は第5ユーザバン
ド12の第1ユーザデータブロック14にデータを記憶すべ
きことことを示す。エントリ22はLIDキー値00406を有す
るユーザデータ17を第4ユーザバンド12の第6ユーザデ
ータブロック14に記憶すべきことを示す。第5図に例示
するユーザキー1はユーザデータブロック14の検索時に
ユーザに有用なユーザデータ17の値を単に例示し、ユー
ザキー2は所与のユーザデータブロック14の検索時に有
用なユーザデータ17の他の値を示す。エントリ(項目)
を系列化する第5図の順序はデータを記憶し得るシーケ
ンスをランダムに説明している。 第6図は、LIDキー19の値によりデータをディスク9
に記憶すべきシーケンスを形成するバンドアドレスA〜
Gのユーザバンド12を表示するディスク9にデータを記
憶する状態を示す。即ち、エントリ(項目)1が記憶さ
れ、続いてエントリ2、エントリ3、エントリ4と最後
のエントリ30が記憶されるまで続けられる。ユーザバン
ド12による記憶を示す第6図は第5図の表との比較から
理解されるように、ディスク9にデータを記憶すシーケ
ンスと順序を示す。 新しいファイルが開かれデータが記憶されるとき、記
憶装置6は索引バンド11にPID18と包括キー15を記憶す
る。好適実施例では、索引バンド11は所与のユーザバン
ド12に対する最低キー値のみをリストする。索引バンド
11に記憶される第1のキーは索引バンド11に対する最低
キー値である。ユーザが所与の索引バンド11に以前に記
憶された情報の削除を決定して、割り当てられた新しい
キー番号と共に、その索引バンド11に新たな組のデータ
を記憶させれば、この新しいキー番号は以前に記憶され
たが削除されたキー値より小さくてもよい。 第7a図はエントリ1〜30に与えられたデータに対する
索引バンド11に記憶された値22のリストを示す。第7b図
に示すように、索引バンド11に転送されるデータは、記
憶装置6のランダムアクセスメモリの索引レジスタ23に
読み取られる。好適実施例では、索引アドレス24はデー
タを記憶するユーザバンド12のバンドアドレスA〜Gで
あり、個別の索引レジスタ25は索引バンド11のユーザバ
ンド12に対して記憶されるユーザデータブロック14から
得られる全包括キー15のキー値を記憶する。好適実施例
では、索引レジスタ25にはディスク9上に書込まれるデ
ータ順にキー値が記憶される。従って、第7b図に示すよ
うに、第2のレジスタ25は内容00401 030 71を持つバ
ンドアドレスDを有し、最後のエントリに一番近いレジ
スタ25は内容00301 430 61のバンドアドレスCを有す
る。 これを達成するために、索引レジスタ25の内容及びユ
ーザバンド12に関係するキー値に基づいて分類されたバ
ンドアドレスA〜Gを有する第8図に示す3個1組のポ
インタテーブル27、28、29が確立される。説明のため
に、本実施例では3つのポインタテーブル27、28、29を
使用する。ユーザデータ17を識別するために単一キーを
使用する場合、索引付けしかつ検索のために単にLIDキ
ー19の上昇するシーケンスに索引レジスタ25を配列する
ことができる。しかしながら、索引付けしかつ検索する
ためにユーザデータを多様に分類する能力を与える包括
キー15と共に、異なる改良された方法を実施できる。索
引キーを分類し、個々のキーの各組に対する異なる索引
レジスタ25で予備的に分類するため、付加的な組の索引
レジスタ25を用いて、多重のキーを有効に使用すること
ができる。 先ず、第7c図は、索引レジスタ25内に位置が存在する
場合と同じ個数の索引レジスタ25内の位置を有する索引
順序表26を構成する位置1、位置6及び位置9を示す。
索引順序表26での各個別位置の値は所与のキーに対する
分類すべき位置を表す。例えば、位置1はLIDキー1を
分類するための索引順序表26内の第1位置で開始し、ユ
ーザキー2に対して索引順序表26内の位置6から分類を
開始し、またユーザキー3に対して索引順序表26内の位
置9から分類を開始すべきことを示す。 第8a図に示すように、位置1から始まるLIDキー19に
対する分類が最低キー値であるLID値0101 105 51(バ
ンドアドレスAに記憶される)であり、最高キー値0701
560 31(バンドアドレスGに記憶される)であるか
ら、索引順序表26が昇順にリストされ、ポインタテーブ
ル1(27)のLIDキー19の分類は第7c図の位置1で開始
する。第8d図に示すように、LIDキー19に対するポイン
タテーブル1はLIDキー19の値の順序を表すバンドアド
レスAからGのシーケンスを構成して配列される。第7c
図に示すように、第2ユーザIDの分類は位置6で始ま
り、ポインタテーブル2(28)に対する分類はバンドア
ドレスDに示すように第1の値03071であり、また最高
値はバンドアドレスEに示すように62521である。従っ
て、第8b図に示すように、ポインタテーブル2は第1値
がバンドアドレスDで最終値がバンドアドレスEである
シーケンスを形成して配列される。第7c図に示すよう
に、ポインタテーブル3に対する分類は索引順序表26か
らの位置9の値で始まるユーザキー2に基づいて与えら
れ、第1の値はバンドアドレスBに関する11であり、最
後の値はバンドアドレスDからの71である。従って、第
8c図に示すように、ポインタテーブル3の索引レジスタ
25の初めの値をバンドアドレスBで表し、ポインタテー
ブル3の最後の値をバンドアドレスDで示す。 検索レジスタ25を設定すると、ユーザは拡張索引及び
迅速なバンド検索機能を用いてディスク9上のユーザデ
ータ17のユーザデータブロック14を検索することができ
る。例えば、第5図からのLID値00304、第1ユーザキー
値460及び第2ユーザキー値64を有するユーザデータの
リストのエントリ12に対して検索が実施される。第9図
は、ディスク9から読出すべきユーザデータに対するタ
ーゲットキー値を示す。第9a図に示すように、包括キー
15を用いて索引付けしかつ検索を実施するために、ター
ゲットキーレジスタ32、選択ポインタテーブルレジスタ
33、キー開始レジスタ34及びキー長さレジスタ35が記憶
装置6のランダムアクセスメモリに配置される。ターゲ
ットキーレジスタ32は、索引の結果を迅速なユーザバン
ドの検索キーと比較するため、検索すべきターゲットキ
ーの値を保持する。選択ポインタテーブルレジスタ33は
検索する特定のポインタテーブルに対する値を保持す
る。キー開始レジスタ34は、索引レジスタ25内の第1値
の位置、検索用のキー値を選択する索引レジスタ25内の
位置の値を保持する。 例えば、エントリ12に対する3個のキー値1、2、3
の全てが与えられる。第9b図に示すようにLIDキー19を
用いて検索する際には、ターゲットキーレジスタ内にタ
ーゲットキー値をセットし、LIDキー19を用いた検索を
表す1に選択ポインタテーブル33をセットし、索引レジ
スタ25内でLIDキー19が開始される位置である1にキー
開始レジスタ34を配置し、またキー長さレジスタ35は第
1位置から始まる全索引レジスタ25内の位置の個数を表
す値10を有する。ターゲットキーレジスタ32〜キー長さ
レジスタ35が所定通り全て入力されると、検索開始が可
能となる。 動作時に記憶装置6はポインタテーブル1(27)から
中間値を選択する。この場合、第10図に示す中間値はD
である。次に、記憶装置6はバンドアドレスDに行き、
バンドアドレスDに対するキー値である索引レジスタ25
の内容を読み出す。次に記憶装置6は、検索基準として
用いるターゲットキー値と選択されたキー値とを比較
し、ターゲットキー値以下か、それに等しい最大キーを
索引内に見出す。 好適実施例では、この基準を用いて、2進探索がポイ
ンタテーブル1(27)で実施される。例えば、LIDキー1
9の場合、選択されたバンドアドレスはDである。バン
ドアドレスDにおける索引レジスタ25の内容が読出さ
れ、ターゲットキー値と比較される。この場合、00401
030 71は00304 460 64以上であり、またポインタ
テーブル1(27)が増加するシーケンスで与えられるの
で、記憶装置6は、第1エントリ値0010110551と中間値
004010371との間のポインタテーブル1(27)の値を選
択し、ポインタテーブル1(27)内を上に向けて移動す
る。第10図に示すように、バンドアドレスBが選択さ
れ、またバンドアドレスBの内容及び索引レジスタ25が
読み出される。この場合、00201 300 11はターゲット
キー値00304 460 64以下である。しかしながら、記憶
装置6は、なおターゲットキー値以下のより大きなキー
値が索引レジスタ25内に存在するか否かを見なければな
らない。従って、記憶装置6はポインタテーブル1(2
7)内を下方の値Cに移動する。記憶装置6は、該当す
る索引レジスタに移行し、バンドアドレスCの索引レジ
スタ25の内容を読取り、ターゲットキー値よりは小さい
がバンドアドレスBからの内容よりは大きい値00301 4
30 61を見出す。バンドアドレスDの内容は既に検索さ
れ比較されるので、記憶装置6はデータが存在すればバ
ンドアドレスCに配置されることを検知する。 第1のユーザキーを用いて検索する場合、第9c図に示
すように、選択ポインタテーブル2は、第2のポインタ
テーブルを検索に用いるべきことを示す値2にセットさ
れる。キー開始レジスタ34は6にセットされ、これによ
り索引レジスタ23を通しての検索が位置6で開始され、
位置6からのターゲットキー値と比較される。キー長さ
レジスタ35は、検索すべきキー値を見出すために索引レ
ジスタ内の5桁を位置6から読取るべきことを示す値05
にセットされる。 動作時、記憶装置6は、第11図に示すように、ポイン
タテーブル2の中間値Bを選択する。次に記憶装置6
は、位置6で位置10を通して始まる中間値Bに関する索
引レジスタ25の内容30011を読取りこれをターゲットキ
ー値460 64と比較する。選択された索引値はターゲッ
トキー値より小さいので、記憶装置6は選択ポインタテ
ーブル2内で下に移動し、バンドアドレスGを選択し、
ターゲットキー値より大きなバンドアドレスGの内容56
031を検索レジスタ25内で読出す。従って記憶装置6は
索引レジスタ25内でターゲットキー値より小さな値430
61を有するバンドアドレスCまでテーブル内を上に移
動する。しかしながら、バンドアドレスGは既に検索さ
れたので、記憶装置6は、データが存在する場合それが
バンドアドレスCに配置されることを知る。 第9d図に示すように、第3のユーザキーを用い検索を
実施すると、ターゲットキーレジスタ32を64にセット
し、ターゲットポインタテーブル33を3にセットし、キ
ー開始レジスタ34を9にセットし、またキー長さレジス
タ35を02にセットする。第12図に示すように、動作時、
記憶装置6はポインタテーブル値Fを選択し、索引レジ
スタ25の内容を41として読取る。この値はターゲットキ
ー値64に比べられ、ターゲットキー値64は索引値41より
大きいので、記憶装置6は第3ポインタテーブル29のバ
ンドアドレスCまで移動する。次に記憶装置6はバンド
アドレスCでの索引レジスタ25の内容をターゲットキー
値64と比較する。索引レジスタ25の値61はターゲットキ
ー値64より小さい。記憶装置6はターゲットキー値64よ
り小さい最大のキー値を探し、そこでバンドアドレスA
まで移動し、64より小さいバンドアドレスAの内容51を
読取るが、バンドアドレスCの値61がバンドアドレスA
の値51より大きいので、記憶装置6はターゲットキー値
64より小さな最大キーとしてバンドアドレスCを選択
し、データが存在する場合、そのデータがバンドアドレ
スCにあることをホスト中央処理ユニット1に通知す
る。 従って、検索に用いる選択されたキーの値とは無関係
に、所望のデータの記憶場所として同一のバンドアドレ
スを識別することができる。包括キー15の利点は、前記
データを識別する複数個の異なるユーザキーを用いてユ
ーザが所与のデータブロックを検索できる点にもある。
例えば、ユーザキー1はソーシャルセキュリティ番号
(social security number)でもよく、一方ユーザキー
2は異なる識別パラメータを用いた所与のデータの組の
迅速な索引付けしかつ検索を許容するシティ(city)又
はステート(state)の記憶場所でもよい。 データが存在するバンドアドレスを識別すると、記憶
装置6は迅速なバンドアドレス検索を開始して所望の情
報の特定のユーザデータブロック14を見出すことができ
る。好適実施例では、バンド上の全720ユーザブロック
に対しバンド当り48個のユーザデータトラックが存在
し、ユーザデータトラック当り15データブロックが存在
する。従って全ユーザバンドを個別に横切る各ユーザデ
ータブロックでのヘッダ情報の読取りは時間がかかり、
効率の悪いことが理解されよう。記憶装置6は、1に等
しい低い境界値を第1の値として動作時にセットし、ま
た48に等しい高い境界値として第2の値をセットする
(これによりそのバンドの48ユーザデータトラックの全
部がカバーされる)。次に中央値(median)が計算さ
れ、記憶装置6は読み書きヘッドをその中央値ユーザデ
ータトラックに送出する。 次に、記憶装置6は、ユーザデータブロック14に対す
る包括キー15を含むヘッダ情報を読出し、ターゲットキ
ー値と読出された値を比較する。読出された値+1がタ
ーゲットキー値より大きいと、低い境界値は読み書きヘ
ッドがトラッキング中のユーザデータトラック番号に等
しくセットされる。逆に、読出された値+1がターゲッ
トキー値以下か1に等しい時は、読み書きヘッドが探索
しているユーザデータトラックの値に等しくより高い境
界値がセットされる。いずれの場合も、記憶装置6はそ
の時点で新しい中央値を再計算し、そのユーザデータト
ラック上の任意のユーザデータブロック14のヘッダ情報
を読み取られたキー値をターゲットキー値に比較でき
る。記憶装置6が下部境界ユーザデータトラックの始点
から上部境界ユーザデータトラックの終点まで各ユーザ
データブロック14のヘッダ情報を読出して、下部境界ユ
ーザデータトラック又は上部境界ユーザデータトラック
の一方に達するまで前記の過程を続行し、その間の到る
所でデータデータブロック14が検索される。例えば第6
図に示すように、バンドアドレスCには6個のデータデ
ータブロック14が書込まれることがわかる。記憶装置6
は所望のバンドアドレス、例えばバンドアドレスCに記
憶装置6の読み書きヘッドを送出する。 バンドアドレスCを用いた第13図に示す例では、説明
のために第1ユーザキー46064を用い、上限及び下限の
間で中央値が計算され、また第1ブロックが読出され
る。この場合、ユーザブロック番号29は、この値がター
ゲットキー値以上であるので、48066として読み出さ
れ、上限がこの新しいユーザデータブロックにされ、こ
の新しい上限の間に見出された中央値と共にユーザデー
タブロック29が上限にされ、ユーザデータブロック29と
ユーザデータブロック8の間で中央値が計算される。ユ
ーザデータブロック10が読出され、第2ブロックはキー
値44062を示す。この値はターゲットキー値46064以下な
ので、記憶装置6はユーザデータブロック10に等しい下
限値をセットし、ユーザデータブロック29とユーザデー
タブロック10の間で中央値を見出す。ユーザデータブロ
ック23で読出し可能な第1ブロックが読出され、47065
を見出す。この値はターゲットキー値46064より大きい
ので、上限はユーザデータブロック23にセットされ、ま
たユーザデータブロック10とユーザデータブロック23と
の間の中央値はユーザデータブロック11として見出され
る。ユーザデータブロック11は値が45063の読出し可能
の第1ブロックとして読出され、この値はターゲットキ
ー値46064以下である。次に記憶装置6はユーザデータ
ブロック12からのキーを読出す。この時点で、記憶装置
6は、ユーザデータブロック23上の位置で47065を読出
し、ユーザデータブロック11上の位置で45063を読出
し、ターゲットキー値がディスク9上にあるかどうかを
通知し、また記憶装置6は、求める情報が存在すると
き、2つのユーザデータブロック11、23域内にあり、こ
れによりターゲットキー値より大きいか等しい最低値の
キーを有するユーザデータブロックを見出すまで45063
を読み出すユーザデータブロック11の後の内向きのユー
ザデータブロック毎の読出しを開始する。この時点で記
憶装置6は、配置動作が完了し、求めるデータが読み取
り可能であることを示す信号を制御装置3及びホスト中
央処理ユニット1に送出する。 以上に開示された本発明は比較的簡単な2進探索に関
して記載したが、任意の探索アルゴリズムを用いて本発
明が実施可能であり、また以上に開示する手順が添付し
た特許請求の範囲を何等限定しないことを理解すべきで
ある。 本発明の適用可能な分野はディジタルデータの大量記
憶の分野であり、WORM(ライトワンスリードメニイタイ
ムズ)光学記憶ディスクの外に他形式の記録媒体にも使
用可能である。
情報の検索、特に情報記録ディスクに記憶されたユーザ
データを迅速かつ効率的に記録しかつ検索するディジタ
ル式情報記憶検索方法及びその装置に関するものであ
る。 また、本発明はホスト中央処理ユニットによって記録
媒体上にディジタルデータを記録し、多様性のあるキー
を使用して、ディジタルデータを迅速な方法で任意に検
索できる情報記憶検索技術に関連する。 磁気テープ駆動装置等の情報記憶装置を用いる場合、
記憶したデータを系列的に読出すので、索引法を改善す
る必要性は非常に少ない。しかしながら、ランダムアク
セス情報記録ディスクが発展するにつれ、ユーザ情報の
特定のブロックを検索するために、効率的な索引付けに
対する需要が増加している。また、ディジタルデータ
は、従来、情報記録ディスクに一層稠密に書込まれるた
めに、特定のユーザデータを迅速かつ効率的に検索し、
読み出す索引検索装置を開発することはむしろ一層困難
になっている。 この問題に対する初期の解答はディスクデータを索引
付けする方法で与えられた。即ち、求める特定のデータ
グループを見出すために、若干効率良く索引を検索でき
かつ更に大きなデータグループを独自に識別する手短な
一般にキーと呼ばれる操作手段がユーザデータに与えら
れた。ユーザデータのヘッダ部分に或る独自の識別キー
(検索キーidentifier)を付与しかつ個別メモリにその
識別キーを分類するか又はユーザデータの或る独自の特
性を取りその値をキーとして用いるかのいずれかにより
一般に検索する。磁気ディスクに記憶されるデータはホ
スト中央処理ユニットに転送され、特定のデータブロッ
クのプラッタの内容と場所を示す拡張索引が与えられ
る。IBMカウントキー方式のように、この方法の初期の
例では、データ記憶と効率的な検索の問題をある程度解
決できた。 しかしながら、ディスク面上にデータが更に稠密に書
込まれ、ディスク面上でより多くの場所が索引に必要と
なるため、更に効率のよいディスク索引システムが必要
となることは明らかである。ユーザには記憶されたデー
タに迅速にアクセスすることを常に要求される。索引が
広範な程、特定のユーザデータの組の検索に必要な検索
時間が長くなる。ディスク面にデータがより稠密に書込
まれる程、検索時間は増加し、システムの効用が対応し
て減少する。また、1つ以上のキー索引法に基づいて特
定の組のデータ用の所与のデータベースをユーザが検索
する必要性が生じる。このために、求めるデータを最初
に索引付けする方法以外の「分類」法に基づいて、前記
データを一層効率的に検索できる効率的で時間短縮でき
る多重キーシステムが必要となる。例えば、ソーシャル
セキュリティナンバ(social security number)に関し
てデータを分類索引付けする場合、アドレス又はエージ
(age)により行う効率的な検索は最も困難になる。使
用されるこのシステムは一般に単一の識別キー及び索引
に対する分類法を有する。 更に最近は、取り外し可能な記憶媒体を有する記憶装
置の開発も進展し、ディスク面に記憶されたデータを効
率的に索引付けする検索装置の必要性が一層高まって
る。ディスクに記憶されたデータに効率的にアクセスす
るには、ディスクが完全な索引を具備しなければなら
ず、また多数の記録用ディスクを使用せずに記録用ディ
スクの単一のプラッタに多量の情報を記録する傾向に記
憶装置が開発されるので、効率的な索引システムに対す
る必要性が増大している。 特に重要な事は、ライトワンスオンリー(write once
only)機能を有する光学媒体が開発されたため、従来
の索引検索法が不適切になっている。消去可能な磁気デ
ィスクではデータは代替可能であり、容易に再配列可能
である。特に、データが特定のシーケンスを持ち、その
データに挿入すべき新しいデータが与えられると、適切
な位置に新しいエントリを配置するデータを再記憶する
ことが比較的容易になる。また、プラッタ面(ディスク
面)の欠陥によりデータの記憶が妨害されても、そのデ
ータを他の場所に記憶でき、また記憶されたポインタ
(アドレスを収容するレジスタ)が新しい記憶場所に導
かれ、ホスト中央処理ユニットがプラッタ面の所定の記
憶位置にデータを記憶したものとして取り扱うことがで
きる。これらの方法は消去不可能な記憶媒体を用いた場
合は実施不能となる。従って、データを書込み、そのデ
ータを索引付けしかつ検索する新しい方法を開発しなけ
ればならない。かくて、記録用ディスクの情報を記録す
る重要なプラッタ面の全記憶容量を消尽しておらず、書
き込み可能な残り容量を含む情報記録ディスクの全てに
対して効率の良い索引検索装置が必要となる。更に、索
引付けのためにるプラッタ記憶容量を増加せずに、多重
分類索引方式に基づいて単一のプラッタ面のより多量の
データにユーザが効率的にアクセスできる手段が必要と
なる。また、「ライトワンスオンリー(write once onl
y)(一度だけ書込める)」ディスクに対し、少なくと
も消去可能媒体と同様に効率良く書込み、索引付けし、
検索できるシステムが要求される。更に最後に、取り外
し可能な記憶媒体を有する記憶装置に対する索引(イン
デックス)をサポートし得るシステムが必要となる。 そこで、本発明は情報記録ディスクに記憶されたユー
ザデータを迅速かつ効率的に検索するディジタル式情報
記憶検索方法及びその装置を提供することを目的とす
る。 ユーザデータを検索する本発明によるディジタル式情
報記憶検索方法は、ホスト中央処理ユニット(1)及び
記憶装置(6)を有する情報記録システム内に配置され
かつ索引バンド(11)及び複数のユーザバンド(12)を
有する情報記録ディスク(9)のブロックフォーマット
に記録されたユーザデータを検索するために使用され
る。情報記録ディスク(9)の各ユーザバンド(12)は
各ユーザデータブロック(14)を記録する複数のユーザ
データトラック(13)を有する。このディジタル式情報
記憶検索方法は、ユーザデータを書き込むべきユーザバ
ンド(12)の位置を索引付けすると共にユーザバンド
(12)のユーザデータブロック(14)の位置を決定する
論理IDキー(19)及びユーザデータブロック(14)に対
する複数のユーザキー(20、21)を含む包括キー(15)
をホスト中央処理ユニット(1)において記録すべきユ
ーザデータブロック(14)に割り当てる過程と、索引を
記憶する索引記憶手段、索引記憶手段に記憶された索引
を分類するソート手段及び索引記憶手段に記憶された索
引を検索するサーチ手段を備えた記憶装置(6)に、ユ
ーザバンド(12)、ユーザデータトラック(13)及びユ
ーザデータブロック(14)をユーザバンド(12)内に系
列化する物理的ID(18)及び包括キー(15)を有するヘ
ッダ(16)を有するユーザデータブロック(14)を転送
する過程と、ホスト中央処理ユニット(1)によって指
定された情報記録ディスク(9)上のユーザデータ位置
内に包括キー(15)と共にユーザデータブロック(14)
を書き込む過程と、ユーザデータブロック(14)を記録
するユーザバンド(12)の位置及び包括キー(15)を情
報記録ディスク(9)上の所定の位置に記録する過程
と、ターゲットキーにより識別される所定のユーザデー
タブロック(14)に対する検索基礎となる包括キー(1
5)内の論理IDキー(19)又は複数のユーザキー(20、2
1)の一つをターゲットキーとして選択する過程と、タ
ーゲットキーを記憶装置(6)に転送する過程と、ター
ゲットキーの値に基づく連続する順序で記憶装置(6)
に設けられたマイクロプロセッサにより索引記憶手段に
記憶された索引を分類する過程と、マイクロプロセッサ
によりターゲットキーに対して分類された索引記憶手段
を検索して、求められるユーザデータに関連する特定の
論理IDキー(19)又はユーザキー(20、21)が存在する
情報記録ディスク(9)上の位置を決定する過程とを含
む。 情報記録ディスク(9)のブロックフォーマットに記
録されたユーザデータを検索する本発明によるディジタ
ル式情報記憶検索装置は、ユーザデータを書き込むべき
ユーザバンド(12)の位置を索引付けすると共にユーザ
バンド(12)のユーザデータブロック(14)の位置を決
定する論理IDキー(19)及びユーザデータブロック(1
4)に対する複数のユーザキー(20、21)を含む包括キ
ー(15)を登録すべきユーザデータブロック(14)に割
り当てるホスト中央処理ユニット(1)と、索引を記憶
するランダムアクセスメモリを有する索引記憶手段及び
索引記憶手段に記憶された索引を分類すると共に索引記
憶手段に記憶された索引を検索するマイクロプロセッサ
を備えた記憶装置(6)に、ユーザバンド(12)、ユー
ザデータトラック(13)及びユーザデータブロック(1
4)をユーザバンド(12)内に系列化する物理的ID(PI
D)(18)及び包括キー(15)を含むヘッダ(16)を有
するユーザデータブロック(14)をホスト中央処理ユニ
ット(1)から転送する制御装置(3)と、ホスト中央
処理ユニット(1)によって指定された情報記録ディス
ク(9)のユーザデータ位置にユーザデータブロック
(14)を包括キー(15)と共に書き込む手段と、ユーザ
データブロック(14)を記録するユーザバンド(12)の
位置及び包括キー(15)を情報記録ディスク(9)上の
所定の位置に記録する手段とを備えている。ターゲット
キーとして論理IDキー(19)又はユーザキー(20、21)
の一つをホスト中央処理ユニット(1)によりユーザデ
ータの検索基礎となる包括キー(15)内で選択し、ユー
ザデータ内で検索すべき選択されたターゲットキーを記
憶装置(6)に転送し、検索に対して選択されたターゲ
ットキーの値に基づ連続する順序で索引記憶手段に記憶
された索引を分類し、ターゲットキーに対して分類され
た索引記憶手段をユーザデータ内で検索して、求められ
るユーザデータに関連する特定の論理IDキー(19)又は
ユーザキー(20、21)が存在する情報記録ディスク
(9)上の位置を決定する。 本発明によれば、ヘッダは論理IDキー(19)と複数の
ユーザキー(20、21)からなる包括キー(15)を含み、
論理IDキー(19)はデータを書き込むべきユーザバンド
(12)の位置を索引付けすると共に、各ユーザバンド
(12)でのユーザデータブロック(14)の位置を決定す
る。複数のユーザキー(20、21)はユーザデータブロッ
ク(14)の所望のキーを含む。包括キー(15)はディス
ク(9)の周囲の索引バンド(11)に記録されるため、
索引バンド(11)を検索するときに、所望のユーザキー
(20、21)が存在したときに、そのユーザキー(20、2
1)がどのユーザバンド(12)の何番目に対応するかを
直ちに検索することができる。従って、索引バンド(1
1)を検索して必要なユーザキー(20、21)が存在した
ときに、包括キー(15)の内容から対応するユーザバン
ド(12)を検索しかつそのユーザバンド(12)内のデー
タの位置を知り、直ちに対応するユーザデータブロック
(14)から必要な情報を読み出すことができる。これに
より、無関係なユーザバンド(12)及びユーザデータブ
ロック(14)を検索する必要がないので、ユーザデータ
を迅速かつ効率的に検索することができる。 また、ライトワンスオンリー機能を有する光学媒体を
使用するとき、索引バンド(11)を検索することによ
り、未書き込みのユーザバンド(12)及びユーザデータ
ブロック(14)を直ちに検索して、そこに新たな情報を
書き込むことができる。このため、ライトワンスオンリ
ー機能を有する光学媒体に対しても、未書き込みのユー
ザデータブロック(14)を使用して、消去可能媒体と同
様に効率良く書込み、索引付けし、検索することが可能
となる。この場合に、複数のユーザキー(20、21)を使
用できるので、ユーザが複数個の独自のユーザキー(2
0、21)を使用してユーザデータを迅速かつ効率的に検
索できる。このように、本発明によれば、包括キー(1
5)を使用してディジタル式情報記憶ディスクに記憶さ
れたユーザ情報を迅速かつ効率的に検索するディジタル
式情報記憶検索方法及びその装置が得られる。 包括キー(15)はホスト中央処理ユニット(1)によ
り指定され、ユーザデータに対するユーザバンド(12)
の位置を決定すると共に、ユーザバンド(12)内のユー
ザデータブロック(14)位置を決定する論理IDキー(1
9)を含む。ユーザブロックを記録するために、ヘッダ
はユーザバンド(12)、ユーザデータトラック(13)及
びユーザデータブロック(14)をユーザバンド(12)内
に系列化(リスト化)する物理的ID(PID)(18)を含
む。包括キー(15)はデータ(情報)を記録すべきユー
ザバンド(12)及びユーザバンド(12)中のユーザデー
タを表示するユーザデータブロック(14)を所定の順序
で指示する。 データを効率的に記録するために、情報はブロックと
呼ばれるデータグループに分類され、包括キー(15)
は、記録すべきデータのユーザデータブロック(14)の
ヘッダ内に配置される。ユーザはユーザキー(20、21)
に対して一定長の1組の記憶用フィールドを定義し、各
記憶用フィールド内には、ユーザデータブロック(14)
に対する独自の識別キーとしてのユーザキー(20、21)
を配置する。 動作時に、ホスト中央処理ユニット(1)(CPU)に
より記録すべきユーザデータのブロックを構成した後、
独自のキー識別子としてユーザキー(20、21)を選択す
る。ユーザキー(20、21)は、ユーザデータブロック
(14)のヘッダ内に包括キー(15)の一部として配置さ
れる。この情報は、制御装置を通して処理され、ディス
ク(9)に記憶される記憶装置(6)に転送される。好
適実施例では、ユーザはディスク(9)面の所定のユー
ザバンド(12)に記録するユーザデータブロック(14)
を検索動作により効率的に検索できる。好適実施例で
は、ディスク(9)のフォーマットは716本のユーザバ
ンド(12)からなり、その1つは索引バンド(11)とし
て用いられ、各ユーザバンド(12)は48本のユーザデー
タトラック(13)を持ち、各ユーザデータトラック(1
3)は最大15個のユーザデータブロック(14)の記録用
空間を有する。 ディスク(9)面に情報を記録する時は、ヘッダに関
する情報はディスク(9)の索引バンド(11)上に記録
されると共に、記憶装置(6)のランダムアクセスメモ
リに記憶される。ユーザバンド(12)内にユーザデータ
ブロック(14)を順次記録することが本発明の実施にと
って必須であるが、ユーザバンド(12)自身を連続的に
記録する必要はない。索引レジスタのアドレスはユーザ
バンド(12)の番号であり、そのレジスタにはユーザキ
ー(20、21)の完全な組(即ち、完全な包括キー(1
5))が配置される。各ユーザキー(20、21)に対して
与えられるポインタテーブルには、ポインタテーブルに
より与えられるユーザキー(20、21)の値に基づいて系
列的に分類される索引アドレスが配置される。例えば、
第2のレジスタの5つの位置がユーザキー(20、21)1
を表すと、ポインタテーブル2はユーザキー(20、21)
に対して適切なシーケンスで分類される。包括キー(1
5)を用いて検索するために、ユーザは検索すべき適切
なキーとして配置すべきターゲットキーを付与して、記
憶装置(6)を指令する。 好適実施例の詳細な説明 第1図に示すように、本発明の好適実施例では記憶す
べきデータは、ホスト中央処理ユニット1のチャネルイ
ンタフェースバッファ2に先ず記憶され、前記データは
ディジタル式情報記憶検索装置の制御装置3に転送すべ
きユーザデータブロック14を構成する。好適実施例で
は、7904バイトの情報はユーザデータの単一ブロックか
らなる。構成されたユーザデータブロック又は複数のユ
ーザデータブロックは、制御装置3に転送され、バッフ
ァ4に記憶された後、マイクロプロセツサ5により記憶
装置6に転送される。記憶装置6に転送された記憶すべ
きデータは、記憶装置6のマイクロプロセツサ7により
記憶装置6のバッファ8を通過可能となり、更に記憶装
置6のディスク9に転送されて記憶される。図示しない
が、記憶装置6は、索引キーを記憶する索引記憶手段、
索引記憶手段を分類するソート手段及び索引記憶手段を
検索するサーチ手段を備える。 ディスク9のフォーマットは、第2図に略示するよう
に、粗調−微調サーボ検索動作によりユーザバンド12の
位置を検出するクロック信号を発生するための複数本の
同心トラック10を有する。好適実施例では、ディスク9
は1つの索引バンド11と714本のユーザバンド12とを持
ち、各ユーザバンド12は、第3図に示すように、48個の
ユーザデータトラック13を有する。好適実施例では、各
ユーザトラック13は最大15個のユーザデータブロック14
を記憶できる。ディスク9の索引バンド11は記憶装置6
のデータ索引機能に用いられる。 好適実施例では、ディスク9は取り外し可能、消去不
能な記憶媒体であり、またライトワンスオンリー機能の
ために、実際の書込み前ではディスク9面上のデータの
物理的記憶場所は不明であり、ディスク9に対する完全
な索引エントリをディスク9上に配置することが必要と
なる。従って、新しい記憶装置6に配置するとき、ディ
スク9の内容を読出し、索引付けしかつ検索することが
できる。 書式配置(フォーマッティング)の条件により、記憶
装置6のプロトコルは、ユーザバンド12に対するユーザ
データ17を増大するキー番号順に記憶することを要求す
る。従って、所与のユーザバンド12には、以前に記憶さ
れたユーザデータブロック14のキー値以下のキー値を有
するデータのユーザデータブロック14は何ら記憶されな
い。従って、記憶されたユーザバンド12に対して、第2
のユーザデータブロック14は第1のユーザデータブロッ
ク14より大きなキー値を常に持ち、第3のユーザデータ
ブロック14は第2のユーザデータブロック14より大き
く、以下同様に与えられる。しかしながら、ユーザバン
ド12自身を系列的に記憶する必要はない。記憶装置6に
記憶する通常の順序は外径から内径へと進むが、ユーザ
の指示により記憶可能なユーザバンド12にデータが記憶
される。記憶すべき新しいユーザデータ17のユーザデー
タブロック14が所定のユーザバンド12に予め記憶された
キー値以下のキー値を持つ場合、記憶装置6は、記憶す
べきユーザデータブロック14のキー値に等しいか又はそ
れ以下の索引キーを割り当てて、別の新しいユーザバン
ド12に前記新しいユーザデータ17を配置する。 第4図に示すように、ホスト中央処理ユニット1は動
作時に包括キー15をユーザデータブロック14のヘッダ16
に配置する。ヘッダ16へのキーの使用は公知であり、IB
Mキーカウント方式がその1例である。しかしながら、
包括キー15には、複数の可変長の特定のユーザキーが配
置され、複数のユーザ指定キーに対する索引付け及び検
索を実施できる。データが記憶装置6に伝送されると、
記憶装置6は記憶前にユーザデータブロック14の始めに
物理的ID(PID)18を配置する。好適実施例では、記憶
装置6にデータを光学的に書込む時、データはライトワ
ンスオンリー容量であり、また、実際の書込み動作前で
は、ユーザデータ17をディスク9に物理的に配置する位
置をホスト中央処理ユニット1が認識できないために、
物理的ID(PID)18が必要となる。包括キー15はホスト
中央処理ユニット1により指定され、ユーザデータに対
するユーザバンド12の位置を決定すると共に、ユーザバ
ンド12内のユーザデータブロック14の位置を決定する。
包括キー15はユーザバンド12、ユーザデータトラック13
及びユーザデータブロック14をユーザバンド12内に系列
化する物理的ID(PID)18を含む。包括キー15は情報ユ
ーザデータブロック14をどのユーザバンド12に記憶すべ
きか及びデータを表示するユーザバンド12のどのユーザ
データブロック14を表すかをシーケンスで指示する。PI
D18はユーザバンド12、ユーザデータトラック13及びユ
ーザデータブロック14をユーザバンド12内に系列化し、
各ユーザデータ17が物理的にディスク9に記憶される。 第4図に示すように、記憶装置6がデータを記憶する
記憶装置6のディスク9面上に特定の記憶場所を決定し
た後、その記憶場所のPID18がディスク9に記憶され、
これに包括キー15が伴い、その後ユーザデータ17が伴
う。この例では、説明のためディジタル数字とα文字を
用いる。記憶されるデータは例えばASCII符号化方式に
よる2進数で与えられる。 第5図の表は、本発明の完全な機能を説明するため
に、記憶すべき複数のユーザデータブロック14の代表的
な組に用いられる包括キー15を示す。例えばユーザデー
タブロック14は3個の個別のユーザキーにより表され
る。第1のキーは、ホスト中央処理ユニット1により与
えられて所定のユーザデータブロック14をどのユーザバ
ンド12に記憶すべきかを指示し、またユーザバンド12内
のユーザデータブロック14の位置をシーケンスで指示す
る論理ID(LID)キー19である。 論理IDキー19は、ホスト中央処理ユニット1が作成す
るデータブロックに対してホスト中央処理ユニット1に
よって設定される。論理IDキー19はデータブロックを書
き込むべきユーザバンド12と、ユーザバンド12内のデー
タブロックを位置決めするシーケンスとを決定する合成
された情報を含む。 例えば、第1LIDキーエントリ「00501」が「データブ
ロックをユーザバンド5内に書き込むべきこと」及び
「データブロックがユーザバンド5のエントリ1にある
べきこと」を示し、第6図のユーザバンドE(第5番目
のユーザバンド)を参照すると、ここで、エントリ順序
は「00501」、「00502」、「00503」である。論理IDキ
ー19は単一であり、同一ディスク上では反復できないこ
とに注意すべきである。 20及び21で示すユーザキー1と2も、同一ディスク上
で反復できない。しかしながら、ユーザキー1及び2は
所望のキー値を選択できる。同一のディスクを通じてそ
の分野に適合して同一の限定された英符号を適用するこ
とを条件として、いかなる英符号もユーザキーの分野に
適用できる。例えば、社会保険番号(ソシャルセキュリ
ティナンバー)を常にユーザー1として使用し、誕生日
を常時ユーザキー2等として使用でき、異なるディスク
に対して異なる基準を使用することも可能である。その
結果、異なる全ての包括キー15はディスク9の日付情報
ブロックを記憶するために使用できる。混乱を避けるた
め、キー値は引用するが参照番号を省略する。例えば、
エントリ1に対して、LIDキー値00501は第5ユーザバン
ド12の第1ユーザデータブロック14にデータを記憶すべ
きことことを示す。エントリ22はLIDキー値00406を有す
るユーザデータ17を第4ユーザバンド12の第6ユーザデ
ータブロック14に記憶すべきことを示す。第5図に例示
するユーザキー1はユーザデータブロック14の検索時に
ユーザに有用なユーザデータ17の値を単に例示し、ユー
ザキー2は所与のユーザデータブロック14の検索時に有
用なユーザデータ17の他の値を示す。エントリ(項目)
を系列化する第5図の順序はデータを記憶し得るシーケ
ンスをランダムに説明している。 第6図は、LIDキー19の値によりデータをディスク9
に記憶すべきシーケンスを形成するバンドアドレスA〜
Gのユーザバンド12を表示するディスク9にデータを記
憶する状態を示す。即ち、エントリ(項目)1が記憶さ
れ、続いてエントリ2、エントリ3、エントリ4と最後
のエントリ30が記憶されるまで続けられる。ユーザバン
ド12による記憶を示す第6図は第5図の表との比較から
理解されるように、ディスク9にデータを記憶すシーケ
ンスと順序を示す。 新しいファイルが開かれデータが記憶されるとき、記
憶装置6は索引バンド11にPID18と包括キー15を記憶す
る。好適実施例では、索引バンド11は所与のユーザバン
ド12に対する最低キー値のみをリストする。索引バンド
11に記憶される第1のキーは索引バンド11に対する最低
キー値である。ユーザが所与の索引バンド11に以前に記
憶された情報の削除を決定して、割り当てられた新しい
キー番号と共に、その索引バンド11に新たな組のデータ
を記憶させれば、この新しいキー番号は以前に記憶され
たが削除されたキー値より小さくてもよい。 第7a図はエントリ1〜30に与えられたデータに対する
索引バンド11に記憶された値22のリストを示す。第7b図
に示すように、索引バンド11に転送されるデータは、記
憶装置6のランダムアクセスメモリの索引レジスタ23に
読み取られる。好適実施例では、索引アドレス24はデー
タを記憶するユーザバンド12のバンドアドレスA〜Gで
あり、個別の索引レジスタ25は索引バンド11のユーザバ
ンド12に対して記憶されるユーザデータブロック14から
得られる全包括キー15のキー値を記憶する。好適実施例
では、索引レジスタ25にはディスク9上に書込まれるデ
ータ順にキー値が記憶される。従って、第7b図に示すよ
うに、第2のレジスタ25は内容00401 030 71を持つバ
ンドアドレスDを有し、最後のエントリに一番近いレジ
スタ25は内容00301 430 61のバンドアドレスCを有す
る。 これを達成するために、索引レジスタ25の内容及びユ
ーザバンド12に関係するキー値に基づいて分類されたバ
ンドアドレスA〜Gを有する第8図に示す3個1組のポ
インタテーブル27、28、29が確立される。説明のため
に、本実施例では3つのポインタテーブル27、28、29を
使用する。ユーザデータ17を識別するために単一キーを
使用する場合、索引付けしかつ検索のために単にLIDキ
ー19の上昇するシーケンスに索引レジスタ25を配列する
ことができる。しかしながら、索引付けしかつ検索する
ためにユーザデータを多様に分類する能力を与える包括
キー15と共に、異なる改良された方法を実施できる。索
引キーを分類し、個々のキーの各組に対する異なる索引
レジスタ25で予備的に分類するため、付加的な組の索引
レジスタ25を用いて、多重のキーを有効に使用すること
ができる。 先ず、第7c図は、索引レジスタ25内に位置が存在する
場合と同じ個数の索引レジスタ25内の位置を有する索引
順序表26を構成する位置1、位置6及び位置9を示す。
索引順序表26での各個別位置の値は所与のキーに対する
分類すべき位置を表す。例えば、位置1はLIDキー1を
分類するための索引順序表26内の第1位置で開始し、ユ
ーザキー2に対して索引順序表26内の位置6から分類を
開始し、またユーザキー3に対して索引順序表26内の位
置9から分類を開始すべきことを示す。 第8a図に示すように、位置1から始まるLIDキー19に
対する分類が最低キー値であるLID値0101 105 51(バ
ンドアドレスAに記憶される)であり、最高キー値0701
560 31(バンドアドレスGに記憶される)であるか
ら、索引順序表26が昇順にリストされ、ポインタテーブ
ル1(27)のLIDキー19の分類は第7c図の位置1で開始
する。第8d図に示すように、LIDキー19に対するポイン
タテーブル1はLIDキー19の値の順序を表すバンドアド
レスAからGのシーケンスを構成して配列される。第7c
図に示すように、第2ユーザIDの分類は位置6で始ま
り、ポインタテーブル2(28)に対する分類はバンドア
ドレスDに示すように第1の値03071であり、また最高
値はバンドアドレスEに示すように62521である。従っ
て、第8b図に示すように、ポインタテーブル2は第1値
がバンドアドレスDで最終値がバンドアドレスEである
シーケンスを形成して配列される。第7c図に示すよう
に、ポインタテーブル3に対する分類は索引順序表26か
らの位置9の値で始まるユーザキー2に基づいて与えら
れ、第1の値はバンドアドレスBに関する11であり、最
後の値はバンドアドレスDからの71である。従って、第
8c図に示すように、ポインタテーブル3の索引レジスタ
25の初めの値をバンドアドレスBで表し、ポインタテー
ブル3の最後の値をバンドアドレスDで示す。 検索レジスタ25を設定すると、ユーザは拡張索引及び
迅速なバンド検索機能を用いてディスク9上のユーザデ
ータ17のユーザデータブロック14を検索することができ
る。例えば、第5図からのLID値00304、第1ユーザキー
値460及び第2ユーザキー値64を有するユーザデータの
リストのエントリ12に対して検索が実施される。第9図
は、ディスク9から読出すべきユーザデータに対するタ
ーゲットキー値を示す。第9a図に示すように、包括キー
15を用いて索引付けしかつ検索を実施するために、ター
ゲットキーレジスタ32、選択ポインタテーブルレジスタ
33、キー開始レジスタ34及びキー長さレジスタ35が記憶
装置6のランダムアクセスメモリに配置される。ターゲ
ットキーレジスタ32は、索引の結果を迅速なユーザバン
ドの検索キーと比較するため、検索すべきターゲットキ
ーの値を保持する。選択ポインタテーブルレジスタ33は
検索する特定のポインタテーブルに対する値を保持す
る。キー開始レジスタ34は、索引レジスタ25内の第1値
の位置、検索用のキー値を選択する索引レジスタ25内の
位置の値を保持する。 例えば、エントリ12に対する3個のキー値1、2、3
の全てが与えられる。第9b図に示すようにLIDキー19を
用いて検索する際には、ターゲットキーレジスタ内にタ
ーゲットキー値をセットし、LIDキー19を用いた検索を
表す1に選択ポインタテーブル33をセットし、索引レジ
スタ25内でLIDキー19が開始される位置である1にキー
開始レジスタ34を配置し、またキー長さレジスタ35は第
1位置から始まる全索引レジスタ25内の位置の個数を表
す値10を有する。ターゲットキーレジスタ32〜キー長さ
レジスタ35が所定通り全て入力されると、検索開始が可
能となる。 動作時に記憶装置6はポインタテーブル1(27)から
中間値を選択する。この場合、第10図に示す中間値はD
である。次に、記憶装置6はバンドアドレスDに行き、
バンドアドレスDに対するキー値である索引レジスタ25
の内容を読み出す。次に記憶装置6は、検索基準として
用いるターゲットキー値と選択されたキー値とを比較
し、ターゲットキー値以下か、それに等しい最大キーを
索引内に見出す。 好適実施例では、この基準を用いて、2進探索がポイ
ンタテーブル1(27)で実施される。例えば、LIDキー1
9の場合、選択されたバンドアドレスはDである。バン
ドアドレスDにおける索引レジスタ25の内容が読出さ
れ、ターゲットキー値と比較される。この場合、00401
030 71は00304 460 64以上であり、またポインタ
テーブル1(27)が増加するシーケンスで与えられるの
で、記憶装置6は、第1エントリ値0010110551と中間値
004010371との間のポインタテーブル1(27)の値を選
択し、ポインタテーブル1(27)内を上に向けて移動す
る。第10図に示すように、バンドアドレスBが選択さ
れ、またバンドアドレスBの内容及び索引レジスタ25が
読み出される。この場合、00201 300 11はターゲット
キー値00304 460 64以下である。しかしながら、記憶
装置6は、なおターゲットキー値以下のより大きなキー
値が索引レジスタ25内に存在するか否かを見なければな
らない。従って、記憶装置6はポインタテーブル1(2
7)内を下方の値Cに移動する。記憶装置6は、該当す
る索引レジスタに移行し、バンドアドレスCの索引レジ
スタ25の内容を読取り、ターゲットキー値よりは小さい
がバンドアドレスBからの内容よりは大きい値00301 4
30 61を見出す。バンドアドレスDの内容は既に検索さ
れ比較されるので、記憶装置6はデータが存在すればバ
ンドアドレスCに配置されることを検知する。 第1のユーザキーを用いて検索する場合、第9c図に示
すように、選択ポインタテーブル2は、第2のポインタ
テーブルを検索に用いるべきことを示す値2にセットさ
れる。キー開始レジスタ34は6にセットされ、これによ
り索引レジスタ23を通しての検索が位置6で開始され、
位置6からのターゲットキー値と比較される。キー長さ
レジスタ35は、検索すべきキー値を見出すために索引レ
ジスタ内の5桁を位置6から読取るべきことを示す値05
にセットされる。 動作時、記憶装置6は、第11図に示すように、ポイン
タテーブル2の中間値Bを選択する。次に記憶装置6
は、位置6で位置10を通して始まる中間値Bに関する索
引レジスタ25の内容30011を読取りこれをターゲットキ
ー値460 64と比較する。選択された索引値はターゲッ
トキー値より小さいので、記憶装置6は選択ポインタテ
ーブル2内で下に移動し、バンドアドレスGを選択し、
ターゲットキー値より大きなバンドアドレスGの内容56
031を検索レジスタ25内で読出す。従って記憶装置6は
索引レジスタ25内でターゲットキー値より小さな値430
61を有するバンドアドレスCまでテーブル内を上に移
動する。しかしながら、バンドアドレスGは既に検索さ
れたので、記憶装置6は、データが存在する場合それが
バンドアドレスCに配置されることを知る。 第9d図に示すように、第3のユーザキーを用い検索を
実施すると、ターゲットキーレジスタ32を64にセット
し、ターゲットポインタテーブル33を3にセットし、キ
ー開始レジスタ34を9にセットし、またキー長さレジス
タ35を02にセットする。第12図に示すように、動作時、
記憶装置6はポインタテーブル値Fを選択し、索引レジ
スタ25の内容を41として読取る。この値はターゲットキ
ー値64に比べられ、ターゲットキー値64は索引値41より
大きいので、記憶装置6は第3ポインタテーブル29のバ
ンドアドレスCまで移動する。次に記憶装置6はバンド
アドレスCでの索引レジスタ25の内容をターゲットキー
値64と比較する。索引レジスタ25の値61はターゲットキ
ー値64より小さい。記憶装置6はターゲットキー値64よ
り小さい最大のキー値を探し、そこでバンドアドレスA
まで移動し、64より小さいバンドアドレスAの内容51を
読取るが、バンドアドレスCの値61がバンドアドレスA
の値51より大きいので、記憶装置6はターゲットキー値
64より小さな最大キーとしてバンドアドレスCを選択
し、データが存在する場合、そのデータがバンドアドレ
スCにあることをホスト中央処理ユニット1に通知す
る。 従って、検索に用いる選択されたキーの値とは無関係
に、所望のデータの記憶場所として同一のバンドアドレ
スを識別することができる。包括キー15の利点は、前記
データを識別する複数個の異なるユーザキーを用いてユ
ーザが所与のデータブロックを検索できる点にもある。
例えば、ユーザキー1はソーシャルセキュリティ番号
(social security number)でもよく、一方ユーザキー
2は異なる識別パラメータを用いた所与のデータの組の
迅速な索引付けしかつ検索を許容するシティ(city)又
はステート(state)の記憶場所でもよい。 データが存在するバンドアドレスを識別すると、記憶
装置6は迅速なバンドアドレス検索を開始して所望の情
報の特定のユーザデータブロック14を見出すことができ
る。好適実施例では、バンド上の全720ユーザブロック
に対しバンド当り48個のユーザデータトラックが存在
し、ユーザデータトラック当り15データブロックが存在
する。従って全ユーザバンドを個別に横切る各ユーザデ
ータブロックでのヘッダ情報の読取りは時間がかかり、
効率の悪いことが理解されよう。記憶装置6は、1に等
しい低い境界値を第1の値として動作時にセットし、ま
た48に等しい高い境界値として第2の値をセットする
(これによりそのバンドの48ユーザデータトラックの全
部がカバーされる)。次に中央値(median)が計算さ
れ、記憶装置6は読み書きヘッドをその中央値ユーザデ
ータトラックに送出する。 次に、記憶装置6は、ユーザデータブロック14に対す
る包括キー15を含むヘッダ情報を読出し、ターゲットキ
ー値と読出された値を比較する。読出された値+1がタ
ーゲットキー値より大きいと、低い境界値は読み書きヘ
ッドがトラッキング中のユーザデータトラック番号に等
しくセットされる。逆に、読出された値+1がターゲッ
トキー値以下か1に等しい時は、読み書きヘッドが探索
しているユーザデータトラックの値に等しくより高い境
界値がセットされる。いずれの場合も、記憶装置6はそ
の時点で新しい中央値を再計算し、そのユーザデータト
ラック上の任意のユーザデータブロック14のヘッダ情報
を読み取られたキー値をターゲットキー値に比較でき
る。記憶装置6が下部境界ユーザデータトラックの始点
から上部境界ユーザデータトラックの終点まで各ユーザ
データブロック14のヘッダ情報を読出して、下部境界ユ
ーザデータトラック又は上部境界ユーザデータトラック
の一方に達するまで前記の過程を続行し、その間の到る
所でデータデータブロック14が検索される。例えば第6
図に示すように、バンドアドレスCには6個のデータデ
ータブロック14が書込まれることがわかる。記憶装置6
は所望のバンドアドレス、例えばバンドアドレスCに記
憶装置6の読み書きヘッドを送出する。 バンドアドレスCを用いた第13図に示す例では、説明
のために第1ユーザキー46064を用い、上限及び下限の
間で中央値が計算され、また第1ブロックが読出され
る。この場合、ユーザブロック番号29は、この値がター
ゲットキー値以上であるので、48066として読み出さ
れ、上限がこの新しいユーザデータブロックにされ、こ
の新しい上限の間に見出された中央値と共にユーザデー
タブロック29が上限にされ、ユーザデータブロック29と
ユーザデータブロック8の間で中央値が計算される。ユ
ーザデータブロック10が読出され、第2ブロックはキー
値44062を示す。この値はターゲットキー値46064以下な
ので、記憶装置6はユーザデータブロック10に等しい下
限値をセットし、ユーザデータブロック29とユーザデー
タブロック10の間で中央値を見出す。ユーザデータブロ
ック23で読出し可能な第1ブロックが読出され、47065
を見出す。この値はターゲットキー値46064より大きい
ので、上限はユーザデータブロック23にセットされ、ま
たユーザデータブロック10とユーザデータブロック23と
の間の中央値はユーザデータブロック11として見出され
る。ユーザデータブロック11は値が45063の読出し可能
の第1ブロックとして読出され、この値はターゲットキ
ー値46064以下である。次に記憶装置6はユーザデータ
ブロック12からのキーを読出す。この時点で、記憶装置
6は、ユーザデータブロック23上の位置で47065を読出
し、ユーザデータブロック11上の位置で45063を読出
し、ターゲットキー値がディスク9上にあるかどうかを
通知し、また記憶装置6は、求める情報が存在すると
き、2つのユーザデータブロック11、23域内にあり、こ
れによりターゲットキー値より大きいか等しい最低値の
キーを有するユーザデータブロックを見出すまで45063
を読み出すユーザデータブロック11の後の内向きのユー
ザデータブロック毎の読出しを開始する。この時点で記
憶装置6は、配置動作が完了し、求めるデータが読み取
り可能であることを示す信号を制御装置3及びホスト中
央処理ユニット1に送出する。 以上に開示された本発明は比較的簡単な2進探索に関
して記載したが、任意の探索アルゴリズムを用いて本発
明が実施可能であり、また以上に開示する手順が添付し
た特許請求の範囲を何等限定しないことを理解すべきで
ある。 本発明の適用可能な分野はディジタルデータの大量記
憶の分野であり、WORM(ライトワンスリードメニイタイ
ムズ)光学記憶ディスクの外に他形式の記録媒体にも使
用可能である。
【図面の簡単な説明】
第1図はホスト中央処理ユニット、ホスト中央処理ユニ
ットに接続された制御装置及び制御装置により操作され
る情報記憶装置との間の関係を示すブロック図、第2図
はユーザデータトラックがその間に配置される複数のユ
ーザバンドを上に配置させた情報記憶ディスクの概略
図、第3図はユーザデータトラックに記憶された複数の
ユーザデータブロックを示すプラッタ上のユーザバンド
の形態を示す概略図、第4図は物理的IDとユーザ包括キ
ーとを有するブロックヘッダを示す単一ブロック図、第
5図は包括キーを説明のためにLIDキー、ユーザキー1
及びユーザキー2の3種の特定キーに分解した一組の包
括キーを系列化した表、第6図は適切なユーザバンド上
に適切なプロトコルにより記憶されたユーザデータを有
する複数のユーザバンドを持つプラッタ面を示す概略
図、第7図は記憶装置の索引レジスタが各索引バンドの
適切な索引値を保持する状態を示す表、第8図はLIDキ
ー、第1ユーザキー及び第2ユーザキーをポインタテー
ブルに加えるバンドアドレスA〜Gを示す表、第9図は
選択ポインタテーブル1、選択ポインタテーブル2及び
選択ポインタテーブル3を用いる時のターゲットキーレ
ジスタ、選択ポインタテーブルレジスタ、キー開始レジ
スタ、キーの長さレジスタ及びこれらのレジスタの内容
を示す後、第10図はLIDキー、索引、及び第1ポインタ
テーブルを用いた探索シーケンスを示す表、第11図は索
引及びポインタテーブル番号2を用いた第1ユーザキー
の探索シーケンスを示す表、第12図は索引ユーザキー2
及びポインタテーブル3を用いたユーザキーの探索シー
ケンスを示す表、第13図は配置すべき特定のユーザデー
タトラックとブロック上にデータを与える連続する2進
探索場所を示すユーザデータトラックCの略図である。 1……ホスト中央処理ユニット、2,4,8……バッファ、
3……制御装置、5,7……マイクロプロセッサ、6……
記憶装置、9……ディスク、10……ユーザデータトラッ
ク、11,12……ユーザバンド、13……ユーザデータトラ
ック、14……ユーザデータブロック、15……包括キー、
16……ヘッダ、17……ユーザデータ、18……PID、19…
…PIDキー、22……エントリ、24……索引アドレス、25
……レジスタ、
ットに接続された制御装置及び制御装置により操作され
る情報記憶装置との間の関係を示すブロック図、第2図
はユーザデータトラックがその間に配置される複数のユ
ーザバンドを上に配置させた情報記憶ディスクの概略
図、第3図はユーザデータトラックに記憶された複数の
ユーザデータブロックを示すプラッタ上のユーザバンド
の形態を示す概略図、第4図は物理的IDとユーザ包括キ
ーとを有するブロックヘッダを示す単一ブロック図、第
5図は包括キーを説明のためにLIDキー、ユーザキー1
及びユーザキー2の3種の特定キーに分解した一組の包
括キーを系列化した表、第6図は適切なユーザバンド上
に適切なプロトコルにより記憶されたユーザデータを有
する複数のユーザバンドを持つプラッタ面を示す概略
図、第7図は記憶装置の索引レジスタが各索引バンドの
適切な索引値を保持する状態を示す表、第8図はLIDキ
ー、第1ユーザキー及び第2ユーザキーをポインタテー
ブルに加えるバンドアドレスA〜Gを示す表、第9図は
選択ポインタテーブル1、選択ポインタテーブル2及び
選択ポインタテーブル3を用いる時のターゲットキーレ
ジスタ、選択ポインタテーブルレジスタ、キー開始レジ
スタ、キーの長さレジスタ及びこれらのレジスタの内容
を示す後、第10図はLIDキー、索引、及び第1ポインタ
テーブルを用いた探索シーケンスを示す表、第11図は索
引及びポインタテーブル番号2を用いた第1ユーザキー
の探索シーケンスを示す表、第12図は索引ユーザキー2
及びポインタテーブル3を用いたユーザキーの探索シー
ケンスを示す表、第13図は配置すべき特定のユーザデー
タトラックとブロック上にデータを与える連続する2進
探索場所を示すユーザデータトラックCの略図である。 1……ホスト中央処理ユニット、2,4,8……バッファ、
3……制御装置、5,7……マイクロプロセッサ、6……
記憶装置、9……ディスク、10……ユーザデータトラッ
ク、11,12……ユーザバンド、13……ユーザデータトラ
ック、14……ユーザデータブロック、15……包括キー、
16……ヘッダ、17……ユーザデータ、18……PID、19…
…PIDキー、22……エントリ、24……索引アドレス、25
……レジスタ、
フロントページの続き
(56)参考文献 特開 昭56−31157(JP,A)
特開 昭57−193837(JP,A)
特開 昭56−22172(JP,A)
特開 昭56−22171(JP,A)
Claims (1)
- (57)【特許請求の範囲】 1.ホスト中央処理ユニット及び記憶装置を有する情報
記録システム内に配置されかつ索引バンド及び複数のユ
ーザバンドを有する情報記憶ディスクを備え、各ユーザ
バンドは各ユーザデータブロックを記録する複数のユー
ザデータトラックを有し、情報記録ディスクのブロック
フォーマットに記録されたユーザデータを検索する方法
において、 ユーザデータを書き込むべきユーザバンドの位置を索引
付けすると共にユーザバンドのユーザデータブロックの
位置を決定する論理IDキー及びユーザデータブロックに
対する複数のユーザキーを含む包括キーをホスト中央処
理ユニットにおいて記録すべきユーザデータブロックに
割り当てる過程と、 索引を記憶する索引記憶手段、索引記憶手段に記憶され
た索引を分類するソート手段及び索引記憶手段に記憶さ
れた索引を検索するサーチ手段を備えた記憶装置に、ユ
ーザバンド、ユーザデータトラック及びユーザデータブ
ロックをユーザバンド内に系列化する物理的ID及び包括
キーを有するヘッダを有するユーザデータブロックを転
送する過程と、 ホスト中央処理ユニットによって指定された情報記録デ
ィスク上のユーザデータ位置内に包括キーと共にユーザ
データブロックを書き込む過程と、 ユーザデータブロックを記録するユーザバンドの位置及
び包括キーを情報記録ディスク上の所定の位置に記録す
る過程と、 ターゲットキーにより識別される所定のユーザデータブ
ロックに対する検索基礎となる包括キー内の論理IDキー
又は複数のユーザキーの一つをターゲットキーとして選
択する過程と、 ターゲットキーを記憶装置に転送する過程と、 ターゲットキーの値に基づく連続する順序で記憶装置に
設けられたマイクロプロセッサにより索引記憶手段に記
憶された索引を分類する過程と、 マイクロプロセッサによりターゲットキーに対して分類
された索引記憶手段を検索して、求められるユーザデー
タに関連する特定の論理IDキー又はユーザキーが存在す
る情報記録ディスク上の位置を決定する過程と、 を含むことを特徴とするユーザデータを検索するディジ
タル式情報記憶検索方法。 2.ホスト中央処理ユニットにより包括キーを指定する
過程を含む特許請求の範囲第(1)項に記載のディジタ
ル式情報記憶検索方法。 3.包括キーはユーザデータを記録すべきユーザバンド
及びユーザバンド中のユーザデータを表示するユーザデ
ータブロックを所定の順序で指示する特許請求の範囲第
(1)項に記載のディジタル式情報記憶検索方法。 4.ホスト中央処理ユニット及び記憶装置を有する情報
記憶システム内に配置されかつ索引バンド及び複数のユ
ーザバンドを有する情報記録ディスクを備え、各ユーザ
バンドは各ユーザデータブロックを記録する複数のユー
ザデータトラックを有し、情報記録ディスクのブロック
フォーマットに記録されたユーザデータを検索する装置
において、 ユーザデータを書き込むべきユーザバンドの位置を索引
付けすると共にユーザバンドのユーザデータブロックの
位置を決定する論理IDキー及びユーザデータブロックに
対する複数のユーザキーを含む包括キーを登録すべきユ
ーザデータブロックに割り当てるホスト中央処理ユニッ
トと、 索引を記憶するランダムアクセスメモリを有する索引記
憶手段及び索引記憶手段に記憶された索引を分類すると
共に索引記憶手段に記憶された索引を検索するマイクロ
プロセツサを備えた記憶装置に、ユーザバンド、ユーザ
データトラック及びユーザデータブロックをユーザバン
ド内に系列化する物理的ID(PID)及び包括キーを含む
ヘッダを有するユーザデータブロックをホスト中央処理
ユニットから転送する制御装置と、 ホスト中央処理ユニットによって指定された情報記憶デ
ィスクのユーザデータ位置にユーザデータブロックを包
括キーと共に書き込む手段と、 ユーザデータブロックを記録するユーザバンドの位置及
び包括キーを情報記録ディスク上の所定の位置に記録す
る手段とを備え、 ターゲットキーとして論理IDキー又はユーザキーの一つ
をホスト中央処理ユニットによりユーザデータの検索基
礎となる包括キー内で選択し、ユーザデータ内で検索す
べき選択されたターゲットキーを記憶装置に転送し、検
索に対して選択されたターゲットキーの値に基づく連続
する順序で索引記憶手段に記憶された索引を分類し、タ
ーゲットキーに対して分類された索引記憶手段をユーザ
データ内で検索して、求められるユーザデータに関連す
る特定の論理IDキー又はユーザキーが存在する情報記録
ディスク上の位置を決定することを特徴とするユーザデ
ータを検索するディジタル式情報記憶検索装置。 5.包括キーはホスト中央処理ユニットにより指定され
る特許請求の範囲第(4)項に記載のディジタル式情報
記憶検索装置。 6.包括キーはデータを記録すべきユーザバンド及びユ
ーザバンド中のデータを表示するユーザデータブロック
を所定の順序で指示する特許請求の範囲第(4)項に記
載のディジタル式情報記憶検索装置。
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US06/544,328 US4633393A (en) | 1983-10-21 | 1983-10-21 | Generic key for indexing and searching user data in a digital information storage and retrieval device |
US544328 | 2006-10-06 |
Publications (2)
Publication Number | Publication Date |
---|---|
JPS60151757A JPS60151757A (ja) | 1985-08-09 |
JP2770855B2 true JP2770855B2 (ja) | 1998-07-02 |
Family
ID=24171735
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP59219403A Expired - Lifetime JP2770855B2 (ja) | 1983-10-21 | 1984-10-20 | ディジタル式情報記憶検索方法及びその装置 |
Country Status (2)
Country | Link |
---|---|
US (1) | US4633393A (ja) |
JP (1) | JP2770855B2 (ja) |
Families Citing this family (29)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5034914A (en) * | 1986-05-15 | 1991-07-23 | Aquidneck Systems International, Inc. | Optical disk data storage method and apparatus with buffered interface |
US5247646A (en) * | 1986-05-15 | 1993-09-21 | Aquidneck Systems International, Inc. | Compressed data optical disk storage system |
US4827462A (en) * | 1987-03-26 | 1989-05-02 | International Business Machines Corporation | Modular data storage directories for large-capacity data storage units |
EP0325823A1 (en) * | 1988-01-26 | 1989-08-02 | Laserdrive Ltd. | Data storage system |
US4961139A (en) * | 1988-06-30 | 1990-10-02 | Hewlett-Packard Company | Data base management system for real-time applications |
EP0369052A1 (en) * | 1988-11-17 | 1990-05-23 | International Business Machines Corporation | Data base access system |
US5829002A (en) * | 1989-02-15 | 1998-10-27 | Priest; W. Curtiss | System for coordinating information transfer and retrieval |
US5020019A (en) * | 1989-05-29 | 1991-05-28 | Ricoh Company, Ltd. | Document retrieval system |
US5367677A (en) * | 1990-05-11 | 1994-11-22 | Thinking Machines Corporation | System for iterated generation from an array of records of a posting file with row segments based on column entry value ranges |
US5313604A (en) * | 1990-11-13 | 1994-05-17 | Hewlett-Packard Company | Method for locating compressed data in a computed memory back up device including steps of refining estimater location |
US5396624A (en) * | 1990-12-20 | 1995-03-07 | Visa International Service Association | Account file for off-line transaction authorization |
US5563997A (en) * | 1992-11-16 | 1996-10-08 | Canon Kabushiki Kaisha | Method and apparatus for sorting records into a list box in a graphic user interface |
US5611066A (en) * | 1994-02-28 | 1997-03-11 | Data/Ware Development, Inc. | System for creating related sets via once caching common file with each unique control file associated within the set to create a unique record image |
EP0794496B1 (en) * | 1995-06-30 | 2004-04-21 | Sony Corporation | Method and device for recording data, data recording medium, and method and device for reproducing data |
US5878410A (en) * | 1996-09-13 | 1999-03-02 | Microsoft Corporation | File system sort order indexes |
US5966732A (en) * | 1996-12-02 | 1999-10-12 | Gateway 2000, Inc. | Method and apparatus for adding to the reserve area of a disk drive |
KR100212747B1 (ko) * | 1997-01-30 | 1999-08-02 | 윤종용 | 키폰교환시스템의 데이터 검색방법 |
US6654881B2 (en) * | 1998-06-12 | 2003-11-25 | Microsoft Corporation | Logical volume mount manager |
CA2244626A1 (en) | 1998-07-31 | 2000-01-31 | Kom Inc. | A hardware and software system |
US6553387B1 (en) | 1999-11-29 | 2003-04-22 | Microsoft Corporation | Logical volume configuration data management determines whether to expose the logical volume on-line, off-line request based on comparison of volume epoch numbers on each extents of the volume identifiers |
US6684231B1 (en) * | 1999-11-29 | 2004-01-27 | Microsoft Corporation | Migration of friendly volumes |
AU5868801A (en) * | 2000-05-29 | 2001-12-11 | Kaisha Saora Kabushiki | System and method for saving browsed data |
US20020147775A1 (en) * | 2001-04-06 | 2002-10-10 | Suda Aruna Rohra | System and method for displaying information provided by a provider |
JP2003337699A (ja) * | 2002-03-13 | 2003-11-28 | Saora Inc | 情報処理装置及びその方法、及びそのプログラムを記憶した記憶媒体 |
US7120641B2 (en) | 2002-04-05 | 2006-10-10 | Saora Kabushiki Kaisha | Apparatus and method for extracting data |
US20030195896A1 (en) * | 2002-04-15 | 2003-10-16 | Suda Aruna Rohra | Method and apparatus for managing imported or exported data |
US20080270401A1 (en) * | 2007-04-26 | 2008-10-30 | Kristin Petersen | Method and Apparatus for Displaying Sorted Test Data Entries |
US8086582B1 (en) * | 2007-12-18 | 2011-12-27 | Mcafee, Inc. | System, method and computer program product for scanning and indexing data for different purposes |
US9870382B2 (en) * | 2014-03-25 | 2018-01-16 | Sap Se | Data encoding and corresponding data structure |
Family Cites Families (11)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US3593309A (en) * | 1969-01-03 | 1971-07-13 | Ibm | Method and means for generating compressed keys |
US3643226A (en) * | 1969-06-26 | 1972-02-15 | Ibm | Multilevel compressed index search method and means |
US3602895A (en) * | 1969-06-30 | 1971-08-31 | Ibm | One key byte per key indexing method and means |
US4086628A (en) * | 1971-11-10 | 1978-04-25 | International Business Machines Corporation | Directory generation system having efficiency increase with sorted input |
US4399503A (en) * | 1978-06-30 | 1983-08-16 | Bunker Ramo Corporation | Dynamic disk buffer control unit |
JPS5622172A (en) * | 1979-07-31 | 1981-03-02 | Toshiba Corp | Retrieving device for picture information |
JPS5622171A (en) * | 1979-07-31 | 1981-03-02 | Toshiba Corp | Retrieving system for picture information |
JPS5631157A (en) * | 1979-08-22 | 1981-03-28 | Hitachi Ltd | Constitution of file |
US4358824A (en) * | 1979-12-28 | 1982-11-09 | International Business Machines Corporation | Office correspondence storage and retrieval system |
JPS57193837A (en) * | 1981-05-25 | 1982-11-29 | Fujitsu Ltd | Retrieval system for data record having a plurality of keys |
US4476526A (en) * | 1981-11-27 | 1984-10-09 | Storage Technology Corporation | Cache buffered memory subsystem |
-
1983
- 1983-10-21 US US06/544,328 patent/US4633393A/en not_active Expired - Lifetime
-
1984
- 1984-10-20 JP JP59219403A patent/JP2770855B2/ja not_active Expired - Lifetime
Also Published As
Publication number | Publication date |
---|---|
JPS60151757A (ja) | 1985-08-09 |
US4633393A (en) | 1986-12-30 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP2770855B2 (ja) | ディジタル式情報記憶検索方法及びその装置 | |
US4760526A (en) | Method for storing data into a file device and for data retrieval | |
JP2501430B2 (ja) | デイジタル式情報記憶検索装及び方法 | |
Dodd | Elements of data management systems | |
US5375235A (en) | Method of indexing keywords for searching in a database recorded on an information recording medium | |
US5321824A (en) | Accessing last recorded data in a continuation chain | |
KR920005107A (ko) | 최초 및 갱신 데이타 기록 및 판독 방법과 데이타 기억 매체 | |
EP0369052A1 (en) | Data base access system | |
JPS63121179A (ja) | ステ−ジング方法 | |
KR910014928A (ko) | 데이터디스크와 데이터디스크상에 기록된 데이터검색방법 | |
JPS62226375A (ja) | 画像情報検索方式 | |
US4853921A (en) | Method for storing data in rotary type recording media | |
JPS63104284A (ja) | デイスクフアイルアクセス方式 | |
JPS6064387A (ja) | 情報表示方法 | |
JP2701271B2 (ja) | 画像ファイル記録方法 | |
JPH02278439A (ja) | 追記型デバイスのデータ管理方式 | |
JPS62177642A (ja) | 追記型フアイル装置のフアイル管理方式 | |
JPS61103242A (ja) | 高速検索方式 | |
JPS60225938A (ja) | 情報検索方式 | |
JPH03109673A (ja) | 文書処理装置 | |
JPH0258167A (ja) | 光デイスクフアイル装置 | |
JPH0770194B2 (ja) | 追記型記録媒体におけるデータ追記方法 | |
JPS60160062A (ja) | 画像情報記憶検索装置 | |
JPH06282479A (ja) | 電子ファイルシステム | |
JPH04230576A (ja) | 項目選択装置 |