Method and apparatus for adding data storage bins to a stored computer database while minimizing movement of data and balancing data distribution

Claim 2

In a database system having a stored database partitioned into a plurality of buckets initially distributed into storage in round robin fashion in n 0 bins and subsequently in n j bins after a j th time that new bins have been added to the stored database, each bucket being associated with a bucket identification "x", a database storage manager for generating a bin identification "y" for the buckets after the m th addition of new bins, comprising: a mapping module that includes: first means for decrementing an index counter variable j=m to 0 by -1 ; second means for defining a variable y=x mod n j ; third means for determining whether y is equal to or greater than n j-1 ; and fourth means responsive to the third means for establishing y as the bin identification when y is equal to or greater than n j-1 and; means for assigning the buckets to the n m bins; and means for obtaining from storage records in the stored database using the bin identification.

Claim 3

The database storage manager of claim 1, wherein the stored database contains "B" buckets, an integer "k" is defined to be a number of new bins being added, and the data records are clustered and accessible by bucket identification, and the database storage manager further comprises: means for entering a do loop for a variable i=0 to B-1 to test each of the "n" existing bins; means for determining whether the i th bucket is in a bin being tested, and if not, retrieving the next i in the do loop; means for defining a variable j=mode (n+k) when the i th bucket is in the bin being tested; and means for moving the i th bucket to the j th bin when j≧n and then retrieving the next i in the do loop, and otherwise retrieving the next i in the do loop.

Claim 4

The database storage manager of claim 2, wherein the data records are not clustered or are not accessible by bucket identification, and the database storage manager further comprises: means for defining j=x mod(n+k) to test each data record in each of the n existing bins, wherein "x" is the bucket identification for a record being tested; and means for moving a record to the j th bin when j≧n.

Claim 5

The database storage manager of claim 1, wherein the stored database includes "n" bins, wherein "n" is a natural number, the database contains "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the database storage manager further comprises: means for determining whether new bins have been added; means for appending an integer to the defining sequence when new bins have been added; means for determining a skew of the database and for returning the defining sequence with n appended thereto when the skew is less than a predetermined skew; means for determining, when the skew is larger than the predetermined skew, whether n is a power of two and if so, returning "n" as the new defining sequence; and means for returning, when n is not a power of two, the sequence of integers (2 i , n) as the new defining sequence, wherein i=floor(log 2 (n)).

Claim 6

The database storage manager of claim 4, in combination with a digital computer.

Claim 7

A computer-implemented method for managing storage of a database, the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the records are clustered in the database storage and accessible by respective logical bucket identifications, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1), wherein the database storage includes "B" buckets; determining whether the i th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and when the index counter variable "j" is at least as great as "n", moving the i th bucket to the j th bin, and otherwise not moving the i th bucket.

Claim 8

A computer-implemented method for managing storage of a database, the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the records are clustered in the database storage and accessible by respective logical bucket identifications, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1), wherein the database storage includes "B" buckets; determining whether the i th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and when the index counter variable "j" is at least as great as "n", moving the i th bucket to the j th bin, and otherwise not moving the i th bucket.

Claim 9

A computer-implemented method for managing storage of a database the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the records are not clustered or are not accessible by bucket identification, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, and for each record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the record modulo the sum of "n" and "k"; determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j th bin, and otherwise not moving the record to the j th bin.

Claim 10

A computer-implemented method for managing storage of a database the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the records are not clustered or are not accessible by bucket identification, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, and for each record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the record modulo the sum of "n" and "k"; determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j th bin, and otherwise not moving the record to the j th bin.

Claim 11

A computer-implemented method for managing storage of a database, the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the database storage initially includes n 0 bins, further comprising the steps of: (a) adding new bins "m" times to the database storage, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m"; (b) defining a variable "y" to be the bucket identification "x" modulo n j ; (c) determining whether the variable "y" is at least equal to n j-1 , and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); (d) subsequently accessing buckets using the variable "y" as the relevant bin identification; (e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

Claim 12

A computer-implemented method for managing storage of a database, the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the database storage initially includes n 0 bins, further comprising the steps of: (a) adding new bins "m" times to the database storage, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m"; (b) defining a variable "y" to be the bucket identification "x" modulo n j ; (c) determining whether the variable "y" is at least equal to n j-1 , and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); (d) subsequently accessing buckets using the variable "y" as the relevant bin identification; (e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

Claim 13

The computer-implemented method of claim 8, wherein the database storage includes "n" bins, wherein "n" is a natural number, the database storage contains "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the method steps further comprise: determining whether new bins have been added, and if so, appending "n" to the defining sequence; determining whether the difference between the size of the largest bin and the ceiling of the quotient "B"/"n" exceeds a predetermined difference, and if not, returning the defining sequence with "n" appended thereto as a new defining sequence, and otherwise: determining whether "n" is a power of two, and if so, returning "n" as the new defining sequence, and otherwise returning the sequence of integers (2 i , n) as the new defining sequence, wherein "i" equals the integer portion of the logarithm of "n".

Claim 14

The computer-implemented method of claim 9, wherein performed in a combination that includes a digital computer.

Claim 15

A computer program device comprising: a computer program storage device readable by a digital computer; and a program means on the program storage device and including instructions executable by the digital computer for performing method steps for mapping to a bin in a database storage a data record bucket stored therein, the data record bucket containing data records of a database and having a bucket identification "x", while minimizing the movement of data when new bins are added to the database storage and while minimizing memory overhead, the method steps comprising: (a) adding new bins "m" times to a database storage initially containing n 0 bins, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m"; (b) defining a variable "y" to be the bucket identification "x" modulo n j ; (c) determining whether the variable "y" is at least equal to n j-1 , and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); and (d) subsequently accessing the bucket using the variable "y" as the relevant bin identification.

Claim 16

A computer program device comprising: a computer program storage device readable by a digital computer; and a program means on the program storage device and including instructions executable by the digital computer for performing method steps for mapping to a bin in a database storage a data record bucket stored therein, the data record bucket containing data records of a database and having a bucket identification "x", while minimizing the movement of data when new bins are added to the database storage and while minimizing memory overhead, the method steps comprising: (a) adding new bins "m" times to a database storage initially containing n 0 bins, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m"; (b) defining a variable "y" to be the bucket identification "x" modulo n j ; (c) determining whether the variable "y" is at least equal to n j-1 , and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); and (d) subsequently accessing the bucket using the variable "y" as the relevant bin identification.

Claim 17

The computer program device of claim 11, wherein the database contains "B" buckets, wherein an integer "k" is defined to be the number of new bins added in step (a), and wherein the method steps further comprise: (e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

Claim 18

The computer program device of claim 12, wherein the data records are clustered and accessible by bucket identification, and the method step (e) further comprises the steps of: (f) for each of the "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1); (g) determining whether the i th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and (h) when the index counter variable "j" is at least as great as "n", moving the i th bucket to the j th bin, and otherwise not moving the i th bucket.

Claim 19

The computer program device of claim 12, wherein the data records are not clustered or are not accessible by bucket identification, and the method step (e) further comprises the steps of: (f) for each of the "n" existing bins, wherein "n" is a natural number, and for each data record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the data record modulo the sum of "n" and "k"; (g) determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j th bin, and otherwise not moving the record to the j th bin.

Claim 20

The computer program device of claim 11, wherein the database storage includes "n" bins, wherein "n" is a natural number, the database storage includes "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the method steps further comprise: determining whether new bins have been added to the database storage, and if so, appending "n" to the defining sequence; determining whether the difference between the size of the largest bin and the ceiling of the quotient "B"/"n" exceeds a predetermined difference, and if not, returning the defining sequence with "n" appended thereto as a new defining sequence, and otherwise: determining whether "n" is a power of two, and if so, returning "n" as the new defining sequence, and otherwise returning the sequence of integers (2 i , n) as the new defining sequence, wherein "i" equals the integer portion of the logarithm of "n".

Claim 21

The computer program device of claim 15, wherein "i" equals the logarithm to the base (2) of "n".

Claim 22

The computer program device of claim 15, in combination with the digital computer.

Claim 23

In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including: adding new bins to the plurality of bins; maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and, populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin; wherein the records are clustered in the database storage and accessible by respective logical bucket identifications, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1), wherein the database storage includes "B" buckets; determining whether the i th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and when the index counter variable "j" is at least as great as "n", moving the i th bucket to the j th bin, and otherwise not moving the i th bucket.

Claim 24

In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including: adding new bins to the plurality of bins; maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and, populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin; wherein the records are clustered in the database storage and accessible by respective logical bucket identifications, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1), wherein the database storage includes "B" buckets; determining whether the i th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and when the index counter variable "j" is at least as great as "n", moving the i th bucket to the j th bin, and otherwise not moving the i th bucket.

Claim 25

In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including: adding new bins to the plurality of bins; maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and, populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin; wherein the records are not clustered or are not accessible by bucket identification, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, and for each record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the record modulo the sum of "n" and "k"; determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j th bin, and otherwise not moving the record to the j th bin.

Claim 26

In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including: adding new bins to the plurality of bins; maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and, populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin; wherein the records are not clustered or are not accessible by bucket identification, and the method further comprises: for each of "n" existing bins, wherein "n" is a natural number, and for each record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the record modulo the sum of "n" and "k"; determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j th bin, and otherwise not moving the record to the j th bin.

Claim 27

In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including: adding new bins to the plurality of bins; maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and, populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin; wherein the database storage initially includes n 0 bins, and the method further comprises: (a) adding new bins "m" times to the database storage, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m"; (b) defining a variable "y" to be the bucket identification "x" modulo n j ; (c) determining whether the variable "y" is at least equal to n j-1 , and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); (d) subsequently accessing buckets using the variable "y" as the relevant bin identification; (e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

Claim 28

In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including: adding new bins to the plurality of bins; maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and, populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record's bucket identification modulo the sum of "n" and "k" signifies the newly added bin; wherein the database storage initially includes n 0 bins, and the method further comprises: (a) adding new bins "m" times to the database storage, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m"; (b) defining a variable "y" to be the bucket identification "x" modulo n j ; (c) determining whether the variable "y" is at least equal to n j-1 , and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); (d) subsequently accessing buckets using the variable "y" as the relevant bin identification; (e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

Claim 29

The computer-implemented method of claim 20, wherein the database storage includes "n" bins, wherein "n" is a natural number, the database storage contains "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the method steps further comprise: determining whether new bins have been added, and if so, appending "n" to the defining sequence; determining whether the difference between the size of the largest bin and the ceiling of the quotient "B"/"n" exceeds a predetermined difference, and if not, returning the defining sequence with "n" appended thereto as a new defining sequence, and otherwise: determining whether "n" is a power of two, and if so, returning "n" as the new defining sequence, and otherwise returning the sequence of integers (2 i , n) as the new defining sequence, wherein "i" equals the integer portion of the logarithm of "n".

Claim 30

The computer-implemented method of claim 21, performed in a combination that includes the database storage.

Claim 31

The computer-implemented method of claim 22, wherein the combination includes a digital computer.