A method implemented by a computing device comprising: partitioning a database with a first partition function (206 ) to allocate existing partitions (208 ), 208 ); and subsequently repartitioning the database by: creating a record of key membership for data entries located in the existing partitions existing at a time of repartitioning, wherein the record of key membership is configured to record key values associated with data entries located in the existing partitions as existing at the time of repartitioning and wherein the repartitioning is performed such that the data entries located in the existing partitions as existing at the time of repartitioning keep their respective locations; adding one or more new partitions (208 ) with a second partition function (206 ); defining a composite partition function for subsequent database operations configured to: apply the first partition function for data having key values found in the record of key membership; or apply the second partition function for data having key values not found in the record of key membership; such that data entries located in the existing partitions existing at the time of repartitioning keep their respective locations in the existing partitions as existing at the time of repartitioning. partitioning a database with a first partition function (206 ) to allocate existing partitions (208 ), 208 ); and subsequently repartitioning the database by: creating a record of key membership for data entries located in the existing partitions existing at a time of repartitioning, wherein the record of key membership is configured to record key values associated with data entries located in the existing partitions as existing at the time of repartitioning and wherein the repartitioning is performed such that the data entries located in the existing partitions as existing at the time of repartitioning keep their respective locations; adding one or more new partitions (208 ) with a second partition function (206 ); defining a composite partition function for subsequent database operations configured to: apply the first partition function for data having key values found in the record of key membership; or apply the second partition function for data having key values not found in the record of key membership; such that data entries located in the existing partitions existing at the time of repartitioning keep their respective locations in the existing partitions as existing at the time of repartitioning. creating a record of key membership for data entries located in the existing partitions existing at a time of repartitioning, wherein the record of key membership is configured to record key values associated with data entries located in the existing partitions as existing at the time of repartitioning and wherein the repartitioning is performed such that the data entries located in the existing partitions as existing at the time of repartitioning keep their respective locations; adding one or more new partitions (208 ) with a second partition function (206 ); defining a composite partition function for subsequent database operations configured to: apply the first partition function for data having key values found in the record of key membership; or apply the second partition function for data having key values not found in the record of key membership; such that data entries located in the existing partitions existing at the time of repartitioning keep their respective locations in the existing partitions as existing at the time of repartitioning. apply the first partition function for data having key values found in the record of key membership; or apply the second partition function for data having key values not found in the record of key membership; such that data entries located in the existing partitions existing at the time of repartitioning keep their respective locations in the existing partitions as existing at the time of repartitioning. <EOS>