×

System for managing and accessing a dynamically expanding computer database

  • US 5,687,361 A
  • Filed: 02/13/1995
  • Issued: 11/11/1997
  • Est. Priority Date: 02/13/1995
  • Status: Expired due to Term
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.

View all claims
  • 9 Assignments
Timeline View
Assignment View
    ×
    ×