【手続補正書】
【提出日】平成25年6月25日(2013.6.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ユニフォームアクセスインデックス付け処理を、ノンユニフォームアクセスメモリ（２６，２３５）に適合させる方法であって、前記方法は、
ａ）  インデックスレコードのディクショナリを前記ノンユニフォームアクセスメモリ（２６）に記憶するステップであって、前記インデックスレコードはインデックスキーを含む、ステップと、
ｂ） 論理バケット識別子を前記メモリの物理バケット位置にマッピングするためのバケット変換テーブル（１７，３００）を維持するステップであって、インデックスキー（１４１）を置き換えハッシングすることにより論理バケット識別子を生成するステップを含み、前記テーブルは、前記論理バケット識別子の、関連付けられた前記インデックスレコード（３１０，３１１，３１２）が記憶された前記メモリの物理バケット位置（２２，３０９）へのマッピングを含む、ステップと、
ｃ） 複数の前記インデックスレコードをキャッシュ（２３）内に集めるステップであって、該ステップは、前記メモリの物理バケット位置への前記キャッシュからのレコードの集まりの順次書き込みとしての書き込みに先立つ、ステップと、
ｄ）  前記バケット変換テーブル（１７）を前記集まりの中のインデックスレコードに対する物理バケット位置で更新するステップと
を含む方法。
【請求項２】
請求項１に記載の方法であって、１つ又は複数の順次インデックスレコードを、前記メモリ（２６，２３）から前記キャッシュへ読み出すステップと、
前記１つ又は複数のインデックスレコードが読み出されたメモリ内の物理位置を、フリーとして指定するステップと
を含む方法。
【請求項３】
請求項１又は２に記載の方法であって、前記ブロック内の任意の有効インデックスレコードを前記キャッシュに読み出すこと、及び、そのようなインデックスレコードが読み出された前記メモリ内の物理位置を、フリーとして指定することによって、前記メモリ内の複数の順次物理バケット位置（２２，３０９）をフリーブロックとするステップを含む方法。
【請求項４】
請求項１から３の何れか一項に記載の方法であって、複数の論理バケット識別子を前記インデックスキーに対して生成すること、前記置き換えハッシングの関数は、複数の生成された前記論理バケット識別子の間で選択することを特徴とする方法。
【請求項５】
請求項１から４の何れか一項に記載の方法であって、前記メモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含むことを特徴とする方法。
【請求項６】
請求項１から５の何れか一項に記載の方法であって、前記メモリは、ランダム書き込みアクセス時間、ランダム読み出し−修正−書き込みアクセス時間、順次書き込み、アラインメント制約、消去時間、消去ブロック境界及び摩耗のうちの１つ又は複数によって制限されることを特徴とする方法。
【請求項７】
請求項１から６の何れか一項に記載の方法であって、前記バケットのサイズは、ページまたは部分ページ等の前記メモリの最小書き込みサイズの関数であることを特徴とする方法。
【請求項８】
請求項７に記載の方法であって、前記メモリは、複数のページを含む消去ブロックを有することを特徴とする方法。
【請求項９】
請求項１から８の何れか一項に記載の方法であって、前記メモリ内のどの物理バケット位置が有効であるかを追跡するためのバケット有効テーブル（２７１）を維持するステップを含む方法。
【請求項１０】
請求項１から９の何れか一項に記載の方法であって、前記メモリの物理バケット位置（２３）は、１つ又は複数のインデックスレコードのセット、及び、前記バケット変換テーブルへのセルフインデックスを含むことを特徴とする方法。
【請求項１１】
請求項１０に記載の方法であって、前記バケットの前記インデックスレコードは順序付けされないことを特徴とする方法。
【請求項１２】
請求項１から１１の何れか一項に記載の方法であって、前記バケット変換テーブルは、永続メモリに記憶されたことを特徴とする方法。
【請求項１３】
請求項１から１２の何れか一項に記載の方法であって、消去ブロック内のフリー物理バケット位置の数を追跡し、フリーバケット位置のしきい値が満たされたとき、フリー消去ブロックを生成するための処理を実施するステップを含む方法。
【請求項１４】
請求項１から１３の何れか一項に記載の方法であって、前記インデックス付け処理は、インデックスレコードが挿入、削除、ルックアップ及び修正のうちの１以上をされる要求に基づいて、インデックス付けオペレーションを行うことを特徴とする方法。
【請求項１５】
請求項１から１４の何れか一項に記載の方法であって、前記インデックス付け処理は、前記インデックスレコードを記憶する物理バケット位置を読み出し該物理バケット位置に書き込むための論理バケットオペレーションを提示することを特徴とする方法。
【請求項１６】
請求項１から１５に記載の方法であって、前記メモリ（２６）は、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含むことを特徴とする方法。
【請求項１７】
請求項１６に記載の方法であって、ランダム読み出しオペレーションに応答して前記キャッシュに対する追加のバケットを読み出すことにより、フリー消去ブロックを生成するステップを含む方法。
【請求項１８】
請求項１６又は１７に記載の方法であって、スキャベンジング処理（１１４）を実行して、前記キャッシュに対する消去ブロックを読みだすことによりフリー消去ブロックを生成するステップを含む方法。
【請求項１９】
プロセッサに請求項１から１８の何れか一項に記載の方法の前記ステップを実行させるプログラムコードを含むコンピュータプログラム。
【請求項２０】
コンピュータシステムであって、
ノンユニフォームアクセスメモリ（２６）であって、前記メモリの物理バケット位置に記憶されたインデックスレコードのディクショナリを含む前記ノンユニフォームアクセスメモリと、
前記ディクショナリのインデックスキーの置き換えハッシングにより生成された論理バケット識別子を、該インデックスキーに関連付けられたインデックスレコード（３１０，３１１，３１２）が記憶された前記メモリの物理バケット位置にマッピングするためのバケット変換テーブル（１７）と、
前記メモリに書き込まれるインデックスレコードを集めるためのキャッシュ（２３）と、
前記メモリのある物理バケット位置にアクセスするための手段（１８）であって、該ある物理バケット位置は、ユニフォームアクセスインデックス付け処理により前記バケット変換テーブルに供給された論理バケット識別子にマッピングされた、手段と、
前記インデックスレコードの集まりを、前記キャッシュから、前記メモリの少なくとも１つの物理バケット位置に順次書き込むための手段（２４）と、
前記バケット変換テーブル（１７）を前記集まりの中のインデックスレコードに対する少なくとも１つの物理バケット位置で更新するための手段（１９）と
を含むコンピュータシステム。
【請求項２１】
請求項２０に記載のコンピュータシステムであって、インデックスを記憶する前記メモリは物理デバイス層を含み、該物理デバイス層は、ノンユニフォーム読み出し及び書き込みアクセス、並びに、サイズ、アラインメント及びタイミングについての不変性によって特徴付けられたコンピュータシステム。
【請求項２２】
請求項２０又は２１に記載のコンピュータシステムであって、インデックスを記憶する前記メモリは、フラッシュ、相変化及びソリッドステートディスクのメモリデバイスのうちの１つ又は複数を含むことを特徴とするコンピュータシステム。
【請求項２３】
請求項２０から２２の何れか一項に記載のコンピュータシステムであって、インデックスを記憶する前記メモリは、複数の消去ブロックを含むフラッシュメモリデバイスを含み、各消去ブロックは複数のページを含み、各ページは複数のバケットを含むことを特著とするコンピュータシステム。