【手続補正書】
【提出日】平成27年8月17日(2015.8.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ記憶媒体と、
各々がキーを含むタプルを含む１又はそれ以上のマッピングテーブルエントリを各レベルが含む複数のレベルとして構成されたマッピングテーブルと、
前記データ記憶媒体に結合されたデータストレージコントローラと、を備え、前記データストレージコントローラは、平坦化条件を検出したことに応答して、
前記複数のレベルのうちの論理的に時間的に隣接する２又はそれ以上のレベルのグループを識別し、
前記複数のレベル内に新たなレベルを作成し、
前記グループに記憶されているキーのうちの一意のキーが１又はそれ以上の最初のレコードの各々に記憶されていることを検出したことに応答して、前記グループに記憶されている前記１又はそれ以上の最初のレコードを前記新たなレベルに挿入するように構成され、
フィルタ条件を利用して、前記最初のレコードのうちのどのレコードを前記新たなレベルに挿入するかを判断し、前記フィルタ条件は、前記オーバーレイテーブルにより判断される所与のレコードの妥当性を含むことを特徴とするコンピュータシステム。
【請求項２】
前記マッピングテーブルの前記複数のレベルは、時間順レベルとして構成される、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項３】
前記データストレージコントローラは、前記新たなレベル内のレコードをソートするようにさらに構成される、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項４】
前記複数のレベルのうちのあるレベル内の前記マッピングテーブルエントリはキー別にソートされる、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項５】
前記データストレージコントローラは、前記マッピングテーブルに対し、前記マッピングテーブルの更新に対して非同期的に平坦化動作を行うように構成される、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項６】
前記データストレージコントローラは、前記平坦化条件を検出したことに応答して、１又はそれ以上の第２のレコードの各々が、
前記グループ内の同じ非一意的なキーを記憶している２又はそれ以上のレコードに対応していること、及び、
前記グループの前記非一意的なキーを有するレコードを含む最も若いレベル内に存在すること、を検出したことに応答して、前記グループ内に記憶されている前記１又はそれ以上の第２のレコードを前記新たなレベルに挿入するようにさらに構成される、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項７】
前記マッピングテーブル内の１つのレコードがキー値の範囲に対応する、ことを特徴とする請求項６に記載のコンピュータシステム。
【請求項８】
オーバーレイテーブルをさらに備え、前記新たなレベルに挿入された前記第１及び第２のレコードのうちの少なくともいくつかが、前記オーバーレイテーブル内のエントリに基づいて修正される、ことを特徴とする請求項６に記載のコンピュータシステム。
【請求項９】
オーバーレイテーブルをさらに備え、前記グループの少なくともいくつかのレコードが、前記オーバーレイテーブル内のエントリに基づいて前記新たなレベルから省略される、ことを特徴とする請求項６に記載のコンピュータシステム。
【請求項１０】
前記グループ内のキー値の範囲に対応する少なくとも１つのレコードが、前記新たなレベルにおいて、前記少なくとも１つのレコードの部分的な範囲に対応する複数のレコードに置き換えられる、ことを特徴とする請求項７に記載のコンピュータシステム。
【請求項１１】
オーバーレイテーブルをさらに備え、前記グループ内の少なくとも１つのレコードが、前記オーバーレイテーブル内の１又はそれ以上のエントリに基づいて、前記１つのレコードの範囲よりも小さな範囲を有する前記新たなレベル内の新規レコードに置き換えられる、ことを特徴とする請求項７に記載のコンピュータシステム。
【請求項１２】
前記グループ内の所与の複数のレコードが、該所与の複数のレコードがカバーする全ての範囲をカバーする範囲を有する前記新たなレベル内の単一のレコードに置き換えられる、ことを特徴とする請求項７に記載のコンピュータシステム。
【請求項１３】
前記データストレージコントローラは、前記隣接する２又はそれ以上のレベルのグループを前記新たなレベルに置き換えるようにさらに構成される、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項１４】
前記データストレージコントローラは、前記隣接する２又はそれ以上のレベルのグループ内の前記レコードの全てよりも少ないレコードから新たなレベルを作成するようにさらに構成される、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項１５】
前記平坦化条件は、前記マッピングテーブル内のレベル数の現在値又は予測値、前記複数のレベルの１つ又はそれ以上のレベル内のエントリ数の現在値又は予測値、平坦化動作の一部として省略又は修正されるマッピングエントリ数の現在値又は予測値、及び前記システム上の負荷の現在値又は予測値のうちの少なくとも１つに基づく、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項１６】
前記フィルタ条件は、前記新たなレベル内の現在の又は予測されるエントリ数に少なくとも部分的に基づく、ことを特徴とする請求項１に記載のコンピュータシステム。
【請求項１７】
ストレージシステム内で使用する方法であって、
各々がキーを含むタプルを含む１又はそれ以上のマッピングテーブルエントリを各レベルが含む複数のレベルとして構成されたマッピングテーブルを記憶するステップと、
平坦化条件を検出したことに応答して、
前記複数のレベルのうちの論理的に時間的に隣接する２又はそれ以上のレベルのグループを識別するステップと、
前記複数のレベル内に新たなレベルを作成するステップと、
前記グループに記憶されているキーのうちの一意のキーが１又はそれ以上の最初のレコードの各々に記憶されていることを検出したことに応答して、前記グループに記憶されている前記１又はそれ以上の最初のレコードを前記新たなレベルに挿入し、
フィルタ条件を利用して、前記最初のレコードのうちのどのレコードを前記新たなレベルに挿入するかを判断し、前記フィルタ条件は、前記オーバーレイテーブルにより判断される所与のレコードの妥当性を含むことを特徴とする方法。
【請求項１８】
プログラム命令を記憶する非一時的コンピュータ可読記憶媒体であって、前記プログラム命令は、プロセッサにより、
各々がキーを含むタプルを含む１又はそれ以上のマッピングテーブルエントリを各レベルが含む複数のレベルとして構成されたマッピングテーブルを記憶し、
平坦化条件を検出したことに応答して、
前記複数のレベルのうちの論理的に時間的に隣接する２又はそれ以上のレベルのグループを識別し、
前記複数のレベル内に新たなレベルを作成し、
前記グループに記憶されているキーのうちの一意のキーが１又はそれ以上の最初のレコードの各々に記憶されていることを検出したことに応答して、前記グループに記憶されている前記１又はそれ以上の最初のレコードを前記新たなレベルに挿入するように実行可能であり、
フィルタ条件を利用して、前記最初のレコードのうちのどのレコードを前記新たなレベルに挿入するかを判断し、前記フィルタ条件は、前記オーバーレイテーブルにより判断される所与のレコードの妥当性を含むことを特徴とするコンピュータ可読記憶媒体。