Abstract:
The master/slave index is an indexing method and apparatus that does not suffer from poor performance when stored in a file system by completely avoiding any seek operation when searching or updating the indexed information. Heterogenous attributes from objects of different types are split in a master index and at least one slave index, reserving no memory for non-existent attributes. Index tables can be merge-joined because they maintain their ordering across tables.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is claiming the benefit under 35 § USC 119(e) of the prior provisional application 60/845,222 (master/slave index in computer systems), filed on Sep. 18, 2006. 
       US PATENT REFERENCES 
       [0002]    Merge join process, U.S. Pat. No. 6,185,557 issued Feb. 6, 2001. 
     
     FIELD OF THE INVENTION 
       [0003]    This invention is generally related to computer systems. More particularly, the invention is related to storage systems, including but not limited to file systems. 
       BACKGROUND OF THE INVENTION 
       [0004]    This invention has been made in the context of, but is not limited to, file systems. A file system associates files with a number of attributes, including but not limited to a name, the size of the file and time of last modification. Supplementing the attributes given to each file, certain file formats introduce further attributes specific to their file type. 
         [0005]    To gain quick access to all attributes, they need to be indexed. The method and apparatus described herein enables quick access by taking the behaviour of file systems and storage media into account. Previously used indexes are derived from database systems and perform poorly when stored as files in file systems. 
         [0006]    The poor performance of known indexing structures, including but not limited to trees in all embodiments, is caused by the fact that seek operations, i.e. jumps inside the file body, are needed when processing queries or updating the index. This is not the case when such indexes are stored in reserved and unstructured regions of the disc, which is the case with most database systems. 
         [0007]    The indexing method and apparatus presented circumvents the penalties described above when storing the index in a file system by completely avoiding any seek operation in the index file, hence always reading them sequentially. Additionally, heterogenous attribute sets of different lengths are stored without wasting memory. 
         [0008]    The advantages of the master/slave index also apply to other data with heterogenous attributes, hence of different type, including but not limited to tuples in relational databases that adhere to different schemes. 
       SUMMARY OF THE INVENTION 
       [0009]    According to an embodiment of the invention, an indexing system that stores attributes assigned to objects and comprises of at least one master index table and at least one slave index table. The master index table stores attributes that are properties of all objects to be indexed; a slave index stores attributes that are only properties of certain object types. The stored information is being altered or searched by merge-joining tuples across index tables that belong to the same object. 
         [0010]    According to another embodiment of the invention, a master/slave index that stores attributes derived from files, including but not limited to so-called “metadata” extracted from the file body. 
         [0011]    According to yet another embodiment of the invention, a master/slave index that stores attributes derived from tuples stored by databases, including but not limited to relational databases. 
     
     
       DESCRIPTION OF THE DRAWINGS 
         [0012]      FIG. 1  illustrates the master/slave index. 
           [0013]      FIG. 2  illustrates the processing of a query on the master/slave index. 
           [0014]      FIG. 3  illustrates the deletion of objects from the master/slave index. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0015]    The embodiments of the master/slave index are described using file system and relational database terminology familiar to one skilled in the art. 
         [0016]    Files stored in a file system have got multiple attributes attached to them. The file system assigns standard attributes, including but not limited to filename, size and the date of the last write access. In addition to these attributes, file formats offer further attributes specific for a file type, e.g. the resolution of an image or the artist and song title of an MP3 audio file. 
         [0017]    To be of any practical use, all files within a directory have to be read and parsed to access the metadata. Since this process is time consuming, it is common practice for applications to extract the attributes only once and store them in a more convenient structure which is called index, the method and apparatus presented here one embodiment thereof. 
       Conceptional Overview 
       [0018]    The basic idea of this utility is to store all attributes common to all data objects in a table which is called master index. For each type of data object that introduces additional attributes, an additional secondary table which is called slave index is stored. 
         [0019]    A specific embodiment of this idea is illustrated in  FIG. 1 . The master/slave index in  FIG. 1  stores the attributes of five data objects. The master index  101  contains all attributes which occur in all five data objects, including but not limited to a name and the object type. 
         [0020]    For each of the two object types in  FIG. 1 , JPEG images and MP3 audio files, secondary slave indexes  102   103  are introduced. They contain all attributes which occur only in the specific object type accounted for by the slave index table, supplemented by the name of each data object. 
         [0021]    Since both the master index  101  and all slave indexes  102   103  store only attributes defined by specific data formats, no memory is wasted which is an advantage of this invention over the obvious approach to store all attributes from all data objects in a large single table. 
       Adding Additional Data Objects 
       [0022]    Additional data objects are indexed by appending their attribute tuples to the master index  101  and the appropriate slave index tables, i.e.  102   103  in  FIG. 1 , processing one data object at a time. 
         [0023]    This method ensures that all data objects maintain their order in all index tables, which is a vital property for other operations presented in subsequent paragraphs. The order of two data objects is only relevant for objects of the same type: if a certain data object precedes another data object of the same type in the master index  101 , it must do so in the appropriate slave index and vice versa. 
         [0024]    If a given embodiment of the master/slave index fullfills this requirement, it will also do this after appending an additional element to the index tables, because the order of already existing tuples is not affected, and the appended attributes will both be the last tuples in master index  101  and the assigned slave index  102   103 , thus also ordered. 
       Query Processing 
       [0025]    Processing queries over a given embodiment of a master/slave index is easily the most prominent function of this invention. A method for query processing, including but not limited to searching, is illustrated in  FIG. 2 . 
         [0026]    In the beginning, a marker  201   202   203  is associated with each index table  101   102   103 , pointing to the first tuple respectively. This is illustrated in  FIG. 2A . It is assumed that the master/slave index is non-empty. 
         [0027]    When the master/slave index has been created by appending tuples to the empty index as described in the paragraphs  22  to  24 , the marker  201  in the master index  101  and the marker at the assigned slave index ( 202  in FIG.  2 A) point to the attributes of the same data object, because elements maintain their order across tables as described in paragraph  24 . 
         [0028]    All attributes of the first data object are now available at the marker positions for processing in a search query (i.e. comparing with query properties) or for updating the attributes. 
         [0029]    In a subsequent step, the marker  201  in the master index  101  and the marker  202  at the assigned slave index  102  are advanced to the next tuple in their respective index table or, if there is no further entry, disposed of. 
         [0030]    The marker  201  in the master index  101  and the marker at the assigned slave index ( 203  in  FIG. 2B ) now point the attributes of the next data object. 
         [0031]    The method described in the paragraphs above are repeated until all markers have been disposed of, hence the index tables have been processed completely.  FIG. 2C  illustrates the next iteration of this process. 
         [0032]    This method of query processing requires no seek operating, i.e. jumps to other tuples other than subsequent ones, thus avoiding any overhead imposed by a file system. 
         [0033]    As trees or similar indexing methods are generally considered to be efficient even by people skilled in the art, the method and apparatus presented here is not obvious to those. 
       Removing Data Objects 
       [0034]    The deletion of attribute tuples from the master/slave index is illustrated in  FIG. 3 . In addition to the master index  101  and the slave indexes  102   103 , an additional table called “deletion list”  300  is introduced, which contains references to the data objects to be deleted (file names in  FIG. 3A ). 
         [0035]    The deletion process is very similar to the method of query processing described above, including the placement of markers  201   202   203  at the first tuple of each table. The deletion list  300  does not need any marker. This configuration is illustrated in  FIG. 3A . 
         [0036]    During processing as described above, each data object is looked up in the deletion list  300 . If found, the tuple in the master index  101 , the assigned slave index  102  and the deletion list  300  is removed. This is illustrated in  FIG. 3B . 
         [0037]    This method is repeated until either all data objects in the master/slave index have been processed, or the deletion  300  list becomes empty. This end situation is illustrated in  FIG. 3C . 
         [0038]    It is to be understood that the above description is intended to be illustrative, and not restrictive. Many other embodiments will be apparent to those skilled in the art upon reviewing the above description. The scope of the invention should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.