Deterministic searching using compressed indexes
AssigneePure Storage, Inc.
InventorsJohn Colgrove, Ethan L. Miller
Life of this patent
Estimating the term…
Abstract
A computing or storage system constructs a table in memory, and constructs a summary table that summarizes the table. The summary table is for determining whether there is likely an entry for a value in the table. The summary table has buckets pointed to by address fields of values. The first bucket in the summary table is split into a second bucket and a third bucket. Prior to the split, the first bucket is pointed to by a first address field of a first value. After the split, the second bucket and the third bucket are pointed to by the first address field plus one extra bit derived from a remainder of the first value.
Claims20
A method, comprising:
- providing a first table in a memory for determining whether there is an entry for a value in a second table, the first table comprising a plurality of buckets pointed to by address fields of values, each bucket having a prefix table and a signature table that are derived from corresponding values;
- and
- splitting a first bucket in the first table into a second bucket and a third bucket, the first bucket having a first prefix table and a first signature table, the second bucket and the third bucket pointed to by an address field pointing to the first bucket plus an extra bit, wherein the first bucket is identified as being split based on a table that tracks bucket splits.
A tangible, non-transient, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to:
- provide a first table in a memory for determining whether there is an entry for a value in a second table, the first table comprising a plurality of buckets pointed to by address fields of values, each bucket having a prefix table and a signature table that are derived from corresponding values;
- and
- split a first bucket in the first table into a second bucket and a third bucket, the first bucket having a first prefix table and a first signature table, the second bucket and the third bucket pointed to by an address field pointing to the first bucket plus an extra bit, wherein the first bucket is identified as being split based on a table that tracks bucket splits.
A computing system, comprising:
- a memory;
- and
- one or more processors, to:
- provide a first table in the memory for determining whether there is an entry for a value in a second table, the first table comprising a plurality of buckets pointed to by address fields of values, each bucket having a prefix table and a signature table that are derived from corresponding values;
- and
- split a first bucket in the first table into a second bucket and a third bucket, the first bucket having a first prefix table and a first signature table, the second bucket and the third bucket pointed to by an address field pointing to the first bucket plus an extra bit, wherein the first bucket is identified as being split based on a table that tracks bucket splits.
Dependencies are inferred from the claim text.