System and method for array-based data storage and search

Abstract

Provided are computer devices and methods for effectively generating and updating a sorted array for quick data access. The array allocates more space than required by the elements it stores. In other words, the array leaves empty spaces between elements such that insertion of a new element only requires the shifting of a small number, or even none, of the existing elements in the array.

1 . A computer system for inserting in an input data element to an array, comprising a processor, memory and program instructions which, when executed by the processor, configure the system to:
 (a) load an array into memory, wherein the array has a size of B for storing, at a maximum, B data elements, wherein the array contains T data elements, and wherein the data elements are sorted in the array such that any position in the array, if not empty, contains a data element that is greater than all data elements stored in positions on the left and smaller than all data elements stored in positions on the right;   (b) identify, in the array, a first data element as the greatest among all data elements smaller than the input data element and a second data element as the smallest among all data elements greater than the input data element, wherein the first and second data elements are adjacent to each other or separated by one or more empty positions therebetween; and   (c) (i) if the first and second data elements are located in adjacent positions, shift the first data elements and all adjacent data elements on the left to one position to the left and then placing the input data element in the position vacated by the first data element, or shift the second data elements and all adjacent data elements on the right to one position to the right and then placing the input data element in the position vacated by the second data element, or
 (ii) place the input data element in a position between the first and second data elements. 
   
     
     
         2 . The computer system of  claim 1 , wherein B is at least 20% greater than T. 
     
     
         3 . The computer system of  claim 1 , wherein the first and second data elements are separated by at least three empty positions and the input data element is placed in the middle position among the empty positions. 
     
     
         4 . The computer system of  claim 1 , wherein the program instructions further configure the system to, when a ratio f=T/B is greater than a predetermined threshold, enlarge the size of the array to L by allocating memory for L-B additional positions to the array. 
     
     
         5 . The computer system of  claim 4 , wherein the predetermined threshold is between 0.5 and 0.9. 
     
     
         6 . The computer system of  claim 4 , wherein the program instructions further configure the system to shift one or more data elements in the array so that empty positions in the array are more evenly distributed. 
     
     
         7 . The computer system of  claim 1 , wherein the program instructions further configure the system to repeat steps (b) and (c) for one or more new input data elements. 
     
     
         8 . The computer system of  claim 7 , wherein, for different input data elements, both steps (i) and (ii) are carried out. 
     
     
         9 . The computer system of  claim 1 , wherein the program instructions further configure the system to insert into a second index array, at position p, a value i, wherein p is a hash function output of the input data element and i is the position of the input data element in the array. 
     
     
         10 . The computer system of  claim 9 , wherein the array and the second index array are of the same length. 
     
     
         11 . The computer system of  claim 9 , wherein the hash function generates a unique non-negative integer value for each data element in the array. 
     
     
         12 . A computer system for deleting in a query data element from an array, comprising a processor, memory and program instructions which, when executed by the processor, configure the system to:
 (a) access an array that contains T data elements, wherein the array has a size of B for storing, at a maximum, B data elements, and wherein the data elements are sorted in the array such that any position in the array, if not empty, contains a data element that is greater than all data elements stored in positions on the left and smaller than all data elements stored in positions on the right;   (d) identify a position in the array for containing a data element equal to the query data element; and   (c) mark the position as empty.   
     
     
         13 . The computer system of  claim 12 , wherein the program instructions further configure the system to, when a ratio f=T/B is smaller than a predetermined threshold, shift data elements in the array so that one end of the array has one or more empty positions, and deleting the empty positions from the array, thereby shrinking the size of the array. 
     
     
         14 . The computer system of  claim 13 , wherein the predetermined threshold is between 0.1 and 0.7. 
     
     
         15 . The computer system of  claim 13 , wherein the number of empty position at the end is at least 10% of B. 
     
     
         16 . A method of inserting in an input data element to an array, comprising:
 (a) loading, by a computer processor, an array into a computer-readable memory, wherein the array has a size of B for storing, at a maximum, B data elements, wherein the array contains T data elements, and wherein the data elements are sorted in the array such that any position in the array, if not empty, contains a data element that is greater than all data elements stored in positions on the left and smaller than all data elements stored in positions on the right;   (b) identifying, in the array, a first data element as the greatest among all data elements smaller than the input data element and a second data element as the smallest among all data elements greater than the input data element, wherein the first and second data elements are adjacent to each other or separated by one or more empty positions therebetween; and   (c) (i) if the first and second data elements are located in adjacent positions, shifting the first data elements and all adjacent data elements on the left to one position to the left and then placing the input data element in the position vacated by the first data element, or shifting the second data elements and all adjacent data elements on the right to one position to the right and then placing the input data element in the position vacated by the second data element, or
 (ii) placing the input data element in a position between the first and second data elements.