1. A method, comprising: maintaining a values-to-partition mapping for a partitioned space; wherein the values-to-partition mapping indicates sets of one or more mapped values, each of said sets being mapped to an existing partition in the partitioned space; receiving a request to store a first item in the partitioned space; in response to the request: based on the values-to-partition mapping for the partitioned space, determining that the first item should be placed in a particular partition that has not yet been created in the partitioned space; wherein determining that the first item should be placed in the particular partition that has not yet been created in the partitioned space comprises determining that the first item comprises a first value that does not belong to any of the sets of one or more mapped values; in response to said determining, creating the particular partition in the partitioned space; and storing the first item in the particular partition; updating the values-to-partition mapping to indicate that a first set of one or more values is mapped to the newly created particular partition, wherein the first set of one or more values comprises the first value; wherein the first set of one or more values is determined at least partially based on at least one of: a hash function of the first value, or a range of continuous values described by a formula; wherein the method is performed by one or more computing devices.