Abstract:
Apparatuses, systems, and methods are disclosed for a key-value store. The method includes associating positions within a sparse array with key values on a one-to-one basis. Intermediate searchable containers of value pairs are sized for improve search efficiency. Containers that reach a maximum count of key value pairs are divided into derivative containers that each contain approximately one half of their originating container.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to the techniques and systems adapted for searching software databases. More particularly the present invention relates to methods and systems effective in searching databases comprising key value pairs wherein database records are associated with keys. 
       BACKGROUND OF THE INVENTION 
       [0002]    A key value pair is a set of data items that contain a key, such as an account number or part number, and a value, such as the actual data item itself or a pointer to where that data item is stored on a disk or some storage device. Key value pairs are widely used in tables and configuration files. When loading large numbers of key value pairs into memory, however, memory space can quickly run, out and the computational burden of search can be expensive both in resource requirements and financial costs. 
         [0003]    There is therefore a long-felt need to provide improved methods and systems for performing searches in databases containing key value pairs. 
       SUMMARY OF THE INVENTION 
       [0004]    Toward this object and other object made obvious in light of the present disclosure, an invented method and system are provided that present a sparse array associated with intervening containers, wherein the sparse array includes at least as many locations as uniquely expressed in a range of key values of a plurality of keys of a selected multiplicity of key value pairs. Each container is dynamically managed to contain, or relate to, less than a maximal count of key value pairs, wherein any container exceeding the maximal count of associated keys is split into two substantively equally sized derivative containers. 
         [0005]    Alternatively, indices are applied in certain alternate preferred embodiments of the method of the present invention (hereinafter, “the invented method”) wherein one or more distinguishable elements of the sparse array represent a unique key value and point to one particular index of a plurality indices, wherein each index is associated with a unique and sequential range of key values, but no index stores a key value pair. The term pointer as applied within the present disclosure is defined to include information that may be digitized and/or stored in electronic media including, but not limited to, memory; further included is data that may be or comprise a representation of information that enables access to, and/or specifies the location of, a key value pair. The term pointer is further defined herein as to include, be or comprise a pointer, a cursor, an index, or other digitized information stored in an electronic storage media, wherein the digitized information may comprise a representation of information that enables access to, and/or specifies the location of, a key value pair. 
         [0006]    This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. 
     
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
         [0007]    These, and further features of the invention, may be better understood with reference to the accompanying specification and drawings depicting the preferred embodiment, in which: 
           [0008]      FIG. 1  is a diagram of a sparse array as stored in a computer memory wherein each element of the sparse array contains a pointer to a container, each container containing or associating a maximum of M key value pairs; 
           [0009]      FIG. 2  is a diagram presenting a plurality of containers; 
           [0010]      FIG. 3  is a diagram illustrating the splitting of a container; 
           [0011]      FIG. 4  is a flow chart of the interactivity of the software of  FIG. 3 ; 
           [0012]      FIG. 5  is a flowchart of computer searching for a value with a key; 
           [0013]      FIG. 6  is a flowchart of a further aspect of the invented method whereby the computer adds a key and value pair to a container; 
           [0014]      FIG. 7  is a flowchart of a yet further aspect of the invented method whereby a database management software directs the computer to increases the array size; 
           [0015]      FIG. 8  is a flowchart of a yet further aspect of the invented method wherein the database management software directs the computer to execute a first method to of splitting a group; 
           [0016]      FIG. 9  is a flowchart of a yet further aspect of the invented method whereby the database management software directs the computer to utilize a second method for the execution of a process of splitting a group; 
           [0017]      FIG. 10  is a flowchart of a yet further aspect of the invented method, whereby the computer utilizes a third method of splitting a group; 
           [0018]      FIG. 11  is a flowchart of a yet further method of the invented method, whereby the database management software directs the computer to delete a key and value pair; 
           [0019]      FIG. 12  is a block diagram of the computer of  FIG. 1  through  FIG. 11 ; and 
           [0020]      FIG. 13  is a block diagram of a database management system of the computer of  FIG. 12 , wherein a plurality of data structures of the methods of  FIGS. 5 through 11  are stored. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    In the computer sciences a key and data pair is a system by which a value, such as a data-containing record, is matched with a key, wherein each key is a unique value found within a key range. 
         [0022]    Inefficiencies persist in the prior systems, however, particularly when a plurality of containers, i.e., a plurality of distinguishable software structures, are assigned in the aggregate to that contain a very large number of key value pairs. 
         [0023]    When a plurality of software encoded containers (hereinafter, “containers”), are each assigned a one or more key value pairs selected from a large number of key and value pairs, for example greater than 100,000,000, a search applying a particular search key may take an extensive amount of time, even searching only the keys recorded in or associated with each container. The invented method seeks to remedy such inefficiencies by means of implementing a sparse array within a memory of, or a memory accessible to, an information technology system tasked with searching for key matches. 
         [0024]    It is understood that, in various alternate preferred embodiments of the invented method, one or more containers may be or comprise, a database, a software object, a subroutine, and/or other suitable data structure known in the art. 
         [0025]    Referring now generally to the Figures, and particularly to  FIG. 1 ,  FIG. 1  is a diagram of sparse array SA as stored in a computer  2  having a database management system  2 A (hereinafter, “DBMS  2 A”) stored in a system memory  2 B. It is understood that each and every software data, record, software object, encoded information or digitized information referenced in the present disclosure may be stored in the system memory  2 B and/or the DBMS  2 A. 
         [0026]    The DBMS  2 A may be or comprise one or more prior art database management systems including, but not limited to, an ORACLE DATABASE™ database management system marketed by Oracle Corporation, of Redwood City, Calif.; a Database 2™, also known as DB2™, relational database management system as marketed by IBM Corporation of Armonk, N.Y.; a Microsoft SQL Server™ relational database management system as marketed by Microsoft Corporation of Redmond, Wash.; MySQL™ as marketed by Oracle Corporation of Redwood City, Calif.; and a MONGODB™ as marketed by MongoDB, Inc. of New York City, USA; and the POSTGRESQL™ open source object-relational database management system. 
         [0027]    The computer  2  may be or comprise a bundled computer software and hardware product such as, (a.) a network-communications enabled THINKPAD WORKSTATION™ notebook computer marketed by Lenovo, Inc. of Morrisville, N.C.; (b.) a NIVEUS 5200 computer workstation marketed by Penguin Computing of Fremont, Calif. and running a LINUX™ operating system or a UNIX™ operating system; (c.) a network-communications enabled personal computer configured for running WINDOWS SERVER™ or WINDOWS 8™ operating system marketed by Microsoft Corporation of Redmond, Wash.; (d.) a MACBOOK PRO™ personal computer as marketed by Apple, Inc. of Cupertino, Calif.; or (e.) other suitable computational system or electronic communications device known in the art capable of providing or enabling a web service known in the art. 
         [0028]    The DBMS  2 A and/or the system memory  2 B store a plurality of software containers C. 0000 -C.N, where N is an arbitrarily large integer. The plurality of software containers C. 0000 -C.N are each temporarily and sequentially bounded to a contiguous subrange of keys K. 0000 -K.N of a key range KR of a multiplicity of sequentially ordered elements E. 0000 -E.N. 
         [0029]    In the invented method, a sparse array memory space SAmem preferably comprises a multiplicity of ordered elements E. 0000 -E.N, wherein each element individually and uniquely relates a key K. 0000 -K.N of a specific sequence of a key range KR. The key range is defined as the extending from a minimum value of an initial key Kmin associated with an initial element E. 0000 , to a maximum value of a key Kmax associated with a maximum element E.N. The instant key range KR thus extends from Kmin to Kmax and the sparse array memory space SA has a separate element for each possible key K. 0000 -K.N within the instant key range KR. A base address ADDRbase of the sparse array memory space SAmem would be equal to a first memory location M.LOC. 0000  within the system memory  2 B, wherein is the base address ADDRbase of an initial element E. 0000  of the sparse array memory space SAmem corresponds to the initial key Kmin. 
         [0030]    Each sparse array element E. 0000 -E.N is sized to contain a pointer PTR. 0000 -PTR.N that expresses a memory location M.LOC. 0000 -M.LOC.N of a particular container C. 0000 -C.N. For example, the initial subrange SR. 0000  defines an initial plurality of elements E. 0000 -E.N that each contain a pointer PTR. 0000 -PTR. 2000  that points to the same initial container C. 0000 . The term “pointer” as applied within the present disclosure is defined to include information that may be digitized and/or stored in electronic media including, but not limited to, system memory  2 B; further included is data that may be or comprise a representation of information that enables access to, and/or specifies the location of, a key value pair KP. 0000 -KP.N. The term pointer is further defined herein as to include, be or comprise a pointer, a cursor, an index, or other digitized information stored in an electronic storage media, wherein the digitized information may comprise a representation of information that enables access to and/or specifies the location of, a key value pair KP. 0000 -KP.N. 
         [0031]    It is understood that in certain alternate preferred embodiments of the invented method, one or more elements E. 0000 -E.N may contain a null value when the instant element fails to contain a pointer PTR. 0000 -PTR.N enabling access to, or indicating a location of, an ordered pair associated with the instant element E. 0000 -E.N. 
         [0032]    It is further understood that each key K. 0000 -K.N is sequentially ordered from Kmin to Kmax, wherein the minimum key value Kmin is the initial key value K. 0000  of the key sequence and the maximum key value Kmax is the highest key value K.N of the sequence. Each key K. 0000 -K.N is assigned a unique numerical position value within the sequence of the key range KR. 
         [0033]    The sparse array memory space SAmem allocated to instantiate the sparse array SA comprises a contiguous block of memory locations M.LOC. 0000 -M.LOC.N, the size of memory allocated to instantiate the sparse array memory space SAmem would be equal to the memory size produced by the following calculated as follows: 
         [0000]      SAsize=( K max− K min)(Pointer Size).
 
         [0034]    In another optional aspect of the invented method, when a particular key K. 0000 -K.N is selected as a search key Ksearch, the unique numerical position value Kvalue of the search key within the sequence of the key range KR is applied to make a determination of a memory location M.LOC of an element E. 0000 -E.N of the sparse array SA that represents a search key Ksearch may be generated by the following calculation: 
         [0000]        M.LOC =( K value− K min)(Pointer Size)+ADDRbase;
 
         [0035]    Wherein the base address value ADDRbase is a numerical or alphanumeric designation of the address within the system memory  2 B of the initial element of the sparse area SA. 
         [0036]    Referring now generally to the Figures, and particularly to  FIG. 2 ,  FIG. 2  represents an aspect of the invented method wherein each container C. 0000 -C.N is temporarily assigned to a bounded subrange SR. 0000 -S.N of keys K. 0000 -K.N of the key range KR, and wherein each container C. 0000 -C.N is associated with a maximum count M 0 -Mn of actual key value pairs KP. 0000 -KP.N selected its assigned bounded subrange of keys K. 0000 -K.N. Each container C. 0000 -C.N optimally stores a plurality of key value pairs KP. 0000 -KP.N, wherein each key value pair KP. 0000 -KP.N stored in each container C. 0000 -C.N includes a key K. 0000 -K.N of the key subrange SR. 0000 -S.N assigned to the comprising container C. 0000 -C.N. For example, the initial container C. 0000  is assigned a contiguous first key subrange K. 0000 -K. 2000  of two thousand sequential key values, wherein the initial container C. 0000  may store only an initial container maximum key M 0  of key value pairs KP. 0000 -KP.N. In an optimal application of the invented method, the initial container maximum key M 0  is generally less than the number of unique keys K. 0000 -K.N associated with the contiguous first key subrange K. 0000 -K. 2000 . 
         [0037]    Furthermore, in an optional aspect of the invented method, one or more containers C. 0000 -C.N may be associated with the same unique maximum key value pair count M 0  or alternate maximum key value pair counts Ml-Mn. More particularly, one exemplary preferred embodiment, the initial container C. 0000  may have a maximum key value pair count M 0  equal to an exemplary count of two thousand keys K. 0000 -K.N, and a third container C. 0003  have an alternate third maximal count M 0  equal to an alternate exemplary count of ten thousand keys K. 0000 -K.N. 
         [0038]    It is further understood that each container C. 0000 -C.N may be temporarily assigned to a different and varying bounded subrange SR. 0000 -SR.N of the key range KR. For example, the initial container C. 0000  may be assigned to an initial subrange SR. 0000  of the key range KR from the minimum key value Kmin to an initial container subrange upper bound KC 0 +, wherein the initial container subrange SR. 0000 -SR.N upper bound KC 0 + is temporarily equal to the minimum key value Kmin plus 2,000. In another optional example, a second container C. 0002  may be assigned to a second subrange SR. 0002  of the key range KR from the key value K. 20001  to the key value K. 5000 . In yet another optional example, a third container C. 0003  may be assigned to a third subrange SR. 0003  of the key range KR from minimum key value K. 5001  to a third container subrange SR. 0003  upper bound key value K. 6000 . 
         [0039]    It is understood that containers C. 0000 -C.N seldom generally store a key value pair KP. 0000 -KP.N for each key value K. 0000 -K.N of its particular assigned key subrange SR. 0000 -SR.N 
         [0040]    Referring now generally to the Figures, and particularly to  FIG. 3 ,  FIG. 3  is a diagram illustrating the splitting of a container C. 0000 -C.N which occurs when an assigned key maximum M 0 -Mn of the selected container C. 0000 -C.N is exceeded. It is understood that, in various alternate preferred embodiments of the invented method, two or more, or all, of the containers C. 0000 -C.N may have an assigned key maximum M 0 -Mn that is a same value, and that in still other alternate preferred embodiments of the invented method one or more containers C. 0000 -C.N may have a unique assigned key maximum M 0 -Mn. 
         [0041]    When a new key value pair KP. 0000 -KP.N within the key range KR. 5001 -KR. 6000  is added to the exemplary third container C. 0003  and that addition causes the third container C. 0003  to reach the third maximum key number M 3  of keys that that may be assigned to the third container C. 0003 , the actually assigned key value pairs KP. 5001 -KP. 6000  of the third container C. 0003  are split between the third container C. 0003  and a new container C.NEW. The new container C.NEW may consist of a key count Kcount equal to one half of the third maximum key number M 3 . It is understood that the new, resultant and reduced subrange KR. 5001 -KR. 5444  of the third container C. 0003  is contiguous, as is the resultant new key range subrange KR. 5445 -KR. 6000  of the new container C.NEW. The third subrange SR. 0003  of the third container C. 0003  is therein modified start at the original first key position K. 5001  of the third container C. 0003  and the resultant new key range subrange KR. 5445 -KR. 6000  of the new container C.NEW will end at the precious maximum key value K. 6000  of the third container C. 0003 . In the exemplary process of  FIG. 3 , the third container C. 003  is modified to store a reduced quantity of keys value pairs KP. 50001 -KP. 5444  equal to one half of the third maximum key number M 3  and comprising keys found within a reduced key value range KR. 5001 -KR. 5444 , and the new container C.NEW is populated with a quantity of key value pairs KP. 5445 -KP. 6000  equal to one plus one half of the third maximum key number M 3  and comprising keys found within a reduced key value range KR. 5445 -KR. 6000 . 
         [0042]    Referring now generally to the Figures, and particularly to  FIG. 4 ,  FIG. 4  is a flowchart of an aspect of the invented method wherein the computer  2  including a CPU  2 C optionally creates the new container C.NEW. In step  4 . 02  the CPU  2 C determines whether a key value pair KP. 0000 -KP.N containing a key K. 0000 -K.N input has been received. When the determination in step  4 . 02  is negative, the CPU  2 C proceeds to step  4 . 04 , wherein the CPU  2 C executes an alternate process. Alternatively, when the determination in step  4 . 02  is positive, the CPU  2 C determines in step  4 . 06  which element E. 0000 -E.N is associated with the keys K. 0000 -K.N received in step  4 . 02 , and reads the pointer PTR. 0000 -PTR.N stored in the associated element E. 0000 -E.N, and thereby determines which container C. 0000 -C.N to store the key value pair KP. 0000 -KP.N received in step  4 . 02 . Subsequently, in step  4 . 08  the CPU  2 C adds the new key value pair KP. 0000 -KP.N to the container C. 0000 -C.N selected in step  4 . 06 . 
         [0043]    In step  4 . 10  the CPU  2 C determines whether the stored count of key value pairs KP. 0000 -KP.N stored in the selected container C. 0000 -C.N of step  4 . 08  is greater than the assigned maximum number M 0 -Mn of keys of that selected container C. 0000 -C.N. When the determination in step  4 . 10  is negative, and the CPU  2 C determines that the stored key value pair count of the designated container C. 0000 -C.N selected in step  4 . 06  is not greater than the maximum key number M 0 -Mn assigned to the selected container C. 0000 -C.N, the CPU  2 C proceeds to step  4 . 20  and executes alternate processes. 
         [0044]    In the alternative, when the determination in step  4 . 12  is positive, i.e. the CPU  2 C determines that the count of key value pairs KP. 0000 -KP.N currently stored within the selected container C. 0000 -C.N is greater than associated maximum key value pair KP. 0000 -KP.N number M 0 -Mn of that selected container, the CPU  2 C forms a new container C.NEW in step  4 . 12 . In step  4 . 14  the CPU  2 C writes the maximum number M 0 -Mn of key value pairs KP. 0000 -KP.N of the selected container C. 0000 -C.N divided by two into the new container C.NEW, wherein the key value pairs KP. 0000 -KP.N written in to the new container C.NEW are sequential and include either the lowest key value or the highest key value of the earlier formed container C. 0000 -C.N selected in step  4 . 08 . In step  4 . 16  the CPU  2 C deletes all key value pairs KP. 0000 -KP.N from the selected container C. 0000 -C.N that were written into the new container C.NEW in step  4 . 14 . The CPU  2 C subsequently proceeds from step  4 . 16  to step  4 . 04  and executes alternate processes. 
         [0045]    It is understood that the function of the containers C. 0000 -C.N may be provided by a plurality of indices that do not store key value pairs KP. 0000 -KP.N but rather are each related to unique key value pairs KP. 0000 -KP.N stored within or accessible to the computer  2 . 
         [0046]    Referring now generally to the Figures, and particularly to  FIG. 5 ,  FIG. 5  is a flowchart of an aspect of the invented method whereby a CPU  2 C searches for a key K. 0000 -K.N with a search value. In step  5 . 02  an invented software  4  of the computer  2  directs the CPU  2 C to acquire a bitset  6 . In step  5 . 04  the CPU  2 C divides the key K. 0000 -K.N by a container size  8  for the purpose of acquiring an index  10 . Alternatively, if the container size  8  is equal to 2″, the key K. 0000 -K.N is shifted n bits to the right, instead of the key K. 0000 -K.N being divided by the container size  8 . In step  5 . 06  the CPU  2 C places the index  10  into an array of references to groups  12 , using the index  10  to acquire a group  14 , wherein the group  14  may be, but is not limited to, a hash table. In step  5 . 08  the CPU  2 C determines a value for the group  14  using the key K. 0000 -K.N. The CPU  2 C subsequently advances to step  5 . 10 , wherein the CPU  2 C terminates the process. 
         [0047]    Referring now generally to the Figures and particularly to  FIG. 6 ,  FIG. 6  is a flowchart of a further aspect of the invented method whereby the CPU  2 C adds a bitset  6  to a container C. 0000 -C.N. In step  6 . 02  CPU  2 C acquires the bitset  6 . In step  6 . 04  the CPU  2 C divides the key K. 0000 -K.N by the container size  8  for the purpose of acquiring the index  10 . In an optional alternative to step  6 . 04 , the CPU  2 C shifts the key K. 0000 -K.N n bits to the right if the group size is equal to 2 n , instead of dividing the key K. 0000 -K.N by the group size. In step  6 . 06  the CPU determines whether the index  10  is greater than an array size  18 . When the determination in step  6 . 06  is negative, i.e. the CPU  2 C determines that the index  10  is not greater than the array size  18 , the CPU  2 C advances to step  6 . 08 . In step  6 . 08  the CPU  2 C increases the array size  18  by means of the method of  FIG. 7 . Alternatively, when the determination in step  6 . 06  is positive, and the CPU  2 C determines that the index  10  is greater than the array size  18 , the CPU  2 C advances to step  6 . 10 . In step  6 . 10  the CPU  2 C indexes into the array of references to groups  12 , using the index  10  to acquire the group  14 . In step  6 . 12  the CPU  2 C determines whether the group  14  is full. If the CPU  2 C determines in step  6 . 12  that the group  14  is full, the CPU  2 C advances to step  6 . 14 , wherein the CPU  2 C executes the methods of  FIG. 8 ,  FIG. 9 , and  FIG. 10 . When the CPU  2 C determines in step  6 . 12  that the group  14  is not full, the CPU  2 C advances to step  6 . 16 , wherein the CPU  2 C adds the bitset  6  to the group  14 . The CPU  2 C subsequently advances to step  6 . 18 , wherein the CPU  2 C terminates the process. 
         [0048]    Referring now generally to the Figures, and particularly to  FIG. 7 ,  FIG. 7  is a flowchart of a yet further aspect of the invented method whereby the software  4  directs the CPU  2 C to increase the array size  18 . In step  7 . 02  the CPU  2 C determines whether the array size  18  is equal to zero, or alternatively whether a last group  18  is full. When the CPU  2 C determines that neither of the criteria set out in step  7 . 02  are designated “true” the CPU  2 C advances to step  7 . 04 , wherein the CPU  2 C sets a group one  20  equal to the last group  18 . When the CPU  2 C determines in step  7 . 02  that the either of the criteria set out in step  7 . 02  are met, the CPU  2 C sets the group one  20  equal to a new group  22 . When the CPU  2 C has executed either step  7 . 04  or alternatively step  7 . 06 , the CPU  2 C advances to step  7 . 08 . In step  7 . 08  the CPU  2 C increases the array size  18  to any value that is greater than that of the index  10 . In order to reduce reallocation calls, the CPU  2 C may optionally increase the array size  18  by a predetermined numerical value, or alternatively by a predetermined percentage of a previous array size  18 . In step  7 . 10  the CPU  2 C initializes new array elements with a pointer PTR. 0000 -PTR.N to the group one  20 . The CPU  2 C then terminates the process in step  7 . 12 . 
         [0049]    Referring now generally to the Figures and particularly to  FIG. 8 ,  FIG. 8  is a flowchart of a yet further aspect of the invented method wherein the software  4  directs the CPU  2 C to execute a first method for the process of splitting a group. In step  8 . 02  the CPU  2 C creates a first new container C.NEW. 0001  and a second new container C.NEW. 0002 . In step  8 . 04  the CPU  2 C calculates a split number  24 . In step  8 . 06  the CPU  2 C determines whether to acquire a next pair  34  from a source group  26 . When the determination in step  8 . 06  is positive, the CPU  2 C advances to step  8 . 08 , wherein the CPU  2 C determines whether the key K. 0000 -K.N is less than a split number  24 . When the CPU  2 C determines in step  8 . 08  that the key K. 0000 -K.N is less than the split number  24 , the CPU  2 C advances to step  8 . 10 , wherein the CPU  2 C adds a key value pair KP. 0000 -KP.N to the first new container C.NEW. 0001 . When the determination in step  8 . 08  is negative, and the CPU  2 C determines that the key K. 0000 -K.N is not less than the split number  24 , the CPU  2 C adds the key value pair KP. 0000 -KP.N to the second new container C.NEW. 0002  in step  8 . 12 . The CPU  2 C subsequently advances from the execution of either step  8 . 10  or step  8 . 12  to the re-execution of the loop of steps  8 . 06  through  8 . 12 , until the determination in step  8 . 06  is negative. 
         [0050]    When the determination in step  8 . 06  is negative, i.e. the CPU  2 C determines not to retrieve a subsequent key value pair KP. 0000 -KP.N from the source group  26 , the CPU  2 C advances to step  8 . 14 . In step  8 . 14  the CPU  2 C sets a split index  10  equal to the split number  24  divided by the container size  8 . For each of the array elements  32  which have an index  10  greater than the split index  30  and which point to the source group  26 , the CPU  2 C changes the array elements to point to the first new container C.NEW. 0001  in step  8 . 16 . For each of the array elements  32  which have an index that is greater than or equal to the split index  30  and which point to the source group  26 , the CPU  2 C changes the elements to point to the second new container C.NEW. 0002  in step  8 . 18 . The CPU  2 C then advances to step  4 . 20 , wherein the CPU  2 C terminates the process. 
         [0051]    Referring now generally to the Figures and particularly to  FIG. 9 ,  FIG. 9  is a flowchart of a yet further aspect of the invented method whereby the software  4  directs the CPU  2 C to utilize a second method for the execution of the process of a split group. In step  9 . 02  the CPU  2 C creates a new container C.NEW. In step  9 . 04  the CPU  2 C calculates a split number  24 . In step  9 . 06  the CPU  2 C determines whether to acquire a next pair  34  from the source group  26 . When the determination in step  9 . 06  is positive, i.e. the CPU  2 C determines to acquire the next pair  34 , the CPU  2 C advances to step  9 . 08 , wherein the CPU  2 C determines if the key K. 0000 -K.N is greater than the split number  24 . When the CPU  2 C determines in step  9 . 08  that the key K. 0000 -K.N is not greater than the split number  24 , the CPU  2 C advances to step  9 . 10  wherein the CPU  2 C adds the key value pair KP. 0000 -KP.N to the new group  22  and removes the key value pair KP. 0000 -KP.N from the source group  26 . The CPU  2 C subsequently advances from a positive determination in step  9 . 08 , or from the execution of step  9 . 10  to a re-execution of the loop of steps  9 . 06  through  9 . 10 , until the determination in step  9 . 06  is negative. 
         [0052]    When the determination in step  9 . 06  is negative, and the CPU  2 C determines to acquire a subsequent key value pair  28  from the source group  26 , the CPU  2 C advances to step  9 . 12 . In step  9 . 12  the CPU  2 C sets the split index  30  equal to the split number  24  divided by the container size  8 . In step  9 . 14 , for each of the array elements  32  which have an index  10  which is greater than or equal to the split index or which points to the source group  26 , the CPU  2 C changes the array elements  32  to point to the new group  22 . The CPU  2 C terminates the process in step  9 . 16 . 
         [0053]    Referring now generally to the Figures and particularly to  FIG. 10 ,  FIG. 10  is a flowchart of a yet further aspect of the invented method, whereby the CPU  2 C utilizes a third method for the process of a splitting a group. In step  10 . 02  the CPU  2 C acquires a minimum value of an initial key Kmin and a maximum value of a key Kmax from the designated container C. 0000 -C.N. In step  10 . 04  the CPU  2 C sets an index 1   34  equal to the initial key Kmin divided by the container size  8 . In an alternate embodiment of step  10 . 04 , the CPU  2 C shifts the key K. 0000 -K.N n bits to the right, instead of dividing the key K. 0000 -K.N by the container size  8  if the group size is equal to 2 n . In step  10 . 06  the CPU  2 C sets an index 2   36  equal to the maximum key value Kmax divided by the container size  8 . The CPU  2 C in step  10 . 06  determines whether the index 1   34  and the index 2   36  are equal. When the determination in step  10 . 08  is positive, the CPU  2 C selects an alternate container type C.TYPE.ALT for the group  14  without splitting the group  14 . Alternatively, when the determination in step  10 . 08  is negative, i.e. when the CPU  2 C determines that the index 1   34  and the index 2   36  are not equal, the CPU  2 C advances to step  10 . 12 , wherein the CPU  2 C utilizes the methods of  FIG. 8  and  FIG. 9  to split the group  14 . The CPU  2 C advances to step  10 . 14  either from the execution of step  10 . 10  or, alternatively, from the execution of step  10 . 12 . In step  10 . 14  the CPU  2 C terminates the process. 
         [0054]    Referring now generally to the Figures and particularly to  FIG. 11 ,  FIG. 11  is a flowchart of a yet further aspect of the invented method, whereby the software  4  directs the CPU  2 C to delete a bitset  6 . In step  11 . 02  the CPU  2 C acquires a key value pair KP. 0000 -KP.N. In step  11 . 04  the CPU  2 C divides the key K. 0000 -K.N by the container size  8  to acquire the index  10 . In an alternate embodiment of step  11 . 04 , the CPU  2 C shifts the key K. 0000 -K.N n bits to the right, instead of dividing the key K. 0000 -K.N by the container size  8  if the container size  8  is equal to 2 n . In step  11 . 06  the CPU  2 C indexes into the array of references to groups  12  using the index  10  to acquire the group  14 . In step  11 . 08  the CPU  2 C deletes the bitset  6  from the group  14  using the key K. 0000 -K.N. In step  11 . 10  the CPU  2 C determines whether the number of key value pairs KP. 0000 -KP.N in the group is less than the minimum value  38 . When the determination in step  11 . 10  is positive, the CPU  2 C executes a post process to merge the group  14  with the a group to the left  40  or with a group to the right  42 , or with both, and to reduce the array size  18  if necessary. Subsequent to a negative determination in step  11 . 10 , or alternatively to the execution of step  11 . 12 , the CPU  2 C advances to step  11 . 14 . In step  11 . 14  the CPU  2 C terminates the process. 
         [0055]    Referring now generally to the Figures and particularly to  FIG. 12 ,  FIG. 12  is a block diagram of the computer  2  of  FIG. 1  through  FIG. 11 . A computer operating system software OP.SYS  2 H of the computer  2  may be selected from freely available, open source and/or commercially available operating system software, to include but not limited to a LINUX™ or UNIX™ or derivative operating system, such as the DEBIAN™ operating system software as provided by Software in the Public Interest, Inc. of Indianapolis, Ind.; a WINDOWS XP™, VISTA™ or WINDOWS 7 ™ operating system as marketed by Microsoft Corporation of Redmond, Wash.; or the MAC OS X operating system or iPhone G4 OS™ as marketed by Apple, Inc. of Cupertino, Calif. 
         [0056]    The computer  2  further includes the central processing unit  2 C that is bi-directionally communicatively coupled by an internal communications bus  2 D with (a.) an optional user input module  2 E that accepts input, e.g., information and commands, from a user, (b.) an optional video display module  2 F that provides visual information rendering output, (c.) a network interface  2 G that bi-directionally communicatively couples the CPU  2 C with alternate devices (d.) the system memory  2 B. Stored within the system memory  2 B, is the operating system OP.SYS  2 H, the invented software SW, a user module driver UDRV, an optional display driver DIS a network interface driver NIF enables the network interface  2 F to bi-directionally communicatively couple the CPU  2 C with optional additional devices, the DBMS  2 A, and the software structures and digitally stored information described within the present disclosure. 
         [0057]    The invented software SW enables the computer  2  and the CPU  2 C to execute, perform and instantiate aspects of the invented method as disclosed within  FIGS. 1 through 11  and accompanying descriptions. The user input module driver UDRV enables the user module  2 C to input information and commands entered by a user into the CPU  2 C. The display driver DIS enables the CPU  2 C to visually render information by means of the video display module  2 D. The network NIF enables the network interface module  2 E to bi-directionally communicate with optional alternate devices. 
         [0058]    Referring now generally to the Figures, and particularly to  FIG. 13 ,  FIG. 13  is a block diagram of additional aspects of the DBMS  2 A, wherein a plurality of data structures  6  through  44  of the methods of  FIG. 5  through  FIG. 11  are stored. 
         [0059]    The foregoing description of the embodiments of the invention has been presented for the purpose of illustration; it is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Persons skilled in the relevant art can appreciate that many modifications and variations are possible in light of the above disclosure. 
         [0060]    Some portions of this description describe the embodiments of the invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are commonly used by those skilled in the data processing arts to convey the substance of their work effectively to others skilled in the art. These operations, while described functionally, computationally, or logically, are understood to be implemented by computer programs or equivalent electrical circuits, microcode, or the like. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules, without loss of generality. The described operations and their associated modules may be embodied in software, firmware, hardware, or any combinations thereof. 
         [0061]    Any of the steps, operations, or processes described herein may be performed or implemented with one or more hardware or software modules, alone or in combination with other devices. In one embodiment, a software module is implemented with a computer program product comprising a non-transitory computer-readable medium containing computer program code, which can be executed by a computer processor for performing any or all of the steps, operations, or processes described. 
         [0062]    Embodiments of the invention may also relate to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, and/or it may comprise a general-purpose computing device selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a non-transitory, tangible computer readable storage medium, or any type of media suitable for storing electronic instructions, which may be coupled to a computer system bus. Furthermore, any computing systems referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability. 
         [0063]    Embodiments of the invention may also relate to a product that is produced by a computing process described herein. Such a product may comprise information resulting from a computing process, where the information is stored on a non-transitory, tangible computer readable storage medium and may include any embodiment of a computer program product or other data combination described herein. 
         [0064]    Finally, the language used in the specification has been principally selected for readability and instructional purposes, and it may not have been selected to delineate or circumscribe the inventive subject matter. It is therefore intended that the scope of the invention be limited not by this detailed description, but rather by any claims that issue on an application based herein. Accordingly, the disclosure of the embodiments of the invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.