System for managing and accessing a dynamically expanding computer database
First Claim
Patent Images
1. In a computer system, a method of record management to provide range access in a hash table for a computer database, comprising the steps of:
- (A) assigning a key value to each record to be stored in the hash table;
(B) constructing the hash table having a hash table size, S, by the steps including;
(1) hashing records using the key value to one or more pages of memory using an order preserving, hashing function, which is a function of the hash table size, S;
(2) setting a split pointer to a first page of the hash table;
(3) updating a range index tree as pages of memory are added or deleted, the range index tree including one or more pages containing a list of ranges and an associated list of page pointers which are entered in range order as the hash table is modified;
(4) storing records to one or more pages of the hash table according to the hashing function of step (B)(1), wherein for a particular record hashed to a particular destination page, the step of storing includes the steps of;
(a) if the particular destination page contains enough memory to store the particular record, then storing the particular record in the particular destination page;
(b) if the particular destination page does not contain enough memory to store the particular record, then storing the particular record in an overflow page and updating the range index tree to point to the overflow page;
(c) splitting an unsplit page pointed to by the split pointer, by the steps including;
(i) reallocating a key space of the unsplit page to both the unsplit page and a buddy page to form an unsplit key space and a buddy key space;
(ii) reallocating records of the unsplit page and the overflow page to the unsplit page and the buddy page according to the unsplit key space and the buddy page key space;
(iii) incrementing the split pointer to a next page in the hash table;
(iv) if the split pointer points to the Sth page of the table,thena. reset the split pointer to the first page of the hash table; and
b. hash future records according to a next level hashing function; and
(v) updating the range index tree to store the unsplit page key space and the buddy page key space.
9 Assignments
0 Petitions
Accused Products
Abstract
A database management and access system is described which provides dynamic key space allocation to one or more pages of the database as records are added to the database. The database management and access system includes a page access subsystem and a record access subsystem to facilitate record access by incorporating an order preserving, linear hashing function for cluster preservation and using empty page flags and overflow page flags to decrease range query time latencies of the database.
57 Citations
12 Claims
-
1. In a computer system, a method of record management to provide range access in a hash table for a computer database, comprising the steps of:
-
(A) assigning a key value to each record to be stored in the hash table; (B) constructing the hash table having a hash table size, S, by the steps including; (1) hashing records using the key value to one or more pages of memory using an order preserving, hashing function, which is a function of the hash table size, S; (2) setting a split pointer to a first page of the hash table; (3) updating a range index tree as pages of memory are added or deleted, the range index tree including one or more pages containing a list of ranges and an associated list of page pointers which are entered in range order as the hash table is modified; (4) storing records to one or more pages of the hash table according to the hashing function of step (B)(1), wherein for a particular record hashed to a particular destination page, the step of storing includes the steps of; (a) if the particular destination page contains enough memory to store the particular record, then storing the particular record in the particular destination page; (b) if the particular destination page does not contain enough memory to store the particular record, then storing the particular record in an overflow page and updating the range index tree to point to the overflow page; (c) splitting an unsplit page pointed to by the split pointer, by the steps including; (i) reallocating a key space of the unsplit page to both the unsplit page and a buddy page to form an unsplit key space and a buddy key space; (ii) reallocating records of the unsplit page and the overflow page to the unsplit page and the buddy page according to the unsplit key space and the buddy page key space; (iii) incrementing the split pointer to a next page in the hash table; (iv) if the split pointer points to the Sth page of the table, then a. reset the split pointer to the first page of the hash table; and b. hash future records according to a next level hashing function; and (v) updating the range index tree to store the unsplit page key space and the buddy page key space.
-
-
2. In a computer system, a method of record retrieval using range access in a hash table for a computer database having a range of records including a first record and a last record, comprising the steps of:
-
(A) using a key value associated with the first record to determine a range in which the first record is stored; (B) locating the range in a range index tree by the steps of; (1) hashing to a lowest level index page in the range access tree; (2) retrieving a page pointer to a page associated with the range; (3) reading a flag from a page designating empty ranges; (4) skipping empty ranges and fetching non-empty pages in the hash table; (5) repeat steps (2),(3), and (4) until reading a last page; and (C) locating the first record by performing a binary search on a fetched page; and (D) locating subsequent records by sequentially searching fetched pages. - View Dependent Claims (3)
-
-
4. A method for distributing a plurality of records to one or more pages in a hash table, comprising the steps of:
-
(A) assigning a key value to each record of the plurality of records; (B) selecting a hashing function for the keys of the records, wherein the hashing function is an order preserving, linear hashing function, which is constructed using a series of functions dependent on hash table size; and (C) distributing records to pages of the hash table according to the hashing function, comprising the steps of; (1) initializing the hash table, including the steps of; (a) pointing to a current page of the hash table using a split pointer; (b) creating a first page of the hash table; (c) setting the split pointer to the first page of the hash table; (d) setting a level counter to zero; (e) creating a hash table range index page, wherein the hash table range index page stores a list of ranges and a list of page pointers, and wherein a single range in the list of ranges is associated with a single page pointer in the list of page pointers; (f) storing in the list of ranges a first range containing a maximum range of key values; and (g) storing in the list of page pointers a first pointer for pointing to the first page; (2) constructing the hash table, comprising the steps of; (a) choosing a record from the plurality of records and its associated key value; (b) hashing to a destination page according to the level counter and split pointer, the destination page having a destination page range and a destination page pointer in the hash table range index page; (c) determining a storage limit for the destination page; and (d) storing the record in the destination page, including the steps of; (i) if adding the record to the destination page would not exceed the storage limit, storing the record in the destination page; (ii) if adding the record to the destination page would exceed the storage limit; a. storing the record in an overflow page, including the steps of; - View Dependent Claims (7, 8, 10, 11)
-
-
5. creating an overflow index page to point to the overflow page;
-
2. setting page pointers in a previous hash table range index page to point to the overflow index page; and 3. setting an overflow flag in the hash table index page to indicate overflow of the destination page; b. constructing a buddy page to the current page, wherein the buddy page is a linear concatenation to the hash table; c. redistributing records in the overflow page, the current page, and the buddy page, according to a (level counter+1)th hashing function of the series of functions; d. updating the hash table range index page, including the steps of;
-
-
6. locating the destination page range and destination page pointer in the hash table range index page;
-
2. splitting the destination page range into two equal ranges, comprising a first range and a second range, wherein the first range is associated with the destination page pointer and the second range is associated with a buddy page pointer; 3. replacing the destination page range with the first range and inserting the second range and buddy page pointer immediately thereafter in the hash table range index page; and 4. if the destination page has no records, then setting an empty flag in the hash table range index page to indicate the destination page is empty; e. incrementing the split pointer; and f. if the split pointer points to the last page of the hash table; 1. setting the split pointer to the first page of the hash table; and 2. incrementing the level counter; and (3) returning to the step of choosing a record until all records have been added to the hash table.
-
-
9. A database management and access system for a computer database, comprising:
-
(A) page access means for pointing to a particular page from a given key value; (B) record access means for pointing to a particular record from the given key value; (C) overflow page generation means for storing overflow data; and (D) empty page flagging means for eliminating empty pages from range queries of the computer database.
-
-
12. A method for managing a plurality of records in a database in a computer system, comprising the steps of:
-
(A) setting a page size; (B) assigning a key value to each record in the plurality of records; (C) inserting records into the database by the steps of; (1) hashing records into destination pages according to an order preserving, linear hashing function, by the steps including; (a) if the destination pages have memory space to store the records, storing the records in the destination pages according to the order preserving, linear hashing function; and (b) if the destination pages do not have memory space to store the records, storing the records in overflow pages according to the order preserving, linear hashing function and storing ranges of overflow key values and associated overflow page pointers in overflow index pages; (2) storing ranges of key values and associated page pointers in hash table range index pages; (3) setting empty flags for ranges which are empty; and (4) setting overflow flags for ranges with overflow pages; (D) deleting records of the database by the steps of; (1) removing references to deleted records of the database; (2) eliminating empty pages and unnecessary buddy pages of the database; (3) redistributing records into pages according to the order preserving, linear hashing function to condense the database; and (4) adjusting ranges of key values and page pointers in the hash table range index pages according to the database after condensation; and (E) accessing records of the database by the steps of; (1) performing page access using the hash table range index pages and the overflow index pages to obtain one or more page pointers, wherein page access uses the empty flags and the overflow flags to accelerate access; and (2) performing record access by fetching records hashed according to the order preserving, linear hashing function.
-
Specification