JP2009503745A - ブロック管理を伴う不揮発性メモリ - Google Patents

Abstract

ブロック消去可能なメモリアレイを含む不揮発性メモリシステムでは、特定の分類のブロックのためのレコードを個別に保守する。ブロックのために１つ以上のリストを保守でき、個々のリストは記述子値に従って序列される。このような序列リストは、記述子値によるブロックの迅速な識別を可能にする。

Description

本願は、半導体フラッシュメモリ等の再プログラム可能な不揮発性メモリシステムの動作に関し、より具体的にはメモリアレイの個別に消去可能なブロックの管理に関する。

ホストシステム、メモリシステム、その他の電子システムの外部インターフェイスを通じて通信されるデータをアドレス指定するには主に２つの手法がある。そのうちの一手法では、システムによって生成または受信されるデータファイルのアドレスが、データの論理ブロックとして設定された別個の連続論理アドレス空間範囲にマップされる（これ以降「ＬＢＡインターフェイス」と称する）。アドレス空間の大きさは通常、システムで取り扱うことのできるアドレス全域を十分にカバーする。一例において、磁気ディスク記憶ドライブは、このような論理アドレス空間を通じてコンピュータをはじめとするホストシステムと通信する。このアドレス空間は、ディスクドライブの全データ記憶容量を十分にアドレス指定する大きさを持つ。

フラッシュメモリシステムは多くの場合、パーソナルコンピュータやカメラ等の様々なホストと着脱可能な状態で接続するメモリカードまたはフラッシュドライブの形で提供されるが、このようなホストシステムの中に埋め込まれることもある。ホストは通常、メモリへデータを書き込む場合に、メモリシステムの連続する仮想アドレス空間の中でセクタ、クラスタ、あるいはその他のデータ単位に一意な論理アドレスを割り当てる。ホストは、ディスクオペレーティングシステム（ＤＯＳ）のように、メモリシステムの論理アドレス空間の中のアドレスにデータを書き込み、かつこれからデータを読み出す。メモリシステムの中のコントローラは、ホストから受け取った論理アドレスをメモリアレイの中のデータが実際に記憶される物理アドレスに翻訳し、これらのアドレス翻訳の経緯を把握する。メモリシステムのデータ記憶容量は少なくとも、メモリシステムのために規定される論理アドレス空間全体にわたってアドレス指定可能なデータ量に相当する。

現在の商用フラッシュメモリシステムにおける消去単位のサイズは、複数セクタのデータを十分に記憶するメモリセルブロックまで拡大している。事実、多数のデータページが１つのブロックに記憶され、１ページで複数セクタのデータを記憶できる。さらに、多くの場合、２つ以上のブロックがまとめてメタブロックとして扱われ、このようなブロックのページはまとめてメタページとして論理的にリンクされる。多数のセクタのデータを含むデータのページまたはメタページがまとめて読み書きされることにより、操作の並列性を高めている。そのような大容量操作単位には、それらを効率的に操作するという課題がともなう。

説明を平易にするため、別段の断りがない限り、ここで用いる用語「ブロック」は、ある特定のシステムでメタブロックが使われるか否かに応じて、ブロック消去単位または多重ブロック「メタブロック」を指すことを意図する。同様に、ここで言及する「ページ」は、システム構成に応じて、単一のブロックまたはメタブロック内の「メタページ」の中でのプログラミングの単位を指すことがある。

現在普及しているメモリシステムのＬＢＡインターフェイスが使われる場合、メモリの接続先にあたるホストによって生成されるファイルには、インターフェイスの論理アドレス空間の中で一意なアドレスが割り当てられる。次いで、メモリシステムは普通、論理アドレス空間とメモリの物理ブロックのページとの間でデータをマッピングする。メモリシステムは論理アドレス空間から物理メモリへのマッピングを絶えず把握するが、ホストはこれを知らない。ホストは、論理アドレス空間の中でそのデータファイルのアドレスを絶えず把握するが、メモリシステムはこのマッピングについて無知かまたはほぼ無知の状態で動作する。
米国特許出願第１１／３８２，２２４号 米国特許出願第１１／３８２，２２８号 米国特許出願第１１／３８２，２３２号 米国特許出願第１１／３８２，２３５号

使用されている２通りのシステムインターフェイス手法の２番目の手法では、電子システムによって生成または受信されたデータファイルが一意に識別され、そのデータはファイル内でのオフセットによって論理的にアドレスされる。コンピュータをはじめとする他のホストシステムと「スマートカード」として知られる着脱可能なメモリカードとの間では、このアドレス指定方法の形態が使われている。スマートカードは通常、識別、バンキング、販売時点購入、ＡＴＭアクセス等のために消費者に利用され、フラッシュメモリカードやフラッシュドライブに比べて少量のメモリを内蔵する。

前に相互参照した特許出願において、大容量フラッシュメモリシステムではホストによって割り当てられたファイル名によってデータファイルが識別され、このファイルのデータはファイル内のオフセットアドレスによってアクセスされる（これ以降「直接データファイルインターフェイス」と称する）。次いで、メモリシステムは、各セクタまたはその他のデータ単位が帰属するホストファイルを知る。ここで論じるファイル単位は、例えば連続する論理オフセットアドレスによって序列される１組のデータであり、メモリシステムの接続先にあたるホスト演算システムで動作するアプリケーションプログラムによって作成され、一意に識別される。

前に援用されている４つの米国特許出願（２００６年５月８日に出願された米国特許出願第１１／３８２，２２４号（特許文献１）、第１１／３８２，２２８号（特許文献２）、第１１／３８２，２３２号（特許文献３）、第１１／３８２，２３５号（特許文献４））では、メモリシステムの動作中にアクセスされるブロックのリストを保守する手法が説明されている。リスト上の個々の項目は、メモリブロックのパラメータとそれぞれのアドレスとを含む。リスト内の項目は、これに対応するブロックの物理アドレスか、またはこの項目の中に記録されたブロックパラメータの値のいずれかに従って選択できる。本願明細書は、フラッシュメモリの指定されたブロックの中でデータブロックの１つ以上のリストを記憶することに、またリスト内の特定の項目に、この項目の中にあるフィールドの情報内容に基づきアクセスすることに関する。

その手法では、２つ以上のリスト上で全ブロックの情報を収容する整列されていないレコードを記憶するため、指定されたブロック内の論理ページのいくつかを使用する。その他のページは、ブロックの内容アドレス指定可能なパラメータと、ブロックの完全レコードへのポインタだけを収容する項目のリストのために使用する。これらのリストの中ではパラメータ値の順序で項目が記憶され、ある特定のパラメータ値を持つ項目には速やかにアクセスできる。これらのリストは、整列されていないブロックレコードに対し一種のディレクトリとしての役割を果たす。

ブロック消去可能な不揮発性メモリでは、個々のブロックとそこに収容されたデータについて最新の情報を保守すれば、効率的なメモリ管理が可能となる。１つ以上のファイルの有効データと、用済みデータと、消去済みの空間とが混在するブロックの場合、これは非常に複雑である。しかし、このようなデータをブロック単位で把握すれば、ある種のメモリシステム操作は、特にメモリアレイにおける使用されていない空間の再生は、効率的に遂行できる。使用されていない空間（用済みデータを収容する空間または使用されていない消去済みの空間）の再生はブロック単位で行われる（ここでブロックは消去の単位である）。有効データのコピーを減らすため、ブロックに対するブロック再生操作は効率的な順序で遂行することが望ましい。ブロック再生の順序を決定するには、１つ以上の記述子値の順序でブロックを格付けすると有益であり、ここで、記述子値は、ブロックに記憶されるデータの少なくとも１つの態様を記述する。例えば、ブロックは、そこに収容された有効データの量によって序列でき、そのようにして収容する有効データ量が最も少ないブロックを最初に再生するべく速やかに識別できる。

第１の例において、必ずしも全てのブロックではないが、メモリアレイの様々なブロックのために、レコードを保守する。有効データを収容するブロックは、それらが消去済みの空間を収容するか否かに従い（不完全ブロック）、収容しない場合にはそれらが用済みデータを収容するか否かに従い（用済みブロック）、分類される。これとは別に、用済みデータだけを収容するブロック（無効ブロック）と消去済みの空間だけを収容するブロック（消去済みブロック）とが分類される。これらの分類のいずれか１つに該当する各ブロックにつきレコードを保守する。レコードは専用のレコードブロックにて保守される。加えて、分類されたブロックはリストに列挙され、このリストは記述子値によって序列される。記述子値は、ブロック内の有効データ量、ブロックのアドレス、または他の何らかの記述子値であってもよい。リスト項目は、第１の例において、対応するレコードのポインタを収容する。

第２の例では、様々な分類に該当するブロックのためのレコードも保守する。２つ以上のファイルのデータを収容し、かつ用済みデータもあるいは消去済みの空間も収容しないブロックのために分類「コンプリート共通ブロック」が加えられる。レコードは、専用レコードブロックの中の専用レコードページにて保守される。レコードは、ブロックのブロックアドレス、ブロックに収容された有効データ量、書き込みポインタの位置等を含む、対応するブロックについて様々な情報を収容できる。

個々のレコードを速やかに見つけることを可能にするためにディレクトリが提供される。ディレクトリの中の項目は、レコードページと、レコードページにおける対応するレコードの位置とを識別する。ディレクトリはディレクトリブロックの中の専用ディレクトリページにて保守され、ディレクトリの項目はブロックアドレスによって序列される。ディレクトリページは重複しないブロックアドレス範囲を収容する。１つのディレクトリページで複数のレコードページのポインタを収容できる。しかし、１つのディレクトリページの項目によって指示されるレコードは１レコードページに収容されたレコードだけである。したがって、レコードページの中でレコードが更新されるときには、ただひとつのディレクトリページを更新すればよい。

ディレクトリブロックはまた、１つ以上のリストを収容できる。リスト内の項目はブロックアドレスと記述子値とを収容し、リスト内の項目は記述子値によって序列される。ブロック内の有効データ量は代表的な記述子値である。再生またはその他の目的でブロック内のデータに基づきブロックを選択するにあたって、リストは簡便な手段を提供する。例えば、有効データ量を記述子値として使用する用済みブロックのリストでは、有効データ量が最も少ない用済みブロックが最初の項目になる。このブロックは再生のためにリストから速やかに識別でき、かくしてリストは再生操作のためのキューを提供する。別の例では、ある特定の記述子値を持つブロックを探すことができる。これは、適切なリストページでバイナリ探索を遂行することによって速やかに識別できる。

第３の例では、不揮発性メモリアレイの各ブロックにつき常時レコードを保守する。この場合のディレクトリページは固定ブロックアドレス範囲の項目を収容し、項目はブロックアドレスによって順次に序列される。これは、特定のブロックの項目をディレクトリページの中で所定のオフセットのところに提供するため、項目の参照先にあたるブロックのブロックアドレスを項目に収容する必要はない。

ここではフラッシュデータファイルインターフェイスとともに動作するフラッシュメモリに使われるリストを管理しこれにアクセスする手法を説明するが、これらの手法は様々な用途でタイプの異なるリストに役立てることもできる。

詳細な第１の例
前述した特許出願で説明されている直接データファイル記憶法はブロックのリストを作成し、個々のブロックの使用に関する所定の値を持つ項目がこのリストから選択される。ここでは、これらのブロックリストの内容アドレス指定可能な探索のための手法を説明する。本願明細書では、添付の図１〜３を参照する。

図１は、メモリセルブロックの、この内容に基づく、分類を示す表である。事実上メモリシステムの全ブロックが図に示されたとおりに分類される。この例では３つの別々のリスト、すなわち不完全ブロックのリストと、用済みブロックのリストと、消去済みブロックのリストとを保守する。

この例で認識されるブロックのタイプは次のとおりである。
「プログラムブロック」は部分的にプログラムされ、かつただひとつのファイルの有効データを収容する。このブロックにはある程度の消去済み容量が残存する。これはある程度の用済みデータを収容することもある。
「共通ブロック」は部分的にプログラムされ、かつ２つ以上のファイルの有効データを収容する。ある程度の消去済み容量が残存する。ある程度の用済みデータを収容することもある。
「フル共通ブロック」は完全にプログラムされ、かつ２つ以上のファイルの有効データを収容する。ある程度の用済みデータを収容することもある。
「ファイルブロック」は完全にプログラムされ、かつ１つのファイルの有効データを収容する。ある程度の用済みデータを収容することもある。
「無効ブロック」は有効データを収容しない。無効ブロックは少なくともある程度は用済みデータを収容し、消去済み容量を収容することもあるが、有効データは収容しない。
「消去済みブロック」はブロックの全容量がプログラムされておらず、データを受け付けることができる。消去済みブロックの中にデータはない。メモリがデータで満たされているかまたはほぼ満たされている場合は通常、使用中のブロックの中にある使われていない容量を連続的に再生することによって特定の最小消去済みブロック数のプールを維持する。

この例を目的とし、前述したタイプを持つブロックは次に示す３つの分類に分類される。
「不完全ブロック」はある程度のプログラムされていない容量を収容し、１つ以上のファイルの有効データを収容し、かつある程度の用済みデータを収容することがある。プログラムブロックと共通ブロックは不完全ブロックの例である。
「用済みブロック」は、ある程度の用済みブロックを収容するファイルブロックまたはフル共通ブロックである。用済みブロックは消去済み容量を収容せず、有効データと用済みデータの両方を収容する。
「消去済みブロック」の定義は同一名のブロックタイプと同じであり、つまりデータがないブロックである。

メモリアレイの全てのブロックがこれらの分類に入るわけではないことと、ブロックによってはこれらの分類から外れることがあることと、またこのようなブロックがこの例のリストに出現しないこととに留意すべきである。

記憶容量を再生するためのブロックを選択する場合、主な要因となるのは、ブロック内の有効データ量（有効データ容量）である。ブロックに対する再生操作にあたってはこれの有効データを別のブロックへコピーする必要があるから、有効データ量が最も少ないブロックが最初に選ばれる。というのは、データコピーには時間がかかり、データをプログラムし読み出すにあたってメモリシステムの効率的な動作に支障をきたすおそれがあるからである。容量の大半が消去済みでデータを記憶するために使用できるブロックの利点は、いくぶんこれに相反する。有用な消去済み記憶容量を持つブロックを再生することによって得られる記憶空間の増大はさほど大きくないから、そのようなブロックは再生操作にとって好ましくない。この特定の例の不完全および用済みブロックリストは、ブロックに収容された有効データ量（ページ数）と消去済みの量（ページ数）とに基づきブロックを分類するために使用される。ここで説明するこれらのリストの目的は、再生操作に供されるブロックを一度に１つずつ選択することにある。

ブロックリストのタイプとアクセス
不完全ブロックリスト（Ｐリスト）は、システム内の全ての不完全ブロックにつき、すなわちある程度の有効データとある程度の消去済み容量の両方を収容する全ブロックにつき、項目を収容する。ある程度の用済みデータを収容することもある。

用済みブロックリスト（Ｏリスト）は、不完全ブロックリストに項目を持たない、用済みデータを収容する、システム内の全ブロックにつき項目を収容する。

消去済みブロックリスト（Ｅリスト）は、システム内の全消去済みブロックにつき項目を収容する。

フラッシュメモリ操作の一具体例において、次のブロックリストを保守する。
Ｐ（Ｖ）リスト：ブロックに記憶される有効データ容量に従って項目が序列される不完全ブロックリスト
Ｐ（Ａ）リスト：ブロックのブロックアドレスに従って項目が序列される不完全ブロックリスト
Ｏ（Ｖ）リスト：ブロックに記憶される有効データ容量に従って項目が序列される用済みブロックリスト
Ｏ（Ａ）リスト：ブロックのブロックアドレスに従って項目が序列される用済みブロックリスト
Ｅリスト：消去済みブロックリスト

Ｐ（Ｖ）リスト、Ｏ（Ｖ）リスト、Ｐ（Ａ）リスト、Ｏ（Ａ）リストとは、ブロックレコードの共通セットに対し「ディレクトリ」の役割を果たす。再生ブロックを選択するには、有効データ容量値が最も低い項目がＰ（Ｖ）リストとＯ（Ｖ）リストとから読み出される。アクティブブロックを選択するには、最も高い有効データ容量値が目標値に満たないかまたはこれに等しい項目がＰ（Ｖ）リストから読み出される。消去済みブロックを選択するには、Ｅリスト上の最初の項目が読み出され、リストから削除される。

ＰリストまたはＯリストで項目を更新するには、ターゲットブロックアドレスを持つ項目がＰ（Ａ）リストまたはＯ（Ａ）リストから読み出される。

ブロックリストの記憶法
前述したセクションで明らかにしたブロックリスト上のブロックに関係する情報を記憶するために、１つ以上のブロックまたはメタブロックが割り当てられる。これらはレコードブロックとして知られ、書き込みまたは更新が１ページ単位で行われる。レコードブロック内の情報のために内容アドレス指定が使用される。

各々のレコードブロックは一定数の論理ページを収容し、論理ページの各々は、使用可能な次の物理ページへこれを再度書き込むことによって更新できる。リスト内のブロックについて情報を収容するレコードを記憶するため、複数の論理ページが割り当てられる。これらはレコードページとして知られている。

レコードは、ブロックリスト内の全ブロックにつき存在する。レコードページとこれの中にあるレコードはどんな順序でもよい。異なるブロックリストの中にあるブロックのレコードを別々にする必要はない。レコードページの中には用済みレコードが存在することがあり、これは、ブロックリストへ追加されたブロックの新しいレコードに置き換えることができる。レコードは、ブロックの物理アドレスと、ブロックの中にある有効データ量（有効データ容量）を定める値とを、他の情報と併せて収容する。

個々のブロックリストの１ブロックリストの中でブロックを識別する項目を記憶するため、１つ以上の論理ページが割り当てられる。これらはリストページとして知られている。異なるブロックリストのための別々のリストページが使用される。リストページ内の各項目は、記述子値を、レコードページ内のブロックレコードのポインタと併せて収容し、記述子値は、対応するブロックの物理アドレスか、またはブロック内の有効データ容量の値（またはブロック内のデータに関連する他の何らかの値）である。レコードに対応するブロックが２つのブロックリストに現れる場合は、異なるブロックリストの異なるリストページにある２つのリスト項目が同じレコードを指示する。

ブロックリスト内の項目は、ブロックのレコードの共通セットに対し「ディレクトリ項目」の役割を果たす。

不完全ブロックリストまたは用済みブロックリストのリストページでは、それらの記述子の順序で項目が記憶される。項目は稠密な形式で書き込まれ、リストページ内の書き込まれていない項目位置は通常、書き込まれた最後の項目の後ろにある。リストページは重複しない記述子範囲を記憶する。リストページが満杯になると、新しい論理ページをリストページとして割り当てることによってその項目を２つのリストページに分けることができる。同様に、記述子範囲が隣接する２つのリストページの項目数がしきい値を下回る場合は、２つのリストページを１つにまとめることができる。レコードブロックのインデックスは、各リストページの最初の項目の記述子を収容する。

不完全ブロックリストまたは用済みブロックリストの中でブロックアドレスかまたは有効データ容量の目標値を持つ項目は、レコードブロックインデックスから該当する記述子範囲を持つリストページを識別することにより、そのページをフラッシュから読み出し、次いでそのページの中で目標項目のリニア探索かまたはバイナリ探索を遂行することにより、見つけることができる。そして、この項目より識別されるレコードページからターゲットブロックのレコードを読み出すことができる。

消去済みブロックリスト内のブロックの項目はリストページに記憶でき、ここでそれらは、それらが書き込まれた順序を保つ。消去済みブロックは常にリストの中で最も古い項目として選択される。

レコードブロックの構造
ブロックリストの中で参照されるブロックの全ての項目とインデックス情報は、フラッシュメモリの１つ以上のレコードブロックに収容される。レコードブロックはメタブロックであり、ページ単位で更新される。
レコードブロックは次の特性を持つ。
１．あらゆるタイプのブロックリストをまとめて１つのレコードブロックに記憶できる。
２．必要に応じ、複数のレコードブロックを使用できる。
３．レコードブロックは特定の数の論理ページを持ち、これはこの例においてブロック内の物理ページ数の２５％に規定される。
４．最後に書き込まれたページのレコードブロックインデックスセクションは、各論理ページから物理ページへのマッピングを提供する。
５．論理ページは、使用可能な次の物理ページにこれを再度書き込むことによって更新できる。
６．ブロックリストのため、またはブロックのレコードのために使用されるあらゆるタイプのページに論理ページを割り当てることができる。
７．レコードブロックは、満杯のときに圧縮され消去済みブロックに再度書き込まれる。

図２にはレコードブロックの一例の構造が示されている。

レコードブロックインデックス
レコードブロックインデックスは、レコードブロックの中にある各ページの１セクションとして存在する。これは最後に書き込まれたページの中にあるものだけが有効である。レコードブロックインデックスは可能な各論理ページにつき項目を収容し、論理ページ番号に従って序列される。各項目は次に示す３つのフィールドを持つ。
１．ページタイプを識別する数字コード
ａ．Ｐ（Ｖ）リストページ
ｂ．Ｐ（Ａ）リストページ
ｃ．Ｏ（Ｖ）リストページ
ｄ．Ｏ（Ａ）リストページ
ｅ．Ｅリストページ
ｆ．レコードページ
ｇ．割り当てされていない論理ページ
２．ページ内の最初の項目の値（これにより、Ｐ（Ｖ）、Ｐ（Ａ）、Ｏ（Ｖ）、Ｏ（Ａ）リストページの各タイプで値の範囲を設定し、キャッシュできる。）
３．論理ページのマップ先にあたる物理ページのポインタ

レコードページ
レコードはそのリストのうちの１つの項目をブロックに関係する必要情報を全て収容し、レコードページに記憶される。レコードページは次に示す３つのセクションに細分される。
１．項目状態
２．レコード
３．共通ブロックレコード

項目状態セクションは、レコードが使用中か、それとも新しいブロックに割り当てることができるかを指示するビットマップを備える。レコードセクションはリスト内の全ブロックにつき一定サイズの項目を有し、フィールドはブロックの属性を次のとおりに規定する。
１．ブロックアドレス
２．ブロック内の有効データ容量
３．ブロック内のページ書き込みポインタの位置
４．ブロック内の最初のデータグループのファイルＩＤ
５．ブロック内にデータが存在するファイルの合計数
６．ブロックの共通ブロックレコードへのオフセット（値０は共通ブロックレコードが存在しないことを意味する。）

共通ブロックレコードセクションの項目のサイズは不定であり、フィールドは共通ブロック内の他のファイルＩＤを次のとおりに規定する。
１．共通ブロックにおける後続データグループのファイルＩＤ
２．レコード終了インジケータ

ブロックリストからブロックが削除される場合、レコードページは用済み項目を収容する。このようなレコードは、リストに追加される新しいブロックに再び割り当てることができる。

ブロックに割り当てられるレコードブロックの中の論理ページ番号とそのページ内のレコード番号は、レコードを参照するためにリストページによって使用されるため、通常は変更されない。しかし、ブロックのレコードを同一のリストページ内の別のレコード番号、別のリストページ、または別のレコードブロックへ移すことは許される。ブロックのレコードが移される場合、いずれかのリスト項目でそのポインタを相応に更新しなければならない。

レコードページが修正され再度書き込まれる場合、用済みの空間をなくすために共通ブロックレコードを圧縮でき、共通ブロックレコードへのオフセットの変化を反映させるためにレコードを更新できる。

レコードと共通ブロックレコードとの間の境界は動的である。

図３にはブロックレコードページの一例の構造が示されている。

リストページ
リストページは、１組のブロックの項目を、記述子値によって規定される順序で収容する。Ｐ（Ｖ）リストとＯ（Ｖ）リスト内の項目における記述子は有効データ容量であり、Ｐ（Ａ）リストとＯ（Ａ）リスト内の項目における記述子はブロックアドレスである。

有効項目はリストページの中で一連の項目位置を占めるが、ページ全体を埋め尽くす必要はない。この中に用済み項目はなく、記述子値は連続しなくともよい。

リストページ内の項目は、記述子フィールド内の値の順序に並ぶ。記述子値の範囲は、他のリストページ内の記述子値の範囲と重複しない。

ブロックリストへ追加されたブロックのための項目を挿入する必要がある場合、その新しいブロックの記述子値を記述子範囲に含むリストページを識別する。新しい項目は記述子範囲内の適切な位置に挿入され、リストページは再度書き込まれる。項目を削除しなければならない場合、その項目を省いてリストページが圧縮され、再度書き込まれる。

満杯になったリストページへ追加を行わなければならない場合、空き論理ページが新しいリストページとして割り当てられ、満杯のリストページの記述子範囲は、２つのほぼ等しい重複しない範囲に分割され、それらは２つの使用可能なリストページに書き込まれる。

記述子範囲が隣接する２つのリストページで総有効項目数がしきい値（この例では、リストページにおける項目位置数の７０％）を下回ると、２つのリストページの範囲は統合され、２つのリストページのうちの一方に書き込まれる。次いで、他方の使用されていないページは空き論理ページとなる。

Ｐ（Ｖ）リストとＯ（Ｖ）リストの場合、リストページ内の項目内のフィールドは次のとおりである。
１．ブロック内の有効データ容量
２．レコードページ内のブロックのレコードを指すポインタ（レコードページはリストページと同じレコードブロックの中になくてもよい。）

Ｐ（Ａ）リストとＯ（Ａ）リストの場合、リストページ内の項目内のフィールドは次のとおりである。
１．ブロックアドレス
２．レコードページ内のブロックのレコードを指すポインタ（レコードページはリストページと同じレコードブロックの中になくてもよい。）

Ｅリストの場合、リストページ内の項目内のフィールドは次のとおりである。
１．ブロックアドレス

レコードのアクセスシーケンス
ＰリストまたはＯリストで目標ブロックのレコードにアクセスするには、次のステップからなるシーケンスを使用する。
１．Ｐ（Ｖ）リスト、Ｏ（Ｖ）リスト、Ｐ（Ａ）リスト、またはＯ（Ａ）リストを目標リストとして設定する。
２．レコードブロックの中で最後に書き込まれたページからレコードブロックインデックスを読み出す。この情報はあらかじめキャッシュの中に存在することがある。
３．ステップ１で規定した目標リストで目標記述子値のリストページに割り当てられた論理ページ番号を判定する。
４．ステップ３で判定した論理ページ番号をレコードブロックから読み出す。
５．目標ブロックの項目を読み出すために、ステップ４で読み出したリストページを探索する。
６．ステップ５で読み出した項目によって規定されるレコードブロックからレコードページを読み出す。
７．ステップ６で読み出したレコードページからターゲットブロックのレコードを読み出す。

詳細な第２の例
第２の例では前述した第１の例と同じく、特定のブロックが、そこに収容されるデータに従い、それぞれ分類され、これらのブロックのためのレコードが保守される。リストは、ブロックに記憶されるデータに関係する記述子値に従って序列され、保守される。ブロックの中にある有効データ量は、このような記述子値の一例である。しかし、この第２の例で、ブロックの管理に用いる構造および方法のいくつかは異なる。第１および第２の例の構造および方法は代案とみなすべきものであり、両例の構造および／または手法の様々な組み合わせもまた本発明の開示の一部とみなされる。第２の例は、第１の例との違いに焦点をあてながら説明する。よって、両例に共通の要素は第２の例に関して重ねて詳述しない場合がある。

第２の例のブロック分類は第１の例のブロック分類と同じであり、「コンプリート共通ブロック分類」が追加される。図４は、追加の分類「コンプリート共通ブロック」を除いて図１とほぼ同じブロック分類表を示す。「不完全ブロック」、「用済みブロック」、「消去済みブロック」、または「コンプリート共通ブロック」のブロック分類を有する各ブロックにつきレコード項目を保守する。分類「コンプリート共通ブロック」は、消去済み容量を収容せず、かつ用済みデータを収容しない共通ブロックに使われる。コンプリート共通ブロック（ＣＣＢ）のレコードは、全コンプリート共通ブロックのブロックレコードにより保守される。再生のために使用できる空間を持たない（消去済みの空間も用済みの空間も持たない）コンプリート共通ブロックは通常、再生操作に供されない。しかし、コンプリート共通ブロックの中である程度のデータが用済みになると、そのブロックは用済みブロックとして再分類され、再生操作に供されることがある。そのような再分類が行われる場合には、ブロックに記憶されるデータの関連情報を収容するブロックレコードが必要である。この情報はブロックの既存のＣＣＢレコード項目から使用可能である。したがって、コンプリート共通ブロックのレコードを保守すれば、ブロックのレコードを生成するために情報を探索するという重い負担を伴わずにコンプリート共通ブロックから用済みブロックへの移行を果たすことができる。

図１および４の分類方式は例示的なものであり、これ以外の方式も予期される。（後ほど詳述する）一例において、メモリアレイの中にある全ブロックのために常時レコードを保守する。この場合は、用済みデータを持たないファイルブロックのための追加のブロック分類を図４の表に加えることができる。別の例では、図４の分類のいくつかは必要とされない。例えば、消去済みブロックや無効ブロックのレコードは保守しなくてよい。さらに別の例では、図４とは異なるブロックタイプにブロックを分けることができる。図４のブロックタイプが特定のメモリ管理方式にとって好都合であるが、他のメモリ管理方式で異なるブロックタイプを使用できることも理解できよう。

図４の表に記載されたブロック分類のいずれか１つに該当する全ブロックにつきレコードを保守する。ブロック分類が異なるブロックのレコードを同じページにまとめて記憶できる。この例では、ブロックレコードだけを記憶する専用のブロックレコードブロックを保守する。レコードブロック内の個々のレコード項目へのアクセスを促進するため、ブロックディレクトリを保守する。（ブロックディレクトリとブロックレコードの両ページをただひとつのブロックで収容する第一の例と違って）ブロックディレクトリとブロックレコードは、フラッシュメモリの中で別個の１組のブロックに記憶される。図５は、ディレクトリブロック５０３の中にあるブロックディレクトリ項目５０１を示し、このブロックディレクトリ項目は、ブロックレコードブロック５０９の中にある対応するブロックレコード５０７の位置を指すポインタ５０５を含む。ブロックディレクトリ項目５０１はブロックアドレス５０６をも含む。

ブロックディレクトリは、ブロックレコードに項目が存在する各ブロックにつき１つのブロックディレクトリ項目を収容する。ブロックディレクトリ項目は重複しないブロックアドレス値範囲の中で記憶され、各々の範囲は別々のブロックディレクトリページに割り当てられる。範囲の中ではブロックアドレス値に従って項目が序列される。目標ブロックアドレスのブロックディレクトリ項目は、１つのブロックディレクトリページを読み出すことにより、またそのページの中でバイナリ探索を遂行することにより、見つけることができる。このようにしてブロックディレクトリは、ブロックアドレスに従って特定のブロックレコード項目を見つける簡便な手段を提供する。

用途によっては、ブロックアドレス以外の基準によってブロックを探索することが望ましい。場合によっては、ブロックに記憶されるデータに関連する記述子値をこのような探索に使用できる。例えば、再生の目的で、有効データが最も少ない不完全ブロックを識別することが望まれるかもしれない。このようなブロックを見つける一方法として、収容された有効データ量が最も少ないブロックがどれなのかを判定するために全ブロックのレコード項目を探索する。しかし、そのような探索によって多大な負担が加わるかもしれない。一代案では、収容される有効データ量（有効データ容量）に従ってブロックが序列されるブロックのリストを保守する。この場合は収容された有効データ量の順にブロックがリストされるから、有効データ量が最も少ないブロックを識別するには、そのリストの中の最初（または最後）の項目を読み出すだけでよい。同様に、一定量の有効データを持つブロックが必要ならば、バイナリ探索でこのようなブロックを速やかに識別できる。ブロックに記憶される有効データ量はリスト項目の中の記述子値によって与えられる。このような記述子値は、ブロックに記憶されるデータを記述する。これは、ブロックの物理位置を記述する（第一の例で記述子値として使われる）ブロックアドレスと対照をなす。

レコードのフィールドの中で規定されるブロック内の有効データ量の記述子値に従ってブロックレコードにアクセスするため、２段階探索プロセスを取り入れたメカニズムが提供される。この内容アドレス指定メカニズムを使用できるブロック分類の場合、有効データ容量値を収容する項目は、ブロックディレクトリの中で別々のリストページに記憶される。これらのブロックリスト項目は重複しない有効データ容量値範囲の中で記憶され、各々の範囲は別々のブロックリストページに割り当てられる。範囲の中では有効データ容量値に従って項目が序列される。各々のブロックリスト項目はブロックアドレスを収容し、そのアドレスは明確にブロックディレクトリ項目を識別する。ブロックリスト項目５１１はブロックアドレス５１３を収容し、これはブロックアドレス５０６と同じであり、よってブロックディレクトリ項目５０１を識別する。ブロックリスト項目５１１はまた、ブロックアドレス５１３を有するブロックの有効データ容量５１５を収容する。目標有効データ容量値のブロックディレクトリ項目は、１つのリストページを読み出すことにより、そのページの中でバイナリ探索を遂行して目標有効データ容量値を持つ項目を見つけることにより、さらに１つのディレクトリページを読み出すことにより、次いでそのディレクトリページの中でバイナリ探索を遂行して目標ブロックアドレスを持つ項目を見つけることにより、見つけることができる。

バイナリ探索は、単にページの記述子値範囲の中間にある項目を調べることを意味する場合がある。この項目の記述子値と探している記述子値との比較に基づき、探索はページの半分に限定される。そしてこの半ページの中間にある項目も同様に調べ、探索はページの４分の１に限定される。連続するステップの後には、探している記述子値を有する１つ以上の項目が見つかる。別の例では、探している記述子値がリストの中で最下位（または最上位）であるため、バイナリ探索は必要ない。したがって、リスト内の最初（または最後）の項目が選択される。

ブロックレコードはブロックディレクトリの中の項目によって直接アドレス指定できる。ブロックレコードのページは、同じまたは別のブロックレコードブロック内のプログラムされていない位置へページを移す読み出し／修正／書き込み操作によって更新される。ページ内のブロックレコードはどれも、同じブロックディレクトリページの中にある項目に対応しなければならない。しかし、１つのディレクトリページで複数のブロックレコードページの項目を収容できる。よって、ブロックレコードページの更新にあたっては、ただひとつのブロックディレクトリページを修正すればよい。

ブロックディレクトリ
ブロックディレクトリは、ブロックアドレスによってブロックを識別し、対応するブロックレコードの位置を指示する、序列された項目の集まりである。ブロックレコードの保守が行われる各ブロックにつき１項目がブロックディレクトリの中に存在する。この例では、不完全ブロック、用済みブロック、コンプリート共通ブロック、および消去済みブロックの各ブロックにつき１項目が存在する。ブロックディレクトリは１つ以上のディレクトリブロックに収容される。

図６は、用済みブロックと不完全ブロックのリストページを収容するディレクトリブロック６２１を示している。図６はまた、ディレクトリブロックの中にあるディレクトリページを示している。各ディレクトリブロックは一定数の論理ページを収容し、この論理ページの各々は、これを使用可能な次の物理ページへ再度書き込むことによって更新できる。有効項目を収容するページには論理ページ番号が割り当てられる。この例で、ディレクトリブロック内の論理ページ数はブロック内の物理ページ数の２５％に指定される。他の例ではこれとは別の制限を指定できる。ディレクトリブロックの最後のページが書き込まれた後には、有効ページの全てを消去済みブロックへ書き込むことにより、そして元のディレクトリブロックを消去することにより、ブロックが圧縮される。

ブロックディレクトリページ
ブロックディレクトリページは、１組のブロックディレクトリ項目を、それらのブロックアドレス値の順に収容する。図７Ａにはブロックディレクトリページ７３１の一例が示されている。有効ブロックディレクトリ項目７３３はブロックディレクトリページ７３１の中で一連の項目位置を占めるが、ページ全体を埋め尽くす必要はないため、消去済みの空間が残ることがある。各々のブロックディレクトリページはレコードインデックス（後述する）を収容する。ここで、ブロックディレクトリページ７３１はレコードインデックス７３５を収容する。ブロックディレクトリ項目７３３の中に用済み項目はなく、ブロックアドレス値は連続しなくともよい。ある１つのブロックディレクトリページにおけるブロックアドレス値の範囲は、別のブロックディレクトリページにおけるブロックアドレス値の範囲に重複しない。

ブロックの項目を挿入する必要がある場合は、その新しいブロックのブロックアドレス値をブロックアドレス範囲に含むブロックディレクトリページが、ディレクトリインデックスの情報から識別される。新しい項目はブロックアドレス範囲の中の適切な位置に挿入され、ブロックディレクトリページは再度書き込まれる。項目を削除しなければならない場合は、その項目を省いてブロックディレクトリページが圧縮され、再度書き込まれる。

満杯になったブロックディレクトリページへ追加を行わなければならない場合は、空き論理ページが新しいブロックディレクトリページとして割り当てられ、満杯になったブロックディレクトリページのブロックアドレス範囲は２つのほぼ等しい重複しない範囲に分割され、それらは２つの使用可能なブロックディレクトリページに書き込まれる。

ブロックアドレス範囲が隣接する２つのブロックディレクトリページの総有効項目数がしきい値（この例では、１ブロックディレクトリページにおける項目位置数の７０％）を下回ると、２つのブロックディレクトリページの範囲は統合され、２つのブロックディレクトリページのうちの一方に書き込まれる。次いで、他方の未使用ページは空き論理ページとなる。

この例のブロックディレクトリ項目７３７は２つのフィールド、すなわち（１）ブロックアドレスと、（２）対応するブロックレコードのポインタとを収容する。このポインタは、ブロックレコードページの論理識別子と、ページ内のある特定のブロックレコードのバイトオフセットとを識別する。ブロックレコードページ論理識別子は、同じブロックディレクトリページの中にある項目によって参照される最高１６個のブロックレコードページのうちの１つを識別する。これは、その項目を収容するブロックディレクトリページの中のレコードインデックスフィールドによって物理ブロックアドレスとページ番号とへ変換される。バイトオフセットは、識別されたブロックレコードページの中でブロックレコードの位置を識別する。

各々の有効ブロックディレクトリページとブロックリストページの中には単独の有効レコードインデックスフィールドが存在する。これは、ブロックレコードページの論理識別子をブロックレコードページが位置するところのページ番号と物理ブロックアドレスとに変換するために使われる。レコードインデックス７３５は、ブロックディレクトリページ７３１のいずれかの項目の中で使われる各論理識別子につき１つの項目（例えば、項目７３９）を収容する。１つのブロックディレクトリページの中でブロックディレクトリ項目により最高１６個のブロックレコードページが参照される。したがって、４ビット論理識別子が使用される。かくして個々のブロックディレクトリ項目は、対応するブロックレコードページの長い物理ページ位置の代わりに４ビット識別子を使用できる。レコードインデックスフィールドは、ブロックディレクトリページ内の全項目のためにこれらの論理識別子を変換する役割を果たす。

有効ディレクトリインデックスフィールド７４１は、最後に書き込まれたブロックディレクトリまたはブロックリストページにのみ存在する。それ以前に書き込まれたページ内のディレクトリインデックスフィールドの情報は用済みである。この目的は、ブロックディレクトリ項目とブロックリスト項目の序列と、論理ページから物理ページへのマッピングとを支援することにある。これが提供する構造では、ブロックディレクトリブロック内の個々のページに関する最新データが記憶される。ディレクトリインデックスは、論理ページ番号に従って序列される項目７４３などの項目を各可能な論理ページにつき収容する。各項目には４つのフィールドがある。
（１）論理ページの割り当て状態フラグ
（２）ページのタイプ、例えばブロックディレクトリ、ＰＢリスト、またはＯＢリスト
（３）ブロックディレクトリページ内の最初の項目のブロックアドレス、またはリストページ（ＰＢまたはＯＢ）内の最初の項目の有効データ容量値（これにより各論理ページでブロックアドレスまたは有効データ値の範囲を確立し、キャッシュできる。）
（４）論理ページのマッピングにあたるブロックディレクトリの中の物理ページへのポインタ

ブロックリストページ
ブロックリストページは、１ブロック分類につき１組のブロックリスト項目を、ブロックに収容されたデータ（例えば、ブロックに収容された有効データ量）を記述する記述子値の順に、収容する。図７Ｂにはブロックリストページ７５１の一例が示されている。この例で、ブロックリストページはＰＢリストページまたはＯＢリストページである。図７ＢはＯＢリストページ７５１を示している。有効ブロックリスト項目７５３はブロックリストページ７５１の中で一連の項目位置を占めるが、ページ全体を埋め尽くす必要はない。ブロックリストページの中には通常、用済み項目はない。ブロックリスト項目７５３は記述子値によって序列されるが、記述子値は連続しなくともよく、繰り返すことができる。この例で、有効データ容量値は連続しなくともよく、繰り返すことができる。ある１つのブロックリストページの記述子値の範囲は、同一ブロック分類の別のブロックリストページの記述子値の範囲に重複しない。

この例で使われる記述子値は有効データ容量であるが、別の記述子値を使用することもできる。例えば、ブロック内の消去済み容量を記述子値として使用できる。再生のためブロックを所望の順序でリストするため、有効データ量と消去済み容量の組み合わせから記述子値を導き出すことができる。リストは、場合によっては重複してよい。この場合、２つの異なるリストの中に同じブロックが現れることがある。例えば、ブロックを、そこに収容される有効データ量に従ってリストすると同時に、（別のリストでは）そこに収容される消去済みの空間の量に従ってリストすることができる。

ブロックの項目を挿入する必要がある場合は、その新しいブロックの有効データ容量値を有効データ容量範囲に含むブロックリストページが、ディレクトリインデックスの情報から識別される。ブロックリストページは再度書き込まれ、新しい項目は、この有効データ容量値に従ってページの適切な位置に挿入される。項目を削除しなければならない場合、その項目を省いて、新しい物理位置にブロックリストページが再度書き込まれる。

満杯になったブロックリストページへ追加を行わなければならない場合、空き論理ページが新しいブロックリストページとして割り当てられ、満杯になったブロックリストページの有効データ範囲は２つのほぼ等しい重複しない範囲に分割され、それらは２つの使用可能なブロックリストページに書き込まれる。

範囲が隣接する２つのブロックリストページの総有効項目数が所定のしきい値（この例では、１ブロックリストページにおける項目位置数の７０％）を下回ると、２つのブロックリストページの範囲は統合され、２つのブロックリストページのうちの一方に書き込まれる。そして、他方の未使用ページは空き論理ページとなる。

ブロックリスト項目７５５は２つのフィールド、すなわち（１）ブロックアドレスと、（２）記述子値とを収容し、この例における記述子値は、ブロック内の有効データ量を示す値である。第１の例と違って、ブロックアドレスによって序列されるリストはない（しかし、ディレクトリはブロックアドレスによって序列される）。この例において、リストはブロックアドレスを含み、このブロックアドレスからディレクトリ項目が見つかり、さらにこのディレクトリ項目が対応するレコードの位置を順に指示する。よって、この例において、リスト項目７５３はレコードを直接指示しない。ブロックリストはディレクトリインデックスを収容できるが、有効なディレクトリインデックスを収容するのは最後に書き込まれたページだけである。図７ＢのＯＢリストページは用済みのディレクトリインデックス７５７を収容する。

ブロックレコード
ブロックレコードはレコードの集まりであり、各レコードは、ブロックアドレスによって識別されるブロックの情報を収容する。各ブロックディレクトリ項目につき１つのレコードが存在する。ブロックレコードはブロックディレクトリ項目によってアドレス指定され、ブロックレコードページが修正されるときにはブロックディレクトリページを修正しなければならない。

ブロックレコードは、図８に示すレコードブロック８６１などのような、１つ以上の専用レコードブロックに収容される。第１の例と違って、ブロックリストとブロックレコードは同じブロックの中にまとめて記憶されない。ただひとつのブロックレコードブロックがプログラムされていないページを収容し、ここへブロックレコードを書き込むことができる。ブロックレコード情報はどれも、ブロックレコード書き込みポインタによって識別されるこのブロックの中のプログラムされていない次のページ位置にプログラムされる。ブロック内の最後のページがプログラムされると、ブロックレコード書き込みポインタは消去済みブロックの最初のページへ移される。ブロックレコードブロックは、ブロックレコードページが再度書き込まれるときに用済みページを収容することができる。いくつかの実施形態において、有効ブロックレコードページは、ブロックレコードページが再度書き込まれてページ内のレコードが常に用済みになるときに用済みレコードを収容しない。別の実施形態において、用済みレコードが有効ブロックレコードページに残ることがある。しかし、用済みレコードのディレクトリ項目は削除されるかまたは有効レコードを指示する項目に置き換えられるので、用済みレコードはアクセスされない。レコードページの中の用済みレコードは、レコードページが再度書き込まれるときにコピーされない。

ブロックレコードページは、１つのブロックディレクトリページの中にあるブロックディレクトリ項目によって参照される１組のブロックレコードを、このブロックディレクトリページ内の項目と同じ順序で収容する。図９は、ブロックレコードページ９６５の一例を示している。ブロックディレクトリページは複数のブロックレコードページを参照できる。ブロックレコードページの修正にあたっては、ただひとつのブロックディレクトリページを修正すればよい。第１の例と違って、ブロックレコードページはブロックディレクトリ項目によって直接識別されるため、この例のブロックレコードページはブロックレコードインデックスを含まない。

ブロックレコードページは、これを読み出すことにより、そして１つ以上のブロックレコードを更新または追加することにより修正できる。いずれの用済みブロックレコードもページの圧縮によって削除され、ページは、ブロックレコード書き込みポインタによって識別される位置にプログラムされる。

ブロックレコードページヘッダは、ブロックレコードページに関連するブロックディレクトリページへの参照符と、このブロックレコードページにおけるブロックレコード情報の長さとを記憶する。ブロックレコードページヘッダはまた、ブロックレコードページが書き込まれたときにブロックレコードブロックの各々に存在する用済みページ数のレコードを記憶する。この情報は、最後に書き込まれたブロックレコードページヘッダの中にあるものだけが有効である。

個々のブロックレコード項目のサイズは不定である。よって、コンプリート共通ブロックのレコードは消去済みブロックのレコードより大きくなることがある。第１の例と違って、別個の共通ブロックレコード領域は必要ない。この例のレコードブロックは、ブロックの属性を定義する次のフィールドを持つ。
（１）ブロックアドレス
（２）ブロックのタイプ、ＰＢ、ＯＢ、ＣＣＢ、またはＥＢ
（３）ブロック内の有効データ容量
（４）ブロック内のページ書き込みポインタの位置
（５）ブロック内にデータが存在するファイルの合計数
（６）ブロック内にデータが存在する各ファイルのファイルＩＤ

他の例では、異なる記述子値を含む異なるフィールドをレコードに収容してよい。

第２の例におけるブロックレコードの再生プロセス
ブロックレコードは１つ以上のレコードブロックの中に収容され、ブロックディレクトリ項目によって直接アドレス指定される。新規または更新済みブロックレコードをプログラムするにあたって使用できる消去済みページは、ただひとつのレコードブロックに収容される。それ以外の全てのレコードブロックで全てのページがプログラムされていたとしても、完全に用済みまたは部分的に用済みのページがブロックに収容されることがある。用済みブロックレコードによって占められる容量の再生は、再生される次のブロックとして１つのレコードブロックを指定することにより、そしてこの再生ブロックからブロックレコード書き込みポインタによって現在指定されているページへページを徐々にコピーすることにより、その後に再生ブロックを消去することにより、遂行される。

レコードブロックに対する前の再生プロセスが完了し、前の再生ブロックが消去されると、再生ブロックが選択される。用済みページ数が最高のレコードブロックが再生ブロックとして選択される。各レコードブロックの用済みページ数は、最後に書き込まれたブロックレコードページのブロックレコードページヘッダに記録される。ブロックレコード書き込みポインタを収容するレコードブロックは再生のために選択されないことがある。選択されたレコードブロックは、再生プロセスが完了してブロックが消去されるまで再生ブロックであり続ける。次いで、消去されたブロックは消去済みブロックのプールへ加えられ、ホストデータを含むあらゆる類のデータを記憶するために再び使用できる。よって、ブロックは暫くの間専用レコードブロックであり続けるが、レコードブロックとして永久的に指定されるのではない。

用済みページを収容するブロックレコードブロックを再生するプロセスでは、ブロックから、有効ブロックレコードを収容する少数のページを、ブロックレコード書き込みポインタによって指定されるページへ、スケジュールされた間隔で段階的にコピーする。良好な性能のため、１段階にコピーされるページの数はメタページに収容されるページの数になる。しかし、場合によっては、これよりも少ないページが書き込まれる。ブロックレコード書き込みポインタのところでページをプログラムすることは、メタページに対する１回のプログラミング操作として遂行できる。再生ブロックにおけるページの段階的コピー操作は、４つのメタページに収容されるページ位置数を通過するブロックレコード書き込みポインタの進捗によって規定される間隔でスケジュールできる。メタページをプログラムするには、書き込みポインタは、段階的コピー操作がスケジュールされるときに物理メタページの最初のページを指示しなければならない。

前述したブロックレコードブロックの再生プロセスとは対照的に、ディレクトリブロックの再生プロセスでは、ディレクトリブロックに消去済みの空間が残っていないときにそのブロックディレクトリブロックを圧縮するだけでよい。常時最大２５％（この例の論理容量は物理容量の２５％）の有効ページを持つブロックディレクトリブロックを圧縮すると、少なくとも７５％の消去済みの空間を有するブロックになる。圧縮が行われると、データのコピー元にあたるブロックは無効ブロックとなり、消去されて消去済みブロックとなる。次いで、このブロックは消去済みブロックのプールへ加えられ、ホストデータを含むあらゆる類のデータを記憶するために使用できる。よって、ブロックは暫くの間専用ディレクトリブロックであり続けるが、ディレクトリブロックとして永久に指定されるのではない。

第２の例の構造の更新
メモリアレイでブロックにデータが書き込まれるとき、またはファイルが削除されるときには、１つ以上のブロックレコードを更新する必要がある。また、対応するブロックディレクトリおよびリスト項目を更新する必要がある。図１０に示された次のプロセスは、第２の例の各種構造の更新を説明するものであり、このとき（既にある程度の用済みデータを収容する）不完全ブロックには追加の有効データが記憶され、ブロックは用済みブロックになる。
（１）追加データを記憶するブロックのアドレスを受け取る。
（２）このブロックのディレクトリ項目１７５を収容するディレクトリページ１７３の物理ページ位置を判定するため、ブロックディレクトリブロック１７０の最終書き込みページでディレクトリインデックス１７１を調べる。
（３）ブロックの項目１７５を見つけるため、ディレクトリページ１７３の中でバイナリ探索を遂行する。
（４）項目１７５の論理識別子からレコードインデックス１７７の情報に沿って、ブロックレコードブロック１８１の中でこのブロックのレコード１８３を収容する物理ページ１７９を判定する。受け取ったアドレスに対応する正しいレコード１８３を見つけるため、ディレクトリ項目１７５の中のオフセットを使用する。
（５）レコード１８３からブロックの分類を判定する。追加データの記憶によって分類が変化するか否かを判定する。ここでブロックは不完全ブロックであり、このブロックに残された空間は追加データで満たされるから、このブロックは用済みブロックになる。
（６）レコードページ１８３の内容を、書き込みポインタ１８５によって指示される位置へコピーし、対象ブロックのレコード１８３は、異なるタイプのブロック、有効データ、ページ書き込みポインタの位置等を反映させるために更新される。
（７）ディレクトリページ１７３をブロックディレクトリブロック１７０の使用可能な次の物理ページへコピーする。レコードページの新しい物理位置を反映させるため、更新された項目とレコードインデックスを新しいディレクトリページに書き込む。また、新しい物理ページでディレクトリインデックスを更新する。
（８）ブロックの項目１８９を収容する不完全ブロックリストページ１８７の物理ページ位置を判定するため、ディレクトリインデックスを再び調べる（場合によっては複数のリストを調べる）。
（９）記述子値が対象ブロックのそれに等しいリスト項目１８９を見つけるため、ページ１８７の中でバイナリ探索を遂行する。複数のリスト項目が記述子値を有する場合は、ブロックアドレスにより一致する全ての項目を探索する。
（１０）不完全ブロックリストページ１８７を新しい位置へコピーし、対象ブロックの項目１８９は削除される。新しい不完全ブロックページは、不完全ブロックページの新しい物理位置で更新されたディレクトリインデックスを含む。
（１１）対象ブロックの有効データ量を含む、ブロック範囲当たりの有効データをカバーする用済みブロックリストページの物理ページ位置を判定するため、ディレクトリインデックスを再び調べる（図示せず）。
（１２）用済みブロックリストページをコピーし、対象ブロックの新しい項目を、ブロック内の現在の有効データ量に基づき、適切なオフセットのところに追加する。新しい用済みブロックリストページは、用済みブロックリストの新しい位置を示す更新済みディレクトリインデックスを含む（図示せず）。

前述したステップは必ずしも示されたとおりの順序で遂行されない。いくつかのステップは並行して遂行できる。例えば、更新済みの用済みブロックリストページと更新済み不完全ブロックリストページの書き込みは、メタブロック書き込みの一部として並行してよい。

詳細な第３の例
第３の例では、メモリアレイの各ブロックにつき常時レコードを保守する。これには１つ以上の追加のブロック分類が関係し、例えば用済みデータを収容しないファイルブロックのための追加の分類を、図４に示された第２の例の分類に加えることができる。各ブロックごとにレコードを保守すると保守する各レコードの合計数が増えるが、より簡素な構造を使用することができる。第３の例は、ブロックごとにレコードを用意する点を除き、第２の例と同様に進行する。

例えば、全てのブロックのためのレコードを保守する場合は、ディレクトリ項目も全てのブロックのために保守する。ディレクトリ項目は一定の均等サイズを有する。したがって、ディレクトリページには、ブロックアドレスによって順次に序列される一定数の項目が収容できる。よって、各ディレクトリページは一定のブロックアドレス範囲をカバーする。このようなページの中の項目はそれぞれのブロックアドレスに従って所定のオフセットをとるため、各項目の中で別々にブロックアドレスを記録する必要はない。ある特定のブロックのディレクトリ項目を見つけるには、そのブロックを含むブロックアドレス範囲をカバーするディレクトリページを見つけ、そのページの中で、ディレクトリページの最初の項目のブロックアドレスと所望のブロックアドレスとの差によって決まるオフセットのところにある項目まで進めばよい。したがって、ディレクトリページのバイナリ探索は必要ない。対照的に、レコードのサイズは通常ならば不定であり、常に一定数の項目がレコードページの中で保守されるとは限らない。この例ではこれまでの例と違って、リスト内に項目を持たないブロックのためのレコードが保守される。

メモリ内の各ブロックにつきレコードを保守することは、いくつかの用途にとって好都合である。例えば、ブロックの物理的特性について記述子を保守できる。このような記述子の一例として消去カウントがある。消去カウントは、消去され損耗レベル化の目的に使用できる特定のブロックの消去回数を示す。ブロックの消去カウントに従って１つ以上のリストでブロックを序列できる。また、ブロックが最後に消去されたときのタイムスタンプをレコードに含むことができ、こうすれば最後の消去から経過した時間に従ってブロックをリストの中で序列できる。

これまで本発明の様々な態様をその例示的な実施形態との関係で説明してきたが、添付の特許請求の範囲の全範囲内においてその権利が保護されるべきであることが理解できよう。

第１の例によるブロック分類の表を示す。 第１の例によるレコードブロックのページを示す。 図２のレコードブロックの個々のページの詳細図を示す。 第２の例によるブロック分類の表を示す。 ブロックレコードブロックにある対応するブロックレコードを指示するブロックディレクトリブロック内のブロックディレクトリ項目を示す。 ディレクトリブロックのページ構造の詳細を示す。 レコードインデックスとディレクトリインデックスとを含む、図６のブロックディレクトリページの構造を示す。 図６の用済みブロックリストページの構造を示す。 レコードブロックのページ構造の詳細を示す。 図８のレコードページの構造をより詳細に示す。 ブロックレコードと関係する構造との更新過程にあるディレクトリブロックとレコードブロックとを示す。

Claims (34)

1. メモリシステムであって、
   データを各々収容する第１の複数の個別に消去可能なブロックを含む不揮発性メモリアレイと、
   前記第１の複数のブロックの各々につき項目を収容するリストであって、前記リスト内の前記項目は、前記第１の複数のブロックの各々に記憶される有効データ量に従って序列されるリストと、
   を備えるメモリシステム。
2. 請求項１記載のメモリシステムにおいて、
   複数のレコードをさらに備え、前記複数のレコードの各々は前記第１の複数の個別に消去可能なブロックのうちの１ブロックに対応し、前記複数のレコードの各々はそれに対応するブロックに関する情報を収容するメモリシステム。
3. 請求項２記載のメモリシステムにおいて、
   前記リスト項目は第１のブロックの中の複数のリストページにて保守され、前記複数のレコードは第２のブロックの中のレコードページにて保守されるメモリシステム。
4. 請求項１記載のメモリシステムにおいて、
   前記複数のブロックは、消去済みの空間と有効データの両方を収容する不揮発性メモリアレイの全ブロックからなるメモリシステム。
5. 請求項１記載のメモリシステムにおいて、
   前記複数のブロックは、用済みデータを収容しかつ消去済みの空間を収容しない不揮発性メモリアレイの前記ブロックの全部からなるメモリシステム。
6. 不揮発性メモリアレイであって、
   複数の個別に消去可能なブロックと、
   前記複数のブロックのための複数のレコードであって、前記複数のレコードの各々は前記複数のブロックのうちの１ブロックに関する情報を収容する複数のレコードと、
   複数のディレクトリ項目を収容するディレクトリであって、前記複数のディレクトリ項目の各々は前記複数のレコードのうちの１レコードの位置を含むディレクトリと、
   複数のリスト項目を収容するリストであって、前記複数のリスト項目の各々は前記複数のブロックのうちの１個の個別のブロックに記憶されるデータを記述し、前記複数のリスト項目はそれぞれの記述子値によって序列されるリストと、
   を備える不揮発性メモリアレイ。
7. 請求項６記載の不揮発性メモリアレイにおいて、
   前記複数のレコードは第１のブロックに置かれ、前記ディレクトリと前記リストは第２のブロックにて保守される不揮発性メモリアレイ。
8. 請求項６記載の不揮発性メモリアレイにおいて、
   前記記述子値は、前記複数のブロックのそれぞれのブロックに記憶される有効データ量を表す不揮発性メモリアレイ。
9. 請求項６記載の不揮発性メモリアレイにおいて、
   前記複数のブロックは、消去済みの空間と有効データの両方を個別に収容する前記不揮発性メモリアレイ内の前記ブロックの全部からなる不揮発性メモリアレイ。
10. 請求項６記載の不揮発性メモリアレイにおいて、
    前記複数のブロックは、用済みデータを個別に収容しかつ消去済みの空間を収容しない前記不揮発性メモリアレイの前記ブロックの全部からなる不揮発性メモリアレイ。
11. 請求項６記載の不揮発性メモリアレイにおいて、
    前記複数のブロックは、前記不揮発性メモリアレイの全ブロックからなる不揮発性メモリアレイ。
12. 請求項６記載の不揮発性メモリアレイにおいて、
    前記リストは、別個のリスト項目範囲を各々記憶する複数のページにて保守される不揮発性メモリアレイ。
13. メモリセルのブロックにグループ分けされ前記ブロックのページでデータを再プログラムする前に消去される記憶セルを具備する不揮発性メモリシステムであって、
    データを記憶する第１の複数のブロックと、
    前記第１の複数のブロックのうちの対応する１ブロックに記憶されるデータを記述する記述子値を少なくとも個別に含む複数のレコードを収容する第１の複数のページと、
    前記第１の複数のページにおけるレコードの位置に対するポインタを収容する第２の複数のページであって、前記第１の複数のページのうちの個別の１ページ中にある有効レコードは、前記第２の複数のページのうちの１ページに記憶されるポインタによって指示されるレコードに限定される第２の複数のページと、
    を備える不揮発性メモリシステム。
14. 請求項１３記載の不揮発性メモリシステムにおいて、
    前記第１の複数のページは１つ以上のブロックからなる第１のグループに置かれ、前記第２の複数のページは１つ以上のブロックからなる第２のグループに置かれる不揮発性メモリシステム。
15. 請求項１３記載の不揮発性メモリシステムにおいて、
    前記第１の複数のページは、前記第１の複数のブロックのうちの１ブロックではない第１のブロックに置かれ、前記第２の複数のページは、前記第１の複数のブロックのうちの１ブロックではない第２のブロックに置かれる不揮発性メモリシステム。
16. 請求項１３記載の不揮発性メモリシステムにおいて、
    第３の複数のページに置かれるリストをさらに備え、前記リストは前記第１の複数のブロックのそれぞれに個別に対応する複数の項目を収容し、項目はこれに対応するブロックの記述子値を収容する不揮発性メモリシステム。
17. ブロック消去可能な不揮発性メモリアレイを操作する方法であって、
    前記不揮発性メモリアレイの複数のブロックの各々につきリスト項目を収容するリストを保守するステップを備え、前記リスト項目は、前記複数のブロックのそれぞれ個別に記憶される有効データ量に従って序列される方法。
18. 請求項１７記載の方法において、
    前記不揮発性メモリアレイの前記複数のブロックの各々につきレコードを保守するステップをさらに備え、前記複数のブロックのうちの１ブロックのための個別のレコードは前記ブロックの物理アドレスを含み、各リスト項目はレコード項目へリンクされる方法。
19. 請求項１８記載の方法において、
    リスト項目は第１のブロックの中にあるリストページにて保守され、前記レコードは第２のブロックの中にあるレコードページにて保守される方法。
20. 請求項１７記載の方法において、
    前記複数のブロックは、消去済みの空間と有効データの両方を収容する前記不揮発性メモリアレイの全ブロックからなる方法。
21. 請求項１７記載の方法において、
    前記複数のブロックは、用済みデータを収容しかつ消去済みの空間を収容しない前記不揮発性メモリアレイの全ての前記ブロックからなる方法。
22. ブロック消去可能な不揮発性メモリアレイを操作する方法であって、
    前記メモリアレイ内の複数のブロックのための複数のレコードを保守するステップであって、前記複数のレコードの各々は前記複数のブロックのうちの１ブロックに関する情報を収容するステップと、
    複数のディレクトリ項目を収容するディレクトリを保守するステップであって、前記複数のディレクトリ項目の各々は前記複数のレコードのうちの１レコードに関する位置情報を含むステップと、
    複数のリスト項目を収容するリストを保守するステップであって、前記複数のリスト項目の各々は前記複数のブロックのうちの１個の個別のブロックに記憶されるデータを記述し、前記複数のリスト項目はそれぞれの記述子値によって序列されるステップと、
    を含む方法。
23. 請求項２２記載の方法において、
    前記複数のレコードは第１のブロックにて保守され、前記ディレクトリと前記リストは第２のブロックにて保守される方法。
24. 請求項２２記載の方法において、
    前記記述子値は、前記複数のブロックのうちのそれぞれのブロックに記憶される有効データ量を表す方法。
25. 請求項２２記載の方法において、
    前記複数のブロックは、消去済みの空間と有効データの両方を個別に収容する前記不揮発性メモリアレイ内の前記ブロックの全部からなる方法。
26. 請求項２２記載の方法において、
    前記複数のブロックは、用済みデータを収容しかつ消去済みの空間を収容しない前記不揮発性メモリアレイ内の前記ブロックの全部からなる方法。
27. 請求項２２記載の方法において、
    前記複数のブロックは、前記不揮発性メモリアレイ内の前記ブロックの全部からなる方法。
28. 請求項２２記載の方法において、
    前記リストは、別個のリスト項目範囲を各々記憶する複数のページにて保守される方法。
29. 請求項２８記載の方法において、
    所定の記述子値を有するブロックを、前記所定の特性に一致するリスト項目を前記リストで探索することによって探索するステップをさらに含む方法。
30. 請求項２９記載の方法において、
    前記所定の特性は、前記リスト内のリスト項目の最小有効データ量である方法。
31. メモリセルのブロックにグループ分けされ前記ブロックのページでデータを再プログラムする前に消去される記憶セルを具備する不揮発性メモリシステムを操作する方法であって、
    第１の複数のブロックでデータを記憶するステップと、
    前記第１の複数のブロックのうちの対応する１ブロックに記憶されるデータを記述する記述子値を少なくとも個別に含むレコードを第１の複数のページにて保守するステップと、
    前記第１の複数のページにおけるレコードの位置に対するポインタを第２の複数のページにて保守するステップであって、前記第１の複数のページのうちの個別の１ページの中にある有効レコードは、前記第２の複数のページのうちの１ページに記憶されるポインタによって指示されるレコードに限定されるステップと、
    を含む方法。
32. 請求項３１記載の方法において、
    前記第１の複数のページは１つ以上のブロックからなる第１のグループに置かれ、前記第２の複数のページは１つ以上のブロックからなる第２のグループに置かれる方法。
33. 請求項３１記載の方法において、
    前記第１の複数のページは、前記第１の複数のブロックのうちの１ブロックではない第１のブロックに置かれ、前記第２の複数のページは、前記第１の複数のブロックのうちの１ブロックではない第２のブロックに置かれる方法。
34. 請求項３１記載の方法において、
    前記第１の複数のブロックのそれぞれと対応する記述子値とのリストを第３の複数のページにて保守するステップをさらに含み、前記リスト項目は記述子値によって序列される方法。

Images