Memory efficient representation of relational data with constant time random access to the data itself

摘要

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.

主权项

1. A method for organizing and storing related items of data in a memory space comprising the steps of:
(a) dividing a memory space into at least a string buffer and a table buffer, said table buffer containing at least one record where each of said at least one record comprises an equal number of equal size fields each of which being configured to contain pointers that reference related items of data stored in the string buffer; (b) determining a resulting database structure capable of holding at least one field and at least two records where each of said at least two records contains a pointer that refer to data stored in the database structure; (c) accepting input of discrete items of related data, said discrete items comprising field values within one or more records; (d) storing a first field value in said string buffer at a first location within said string buffer; (e) returning a first string pointer to an offset in said string buffer where said first field value is stored; (f) storing said first string pointer in a first location within said table buffer where said first location and each of all other locations in said table buffer have a fixed size equal to the size of the fixed size pointer; (g) repeating steps (a)-(f) for all field values comprising a first record; (h) if additional data has been accepted, determining a next field value for a next record; (i) searching said string buffer to determine whether said next field value exists within said string buffer; (j) if said next field value exists within said string buffer, returning a next string pointer to said stored field value in said string buffer and storing said next string pointer in a fixed size next location within said table buffer; (k) if said next field value does not exist within said string buffer, storing said next field value in said string buffer at a next location within said string buffer, returning a next string pointer to said next location in said string buffer, and storing said next string pointer in a next location within said table buffer; (l) repeating steps (h)-(k) for all field values for said next record; and (m) repeating step (1) for all records until all records have been stored.