A key-value storage system, implemented by one or more computing devices, comprising: a content store for storing a plurality of key-value entries, each key-value entry providing a full key and an associated value; an index including an in-memory index store and a secondary index store; and a store interaction component configured to interact with the content store using the index, the index providing an index data structure that includes: a plurality of hash buckets, each hash bucket including a collection of linked hash bucket units, each hash bucket unit including a set membership filter and a hash block, each set membership filter providing a mechanism for determining whether a set membership key under consideration is associated with a corresponding hash bucket unit, each hash block including a plurality of hash entries, each hash entry providing at least a partial key and an address value, each partial key and each set membership key being derived from a full key under consideration, and each address value specifying a location of a corresponding key-value entry in the content store, the store interaction component being configured to store hash entries in a particular collection of linked hash bucket units in a chronological order based on time of creation, by storing each new hash entry in a head hash bucket unit of the particular collection, and creating a new head hash bucket unit when a previous head hash bucket unit cannot accommodate a new hash entry, and each collection of linked hash bucket units storing at least one of its most-recently-created hash blocks in the in-memory index store, and at least some of its other hash blocks in the secondary index store. a content store for storing a plurality of key-value entries, each key-value entry providing a full key and an associated value; an index including an in-memory index store and a secondary index store; and a store interaction component configured to interact with the content store using the index, the index providing an index data structure that includes: a plurality of hash buckets, each hash bucket including a collection of linked hash bucket units, each hash bucket unit including a set membership filter and a hash block, each set membership filter providing a mechanism for determining whether a set membership key under consideration is associated with a corresponding hash bucket unit, each hash block including a plurality of hash entries, each hash entry providing at least a partial key and an address value, each partial key and each set membership key being derived from a full key under consideration, and each address value specifying a location of a corresponding key-value entry in the content store, a plurality of hash buckets, each hash bucket including a collection of linked hash bucket units, each hash bucket unit including a set membership filter and a hash block, each set membership filter providing a mechanism for determining whether a set membership key under consideration is associated with a corresponding hash bucket unit, each hash block including a plurality of hash entries, each hash entry providing at least a partial key and an address value, each partial key and each set membership key being derived from a full key under consideration, and each address value specifying a location of a corresponding key-value entry in the content store, the store interaction component being configured to store hash entries in a particular collection of linked hash bucket units in a chronological order based on time of creation, by storing each new hash entry in a head hash bucket unit of the particular collection, and creating a new head hash bucket unit when a previous head hash bucket unit cannot accommodate a new hash entry, and each collection of linked hash bucket units storing at least one of its most-recently-created hash blocks in the in-memory index store, and at least some of its other hash blocks in the secondary index store.