Abstract:
An efficient method for storing relational data in a memory space uses B tree and B+ tree structures to store data for a database where non-identical values are stored in a string buffer and pointers to the string buffer are stored in a table buffer, and where identical data is stored only once, and each instance of that value in the database is referenced by a pointer to such identical data corresponding to the locations in the database where that identical value exists, thereby preserving physical memory and increasing the storage capacity of a fixed memory space.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application claims priority benefit under 35 U.S.C. §119(e) of U.S. Provisional Patent Application Ser. No. 60/970,164 filed Sep. 5, 2007. The disclosure this application is incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     Traditionally, mobile computing devices have been at a disadvantage in contrast to their non-mobile counterparts in that they have smaller viewing screens, smaller input mechanisms, smaller memory spaces, limited battery capacity, and, frequently, less powerful processors. Although all of these limitations have been substantially reduced through technological advances in the various technologies, each technological advance has largely been mirrored by an increase in the size and capability of applications that may be run on mobile devices. As a result, although modern mobile computing devices have capabilities far in excess of those of only a few years ago, there still is, and in the foreseeable future will continue to be, a premium placed upon processing power and memory capacity of mobile computing devices. When considering the memory requirements for an application and associated data, the only options for increasing the amount of data that may be stored are by enlarging the physical memory space or through software methods that can store increased amounts of data within a limited physical memory space. 
     B trees and B+ trees are standard methods for storing data within a searchable data structure, and either of them, or any other suitable data structure, may be used in the invention. Efficiency in this context translates to a shorter search time and a fewer number of processing steps and resulting memory accesses. By using an efficient memory data structure, processing efficiency can be improved and the time for data retrieval can be reduced, increasing the overall performance of the mobile computing device using such an efficient data structure. 
     This invention is a method and system by which a relational database may be implemented so as to minimize the amount of memory storage space needed for data storage while allowing for constant time random access to the data. 
     SUMMARY OF THE INVENTION 
     The data structure of this invention uses expandable string buffers, tables, and indexes to hold searchable values for a database. Variable length fields are stored in one or more string buffers, and each item of data will return a pointer to its location. Pointers are uniformly sized records that are stored in one or more tables. One or more indexes are maintained to access the records efficiently. Indexes may be based upon alphabetical or any other desired sorting criteria for indexing of records. 
     When a new entry is made into the system, the value for each field is checked against the existing values in the string buffer(s). If the value is found, a pointer (the buffer offset) is returned. If the value is not in the string buffer(s), the value is added into the string buffer and a pointer to it is returned. Records in the database contain a set number of fields, each of which is an n-byte pointer into a string buffer where the corresponding value for the field is stored. As such records are all of the same size—n times the number of fields (so in a 4-byte system a record with 5 fields would be 20 bytes in size), thus eliminating the need for record headers. String buffers and table buffers are maintained by using B trees, B+ trees, or other suitable data structures. Both the values stored in the string buffer, and the string buffer as a whole may be compressed using conventional techniques. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  represents data as it was entered into the database. 
         FIG. 2  represents the data stored within the string buffer. 
         FIG. 3  relates information from the string buffer to records in the table buffer. 
         FIG. 4  represents pointers in the table buffer referencing the data of  FIG. 2 . 
         FIG. 5  represents indexes stored in the index buffer in alphabetical order. 
         FIG. 6  shows a graphical depiction of a non-contiguous string buffer comprising four segments and containing representative data. 
         FIG. 7  graphically depicts a non-contiguous table buffer containing values related to the representative data shown in  FIG. 6 . 
         FIG. 8  is a graphical representation of records retrieved from the database. 
         FIG. 9  graphically represents an index buffer having an alphabetical index to the table buffer of  FIG. 7 . 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     As shown in  FIG. 1 , information is entered into a database as a serial string of inputs I 1, I 2, and I 3. Each input string represents a named entity having an address. In practice, the information may consist of any set of related data which may include but not be limited to contact information (address, telephone numbers, e-mail addresses, etc.), accounting information, organized lists, or any other data that is or can be related to other data within an organized data structure. As data is entered, it is preferably stored contiguously in one or more string buffers, as in  FIG. 2 , and a pointer is returned to the table buffer. However, before each input field value is stored, the string buffer is checked to see whether the same value already exists within that buffer. If the same value does exist, a pointer to the existing value is returned and processing moves to the next input field. If that value does not exist, however, it is stored in the string buffer, preferably contiguously, and a pointer to that value is returned. Once this is done for each field in the entry, a record is added to the table, and the index is updated. The string buffers, tables and indexes are all expandable to meet demand. Although a single string buffer, table buffer, and index buffer are referenced, it will be understood that each buffer may comprise more than one continuous segment, and that such occurrence will have little or no effect upon the application or efficiency of the invention. The string buffers and pointers are maintained by using either B trees, B+ trees or other suitable data structure. 
       FIG. 3  references field values from the string buffer with pointers (offsets within the string buffer) indicating the memory locations in one or more string buffer(s) at which each field value may be found. Pointers have a fixed size and are maintained in one or more table buffers. Each pointer is a number comprising n-bytes. In the preferred embodiment, n=4 bytes, although pointers of any reasonable size can be used. Where n=4 bytes, and each record has five fields or columns, as in the example depicted in the drawings, each record in the string buffer, regardless of length, will be referenced using only 20 bytes of memory in the table buffer. This may be seen, for example, in the storage of Record R 1  in the string buffer ( FIG. 2 ). The “Name” value for the first record (“ABC”) is stored at string buffer offset 00. A pointer in the table buffer to that value points to offset 0 in the string buffer. The “Address”, “City”, “State”, and “Zip Code” fields for Record R 1  are similarly pointed to at offsets  4 ,  14 ,  21  and  29 , respectively. 
     Record R 2  may similarly be located by reference to  FIGS. 2 and 3 . However, as is shown in  FIG. 3 , the “City” and “State” fields for Record R 2  are the same as for Record R 1 , and will not be duplicated in the string buffer ( FIG. 2 ). Rather, as shown in  FIG. 3 , pointers to “City 1” and “State 1” for Record R 2  will point to the offsets in the string buffer where those values are already stored, at offsets  14  and  21 . Similarly, Record R 3  has a value for “State” that is the same as for Records R 1  and R 2 . Hence, the pointer in Record R 3  points to offset 21 in the string buffer, and avoids the need for duplicate values to be entered into the string buffer. 
     As shown in  FIG. 4 , each pointer (“Val”) in the table buffer is a 4-byte value, the positions within that buffer being of a uniform size. Each record utilizes five 4-byte values, or a total of 20 bytes. The indicators “R 1 ,” “R 2 ,” and “R 3 ” are not part of the table itself, but are given only for reference in showing the structure of the table. 
       FIG. 5  shows an index buffer in which the beginning offset for each record in the table buffer is given. The index buffer shows the records in alphabetical order, with “ABC” being the “Name” for the first record, and being located by referring to offset 00 in the table buffer which, in turn, references offset 00 in the string buffer. The second record begins with a “T” (for entity “TEST 1”). In the index buffer, the second alphabetical record is shown with a value of 40. Referring to offset 40 in the table buffer, the offset at location 66 in the string buffer is where the record begins, as can be verified by reference to  FIG. 2 . The third record alphabetically begins with the name “WXYZ,” and may be located in the index buffer at value 20, referring to offset 20 in the table buffer, which points to location 40 in the string buffer. 
       FIGS. 1-5  depict the data structure of the invention in idealized format. That is, each entry is located contiguous to the preceding and subsequent entries, with no gaps in the relevant memory buffers. In practice, however, such is seldom the case, as memory storage may require the use of non-contiguous blocks of memory. This is particularly so where long term storage may be maintained on a disc drive. Because of this potential limitation,  FIGS. 6 ,  7 , and  9  represent the efficient memory utilization of the invention under conditions that may be encountered in practice. 
       FIG. 6  depicts a string buffer comprising four non-contiguous buffers, each beginning at offset “1” and being capable of holding fewer than 30 characters. A comparison of  FIGS. 1 and 6  shows that identical data has been entered and stored in memory, with  FIG. 6  showing the data distributed across four non-contiguous string buffers.  FIG. 7  depicts a table buffer comprising two non-contiguous buffers, each beginning at offset 0. In this depiction, however, pointers to the string buffer are made by first referencing the buffer number ( 1 - 4 ), followed by the offset within that buffer. For example in table buffer No. 1, the first field (“Name”) in record (R 1 ) is referenced as string buffer no. 1, offset 1. The second field (“Address”) is referenced at string buffer no. 1, offset 5. This procedure is followed for all pointers in the table buffer. Once entered, such information can be stored and later recalled for display or printing as shown in  FIG. 8 . In  FIG. 8 , the information is formatted as discrete records divided into separate fields as mailing addresses in the United States, each record having five fields, each field representing an entity name, a street or box office address, a city, a state, and a zip code. 
       FIG. 9  depicts an index buffer in which records stored in the string buffer of  FIG. 6  and the table buffer of  FIG. 7  may be retrieved or listed in alphabetical order, using the same buffer number—offset location schema as described for  FIGS. 6 and 7 . 
     It will be understood that the embodiments shown herein are exemplary and instructional, and that the invention is not limited to such embodiments and examples, but may be used for the efficient storage of any items of related data or information without departing from the scope and spirit of the invention.