(57)【要約】      （修正有）【課題】レコード毎に設定されるデータ長からなるレコードの単位でテープ上のデータを管理するテープドライブにおいて、テープ上に書き込まれた複数のレコード群を連続して読み出す際に、データを読み出す順番の検索（並べ替え）時間を短縮しつつ、ホストからの一括データ読み出しの総処理時間を改善する検索方法を提供する。【解決手段】読み出す複数のレコード群の情報を受信するステップと、読み出す複数のレコード群をその読み出し時間が短くなるように並べ替えるステップとを含み、その並べ替えるステップにおいて、連続する少なくとも２以上のレコード群が、複数の領域中の同一領域に割り当てられている、または隣接する領域にまたがって割り当てられている場合に、当該２以上のレコード群を結合して１つの並べ替えの対象として扱うことにより、並べ替えに要する時間を低減させる。【選択図】図４
2014179140.tif 000002
【特許請求の範囲】
【請求項１】
レコード毎に設定されるデータ長からなるレコードの単位でテープ上のデータを管理するテープドライブにおいて、テープ上に書き込まれた複数のレコード群を連続して読み出す際の当該複数のレコード群の読み出し順序を検索する検索方法であって、
複数のレコード群の各々は少なくとも１以上のレコードを含み、各レコード群の先頭のレコード番号と最後尾のレコード番号はテープドライブによって管理され、
テープの各ラップの長手方向において、所定数の複数の領域が設定され、当該複数の領域の各々には、少なくとも１つ以上のレコード群が割り当てられ、
読み出す複数のレコード群の情報を受信するステップと、
前記読み出す複数のレコード群をその読み出し時間が短くなるように並べ替えるステップと、を含み、
前記並べ替えるステップにおいて、連続する少なくとも２以上のレコード群が、前記複数の領域中の同一領域に割り当てられている、または隣接する領域にまたがって割り当てられている場合に、当該２以上のレコード群を結合して１つの並べ替えの対象として扱うことにより、並べ替えに要する時間を低減させることを特徴とする、検索方法。
【請求項２】
前記複数のレコード群を並べ替えるステップは、
前記複数のレコード群の各々を、各レコード群の先頭のレコード番号が小さい順に連続する番号を付与して並び替えるステップと、
１つのレコード群の後に続けて読み出す次のレコード群を検索するステップを含み、
前記検索するステップは、前記次のレコード群が割り当てられた領域内の当該レコード群の開始位置ヘの読み取りヘッドの移動時間が最小となるように、前記次のレコード群を選択することを含み、
前記２以上のレコード群が結合された場合、当該結合された２以上のレコード群の一番小さなレコード番号が当該結合されたレコード群の最初のレコード番号であり、一番大きなレコード番号が当該結合されたレコード群の最後のレコード番号である、請求項１の検索方法。
【請求項３】
前記複数のレコード群を並べ替えるステップは、前記複数のレコード群の列の最後のレコード群を、当該最後の位置を除く他のレコード群の後に入れることにより、前記複数のレコード群全体の読み出し時間が短くなるか否かを検索するステップを含み、
前記検索するステップは、
前記最後のレコード群と少なくともその１つ前のレコード群とを結合し、当該結合された２以上のレコード群を前記他のレコード群であって結合されていないレコード群の後に入れることにより、前記複数のレコード群全体の読み出し時間が短くなるか否かを検索することを含む、請求項１の検索方法。
【請求項４】
前記テープドライブは、ファイルシステムまたは仮想テープサーバ（ＶＴＳ）において、ホストに通信可能に接続されたテープドライブであり、
前記読み出す複数のレコード群の情報は、前記ホストから前記テープドライブに送信され、
前記並べ替えるステップにおいて並べ替えられた前記複数のレコード群は、前記テープドライブから前記ホストに送信される、請求項１〜３のいずれか１項の検索方法。
【請求項５】
レコード毎に設定されるデータ長からなるレコードの単位でテープ上のデータを管理するテープドライブにおいて、テープ上に書き込まれた複数のレコード群を連続して読み出す際の当該複数のレコード群の読み出し順序を検索するためのプログラムであって、
複数のレコード群の各々は少なくとも１以上のレコードを含み、各レコード群の先頭のレコード番号と最後尾のレコード番号はテープドライブによって管理され、
テープの各ラップの長手方向において、所定数の複数の領域が設定され、当該複数の領域の各々には、少なくとも１つ以上のレコード群が割り当てられ、
読み出す複数のレコード群の情報を受信するステップと、
前記読み出す複数のレコード群をその読み出し時間が短くなるように並べ替えるステップと、を前記テープドライブに実行させることを含み、
前記並べ替えるステップにおいて、連続する少なくとも２以上のレコード群が、前記複数の領域中の同一領域に割り当てられている、または隣接する領域にまたがって割り当てられている場合に、当該２以上のレコード群を結合して１つの並べ替えの対象として扱うことにより、並べ替えに要する時間を低減させることを特徴とする、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テープドライブに関し、より具体的には、テープドライブにおいてテープ上の複数のレコード群の読み出し順序を検索する方法に関する。
【背景技術】
【０００２】
近年のテープドライブは、テープメディア（以下、本明細書では「テープ」と呼ぶ）の容量の増加にともなって多量のデータを高速に転送できるようになり、ファイルシステムや仮想テープサーバ（ＶＴＳ）において利用されるようになってきた。その場合、テープドライブは、テープ上に分散して書かれている多数のデータを一括して読み出す機能が求められる。
【０００３】
しかし、テープ上のデータは、数百メートルの長さのテープ上に分散して書かれているので、データの読み出し順序を考慮せずに読み出しを行うと、ヘッドの各データの先頭への移動（位置あわせ）に多くの時間がかかり、ホストから要求される一括データの読み出し処理が著しく遅くなってしまうという問題が生じる。
【０００４】
特許文献１は、上記問題を改善するための方法として、最近傍アルゴリズム（以下、本明細書では「最近接選択法」と呼ぶ）またはペアワイズ交換アルゴリズム（以下、本明細書では「最後尾入れ替え法」と呼ぶ）を開示する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開2012-128937号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１の方法では、一括したデータを読み出すための総位置あわせ所要時間を短縮することができる。しかし、本発明者らが得た知見によれば、読み出すべきデータ数の増加に伴い、その位置合わせのための処理時間、すなわちデータを読み出す順番の検索（並べ替え）時間が増加してしまい、場合によっては、ホストからの読み出し要求に予め設定された応答時間以内に応答できない、といった問題さえも発生する恐れがあることが判明した。
【０００７】
したがって、本発明の目的は、上述した従来技術の問題を軽減して、すなわち、一括データを読み出す順番の検索（並べ替え）時間を短縮しつつ、ホストからの一括データ読み出しの総処理時間を改善することができる検索方法を提供することである。
【課題を解決するための手段】
【０００８】
本発明は、レコード毎に設定されるデータ長からなるレコードの単位でテープ上のデータを管理するテープドライブにおいて、テープ上に書き込まれた複数のレコード群を連続して読み出す際の当該複数のレコード群の読み出し順序を検索する検索方法を提供する。ここで言うレコード群は、ユーザ・データ・セグメント（以下、本明細書では「ＵＤＳ」と呼び、以下の説明では「レコード群」と同様な意味で用いる）とも呼ばれ、複数のレコード群の各々は少なくとも１以上のレコードを含み、各レコード群の先頭のレコード番号と最後尾のレコード番号を含む。このＵＤＳの情報は、ホストアプリケーションが連続して読み出すレコード群をリストにして、例えばＧＲＡＯ（Generate Recommended Access Order）というＳＣＳＩコマンドにより、実際のデータアクセスの前にホストアプリケーションからドライブに提供されるものであり、その情報を受け取ったテープドライブはそのレコード群のリストを保持しているものとする。
【０００９】
テープの各ラップの長手方向において、所定数の複数の領域が設定され、当該複数の領域の各々には、少なくとも１つ以上のレコード群が割り当てられる。上記の検索方法は、読み出す複数のレコード群の情報を受信するステップと、読み出す複数のレコード群をその読み出し時間が短くなるように並べ替えるステップとを含む。さらに、並べ替えるステップにおいて、連続する少なくとも２以上のレコード群が、複数の領域中の同一領域に割り当てられている、または隣接する領域にまたがって割り当てられている場合に、当該２以上のレコード群を結合して１つの並べ替えの対象として扱うことにより、並べ替えに要する時間を低減させることを特徴とする。
【００１０】
本発明によれば、テープ上の読み出すデータの並べ替えの対象数（レコード群の数）、言い換えれば、検索対象（パターン）数を減らすことにより、読み出すデータの並べ替え時間を短縮することができる。
【００１１】
本発明の一態様では、複数のレコード群を並べ替えるステップは、複数のレコード群の各々を、各レコード群の先頭のレコード番号が小さい順に連続する番号を付与して並び替えるステップと、１つのレコード群の後に続けて読み出す次のレコード群を検索するステップを含む。その検索するステップは、次のレコード群が割り当てられた領域内の当該レコード群の開始位置ヘの読み取りヘッドの移動時間が最小となるように、次のレコード群を選択することを含む。さらに、２以上のレコード群が結合された場合、当該結合された２以上のレコード群の一番小さなレコード番号が当該結合されたレコード群の最初のレコード番号であり、一番大きなレコード番号が当該結合されたレコード群の最後のレコード番号である。
【００１２】
本発明の一態様によれば、特許文献１の最近接選択法を用いた場合において、検索対象（パターン）数を減らすことにより、読み出すデータの並べ替え時間を短縮することができる。
【００１３】
本発明の一態様では、並べ替えるステップは、複数のレコード群の列の最後のレコード群を、当該最後の位置を除く他のレコード群の後に入れることにより、複数のレコード群全体の読み出し時間が短くなるか否かを検索するステップを含む。その検索するステップは、最後のレコード群と少なくともその１つ前のレコード群とを結合し、当該結合された２以上のレコード群を他のレコード群であって結合されていないレコード群の後に入れることにより、複数のレコード群全体の読み出し時間が短くなるか否かを検索することを含む。
【００１４】
本発明の一態様によれば、特許文献１の最後尾入れ替え法を用いた場合において、検索対象（パターン）数を減らすことにより、読み出すデータの並べ替え時間を短縮することができる。
【００１５】
本発明の一態様では、テープドライブは、ファイルシステムまたは仮想テープサーバ（ＶＴＳ）において、ホストに通信可能に接続されたテープドライブである。そして、読み出す複数のレコード群の情報は、ホストから前記テープドライブに送信され、並べ替えるステップにおいて並べ替えられた複数のレコード群は、テープドライブから前記ホストに送信される。
【００１６】
本発明の一態様によれば、ホストから受信した読み出す複数のレコード群を短い時間で一括データの読み出し時間が短くなるように並べ替えてホストへ返信することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明のテープドライブが利用されるファイルシステムの構成例を示す図である。
【図２】本発明のテープドライブの構成例を示す図である。
【図３】本発明のテープの構成例を示す図である。
【図４】本発明のＢＩＮＤ属性付き最近接選択法を説明するための図である。
【図５】本発明のＢＩＮＤ属性付き最後尾入れ替え法を説明するための図である。
【図６】ＵＤＳ数と処理時間との関係を示す図である。
【図７】ＵＤＳ数と読み出し時間との関係を示す図である。
【発明を実施するための形態】
【００１８】
図面を参照しながら本発明の実施の形態を説明する。図１は、本発明のテープドライブが利用されるファイルシステムの構成例を示す図である。ファイルシステム１００は、ネットワーク３６を介して相互に通信可能なテープドライブ１０、ホスト（サーバー）３０、ＰＣ（端末）３２、３４からなる。図１では、テープドライブ１０とホスト（サーバー）３０は、それぞれ１つしか描かれていないが、これはあくまで例示であって、２以上のテープドライブ１０やホスト（サーバー）３０を含むことができることは言うまでもない。
【００１９】
ファイルシステム１００は、例えばＬＴＦＳ（Linear Tape File System）とすることができる。ＬＴＦＳは、ＨＤＤやＵＳＢメモリ、あるいはＣＤ−Ｒを始めとする他のリムーバブルな記録媒体同様に、テープカートリッジをテープドライブに挿入すれば、そのテープカートリッジに保存されたファイルに直接アクセスできる仕組みである。
【００２０】
図２は、本発明のテープドライブの構成例を示す図である。テープドライブ１０は、ホストインターフェイス（以下、「ホストＩ／Ｆ」という）１１と、バッファ１２と、チャネル１３と、ヘッド１４と、モータ１５とを含む。また、コントローラ１６と、ヘッド位置制御システム１７と、モータドライバ１８とを含む。更に、テープドライブ１０には、テープカートリッジ２０が挿入されることにより装填可能となっているので、ここでは、テープカートリッジ２０も図示している。このテープカートリッジ２０は、リール２１、２２に巻かれたテープ２３を含む。テープ２３は、リール２１、２２の回転に伴い、リール２１からリール２２の方向へ、又は、リール２２からリール２１の方向へ、長手方向に移動する。なお、テープ２３としては、磁気テープが例示されるが、磁気テープ以外のテープ媒体でもよい。
【００２１】
また、テープカートリッジ２０は、カートリッジメモリ（ＣＭ）２４も含む。このＣＭ２４は、例えば、テープ２３上にどのようにデータが書かれたかの情報を記録する。そして、例えばＲＦインターフェイスを用いて非接触でテープ２３に書かれたデータのインデックスやテープ２３の使用状況等を調べることにより、データへの高速アクセスを可能としている。なお、図２では、このＲＦインターフェイスのようなＣＭ２４へのアクセスを行うためのインターフェイスを、カートリッジメモリインターフェイス（以下、「ＣＭＩ／Ｆ」という）１９として示している。
【００２２】
ここで、ホストＩ／Ｆ１１は、ホスト（サーバー）３０や他のＰＣ３２等との通信を行う。例えば、ホスト３０のＯＳから、テープ２３へのデータの書込みを指示するコマンド、テープ２３を目的の位置に移動させるコマンド、テープ２３からのデータの読出しを指示するコマンドを受け取る。上述したＬＴＦＳの例では、デスクトップＯＳなどから直接、テープドライブ内のデータを参照でき、ＨＤＤ内のファイルを扱うのと同様に、ダブルクリックでファイルを実行したり、ドラッグアンドドロップでコピーしたりできる。
【００２３】
バッファ１２は、テープ２３に書き込むべきデータやテープ２３から読み出されたデータを蓄積するメモリである。例えば、ＤＲＡＭによって構成される。また、バッファ１２は、複数のバッファセグメントからなり、各バッファセグメントが、テープ２３に対する読み書きの単位であるデータセットを格納している。
【００２４】
チャネル１３は、テープ２３に書き込むべきデータをヘッド１４に送ったり、テープ２３から読み出されたデータをヘッド１４から受け取ったりするために用いられる通信経路である。ヘッド１４は、テープ２３が長手方向に移動するとき、テープ２３に対して情報を書き込んだり、テープ２３から情報を読み出したりする。モータ１５は、リール２１、２２を回転させる。なお、図２では、１つの矩形でモータ１５を表しているが、モータ１５としては、リール２１、２２の各々に１つずつ、合計２個設けるのが好ましい。
【００２５】
一方、コントローラ１６は、テープドライブ１０の全体を制御する。本発明の方法やプログラムは、このコントローラ１６によって実行される。コントローラ１６は、ホストＩ／Ｆ１１で受け付けたコマンドに従って、データのテープ２３への書込みやテープ２３からの読出しを制御する。また、ヘッド位置制御システム１７やモータドライバ１８の制御も行う。ヘッド位置制御システム１７は、所望のラップを追跡するシステムである。ここで、ラップとは、テープ２３上の複数のトラックのグループであり、言い換えれば、ヘッド１４がテープ２３に総容量のデータを書き込む場合に、テープ２３の長手方向に数十往復する際のその片道一回分のデータ群を意味する。ラップを切り換える必要が生じると、ヘッド１４を電気的に切り換える必要も生じるので、このような切り換えの制御を、このヘッド位置制御システム１７で行う。
【００２６】
モータドライバ１８は、モータ１５を駆動する。尚、上述したように、モータ１５を２個使用する場合であれば、モータドライバ１８も２個設けられる。ＣＭＩ／Ｆ１９は、例えば、ＲＦリーダライタにより実現され、ＣＭ２４への情報の書込みや、ＣＭ２４からの情報の読出しを行う。
【００２７】
図３は、本発明のテープカートリッジ２０内のテープ２３の構成例を示す図である。図３は、ＩＢＭ社のエンタープライズテープドライブでサポートされているテープ２３の一例である。なお、以下の説明は、このＩＢＭ社のエンタープライズテープドライブでの例を用いて行うが、本発明の実施形態はこれに限定されるものではないことは言うまでもない。図３の（ａ）は、テープ２３の全体を示し、（ｂ）はテープ２３の１つのデータバンド（ＤＢ）の構成を示す一例である。
【００２８】
図３（ａ）において、記録面は、１２．６５ｍｍ幅のテープに４本のデータバンドＤＢ０〜３を挟む形で５本のサーボバンド４０が配置されている。サーボバンド４０の各々には、ヘッド１４を正確に導く（トラッキングさせる）ためのサーボパターンが予め記録されている。テープドライブ１０は、各データバンドＤＢ０〜３を挟む２本のサーボバンド４０中のサーボパターンを読み取りながら高精度にヘッド１４を位置付けし、データの書き込みや読み出しを実現する。
【００２９】
図３（ｂ）において、１つのデータバンド（ＤＢ）には、既に上述したラップ４２が２０本設けられており（テープ全体で８０本）、各ラップ４２には順番にデータ（レコード）が書き込まれる。なお、テープドライブ１０及びホスト３０において、書きこまれた順番にそのレコードの番号（通し番号）が管理される。
【００３０】
各ラップ４２は、所定数、例えば６４個の領域に分割され、その各領域にレコード番号の何番から何番まで格納されているかという詳細な情報をHigh Resolution Tape Directory（以下、「ＨＲＴＤ」と呼ぶ）として、レコード書き込み時にＨＲＴＤを構築し、ＣＭ２４、もしくは特定のテープ領域上に格納している。テープカートリッジ２０がテープドライブ１０にロードされた際に、テープドライブ１０は、ＨＲＴＤを読み出し、どのレコードがどこに記録されているかを知る。データを読み出す時には、そのレコード（もしくはＵＤＳ）が含まれる領域をＨＲＴＤから算出し、読み出すレコードを含むＨＲＴＤの先頭の物理位置（テープ上の位置）を起点として、順にレコード通し番号を走査しながら読み出しを続けることで、目的のデータを見つけることになる。
【００３１】
ＩＢＭ社のエンタープライズテープドライブでは、図３（ｂ）に例示されるような分散したレコード群（例えば、図のＡ〜Ｄ）（以下、「レコード群」を上述したように同義の「ＵＤＳ」と表記する）を読み出し手順を決める手法として、Recommended Access Order（以下、「ＲＡＯ」と呼ぶ）機能を採用する。ＲＡＯ機能は、ヘッドの各データの先頭への移動（位置あわせ）時間の短縮のために、データ読み出し順序の並べ替えをテープドライブ１０側で行う機能である。ホスト３０は、複数のＵＤＳを読み出す前に、各ＵＤＳの先頭のレコード番号と最後尾のレコード番号の情報（リスト）を既に上述したＧＲＡＯコマンドによりテープドライブ１０に送信する。テープドライブ１０はそのリストを位置あわせ所要時間が短縮できるよう並べ替えたリストを作成する。次に、ホスト３０がＲＲＡＯ（Receive Recommended Access Order）コマンドによりその並べ替えられたリストを受け取る。ホスト３０は、その並べ替えられたＵＤＳのリストに従って読み出しを行うことによって、データの読み出しの処理時間を短縮する。なお、ＧＲＡＯコマンドとＲＲＡＯコマンドのタイムアウト時間は、例えば３０秒と規定されている。
【００３２】
本発明の方法は、ＧＲＡＯコマンドによって、テープドライブ１０がホスト３０から受け取ったＵＤＳのリストを位置あわせ所要時間が短縮できるよう並べ替えるための方法である。その方法の特徴は、下記に述べる「ＢＩＮＤ属性」を用いることである。なお、本発明の方法によって並べ替えられたリストは、ＲＲＡＯコマンドによって、テープドライブ１０からホスト３０へ返信される。
【００３３】
上述したように、テープドライブ１０の読み出し操作は、ＨＲＴＤエントリを起点としている。同一ラップの同一領域、すなわち１つのＨＲＴＤエントリと次のＨＲＴＤエントリの間に複数のＵＤＳがある場合、後ろのＵＤＳ（先頭のレコード番号が大きい）を読むためには前のＵＤＳ（先頭のレコード番号が小さい）を必ず読むことになるため、両者を連続したデータとみなすことができる。同一ラップの隣接する領域にまたがる複数のデータも、他のラップへ移動するときに発生するバックヒッチがないため、データの位置あわせ時間は最短となるので、連続したデータとみなすことができる。
【００３４】
ＨＲＴＤエントリの数は、上述したように各ラップに６４個ある。同一もしくは隣接するエントリ上のデータをまとめると、最大２２個のデータ群にまとめることができる。テープ上の総ラップ数が８０の場合、最大データ数は１７６０となる。物理位置を推定する作業中に、同一もしくは隣接するＨＲＴＤ領域に他のデータがないかを走査する。他のＵＤＳがあった場合、後ろのＵＤＳにＢＩＮＤという属性を割り振ることにする。ここで、ＢＩＮＤ属性とは、直前のデータの後に連続して読み出すことが確定していることを意味する。そして、このＢＩＮＤ属性のついたデータを、特許文献１の「最近接選択法」または「最後尾入れ替え法」の方法において、走査（検索）の対象としないことで走査（検索）数を削減することが本発明の特徴（実施例）である。以下に、その内容を説明する。
【００３５】
（Ａ）ＢＩＮＤ属性付き最近接選択法
最近接選択法は、現在のデータ位置（レコード番号で特定される位置）からすべてのＵＤＳの位置あわせ所要時間を計算し最小のものを次に読み出すＵＤＳとし、その次のＵＤＳの終了位置から残りのすべてのＵＤＳの位置あわせ所要時間を計算し最小のものをさらに次のＵＤＳとし、という流れを最後まで繰り返すという方法である。
【００３６】
本発明のＢＩＮＤ属性付き最近接選択法では、まず、それぞれのＵＤＳがＢＩＮＤ属性を持つかどうかを調べる。ＧＲＡＯコマンドにより受け取ったＵＤＳのリストを各々のＵＤＳの先頭のレコード番号順に並べ替えて、ＵＤＳ毎に番号を付与する。レコード番号順に並べ替えられたＵＤＳを用いて、前述の方法により、ＢＩＮＤ属性を与えることができるものには、各々のＵＤＳにＢＩＮＤ属性を付与する。次に、現在のデータ位置（レコード番号で特定される位置）からすべてのＢＩＮＤ属性のないＵＤＳへの位置あわせ処理時間を計算し、最小のものを次に読み出すＵＤＳとする。以降に、ＢＩＮＤ属性のあるデータ群があれば併せて次のＵＤＳとする。図４にその一例を示す。
【００３７】
図４において、（ａ）に示されるように、ＵＤＳ１〜Ｎの読み出し対象において、ＵＤＳ３、５がそれぞれテープの同一ラップの同一領域あるいは隣接する領域にあって、ＢＩＮＤ属性を持っているとする。（ｂ）に示すように、最初にデータ１からＢＩＮＤ属性のないＵＤＳ２、４・・・Ｎまでの各ＵＤＳへの位置合わせ処理時間ｔ（１、２）、ｔ（１、４）・・・ｔ（１、Ｎ）を計算し、その最小値を探索する。ここで、位置合わせ処理時間ｔ（Ａ、Ｂ）は、テープドライブが、現在のデータ位置Ａから目的のデータ位置Ｂに移動するために必要な位置あわせ所要時間であって、下記の式（１）で求められる。
t(A、B) = tLEN(A、B)＋tBAND(A、B)＋tDIR(A、B)      （１）
tLEN(A、B)はテープの長さ方向の移動時間であり、tBAND(A、B)はテープの幅方向の移動時間であり、tDIR(A、B)はテープの進行方向を変えるために必要な時間である。
【００３８】
今、ｔ（１、４）が最小値であったとする。そのＵＤＳ４にＢＩＮＤ属性を持つＵＤＳ５を結合させてあたかも１つのＵＤＳとして見なして、（ｃ）に示されるように、その結合されたＵＤＳ５からＵＤＳ２、６、・・・Ｎまでの各ＵＤＳへの位置合わせ処理時間ｔ（５、２）、ｔ（５、６）・・・ｔ（５、Ｎ）を計算し、その最小値を探索する。以下、同様にして計算及び最小値の探索を繰り返す。この方法によれば、位置合わせ処理時間の計算の基となるデータ数（ＵＤＳ数）をＢＩＮＤ属性を持つＵＤＳ数の分だけ減らすことができるので、位置合わせ処理時間を大幅に短縮することが可能となる。
【００３９】
（Ｂ）ＢＩＮＤ属性付き最後尾入れ替え法
最後尾入れ替え法は、最後のＵＤＳを最後以外の位置に移動挿入することによって、総位置あわせ所要時間が短くならないかを走査する方法である。元よりも短い時間となる位置が見つかった場合はそこに挿入し、さらに、次の最後のＵＤＳについて同じことを繰り返す。最後（Ｎ番目）のＵＤＳを挿入できる箇所が見つからなかった場合は終了する。
【００４０】
本発明のＢＩＮＤ属性付き最後尾入れ替え法は、最後尾からＢＩＮＤ属性のないＵＤＳを探し、そこから最後尾までのＵＤＳが、その位置よりも前のＢＩＮＤ属性のないＵＤＳの前に挿入できるか、すなわち総位置あわせ処理時間が短縮されるかを走査する。もしできれば挿入し、できなければ、さらにその手前のＢＩＮＤ属性のないＵＤＳにさかのぼって、走査を繰り返す。図５にその一例を示す。
【００４１】
図５において、（ａ）に示されるように、ＵＤＳ１〜Ｎの読み出し対象において、ＵＤＳ３およびＮがそれぞれテープの同一ラップの同一領域あるいは隣接する領域にあって、ＢＩＮＤ属性を持っているとする。（ｂ）に示されるように、ＵＤＳＮ−１にＢＩＮＤ属性を持つＵＤＳＮを結合させてあたかも１つのＵＤＳとして見なして、次式（２）を満たすＭを探索する。
t(M、M+1)＋t(N-2、N-1) ＞ t(M、N-1)＋t(N、M+1)    （２）
今、式（２）を満たすＭが１（Ｍ＝１）だったとする。次に、（ｃ）に示されるように、結合されたＵＤＳＮ−１とＵＤＳＮをＵＤＳ１と２の間に挿入して、１つ前のＢＩＮＤ属性なしのＵＤＳＮ−２について、次式（３）を満たすＭを探索する。
t(M、M+1)＋t(N-3、N-2) ＞ t(M、N-2)＋t(N-2、M+1)    （３）
【００４２】
上記（２）式を満たすＭが見つからなかった場合、さらに１つ前のＢＩＮＤ属性なしのＵＤＳＮ−２を結合させて、ＵＤＳＮ−２、Ｎ−１、Ｎをあたかも１つのＵＤＳとして見なして、（ｄ）に示すように、この結合されたＵＤＳが挿入可能な位置を同様に探索する。この方法によれば、位置合わせ処理時間の計算の基となるデータ数（ＵＤＳ数）をＢＩＮＤ属性を持つＵＤＳ数の分だけ減らすことができるので、位置合わせ処理時間を大幅に短縮することが可能となる。
【００４３】
図６は、読み出すＵＤＳ数と並べ替え（ＲＡＯ）処理時間との関係を示す図である。図６において、グラフＡは、特許文献１の最近接選択法と最後尾入れ替え法を用いた場合の並べ替えに必要なＲＡＯ処理時間を示したものである。一方、グラフＢは、本発明のＢＩＮＤ属性を組み込んだ、ＢＩＮＤ属性付き最近接選択法と、ＢＩＮＤ属性付き最後尾入れ替え法とを用いた場合のＲＡＯ処理時間を示したものである。グラフＡとＢの比較から明らかなように、本発明の方法を用いた場合、取り扱うＵＤＳ数が増えても、ＲＡＯ処理時間は増加していないことが分かる。これは、ＲＡＯ処理時間は、ＢＩＮＤ属性を持たないＵＤＳ数に大きく依存するためであると考えられる。
【００４４】
図７は、ファイル数と読み出し時間との関係を示す図である。図７において、グラフＣは、各々のＵＤＳの最初のレコードの番号順に、ＵＤＳ毎に通し番号を与え、そのＵＤＳ番号順に読み出した場合にかかった総時間のグラフである。一方、グラフＤは、本発明のＢＩＮＤ属性を組み込んだ、ＢＩＮＤ属性付き最近接選択法と、ＢＩＮＤ属性付き最後尾入れ替え法とを用いた場合のデータの読み出しにかかった総時間のグラフである。グラフＣとＤの比較から明らかなように、本発明の方法を用いた場合、ＵＤＳの読み出しにかかった時間をＵＤＳ数が8000程度までは改善することができる。8000以上で改善が見られないのは、ＵＤＳ数が多いため、先頭から最後まですべてのデータを順次読み出しを行う場合（すなわち、レコード通し番号の順番）と同じ時間が必要となってしまうからである。
【００４５】
本発明の実施形態について、図を参照しながら説明をした。しかし、本発明はこれらの実施形態に限られるものではなく、本発明はその趣旨を逸脱しない範囲で当業者の知識に基づき種々なる改良、修正、変形を加えた態様で実施できるものである。
【符号の説明】
【００４６】
１０  テープドライブ
１１  ホストＩ／Ｆ
１２  バッファ
１３  チャネル
１４  ヘッド
１５  モータ
１６  コントローラ
１７  ヘッド位置制御システム
１８  モータドライバ
１９  カートリッジメモリＩ／Ｆ
２０  テープカートリッジ
２１、２２  リール
２３  テープ
２４  カートリッジメモリ（ＣＭ）
３０  サーバー（ホスト）
３２、３４  ＰＣ
３６  ネットワーク
４０  サーボバンド
４２  ラップ
１００  ファイルシステム
【図１】
2014179140.tif 000003
【図２】
2014179140.tif 000004
【図３】
2014179140.tif 000005
【図４】
2014179140.tif 000006
【図５】
2014179140.tif 000007
【図６】
2014179140.tif 000008
【図７】
2014179140.tif 000009