(57)【特許請求の範囲】
【請求項１】
ブロック単位で記憶データの消去が行われるフラッシュメモリに対するアクセスを制御するメモリコントローラであって、
前記フラッシュメモリにアクセスするための第１のインターフェースと第２のインターフェースとを有するインターフェース手段と、
前記第１のインターフェースに接続されたフラッシュメモリ内の物理ブロックと前記第２のインターフェースに接続されたフラッシュメモリ内の物理ブロックとを仮想的に結合した仮想ブロックを形成し、該仮想ブロックの前記第１のインターフェース側の物理ブロック内のセクタ領域と前記第２のインターフェース側の物理ブロック内のセクタ領域とにデータを書き込む書き込み手段と、
前記仮想ブロック内の検索範囲を特定する情報として、検索範囲の先頭セクタ領域の番号を示す先頭位置情報と検索範囲の末尾セクタ領域の番号を示す末尾位置情報とを保持する検索範囲保持手段と、
前記先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算した番号Ｎａに対応する第１のセクタ領域と前記末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、前記末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに前記末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更するセクタ領域検索手段とを備え、
前記番号Ｎｓ、番号Ｎｅ、番号Ｎａ及び番号Ｎｂが、番号Ｎｅと番号Ｎｓの差が３以上の範囲で、
Ｎｓ＜Ｎａ＜Ｎｂ＜Ｎｅ
Ｎａ−Ｎｓ≦（Ｎｅ−Ｎｓ）／２
Ｎｂ−Ｎａ≦（Ｎｅ−Ｎｓ）／２
Ｎｅ−Ｎｂ≦（Ｎｅ−Ｎｓ）／２
を満たし
かつ、前記第１のセクタ領域と前記第２のセクタ領域の一方が前記第１のインターフェース側の物理ブロック内のセクタ領域に、他方が前記第２のインターフェース側の物理ブロック内のセクタ領域になるように前記変数Ａ及び変数Ｂの値が設定される
ことを特徴とするメモリコントローラ。
【請求項２】
前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記先頭位置情報が示す番号Ｎｓから前記仮想ブロック内のデータが書き込まれているセクタ領域の末尾を判別する第１のセクタ領域判別手段を有することを特徴とする請求項１に記載のメモリコントローラ。
【請求項３】
前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記末尾位置情報が示す番号Ｎｅから前記仮想ブロック内のデータが書き込まれていないセクタ領域の先頭を判別する第２のセクタ領域判別手段を有することを特徴とする請求項１に記載のメモリコントローラ。
【請求項４】
前記変数Ａ及び変数Ｂの値が、（Ｎｅ−Ｎｓ）／３又は（Ｎｅ−Ｎｓ）／４であることを特徴とする請求項１乃至３のいずれか１項に記載のメモリコントローラ。
【請求項５】
請求項１乃至４のいずれか１項に記載のメモリコントローラと、このメモリコントローラによりアクセスが制御されるフラッシュメモリとを備えることを特徴とするフラッシュメモリシステム。
【請求項６】
ブロック単位で記憶データの消去が行われるフラッシュメモリに対するアクセスを制御するフラッシュメモリの制御方法であって、
前記フラッシュメモリにアクセスするための第１のインターフェースに接続されたフラッシュメモリ内の物理ブロックと前記フラッシュメモリにアクセスするための第２のインターフェースに接続されたフラッシュメモリ内の物理ブロックとを仮想的に結合した仮想ブロックを形成し、該仮想ブロックの前記第１のインターフェース側の物理ブロック内のセクタ領域と前記第２のインターフェース側の物理ブロック内のセクタ領域とにデータを書き込むステップと、
前記仮想ブロック内の検索範囲を特定する情報として、検索範囲の先頭セクタ領域の番号を示す先頭位置情報と検索範囲の末尾セクタ領域の番号を示す末尾位置情報とを保持するステップと、
前記先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算した番号Ｎａに対応する第１のセクタ領域と前記末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、前記末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに前記末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更するステップとを有し、
前記番号Ｎｓ、番号Ｎｅ、番号Ｎａ及び番号Ｎｂが、番号Ｎｅと番号Ｎｓの差が３以上の範囲で、
Ｎｓ＜Ｎａ＜Ｎｂ＜Ｎｅ
Ｎａ−Ｎｓ≦（Ｎｅ−Ｎｓ）／２
Ｎｂ−Ｎａ≦（Ｎｅ−Ｎｓ）／２
Ｎｅ−Ｎｂ≦（Ｎｅ−Ｎｓ）／２
を満たし
かつ、前記第１のセクタ領域と前記第２のセクタ領域の一方が前記第１のインターフェース側の物理ブロック内のセクタ領域に、他方が前記第２のインターフェース側の物理ブロック内のセクタ領域になるように前記変数Ａ及び変数Ｂの値が設定される
ことを特徴とするフラッシュメモリの制御方法。
【請求項７】
前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記先頭位置情報が示す番号Ｎｓから前記仮想ブロック内のデータが書き込まれているセクタ領域の末尾を判別するステップを有することを特徴とする請求項６に記載のフラッシュメモリの制御方法。
【請求項８】
前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記末尾位置情報が示す番号Ｎｅから前記仮想ブロック内のデータが書き込まれていないセクタ領域の先頭を判別するステップを有することを特徴とする請求項６に記載のフラッシュメモリの制御方法。
【請求項９】
前記変数Ａ及び変数Ｂの値が、（Ｎｅ−Ｎｓ）／３又は（Ｎｅ−Ｎｓ）／４であることを特徴とする請求項６乃至８のいずれか１項に記載のフラッシュメモリの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フラッシュメモリに対するアクセスを制御するメモリコントローラ、フラッシュメモリシステム及びフラッシュメモリの制御方法に係り、特に、フラッシュメモリに対する書き込み処理において、書き込み先の物理ブロックのデータが書き込まれていないセクタ領域の先頭を検索する機能を有するメモリコントローラ、フラッシュメモリシステム及びフラッシュメモリの制御方法に関するものである。
【背景技術】
【０００２】
メモリカードやシリコンディスク等の記憶媒体である半導体メモリとして、ＮＡＮＤ型フラッシュメモリが多く用いられている。このフラッシュメモリは、複数のメモリセルを有し、各メモリセルが消去状態のとき論理値「１」とされ、書き込み状態のとき論理値「０」とされる。
【０００３】
ところで、これらのメモリセルを消去状態から書き込み状態に変化させる場合には、メモリセル単位で行うことができるが、メモリセルを書き込み状態から消去状態に変化させる場合には、メモリセル単位で行うことができず、所定数のメモリセルからなるブロック単位で一括消去することが行われる（ブロック消去）。
【０００４】
また、所定数のメモリセルからなるブロック（物理ブロック）は、書き込み及び読み出しのアクセス処理単位である複数のページで構成されている。すなわち、小ブロックでは３２ページ、大ブロックでは６４ページである。また、小ブロックでは、１個のページが１セクタ（５１２バイト）のユーザ領域と１６バイトの冗長領域とによって構成されている。
【０００５】
また、大ブロックでは、１個のページが、４セクタ（２０４８バイト）のユーザ領域（以下、５１２バイト単位のユーザ領域をセクタ領域という）と、６４バイトの冗長領域とで構成され、ユーザ領域と冗長領域とがそれぞれ４分割して使用される（以下、大ブロックでは、冗長領域を４分割したものを部分冗長領域という）。よって、小ブロックでは１個のページが１個のセクタ領域に対応し、大ブロックでは１個のページが４個のセクタ領域に対応している。
【０００６】
このようなフラッシュメモリに対する書き込み処理を制御するメモリコントローラは、ホストシステムから与えられるコマンド等に従ってって、ホストシステムから与えられるデータをフラッシュメモリに書き込む。ここで、フラッシュメモリにデータを書き込む場合は、物理ブロック内の先頭のページ（セクタ領域）から順番にデータが書き込まれる。従って、物理ブロック内の途中のページ（セクタ領域）までデータが書き込まれている物理ブロックにデータを書き込む場合には、データが書き込まれていないページ（セクタ領域）の先頭を検索し、検出されたページ（セクタ領域）からデータの書き込みが開始される。
【０００７】
また、一連データの書き込み処理を開始するときに、その一連データの書き込み先の物理ブロックに既にデータが存在する場合には、その物理ブロックのデータが書き込まれていないセクタ領域の先頭を検索する検索処理が行われ、検出されたセクタ領域が一連データの書き込みを開始するセクタ領域より前であれば、その物理ブロックに対して一連データの書き込み処理を開始する。一方、検出されたセクタ領域が一連データの書き込みを開始するセクタ領域より後であれば、別のブロック消去されている物理ブロックに一連データが書き込まれる。つまり、データが書き込まれていないセクタ領域の先頭を検索する検索処理は、既にデータが存在する物理ブロックに対して、一連データを書き込むことができるかどうかを判別する。
【０００８】
このようなデータが書き込まれていないセクタ領域の先頭を検索する方法として、例えば特許文献１に示されているようなスタートページ情報を用いた検索方法と一般的に用いられている二分木検索とがある。この二分木検索について、以下、図９を参照して説明する。なお、図９（ａ）は、第１のインターフェース（ｃｈＡ）を介してアクセスされる物理ブロックと、第２のインターフェース（ｃｈＢ）を介してアクセスされる物理ブロックとを示している。また、第１のインターフェース（ｃｈＡ）を介してアクセスされる物理ブロックと、第２のインターフェース（ｃｈＢ）を介してアクセスされる物理ブロックは、仮想的に結合された仮想ブロックを形成する。以下、第１のインターフェース（ｃｈＡ）を介してアクセスされる物理ブロックを“ｃｈＡの物理ブロック”と言い、第２のインターフェース（ｃｈＢ）を介してアクセスされる物理ブロックを“ｃｈＢの物理ブロック”と言う。
【０００９】
この仮想ブロックは、図９（ｂ）に示したようにｃｈＡの物理ブロック内のセクタ領域とｃｈＢの物理ブロック内のセクタ領域が交互配列された５１２個のセクタ領域を含んでいる。ここで、ＳＮａ＃０〜ＳＮａ＃２５５はｃｈＡの物理ブロック内のセクタ領域に付けられた通番であり（以下、物理セクタ番号と言う）、ＳＮｂ＃０〜ＳＮｂ＃２５５はｃｈＢの物理ブロック内のセクタ領域に付けられた通番である（以下、物理セクタ番号と言う）。
【００１０】
また、ＳＮ＃０〜ＳＮ＃５１１は仮想ブロックに含まれる５１２個のセクタ領域に付けられた通番である（以下、セクタ番号ＳＮという）。また、以下のデータが書き込まれていないセクタ領域の検索において、検索する範囲の先頭を示す先頭位置情報をスタートポインタＸとし、その末尾を示す末尾位置情報をエンドポインタＹとしている。
【００１１】
図９（ｃ）は、ＳＮ＃３００のセクタ領域（物理セクタ番号ＳＮａ＃１５０）までデータが書き込まれている場合の検索過程を示している。この検索では、まずスタートポインタＸに最初のセクタ領域のセクタ番号ＳＮ＃０に対応する０を設定し、エンドポインタＹに最後のセクタ領域のセクタ番号ＳＮ＃５１１に１を加えた５１２を設定する。続いて、スタートポインタＸに設定されている値（０）とエンドポインタＹに設定されている値（５１２）の中間点のセクタ番号ＳＮがＳＮ＃２５６のセクタ領域に対応する部分冗長領域に書き込まれている付加情報（セクタ領域にデータが書き込まれているか否かを判断することができる付加情報）を参照し、セクタ番号ＳＮがＳＮ＃２５６のセクタ領域にデータが書き込まれているか否かを判断する（検索回数：１）。
【００１２】
ここで、データが書き込まれていると判断した場合には、スタートポインタＸの設定値を参照したセクタ領域のセクタ番号ＳＮの値に変更する。一方、データが書き込まれていないと判断した場合には、エンドポインタＹの設定値を参照したセクタ領域のセクタ番号ＳＮの値に変更する。この例では、セクタ番号ＳＮがＳＮ＃２５６のユーザ領域（物理セクタ番号ＳＮａ＃１２８）にデータが書き込まれているので、スタートポインタＸの設定値を２５６に変更する。
【００１３】
次に、スタートポインタＸに設定した値（２５６）とエンドポインタＹに設定した値（５１２）の中間点のセクタ番号ＳＮがＳＮ＃３８４のセクタ領域に対応する部分冗長領域に書き込まれている付加情報（セクタ領域にデータが書き込まれているか否かを判断することができる付加情報）を参照し、セクタ番号ＳＮがＳＮ＃３８４のセクタ領域にデータが書き込まれているか否かを判断する（検索回数：２）。この例では、セクタ番号ＳＮがＳＮ＃３８４のユーザ領域（物理セクタ番号ＳＮａ＃１９２）にデータが書き込まれていないので、エンドポインタＹの設定値を３８４に変更する。
【００１４】
次に、スタートポインタＸに設定した値（２５６）とエンドポインタＹに設定した値（３８４）の中間点のセクタ番号ＳＮがＳＮ＃３２０のセクタ領域に対応する部分冗長領域に書き込まれている付加情報（セクタ領域にデータが書き込まれているか否かを判断することができる付加情報）を参照し、セクタ番号ＳＮがＳＮ＃３２０のセクタ領域にデータが書き込まれているか否かを判断する（検索回数：３）。この例では、セクタ番号ＳＮがＳＮ＃３２０のユーザ領域（物理セクタ番号ＳＮａ＃１６０）にデータが書き込まれていないので、エンドポインタＹの設定値を３２０に変更する。
【００１５】
以下同様に、スタートポインタＸに設定した値とエンドポインタＹに設定した値の中間点である（Ｘ＋Ｙ）／２に対応する部分冗長領域に書き込まれている付加情報（セクタ領域にデータが書き込まれているか否かを判断することができる付加情報）の参照と、スタートポインタＸ又はエンドポインタＹの更新を順次行っていき、スタートポインタＸに設定した値とエンドポインタＹに設定した値の差が１になったときにエンドポインタＹに設定した値を、データが書き込まれていないセクタ領域の先頭のセクタ番号ＳＮであると判断する。
【特許文献１】特開２００２−１９６９７７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
ところが、上述した二分木検索を用いた検索処理では、検索回数がセクタ領域の数によって決まってしまい、図９のように、例えばセクタ番号ＳＮがＳＮ＃０〜ＳＮ＃５１１で示されるセクタ領域が５１２個（２の９乗個）の場合、９回の検索が必要となる。言い換えれば、セクタ領域の数が２のｎ乗個の場合には常にｎ回の検索を行わなければならないという問題があった。
【００１７】
本発明は、このような状況に鑑みてなされたものであり、上記問題点を解決することができるメモリコントローラ、フラッシュメモリシステム及びフラッシュメモリの制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明のメモリコントローラは、ブロック単位で記憶データの消去が行われるフラッシュメモリに対するアクセスを制御するメモリコントローラであって、前記フラッシュメモリにアクセスするための第１のインターフェースと第２のインターフェースとを有するインターフェース手段と、前記第１のインターフェースに接続されたフラッシュメモリ内の物理ブロックと前記第２のインターフェースに接続されたフラッシュメモリ内の物理ブロックとを仮想的に結合した仮想ブロックを形成し、該仮想ブロックの前記第１のインターフェース側の物理ブロック内のセクタ領域と前記第２のインターフェース側の物理ブロック内のセクタ領域とにデータを書き込む書き込み手段と、前記仮想ブロック内の検索範囲を特定する情報として、検索範囲の先頭セクタ領域の番号を示す先頭位置情報と検索範囲の末尾セクタ領域の番号を示す末尾位置情報とを保持する検索範囲保持手段と、前記先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算した番号Ｎａに対応する第１のセクタ領域と前記末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、前記末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに前記末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更するセクタ領域検索手段とを備え、前記番号Ｎｓ、番号Ｎｅ、番号Ｎａ及び番号Ｎｂが、番号Ｎｅと番号Ｎｓの差が３以上の範囲で、
Ｎｓ＜Ｎａ＜Ｎｂ＜Ｎｅ
Ｎａ−Ｎｓ≦（Ｎｅ−Ｎｓ）／２
Ｎｂ−Ｎａ≦（Ｎｅ−Ｎｓ）／２
Ｎｅ−Ｎｂ≦（Ｎｅ−Ｎｓ）／２
を満たし
かつ、前記第１のセクタ領域と前記第２のセクタ領域の一方が前記第１のインターフェース側の物理ブロック内のセクタ領域に、他方が前記第２のインターフェース側の物理ブロック内のセクタ領域になるように前記変数Ａ及び変数Ｂの値が設定されることを特徴とする。
また、前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記先頭位置情報が示す番号Ｎｓから前記仮想ブロック内のデータが書き込まれているセクタ領域の末尾を判別する第１のセクタ領域判別手段を有するようにすることができる。
また、前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記末尾位置情報が示す番号Ｎｅから前記仮想ブロック内のデータが書き込まれていないセクタ領域の先頭を判別する第２セクタ領域判別手段を有するようにすることができる。
また、前記変数Ａ及び変数Ｂの値は、（Ｎｅ−Ｎｓ）／３又は（Ｎｅ−Ｎｓ）／４とすることができる。
本発明のフラッシュメモリシステムは、上記のメモリコントローラと、このメモリコントローラによりアクセスが制御されるフラッシュメモリとを備えることを特徴とする。
本発明のフラッシュメモリの制御方法は、ブロック単位で記憶データの消去が行われるフラッシュメモリに対するアクセスを制御するフラッシュメモリの制御方法であって、前記フラッシュメモリにアクセスするための第１のインターフェースに接続されたフラッシュメモリ内の物理ブロックと前記フラッシュメモリにアクセスするための第２のインターフェースに接続されたフラッシュメモリ内の物理ブロックとを仮想的に結合した仮想ブロックを形成し、該仮想ブロックの前記第１のインターフェース側の物理ブロック内のセクタ領域と前記第２のインターフェース側の物理ブロック内のセクタ領域とにデータを書き込むステップと、前記仮想ブロック内の検索範囲を特定する情報として、検索範囲の先頭セクタ領域の番号を示す先頭位置情報と検索範囲の末尾セクタ領域の番号を示す末尾位置情報とを保持するステップと、前記先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算をした番号Ｎａに対応する第１のセクタ領域と前記末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算をした番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、前記末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに前記末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、前記先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更するステップとを有し、前記番号Ｎｓ、番号Ｎｅ、番号Ｎａ及び番号Ｎｂが、番号Ｎｅと番号Ｎｓの差が３以上の範囲で、
Ｎｓ＜Ｎａ＜Ｎｂ＜Ｎｅ
Ｎａ−Ｎｓ≦（Ｎｅ−Ｎｓ）／２
Ｎｂ−Ｎａ≦（Ｎｅ−Ｎｓ）／２
Ｎｅ−Ｎｂ≦（Ｎｅ−Ｎｓ）／２
を満たし
かつ、前記第１のセクタ領域と前記第２のセクタ領域の一方が前記第１のインターフェース側の物理ブロック内のセクタ領域に、他方が前記第２のインターフェース側の物理ブロック内のセクタ領域になるように前記変数Ａ及び変数Ｂの値が設定されることを特徴とする。
また、前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記先頭位置情報が示す番号Ｎｓから前記仮想ブロック内のデータが書き込まれているセクタ領域の末尾を判別するステップを有するようにすることができる。
また、前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅとの差が１となったときに、前記末尾位置情報が示す番号Ｎｅから前記仮想ブロック内のデータが書き込まれていないセクタ領域の先頭を判別するステップを有するようにすることができる。
また、前記変数Ａ及び変数Ｂの値は、（Ｎｅ−Ｎｓ）／３又は（Ｎｅ−Ｎｓ）／４とすることができる。
以上のように、本発明のメモリコントローラ、フラッシュメモリシステム及びフラッシュメモリの制御方法では、先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算した番号Ｎａに対応する第１のセクタ領域と末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを並行して判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更する。
ここで、前記番号Ｎｓ、番号Ｎｅ、番号Ｎａ及び番号Ｎｂが、番号Ｎｅと番号Ｎｓの差が３以上の範囲で、
Ｎｓ＜Ｎａ＜Ｎｂ＜Ｎｅ
Ｎａ−Ｎｓ≦（Ｎｅ−Ｎｓ）／２
Ｎｂ−Ｎａ≦（Ｎｅ−Ｎｓ）／２
Ｎｅ−Ｎｂ≦（Ｎｅ−Ｎｓ）／２
を満たすように変数Ａ、変数Ｂの値を設定すれば、前記先頭位置情報が示す番号Ｎｓと前記末尾位置情報が示す番号Ｎｅを更新した後の検索範囲は更新前の１／２以下になる。
また、前記第１のインターフェース側の物理ブロック内のセクタ領域に偶数のセクタ番号を割り当て、前記第２のインターフェース側の物理ブロック内のセクタ領域に奇数のセクタ番号を割り当て、番号Ｎａと番号Ｎｂの一方が偶数で他方が奇数になるように変数Ａ、変数Ｂの値を設定すれば、前記第１のセクタ領域と前記第２のセクタ領域の一方が前記第１のインターフェース側の物理ブロック内のセクタ領域に、他方が前記第２のインターフェース側の物理ブロック内のセクタ領域になる。
そして、先頭位置情報が示す番号Ｎｓと末尾位置情報が示す番号Ｎｅとの差が１となったときに、先頭位置情報が示す番号Ｎｓから仮想ブロック内のデータが書き込まれているセクタ領域の末尾を判別する。
また、先頭位置情報が示す番号Ｎｓと末尾位置情報が示す番号Ｎｅとの差が１となったときに、末尾位置情報が示す番号Ｎｅから仮想ブロック内のデータが書き込まれていないセクタ領域の先頭を判別する。
【発明の効果】
【００１９】
本発明のメモリコントローラ、フラッシュメモリシステム及びフラッシュメモリの制御方法によれば、先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算した番号Ｎａに対応する第１のセクタ領域と末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを並行して判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更するようにしたので、物理ブロック内でのデータが書き込まれていないセクタ領域の先頭を検索する平均的な検索速度を向上させることができる。例えば、仮想的な１ブロック内のセクタ領域の数が２のｎ乗個の場合、通常の二分木検索であれば、常にｎ回の検索を行わなければならないが、本発明のメモリコントローラ、フラッシュメモリシステム及びフラッシュメモリの制御方法によれば、ｎ回以下の検索回数で、検索対象のセクタ領域を検出することができる。
【発明を実施するための最良の形態】
【００２０】
本実施形態では、先頭位置情報が示す番号Ｎｓに所定の変数Ａを加算した番号Ｎａに対応する第１のセクタ領域と末尾位置情報が示す番号Ｎｅから所定の変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域にデータが書き込まれているか否かを並行して判断し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていないと判断した場合は、末尾位置情報が示す番号Ｎｅを番号Ｎａに変更し、第１のセクタ領域だけにデータが書き込まれていると判断した場合は、先頭位置情報が示す番号Ｎｓを番号Ｎａに変更するとともに末尾位置情報が示す番号Ｎｅを番号Ｎｂに変更し、第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれていると判断した場合は、先頭位置情報が示す番号Ｎｓを番号Ｎｂに変更する処理を繰り返すことで、物理ブロック内でのデータが書き込まれていないセクタ領域の先頭を検索するようにした。
【００２１】
また、変数Ａ、変数Ｂ、及び番号Ｎｂと番号Ｎａとの差（Ｎｂ−Ｎａ）が番号Ｎｅと番号Ｎｓとの差の１／２（（Ｎｅ−Ｎｓ）／２）以下であり、変数Ａ、変数Ｂ、及び番号Ｎｂと番号Ｎａとの差（Ｎｂ−Ｎａ）の少なくとも１つが番号Ｎｅと番号Ｎｓとの差の１／２（（Ｎｅ−Ｎｓ）／２）より小さく、かつ番号Ｎａと番号Ｎｂの一方が偶数で他方が奇数になるように変数Ａ、変数Ｂの値が設定される。
【００２２】
これにより、例えば、仮想的な１ブロック内のセクタ領域の数が２のｎ乗個の場合、通常の二分木検索であれば、常にｎ回の検索を行わなければならないが、本実施形態では、ｎ回以下の検索回数で物理ブロックのデータが書き込まれていないセクタ領域の先頭を検出することができる。また、第１のセクタ領域と第２のセクタ領域の一方は前記第１のインターフェース側の物理ブロック内のセクタ領域になり、他方は前記第２のインターフェース側の物理ブロック内のセクタ領域になるので、第１のセクタ領域と第２のセクタ領域にデータが書き込まれているか否かを並行して判断することができる。
【実施例】
【００２３】
以下、本発明の詳細を図面に基づいて説明する。図１は、本発明のフラッシュメモリシステムの一実施例の概略を説明するためのブロック図である。図１に示すように、フラッシュメモリシステム１は、フラッシュメモリ２と、それを制御するメモリコントローラ３で構成されている。また、フラッシュメモリシステム１は、外部バス１３を介してホストシステム４と接続される。
【００２４】
ホストシステム４は、ホストシステム４の全体の動作を制御するためのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、フラッシュメモリシステム１との情報の授受を担うコンパニオンチップ等とから構成される。ホストシステム４は、例えば文字、音声、あるいは画像情報等の種々の情報を処理するパーソナルコンピュータやデジタルスチルカメラをはじめとする各種情報処理装置であってもよい。
【００２５】
フラッシュメモリ２は、不揮発性メモリであり、レジスタとメモリセルアレイとの間でデータの複写を行って、データの書き込み又は読み出しを行う。
【００２６】
メモリセルアレイは、複数のメモリセル群と、ワード線とを備える。各メモリセル群は、複数のメモリセルが直列に接続されたものである。ワード線は、メモリセル群の特定のメモリセルを選択するためのものである。このワード線を介して選択されたメモリセルとレジスタとの間で、データの複写、すなわち、レジスタから選択されたメモリセルへの複写又は選択されたメモリセルからレジスタへのデータの複写が行われる。つまり、メモリコントローラ３から与えられたデータは、レジスタを介してメモリセルアレイに書き込まれ、メモリセルアレイに記憶されているデータはレジスタを介してメモリコントローラ３に供給される。
【００２７】
メモリセルアレイを構成するメモリセルは、上下にゲートを備えたＭＯＳトランジスタによって構成される。ここで、上側のゲートはコントロールゲート、下側のゲートはフローティングゲートとそれぞれ呼ばれている。フローティングゲートに電荷（電子）を注入若しくはフローティングゲートから電荷（電子）を排出することによって、データの書き込み若しくはデータの消去が行われる。
【００２８】
このフローティングゲートは、周囲が絶縁体で囲まれているので、注入された電子は長期間にわたって保持される。なお、フローティングゲートに電子を注入するときは、コントロールゲートが高電位側となる高電圧がコントロールゲートとフローティングゲートとの間に印加される。また、フローティングゲートから電子を排出するときは、コントロールゲートが低電位側となる高電圧がコントロールゲートとフローティングゲートとの間に印加される。
【００２９】
ここで、フローティングゲートに電子が注入されている状態が書き込み状態であり、論理値「０」に対応する。また、フローティングゲートから電子が排出されている状態が消去状態であり、論理値「１」に対応する。
【００３０】
このようなフラッシュメモリ２のアドレス空間は、“ページ”及び“ブロック（物理ブロック）”で構成されている。ページは、フラッシュメモリ２にて行われるデータ読み出し動作及びデータ書き込み動作における処理単位である。物理ブロックは、フラッシュメモリ２にて行われるデータ消去動作における処理単位であり、複数個のページで構成されている。
【００３１】
ここで、図２は、フラッシュメモリ２のアドレス空間の構造を概略的に示すものであり、１個のページが、４セクタ（２０４８バイト）のユーザ領域２５と、６４バイトの冗長領域２６とで構成され、１個の物理ブロックは６４個のページで構成されている。ここでは、１バイトがビットｂ０〜ｂ７からなる８ビットである場合を示している。なお、ユーザ領域２５を４分割した５１２バイトの領域をセクタ領域といい、冗長領域２６内の各セクタ領域に割り当てられる領域を部分冗長領域と言う。また、このフラッシュメモリ２の物理ブロックは、２５６個のセクタ領域と各セクタ領域に割り当てられた２５６個の部分冗長領域とで構成されているとみなすことができる。
【００３２】
また、物理ブロックには、図３（ｃ）に示すように、それぞれに固有の物理ブロックアドレス（ＰＢＡ）が割り当てられている。さらに、記憶領域を複数のゾーンに分割して管理する場合には、複数個の物理ブロックで物理ゾーンを構成し、各物理ゾーンに固有の物理ゾーン番号（ＰＺＮ）を割り当てている。各物理ゾーンに含まれる物理ブロックの、各物理ゾーン内での通番を物理ゾーン内ブロック番号（ＰＺＩＢＮ）と呼んでいる。
【００３３】
一方、ホストシステム４側のアドレス空間は、図３（ａ）に示すようにセクタ（５１２バイト）単位で分割した領域に付けた通番であるＬＢＡ（Logical Block Address）で管理されている。ここで、複数個のセクタをまとめたものを論理ブロックと言い、複数個の論理ブロックをまとめたものを論理ゾーンと言う。また、図３（ｂ）に示すように論理ブロックに付けられた通番を論理ブロック番号（ＬＢＮ）と言い、論理ゾーンに付けられた通番を論理ゾーン番号（ＬＺＮ）と言う。また、各論理ゾーンに含まれる論理ブロックの、各論理ゾーン内での通番を論理ゾーン内ブロック番号（ＬＺＩＢＮ）と言う。
【００３４】
また、各論理ゾーンにはそれぞれ１個の物理ゾーンが割り当てられ、論理ゾーンに含まれる各論理ブロックに対応するデータは、その論理ゾーンに割り当てられた物理ゾーンに含まれる物理ブロックに書き込まれる。従って、１個の論理ブロックに含まれるセクタ数は、１個の物理ブロックに含まれるセクタ領域の個数に応じて設定される。但し、１個の論理ブロックを複数個の物理ブロックに割り当てる場合には、その複数個の物理ブロックを１個の物理ブロックとみなして１個の論理ブロックに含まれるセクタ数を設定する。
【００３５】
図３に示した例では、１個の物理ブロックが２５６個のセクタ領域で構成されたフラッシュメモリを想定しているため、２５６セクタが１個の論理ブロックに対応している。従って、ＬＢＮ＃０〜＃４９９の５００個の論理ブロックで構成されたＬＺＮ＃０の論理ゾーンは、ＬＢＡ＃０〜＃１２７９９９の１２８０００セクタの領域に対応している。
【００３６】
以下同様に、ＬＺＮ＃１の論理ゾーンは、ＬＢＡ＃１２８０００〜＃２５５９９９の１２８０００セクタの領域に対応し、ＬＺＮ＃２の論理ゾーンは、ＬＢＡ＃２５６０００〜＃３８３９９９の１２８０００セクタの領域に対応し、ＬＺＮ＃３の論理ゾーンは、ＬＢＡ＃３８４０００〜＃５１１９９９の１２８０００セクタの領域に対応している。
【００３７】
また、ＬＢＮ＃０〜＃４９９の５００個の論理ブロックで構成されたＬＺＮ＃０の論理ゾーンは、ＰＢＡ＃０〜＃５１１の５１２個の物理ブロックで構成されたＰＺＮ＃０の物理ゾーンに割り当てられている。以下同様に、ＬＺＮ＃１の論理ゾーンは、ＰＺＮ＃１の物理ゾーンに割り当てられ、ＬＺＮ＃２の論理ゾーンは、ＰＺＮ＃２の物理ゾーンに割り当てられ、ＬＺＮ＃３の論理ゾーンは、ＰＺＮ＃３の物理ゾーンに割り当てられている。  
【００３８】
ここで、物理ゾーンに含まれる物理ブロックの個数を、論理ゾーンに含まれる論理ブロックの個数より多くしているのは、同一の論理ブロックに対応する新データと旧データが別々の物理ブロックに並存する場合や、データを正常に書き込むことができない不良ブロックが発生した場合等を考慮したものである。
【００３９】
また、各物理ブロックには、その物理ブロックに割り当てられた論理ブロックのデータがＬＢＡの順番で書き込まれるので、物理ブロックと論理ブロックとの対応関係を管理することにより、ホストシステム４から与えられるＬＢＡとフラッシュメモリ２内のアクセス領域の対応関係を管理することができる。
【００４０】
なお、物理ブロックと論理ブロックとの対応関係は、データの書き込みや消去が行われる毎に変化する。このため、個々の時点における両者の対応関係を管理するためアドレス変換テーブルが作成され、対応関係が変化する毎にアドレス変換テーブルが更新される。また、論理ゾーンと物理ゾーンとの対応関係は予め設定されており、アドレス変換テーブルは論理ゾーン毎に作成することができる。
【００４１】
このアドレス変換テーブルは、物理ブロックの先頭ページの冗長領域２６に書き込まれる論理ブロックを示す情報（以下、論理アドレス情報という）に基づいて作成される。冗長領域２６に書き込まれる論理アドレス情報としては、ＬＢＮ等の論理ブロックを特定する情報が用いられる。なお、論理ゾーンと物理ゾーンとの対応関係は予め設定されている場合は、ＬＺＩＢＮに基づいてアドレス変換テーブルを作成することができるので、ＬＢＮよりデータ量の少ないＬＺＩＢＮを用いることが好ましい。
【００４２】
また、物理ブロックの先頭ページの冗長領域２６には、その物理ブロックが不良ブロックであるか否かを示すブロックステータス（フラグ）が書き込まれる。各セクタ領域に対応する部分冗長領域には、それぞれ対応するセクタ領域に書き込まれたユーザデータのエラーコレクションコード（ＥＣＣ）と、付加情報（セクタ領域にデータが書き込まれているか否かを判断することができる付加情報）とが書き込まれる。
【００４３】
次に、フラッシュメモリ２に対してアクセス処理を行うメモリコントローラ３について説明する。メモリコントローラ３は、フラッシュメモリ２にデータ、アドレス情報、内部コマンド等を供給することにより読み出し処理、書き込み処理、ブロック消去処理等の各処理を行う。
【００４４】
ここで、内部コマンドとは、メモリコントローラ３がフラッシュメモリ２に処理の実行を指示するためのコマンドであり、フラッシュメモリ２はメモリコントローラ３から与えられる内部コマンドに従ってって動作する。一方、ホストシステム４からメモリコントローラ３に与えられるコマンドを外部コマンドと言う。
【００４５】
メモリコントローラ３は、図１に示すように、マイクロプロセッサ６と、ホストインターフェースブロック７と、ワークエリア８と、バッファ９と、フラッシュメモリインターフェースブロック１０と、ＥＣＣ（エラー・コレクション・コード）ブロック１１と、ＲＯＭ（Read Only Memory）１２とを備えている。これら機能ブロックによって構成されるメモリコントローラ３は、１つの半導体チップ上に集積される。
【００４６】
マイクロプロセッサ６は、ＲＯＭ１２に記憶されているプログラムに従ってって、メモリコントローラ３の全体の動作を制御する。
【００４７】
また、マイクロプロセッサ６は、ＲＯＭ１２に記憶されているプログラムに基づいてフラッシュメモリインターフェースブロック１０等の動作を制御することにより、インターフェース手段と、書き込み手段と、検索範囲保持手段と、セクタ領域検索手段と、第１のセクタ領域判別手段と、第２のセクタ領域判別手段とを実現している。
【００４８】
また、マイクロプロセッサ６は、各種処理等を定義したコマンドセット（以下、シーケンスコマンドという）をＲＯＭ１２から読み出し、このシーケンスコマンドに従ってってフラッシュメモリインターフェースブロック１０に処理を実行させる。
【００４９】
ＲＯＭ１２は、不揮発性の記憶素子であり、上記のシーケンスコマンド等を記憶している。ワークエリア８は、フラッシュメモリ２の制御に必要なデータが一時的に格納される作業領域であり、複数のＳＲＡＭ（Static Random Access Memory）セルによって構成される。上述のアドレス変換テーブルは、このワークエリア８上に作成される。
【００５０】
バッファ９は、フラッシュメモリ２から読み出されたデータ及びフラッシュメモリ２に書き込むべきデータを一時的に蓄積する。すなわち、フラッシュメモリ２から読み出されたデータは、ホストシステム４が受け取り可能な状態となるまでバッファ９に保持され、フラッシュメモリ２に書き込むべきデータは、フラッシュメモリ２が書き込み可能な状態となるまでバッファ９に保持される。
【００５１】
ＥＣＣブロック１１は、フラッシュメモリ２に書き込むデータに付加されるエラーコレクションコードを生成するとともに、読み出しデータに付加されたエラーコレクションコードに基づいて、読み出したデータに含まれる誤りを検出・訂正する。
【００５２】
ホストインターフェースブロック７は、ホストシステム４との間で、外部バス１３を介し、データ、アドレス情報、外部コマンド等の授受を行う。ホストシステム４よりフラッシュメモリシステム１に供給されるデータ等は、ホストインターフェースブロック７を入口としてフラッシュメモリシステム１の内部（例えば、バッファ９）に取り込まれる。また、フラッシュメモリシステム１からホストシステム４に供給されるデータ等は、ホストインターフェースブロック７を出口としてホストシステム４に供給される。
【００５３】
フラッシュメモリインターフェースブロック１０は、内部バス１４を介して、フラッシュメモリ２とデータ、アドレス情報、ステータス情報、内部コマンド等の授受を行う。
【００５４】
ホストインターフェースブロック７及びフラッシュメモリインターフェースブロック１０は、図４に示すような各種レジスタを備える。すなわち、ホストインターフェースブロック７は、コマンドレジスタＲ１、セクタ数レジスタＲ２及びＬＢＡレジスタＲ３等を備えている。また、フラッシュメモリインターフェースブロック１０は、物理ブロックアドレスレジスタＲ１１、セクタ番号レジスタＲ１２、カウンタＲ１３等を備えている。
【００５５】
コマンドレジスタＲ１、セクタ数レジスタＲ２及びＬＢＡレジスタＲ３には、ホストシステム４から与えられる情報が書き込まれる。コマンドレジスタＲ１には、書き込みコマンド、読み出しコマンド等の外部コマンドが書き込まれる。セクタ数レジスタＲ２にはアクセス対象領域のセクタ数が書き込まれる。ＬＢＡレジスタＲ３には、アクセス対象領域の先頭のＬＢＡが書き込まれる。
【００５６】
物理ブロックアドレスレジスタＲ１１、セクタ番号レジスタＲ１２、カウンタＲ１３には、セクタ数レジスタＲ２及びＬＢＡレジスタＲ３に書き込まれた情報に基づく、フラッシュメモリ２内のアクセス対象領域を指示する情報が書き込まれる。
【００５７】
例えば、ＬＢＡが連続する２５６セクタの領域を、フラッシュメモリ２（１ブロックが６４ページで、１ページが４セクタの場合）の１個の物理ブロックに割り当てた場合、図３で説明したＬＢＡの下位８ビットがセクタ番号ＳＮに対応し、この下位８ビットを除いた上位側のビットが論理ブロック番号（ＬＢＮ）に対応する。
【００５８】
つまり、ＬＢＡが連続する２５６セクタの領域を１個の論理ブロックとした場合、ＬＢＡの下位８ビットが論理ブロック内の各セクタに付けた通番であるセクタ番号ＳＮ（０〜２５５）を示し、このＬＢＡの下位８ビットを除いた上位側のビットが論理ブロック番号（ＬＢＮ）を示している。なお、ＬＢＡ、論理ブロック番号（ＬＢＮ）及びセクタ番号ＳＮのビット数については、フラッシュメモリ２の容量や仕様等に応じて決定される。
【００５９】
次に、物理ブロックアドレスレジスタＲ１１、セクタ番号レジスタＲ１２、カウンタＲ１３に設定される情報について説明する。セクタ番号レジスタＲ１２には、ＬＢＡレジスタＲ３に書き込まれたＬＢＡのセクタ番号ＳＮに対応する部分が書き込まれる。
【００６０】
ここで、各物理ブロックにはＬＢＡの順番でユーザデータが書き込まれるので、上記のセクタ番号ＳＮは、各物理ブロックに含まれるセクタ領域に付けられた通番に対応する。一方、物理ブロックアドレスレジスタＲ１１には、ＬＢＡレジスタＲ３に書き込まれたＬＢＡの論理ブロック番号（ＬＢＮ）を示す部分に基づいて特定された論理ブロックと対応する物理ブロックの物理ブロックアドレス（ＰＢＡ）又は空きブロックの物理ブロックアドレス（ＰＢＡ）が書き込まれる。
【００６１】
つまり、特定された論理ブロックに対応する物理ブロックからユーザデータを読み出す場合、又は、その物理ブロックに追加書き込みをする場合には、特定された論理ブロックと対応する物理ブロックの物理ブロックアドレス（ＰＢＡ）が物理ブロックアドレスレジスタＲ１１に書き込まれる。また、特定された論理ブロックに対応するユーザデータを空きブロックに書き込む場合には、その空きブロックの物理ブロックアドレス（ＰＢＡ）が物理ブロックアドレスレジスタＲ１１に書き込まれる。カウンタＲ１３には、セクタ数レジスタＲ２に設定されたセクタ数が書き込まれる。
【００６２】
なお、ＬＢＡレジスタＲ３及びセクタ数レジスタＲ２に設定された情報に基づいて特定されるアクセス対象領域が複数の論理ブロックに跨っている場合、アクセス対象領域の物理ブロックも複数の物理ブロックに跨っているので、物理ブロックアドレスレジスタＲ１１、セクタ番号レジスタＲ１２、カウンタＲ１３に対する情報の設定は論理ブロック毎に行い、カウンタＲ１３には各論理ブロックに書き込まれるユーザデータのセクタ数を設定する。
【００６３】
また、フラッシュメモリインターフェースブロック１０は、物理ブロックアドレスレジスタＲ１１、セクタ番号レジスタＲ１２、カウンタＲ１３に設定された値に基づいて、一連の書き込み処理（以下、シーケンス書き込み処理と言う。）や一連の読み出し処理（以下、シーケンス読み出し処理と言う。）を実行する。
【００６４】
シーケンス書き込み処理では、１セクタのデータがバッファ９からフラッシュメモリ２に供給される毎にセクタ番号レジスタＲ１２に設定されている値がインクリメント（１ずつ増加）され、カウンタＲ１３に設定されている値がデクリメント（１ずつ減少）される。カウンタＲ１３に設定されている値が０になったときにシーケンス書き込み処理が終了する。従って、セクタ番号レジスタＲ１２に最初に設定されたセクタ番号のセクタ領域からカウンタＲ１３に最初に設定されたセクタ数分の領域にデータが書き込まれる。
【００６５】
同様に、シーケンス読み出し処理では、１セクタのデータがフラッシュメモリ２からバッファ９に読み出される毎にセクタ番号レジスタＲ１２に設定されている値がインクリメント（１ずつ増加）され、カウンタＲ１３に設定されている値がデクリメント（１ずつ減少）される。カウンタＲ１３に設定されている値が０になったときにシーケンス読み出し処理が終了する。従って、セクタ番号レジスタＲ１２に最初に設定されたセクタ番号のセクタ領域からカウンタＲ１３に最初に設定されたセクタ数分の領域に記憶されているデータが読み出される。
【００６６】
例えば、セクタ番号レジスタＲ１２に「１０」を設定し、カウンタＲ１３に「８」を設定してシーケンス書き込み処理を開始した場合、ＳＮ＃１０〜＃１７のセクタ領域にユーザデータが書き込まれる。
【００６７】
次に、このようなデータが書き込まれていないセクタ領域の先頭を検索する検索処理を、図５から図８を用いて説明する。なお、以下に説明する検索処理は、図９（ａ）、（ｂ）で説明したように、第１のインターフェースを介してアクセスされるｃｈＡの物理ブロックと、第２のインターフェースを介してアクセスされるｃｈＢの物理ブロックを仮想的に結合した仮想ブロックで行うものとする。また、それぞれの物理ブロックは、１個の物理ブロックが２５６個のセクタ領域で構成されているとみなすことができる大ブロックの場合とする。
【００６８】
なお、ｃｈＡの物理ブロックとｃｈＢの物理ブロックには交互にデータが書き込まれるので、仮想ブロック内のセクタ領域に付けられたセクタ番号が偶数であれば、そのセクタ領域はｃｈＡの物理ブロックに含まれ、仮想ブロック内のセクタ領域に付けられたセクタ番号が奇数であれば、そのセクタ領域はｃｈＢの物理ブロックに含まれる。
【００６９】
また、仮想ブロック内の検索範囲を特定する情報として、先頭位置情報（検索範囲の先頭セクタ領域の番号を示す情報）が示す番号Ｎｓと末尾位置情報（検索範囲の末尾セクタ領域の番号を示す情報）が示す番号Ｎｅを用いる。第１のセクタ領域は、番号Ｎｓに変数Ａを加算した番号Ｎａに対応するセクタ領域であり、第２のセクタ領域は、番号Ｎｅから変数Ｂを減算した番号Ｎｂに対応する第２のセクタ領域である。
【００７０】
また、番号Ｎｅと番号Ｎｓの差が３以上の範囲（Ｎｅ−Ｎｓ≧３の範囲）では、変数Ａと変数Ｂは、以下の条件を満たす範囲内で適宜設定できる。第１の条件は、番号Ｎｓ、番号Ｎｅ、番号Ｎａ、及び番号Ｎｂが、下記条件式（１）〜（４）を満たすように変数Ａ、変数Ｂを設定しなければならない。
Ｎｓ＜Ｎａ＜Ｎｂ＜Ｎｅ                  （１）
Ｎａ−Ｎｓ≦（Ｎｅ−Ｎｓ）／２          （２）
Ｎｂ−Ｎａ≦（Ｎｅ−Ｎｓ）／２          （３）
Ｎｅ−Ｎｂ≦（Ｎｅ−Ｎｓ）／２          （４）
【００７１】
この条件を満たすようように変数Ａ、変数Ｂを設定した場合、データが書き込まれていないセクタ領域の先頭を検索する検索処理の処理時間を、通常の２分木検索より短くすることができる。つまり、通常の２分木検索の場合は、検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）は、常に前回の範囲の１／２になるが、上記条件式（１）〜（４）を満たすように変数Ａ、変数Ｂを設定すれば、検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）が、前回の範囲の１／２よりも狭くなるときがあるので、通常の２分木検索より検索時間を短縮することができる。
【００７２】
詳細に説明すれば、検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）は、第１のセクタ領域と第２のセクタ領域にデータが書き込まれているか否かに応じて、検索範囲の先頭セクタ領域から第１のセクタ領域までの範囲（Ｎａ−Ｎｓ）と、第１のセクタ領域から第２のセクタ領域までの範囲（Ｎｂ−Ｎａ）と、第２のセクタ領域から検索範囲の末尾セクタ領域までの範囲（Ｎｅ−Ｎｂ）のいずれかの範囲に狭まる。
【００７３】
ここで、検索範囲の先頭セクタ領域から第１のセクタ領域までの範囲（Ｎａ−Ｎｓ）と、第１のセクタ領域から第２のセクタ領域までの範囲（Ｎｂ−Ｎａ）と、第２のセクタ領域から検索範囲の末尾セクタ領域までの範囲（Ｎｅ−Ｎｂ）が全て検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）の１／２より小さくなるようにすれば、検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）は、前回の範囲の１／２よりも狭くなる。
【００７４】
また、検索範囲の先頭セクタ領域から第１のセクタ領域までの範囲（Ｎａ−Ｎｓ）と、第１のセクタ領域から第２のセクタ領域までの範囲（Ｎｂ−Ｎａ）と、第２のセクタ領域から検索範囲の末尾セクタ領域までの範囲（Ｎｅ−Ｎｂ）のいずれか１つの範囲が検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）の１／２と等しい場合、検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）が、前回の範囲の１／２より狭くならないときある（前回の範囲の１／２になるときがある）。しかし、この場合、他の２つの範囲は検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）の１／２より小さくなるので、検索範囲の先頭セクタ領域から末尾セクタ領域までの範囲（Ｎｅ−Ｎｓ）が、前回の範囲の１／２よりも狭くなるときもある。
【００７５】
第２の条件は、第１のセクタ領域と第２のセクタ領域のいずれか一方が第１のインターフェース側の物理ブロック内のセクタ領域で、他方が第２のインターフェース側の物理ブロック内のセクタ領域になるように変数Ａ、変数Ｂを設定しなければならない。
【００７６】
ここで、第１のインターフェース側の物理ブロック内のセクタ領域に偶数のセクタ番号が割り当てられ、第２のインターフェース側の物理ブロック内のセクタ領域に奇数のセクタ番号が割り当てられている場合、番号Ｎａと番号Ｎｂのいずれか一方が偶数で、他方が奇数になるようにすれば第３の条件を満たすことができる。従って、番号Ｎａと番号Ｎｂを求めた後に、番号Ｎａと番号Ｎｂのいずれか一方に１を加算又はいずれか一方から１を減算してこの条件を満たすようにしてもよい。なお、このように番号Ｎａと番号Ｎｂのいずれか一方に１を加算又はいずれか一方から１を減算するのは、実質的に変数Ａ、変数Ｂの値の変更とみなすことができる。
【００７７】
この条件を満たすように変数Ａ、変数Ｂを設定すれば、第１のセクタ領域にデータが書き込まれているか否かと、第２のセクタ領域にデータが書き込まれているか否かを並行して判断することができる。
【００７８】
次に、図５のフローチャートを参照してデータが書き込まれていないセクタ領域の先頭を検索する検索処理の処理手順を説明する。なお、以下の説明では、先頭位置情報（検索範囲の先頭セクタ領域の番号を示す情報）が示す番号Ｎｓを、スタートポインタＸと言い、末尾位置情報（検索範囲の先頭セクタ領域の番号を示す情報）が示す番号Ｎｅを、エンドポインタＹと言う。また、変数Ａと変数Ｂは（Ｎｅ−Ｎｓ）／４に相当する（Ｙ−Ｘ）／４とする。
【００７９】
この検索処理を開始するときは、スタートポインタＸとエンドポインタＹに初期値を設定する。つまり、スタートポインタＸには仮想ブロック内の先頭セクタ領域のセクタ番号である０を設定し、エンドポインタＹには、仮想ブロック内の末尾セクタ領域のセクタ番号に１を加算した５１２を設定する（ステップＳ１）。
【００８０】
次に、エンドポインタＹとスタートポインタＸとの差が４より小さいか否かを判断する（ステップＳ２）。この条件に基づいて、番号Ｎａと番号Ｎｂ算出方法が決定される。エンドポインタＹとスタートポインタＸとの差が４以上の場合（ステップＳ２：Ｎｏ）、番号Ｎａと番号Ｎｂは下記の式（５）、（６）で算出される（ステップＳ３）。
Ｎａ＝Ｘ＋（Ｙ−Ｘ）／４          （５）
Ｎｂ＝Ｙ−（Ｙ−Ｘ）／４          （６）
【００８１】
エンドポインタＹとスタートポインタＸとの差が４より小さい場合（ステップＳ２：Ｙｅｓ）、番号Ｎａと番号Ｎｂは下記の式（７）、（８）で算出される（ステップＳ４）。
Ｎａ＝Ｘ＋１          （７）
Ｎｂ＝Ｙ−１          （８）
【００８２】
つまり、エンドポインタＹとスタートポインタＸとの差が４より小さい場合は、変数Ａと変数Ｂを１として番号Ｎａと番号Ｎｂが算出される。ここで、変数Ａと変数Ｂを１としたのは、（Ｙ−Ｘ）／４の値（小数点以下を切り捨てた値）が０になり、Ｎａ＝Ｘ、Ｎｂ＝Ｙとなってしまうことを回避するためである。
【００８３】
ステップＳ３又はステップＳ４で算出した番号Ｎａと番号Ｎｂの双方が偶数、又は奇数であるかを判断する（ステップＳ５）。
【００８４】
番号Ｎａと番号Ｎｂの一方が偶数で他方が奇数の場合（ステップＳ５：Ｎｏ）、セクタ番号ＳＮがＮａの第１のセクタ領域とセクタ番号ＳＮがＮｂの第２のセクタ領域は、一方が第１のインターフェース側の物理ブロック内のセクタ領域で、他方が第２のインターフェース側の物理ブロック内のセクタ領域になる。従って、番号Ｎａと番号Ｎｂに対する調整行わずにステップＳ８に進む。
【００８５】
番号Ｎａと番号Ｎｂの双方が偶数、又は奇数の場合（ステップＳ５：Ｙｅｓ）、番号Ｎａと番号Ｎｂが同じ番号であるか否かを判断する（ステップＳ６）。番号Ｎａと番号Ｎｂが同じ番号である場合（ステップＳ６：Ｙｅｓ）、第１のインターフェースと第２のインターフェースの２つのインターフェースでアクセスする必要がないので番号Ｎａと番号Ｎｂに対する調整行わずにステップＳ８に進む。番号Ｎａと番号Ｎｂが同じ番号でない場合（ステップＳ６：Ｎｏ）、番号Ｎａに１を加算する調整を行った後（ステップＳ７）、ステップＳ８に進む。
【００８６】
次に、第１のインターフェースと第２のインターフェースを介して、セクタ番号ＳＮがＮａの第１のセクタ領域とセクタ番号ＳＮがＮｂの第２のセクタ領域が並行してアクセスされる。なお、ステップＳ７の番号Ｎａの調整は、この並行処理を可能にするために行われる。従って、番号Ｎａを変更せずに、番号Ｎｂから１を減算する調整を行ってもよい。また、第１のセクタ領域と第２のセクタ領域に対するアクセスでは、それぞれのセクタ領域に対応する部分冗長領域に書き込まれている付加情報（セクタ領域にデータが書き込まれているか否かを判断することができる付加情報）を参照し、その参照結果に基づいて第１のセクタ領域と第２のセクタ領域にデータが書き込まれているか否かが判断される。
【００８７】
第１のセクタ領域にデータが書き込まれているか否かの判断（ステップＳ８）と、第２のセクタ領域にデータが書き込まれているか否かの判断（ステップＳ９）の結果に基づいてスタートポインタＸとエンドポインタＹの双方又はいずれか一方の値が変更される。
【００８８】
第１のセクタ領域にデータが書き込まれていない場合（ステップＳ８：Ｎｏ）、第１のセクタ領域より後のセクタ領域にはデータは書き込まれていないので、エンドポインタＹの値を番号Ｎａの値に変更する（ステップＳ１１）。なお、各セクタ領域にはセクタ番号の順番でデータが書き込まれるため、第１のセクタ領域にデータが書き込まれていない場合、第２のセクタ領域にもデータが書き込まれていない。
【００８９】
第１のセクタ領域と第２のセクタ領域の双方にデータが書き込まれている場合（ステップＳ８：Ｙｅｓ、ステップＳ９：Ｙｅｓ）、第２のセクタ領域より前のセクタ領域にはデータは書き込まれているので、スタートポインタＸの値を番号Ｎｂの値に変更する（ステップＳ１２）。
【００９０】
第１のセクタ領域にデータが書き込まれていて、第２のセクタ領域にデータが書き込まれていない場合（ステップＳ８：Ｙｅｓ、ステップＳ９：Ｎｏ）、第１のセクタ領域より前のセクタ領域にはデータは書き込まれているので、スタートポインタＸの値を番号Ｎａの値に変更し、第２のセクタ領域より後のセクタ領域にはデータは書き込まれていないので、エンドポインタＹの値を番号Ｎｂの値に変更する（ステップＳ１０）。
【００９１】
ステップＳ１０〜１２でスタートポインタＸとエンドポインタＹの双方又はいずれか一方の値を変更した後に、変更後のスタートポインタＸとエンドポインタＹの差が１であるか否か判断する（ステップＳ１３）。スタートポインタＸとエンドポインタＹの差が１の場合（ステップＳ１３：Ｙｅｓ）、検索処理を終了する。スタートポインタＸとエンドポインタＹの差が１でない場合（ステップＳ１３：Ｙｅｓ）、ステップＳ２に戻る。
【００９２】
つまり、この検索処理はスタートポインタＸとエンドポインタＹの差が１になるまで繰り返され、スタートポインタＸとエンドポインタＹの差が１になったときにスタートポインタＸに設定されている値が、データが書き込まれているセクタ領域の末尾のセクタ番号ＳＮに一致し、エンドポインタＹに設定されている値が、データが書き込まれていないセクタ領域の先頭のセクタ番号ＳＮに一致する。
【００９３】
次に、仮想ブロック内のセクタ番号ＳＮのＳＮ＃３００のセクタ領域までデータが書き込まれている場合の検索処理について図６を参照して具体的に説明する。
【００９４】
＜検索回数１＞
スタートポインタＸの初期値０とエンドポインタＹの初期値５１２に基づいてＮａの値１２８（＝０＋（５１２−０）／４）とＮｂの値３８４（＝５１２−（５１２−０）／４）を算出し、ＮａとＮｂの双方が偶数なのでＮａの値を１２９（＝１２８＋１）にする。セクタ番号ＳＮが＃１２９の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３８４の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値１２９に変更すると共にエンドポインタＹの値をＮｂの値３８４に変更する。
【００９５】
＜検索回数２＞
スタートポインタＸの値１２９とエンドポインタＹの値３８４に基づいてＮａの値１９２（＝１２９＋（３８４−１２９）／４）とＮｂの値３２１（＝３８４−（３８４−１２９）／４）を算出する。セクタ番号ＳＮが＃１９２の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３２１の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値１９２に変更すると共にエンドポインタＹの値をＮｂの値３２１に変更する。
【００９６】
＜検索回数３＞
スタートポインタＸの値１９２とエンドポインタＹの値３２１に基づいてＮａの値２２４（＝１９２＋（３２１−１９２）／４）とＮｂの値２８９（＝３２１−（３２１−１９２）／４）を算出する。セクタ番号ＳＮが＃２２４の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃２８９の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域と第２のセクタ領域の双方にデータが有ると判断し、スタートポインタＸの値をＮｂの値２８９に変更する。
【００９７】
＜検索回数４＞
スタートポインタＸの値２８９とエンドポインタＹの値３２１に基づいてＮａの値２９７（＝２８９＋（３２１−２８９）／４）とＮｂの値３１３（＝３２１−（３２１−２８９）／４）を算出し、ＮａとＮｂの双方が奇数なのでＮａの値を２９８（＝２９７＋１）にする。セクタ番号ＳＮが＃２９８の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３１３の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値２９８に変更すると共にエンドポインタＹの値をＮｂの値３１３に変更する。
【００９８】
＜検索回数５＞
スタートポインタＸの値２９８とエンドポインタＹの値３１３に基づいてＮａの値３０１（＝２９８＋（３１３−２９８）／４）とＮｂの値３１０（＝３１３−（３１３−２９８）／４）を算出する。セクタ番号ＳＮが＃３０１の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３１０の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域と第２のセクタ領域の双方にデータが無いと判断し、エンドポインタＹの値をＮａの値３０１に変更する。
【００９９】
＜検索回数６＞
スタートポインタＸの値２９８とエンドポインタＹの値３０１の差が４より小さいので、スタートポインタＸの値２９８に１を加算したＮａの値２９９とエンドポインタＹの値３０１から１を減算したＮｂの値３００を求める。セクタ番号ＳＮが＃２９９の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３００の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域と第２のセクタ領域の双方にデータが有ると判断し、スタートポインタＸの値をＮｂの値３００に変更する。
【０１００】
ここで、スタートポインタＸの値３００とエンドポインタＹの値３０１の差が１になったので検索を終了し、データが書き込まれているセクタ領域の末尾のセクタ番号ＳＮが＃３００であると判断し、データが書き込まれていないセクタ領域の先頭のセクタ番号ＳＮが＃３０１であると判断する。
【０１０１】
次に、仮想ブロック内のセクタ番号ＳＮのＳＮ＃３０５のセクタ領域までデータが書き込まれている場合の検索処理について図７を参照して具体的に説明する。なお、検索回数４までは図６の場合と同じなので検索回数５以降について説明する。
【０１０２】
＜検索回数５＞
スタートポインタＸの値２９８とエンドポインタＹの値３１３に基づいてＮａの値３０１（＝２９８＋（３１３−２９８）／４）とＮｂの値３１０（＝３１３−（３１３−２９８）／４）を算出する。セクタ番号ＳＮが＃３０１の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３１０の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値３０１に変更すると共にエンドポインタＹの値をＮｂの値３１０に変更する。
【０１０３】
＜検索回数６＞
スタートポインタＸの値３０１とエンドポインタＹの値３１０に基づいてＮａの値３０３（＝３０１＋（３１０−３０１）／４）とＮｂの値３０８（＝３１０−（３１０−３０１）／４）を算出する。セクタ番号ＳＮが＃３０３の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３０８の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値３０３に変更すると共にエンドポインタＹの値をＮｂの値３０８に変更する。
【０１０４】
＜検索回数７＞
スタートポインタＸの値３０３とエンドポインタＹの値３０８に基づいてＮａの値３０４（＝３０３＋（３０８−３０３）／４）とＮｂの値３０７（＝３０８−（３０８−３０３）／４）を算出する。セクタ番号ＳＮが＃３０４の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３０７の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値３０４に変更すると共にエンドポインタＹの値をＮｂの値３０７に変更する。
【０１０５】
＜検索回数８＞
スタートポインタＸの値３０４とエンドポインタＹの値３０７の差が４より小さいので、スタートポインタＸの値３０４に１を加算したＮａの値３０５とエンドポインタＹの値３０７から１を減算したＮｂの値３０６を求める。セクタ番号ＳＮが＃３０５の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３０６の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無いと判断し、スタートポインタＸの値をＮａの値３０５に変更すると共にエンドポインタＹの値をＮｂの値３０６に変更する。
【０１０６】
ここで、スタートポインタＸの値３０５とエンドポインタＹの値３０６の差が１になったので検索を終了し、データが書き込まれているセクタ領域の末尾のセクタ番号ＳＮが＃３０５であると判断し、データが書き込まれていないセクタ領域の先頭のセクタ番号ＳＮが＃３０６であると判断する。
【０１０７】
次に、仮想ブロック内のセクタ番号ＳＮのＳＮ＃３０９のセクタ領域までデータが書き込まれている場合の検索処理について図８を参照して具体的に説明する。なお、検索回数５までは図７の場合と同じなので検索回数６以降について説明する。
【０１０８】
＜検索回数６＞
スタートポインタＸの値３０１とエンドポインタＹの値３１０に基づいてＮａの値３０３（＝３０１＋（３１０−３０１）／４）とＮｂの値３０８（＝３１０−（３１０−３０１）／４）を算出する。セクタ番号ＳＮが＃３０３の第１のセクタ領域に対応する部分冗長領域とセクタ番号ＳＮが＃３０８の第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域と第２のセクタ領域の双方にデータが有ると判断し、スタートポインタＸの値をＮｂの値３０８に変更する。
【０１０９】
＜検索回数７＞
スタートポインタＸの値３０８とエンドポインタＹの値３１０の差が４より小さいので、スタートポインタＸの値３０８に１を加算したＮａの値３０９とエンドポインタＹの値３１０から１を減算したＮｂの値３０９を求める。ここで、ＮａとＮｂの値は同じなので、番号Ｎａの調整は行わずに、セクタ番号ＳＮが＃３０９の第１のセクタ領域及び第２のセクタ領域に対応する部分冗長領域を参照する。参照した結果、第１のセクタ領域と第２のセクタ領域の双方にデータが有ると判断し、スタートポインタＸの値をＮｂの値３０９に変更する。
【０１１０】
ここで、スタートポインタＸの値３０９とエンドポインタＹの値３１０の差が１になったので検索を終了し、データが書き込まれているセクタ領域の末尾のセクタ番号ＳＮが＃３０９であると判断し、データが書き込まれていないセクタ領域の先頭のセクタ番号ＳＮが＃３１０であると判断する。
【０１１１】
以上で説明したように、第１のセクタ領域のデータの有無と第２のセクタ領域のデータの有無を並行して判断して、スタートポインタＸとエンドポインタＹを更新していった場合、第１のセクタ領域と第２のセクタ領域の双方にデータが有ったときはスタートポインタＸとエンドポインタＹの差が変数Ｂの値まで狭まり、第１のセクタ領域と第２のセクタ領域の双方にデータが無かったときはスタートポインタＸとエンドポインタＹの差が変数Ａの値まで狭まり、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無かったときはスタートポインタＸとエンドポインタＹの差が番号Ｎｂと番号Ｎａの差の値まで狭まる。従って、上述の例のように変数Ａと変数Ｂを（Ｎｅ−Ｎｓ）／４に相当する（Ｙ−Ｘ）／４とした場合、第１のセクタ領域と第２のセクタ領域の双方にデータが有ったとき、又は第１のセクタ領域と第２のセクタ領域の双方にデータが無かったときは、スタートポインタＸとエンドポインタＹの差が１／４に狭まり、第１のセクタ領域にデータが有り第２のセクタ領域にデータが無かったときはスタートポインタＸとエンドポインタＹの差が１／２に狭まる。一方、通常の２分木検索ではスタートポインタＸとエンドポインタＹの差が１／２ずつ狭まっていく。
【０１１２】
従って、上述の例では、何番目のセクタ領域までデータが書き込まれているかによって検索回数が変動するが、通常の２分木検索による検索回数以下の回数でデータが書き込まれていないセクタ領域の先頭を検出することができる。
【０１１３】
なお、上述の例では、変数Ａと変数Ｂを（Ｎｅ−Ｎｓ）／４に相当する（Ｙ−Ｘ）／４としたが、変数Ａと変数Ｂを（Ｎｅ−Ｎｓ）／３に相当する（Ｙ−Ｘ）／３とすれば、スタートポインタＸとエンドポインタＹの差が１／３ずつ狭まっていく。また、変数Ａと変数Ｂは異なる値であっってもよい。例えば、変数Ａを（Ｎｅ−Ｎｓ）／４に相当する（Ｙ−Ｘ）／４とし、変数Ｂを（Ｎｅ−Ｎｓ）／２に相当する（Ｙ−Ｘ）／２としてもよい。
【図面の簡単な説明】
【０１１４】
【図１】本発明のフラッシュメモリシステムの一実施例の概略を説明するためのブロック図である。
【図２】図１のフラッシュメモリのアドレス空間の構造を概略的に示す図である。
【図３】アドレス変換の概要を説明するための図である。
【図４】図１のホストインターフェースブロック及びフラッシュメモリインターフェースブロックの詳細を示すブロック図である。
【図５】仮想ブロック内でのデータが書き込まれていないセクタ領域の先頭を検索する検索処理を説明するためのフローチャートである。
【図６】セクタ番号ＳＮのＳＮ＃３００までデータが書き込まれている場合の検索処理を説明するための図である。
【図７】セクタ番号ＳＮのＳＮ＃３０５までデータが書き込まれている場合の検索処理を説明するための図である。
【図８】セクタ番号ＳＮのＳＮ＃３０９までデータが書き込まれている場合の検索処理を説明するための図である。
【図９】従来の二分木検索を用いた検索処理を説明するための図である。
【符号の説明】
【０１１５】
１  フラッシュメモリシステム
２  フラッシュメモリ
３  メモリコントローラ
４  ホストシステム
６  マイクロプロセッサ（インターフェース手段、書き込み手段、検索範囲保持手段        、セクタ領域検索手段、第１のセクタ領域判別手段、第２のセクタ領域判別手        段）
７  ホストインターフェースブロック
８  ワークエリア
９  バッファ
１０  フラッシュメモリインターフェースブロック
１１  ＥＣＣブロック
１２  ＲＯＭ
１３  外部バス
１４  内部バス
２５  ユーザ領域
２６  冗長領域
Ｒ１  コマンドレジスタ
Ｒ２  セクタ数レジスタ
Ｒ３  ＬＢＡレジスタ
Ｒ１１  物理ブロックアドレスレジスタ
Ｒ１２  セクタ番号レジスタ
Ｒ１３  カウンタ
【図１】
0004513782.tif 000002
【図２】
0004513782.tif 000003
【図３】
0004513782.tif 000004
【図４】
0004513782.tif 000005
【図５】
0004513782.tif 000006
【図６】
0004513782.tif 000007
【図７】
0004513782.tif 000008
【図８】
0004513782.tif 000009
【図９】
0004513782.tif 000010