本明細書は、冗長性の少ない形式でデータを格納するための方法および装置を記載する。バイナリ・ラージ・オブジェクト（ＢＬＯＢ）は、分割方法に従ってサブブロックに分割され、サブブロックはサブブロック・クラスタに格納される。各ＢＬＯＢは、クラスタ内のサブブロックの隣接シーケンスを識別するサブブロックのスパンのリストとして表示される。記憶装置の冗長性は低減することができる。何故なら、２つの異なるＢＬＯＢのスパンは同じサブブロックを参照することができるからである。サブブロック・ハッシュをサブブロック・クラスタ番号にマッピングするためにインデックスを使用することができる。 （もっと読む）

本発明は、低冗長記憶システムでサブブロックを索引するための方法および装置を提供する。各サブブロックはＫビット・キーにハッシュされ、このサブブロックに対するエントリが、ハッシュ・テーブルのツリーから構成されるインデックス・データ構造に追加される。他の態様によれば、ツリーの頂部をアレイにより置換することにより、データ構造は、比較的スムースな成長をしながら、ランダム・キーに対してＯ（１）アクセス時間を達成することができる。 （もっと読む）

本発明は、データの特定のサブブロックが低冗長記憶システム内に存在するか否かを迅速に判定するための方法および装置を提供する。ある態様においては、本発明は、これを記憶システム内の各サブブロックを少なくとも１つのサブブロックがハッシュする各位置に対する「１」ビットを含むビットフィルタにハッシュすることにより達成する。このビットフィルタは、記憶システム内にサブブロックが存在するか否かを非常に迅速に判定する方法を提供する。本発明の他の態様においては、多数のランダム・アクセス読出しおよび書込み動作を１つのシーケンシャル読出し動作およびシーケンシャル書込み動作に変換するために、新しいサブブロック用のインデックス・エントリをサブブロック・インデックス書込みバッファ内にバッファすることができる。ビットフィルタと書込みバッファとを組み合わせると、メモリ内の全サブブロック・インデックスを格納するシステムが使用するよりかなり高速でないランダム・アクセス・メモリを使用する低冗長記憶システムを得ることができる。 （もっと読む）