Database indexing method and apparatus

• US 20030135495A1
• Filed: 06/21/2002
• Published: 07/17/2003
• Est. Priority Date: 06/21/2001
• Status: Abandoned Application

• Current Assignee: ISC Incorporated (Svenska Cellulosa AB)
• Original Assignee: ISC Incorporated (Svenska Cellulosa AB)
• Inventors: Vagnozzi, Paul P.
• Application Number:
  US10/176,566
• Publication Number:
  US 20030135495A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures

Abstract

A database indexing method and apparatus which includes an index structure for indexing a plurality of objects that are logically divided into fine slices of 8,000 records each, and the fine slices are grouped into coarse slices of 4,000 fine slices each. The indexes include fine and coarse keys, each of which corresponds to a particular data value and a particular fine or coarse slice. Bit vectors are used to determine which of the fine slices or objects identified by the fine slices have particular attributes, and these bit vectors can be stored in compressed format. The index structure can be used to index data where no data records exist. A word indexing technique for crossing page boundaries within a document is also disclosed, as well as a technique for enumerating and displaying virtual folders and their contents.

Claims

1. A computer-readable memory for storing one or more indexes used to associate data with a plurality of objects, wherein each of the objects has a plurality of attributes associated therewith and one or more data values for each of the attributes, said computer-readable memory comprising:

a non-volatile data storage device;

an index stored on said data storage device, said index being associated with a first attribute of the objects, wherein said index comprises a number of keys that include one or more coarse keys and a number of fine keys, wherein each of said fine keys is associated with a group of the objects and with one of the first attribute'"'"'s data values, and wherein said one or more coarse keys are each associated with a particular one of the first attribute'"'"'s data values and with a set of said fine keys that are also each associated with that particular data value.

2. A computer-readable memory as defined in claim 1, wherein some of said fine keys are associated with a first data value and others of said fine keys are associated with a second data value, wherein both said first and second data values are data values associated with the first attribute.

3. A computer-readable memory as defined in claim 2, wherein said index includes coarse keys associated with each of said first and second data values.

4. A computer-readable memory as defined in claim 1, wherein said keys include a first portion that identifies whether it is a group key or a set key, a second portion that identifies the group or set to which it corresponds, and a third portion that indicates the data value to which it corresponds.

5. A computer-readable memory as defined in claim 4, wherein said third portion comprises an attributename:

;

attributevalue pair wherein the attributename identifies the attribute with which the key is associated and the attributevalue indicates the data value with which the key is associated.

6. A computer-readable memory as defined in claim 4, wherein said keys are stored in order based upon the contents of said first, second, and third portions.

7. A computer-readable memory as defined in claim 4, wherein said first portion comprises the left most portion of each key, said second portion comprises the middle portion of each key, and said third portion comprises the right-most portion of each key.

8. A computer-readable memory as defined in claim 7, wherein said first portion comprises a single bit.

9. A computer-readable memory as defined in claim 1, wherein said index includes a number of bit vectors, each comprising a sequence of bits, and wherein each of said bit vectors is associated with a particular one of the keys and with the data value associated with that particular key.

10. A computer-readable memory as defined in claim 9, wherein said index includes a link for each of said keys, and wherein at least some of said links each indicate the location of the bit vector corresponding to the key associated with the link.

11. A computer-readable memory as defined in claim 9, wherein at least some of said bit vectors comprise fine bit vectors, with each bit within any selected one of the fine bit vectors corresponding to one of the objects and indicating whether its corresponding object has the data value associated with the bit vector as it first attribute.

12. A computer-readable memory as defined in claim 11, wherein each bit position with a fine bit vector corresponds to a different one of the objects.

13. A computer-readable memory as defined in claim 11, wherein each of said fine keys is associated with a fine link and wherein at least some of said fine links each provide a pointer to a corresponding one of said fine bit vectors.

14. A computer-readable memory as defined in claim 13, wherein at least one other of said fine links identifies a single object within the group of objects associated with that fine link.

15. A computer-readable memory as defined in claim 14, wherein each of said fine links includes at least one bit that indicates whether the link includes a pointer to a fine bit vector or an identifier of the single object.

16. A computer-readable memory as defined in claim 9, wherein at least some of said bit vectors comprise coarse bit vectors each associated with a different one of the coarse keys, with each bit within any selected one of the coarse bit vectors corresponding to a different group of objects and indicating whether any of the objects with the corresponding group has the data value associated with the coarse bit vector as it first attribute.

17. A computer-readable memory as defined in claim 16, wherein each of said coarse keys is associated with a coarse link and wherein at least some of said coarse links are each used to link one of the coarse bit vectors with its associated key.

18. A computer-readable memory as defined in claim 17, wherein at least one other of said coarse links identifies a single group of objects within the set of groups associated with that coarse link.

19. A computer-readable memory as defined in claim 18, wherein each of said coarse links includes at least one bit that indicates whether the link includes a pointer to a coarse bit vector or an identifier of the single group.

20. A computer-readable memory as defined in claim 18, wherein each of the ones of said coarse links that identify a single group include at least one bit that identifies whether or not all of the records within that single group contain the data value associated with the coarse link.

21. A computer-readable memory as defined in claim 1, wherein said index is stored as a B-tree.

22. A computer-readable memory as defined in claim 21, wherein said B-tree includes a root node, a plurality of intermediate nodes, and a plurality of leaves and wherein some of said keys are stored at said leaves and others of said keys are stored at said root and intermediate nodes.

23. A computer-readable memory as defined in claim 1, wherein said non-volatile data storage device comprises a plurality of fixed magnetic disk drives, wherein said database is stored as a single file that spans at least two of said fixed magnetic disk drives.

24. A computer-readable memory as defined in claim 1, further comprising a second index stored on said non-volatile data storage device, said second index being associated with a second attribute of the objects, wherein said second index comprises a number of keys that include one or more coarse keys and a number of fine keys, wherein each of said fine keys of said second index is associated with a group of the objects and with one of the second attribute'"'"'s data values, and wherein said one or more coarse keys of said second index are each associated with a particular one of the second attribute'"'"'s data values and with a set of said fine keys from said second index that are also each associated with that particular data value.

25. A computer-readable memory as defined in claim 24, wherein said indexes are each stored in a separate file on said non-volatile data storage device.

26. A computer-readable memory as defined in claim 24, wherein said indexes are stored as a single file and together comprise a single index with each key of the single index including an indexname:

;

attributename;

;

attributevalue triplet, wherein the indexname identifies one of the two indexes, the attributename identifies the attribute with which the key is associated, and the attributevalue indicates the data value with which the key is associated.

27. A computer-readable memory for storing one or more indexes used to associate data with a plurality of objects, wherein each of the objects has a plurality of attributes associated therewith and one or more data values for each of the attributes, said computer-readable memory comprising:

a non-volatile data storage device;

an index stored on said data storage device and being associated with a first one of the attributes, said index including a plurality of compressed bit vectors used to identify which objects have a particular data value for the first attribute, wherein at least some of said compressed bit vectors utilize run length encoding and have a variable run length field size.

28. A computer-readable memory for storing one or more word indexes used to index words contained in documents, said computer-readable memory comprising:

a non-volatile data storage device;

a word index stored on said data storage device, said word index being associated with a text word contained in at least one of the documents, wherein said word index includes a number of bit vectors that include a sequence of bits wherein each bit corresponds to a portion of one of the documents, with some of the bits corresponding to an individual page of the document and others corresponding to portions of two adjacent pages of the document.

29. A computer-readable memory for storing indexes used to associate a time stamp with a plurality of objects, said computer-readable memory comprising:

a non-volatile data storage device;

a plurality of indexes stored on said data storage device, each having time stamp information related to an event concerning each of the associated objects, wherein each index includes a number of keys with the keys of each index being associated with a different length time interval than the keys of the other index(es), and wherein the time stamp for each of the objects is determinable from a combination of data contained in each of the indexes.

30. A computer-readable memory for storing one or more indexes used to represent hierarchical relationships between objects, wherein each of the objects has a plurality of attributes associated therewith and one or more data values for each of the attributes, said computer-readable memory comprising:

a non-volatile data storage device;

a plurality of indexes stored on said data storage device and each being associated with a different one of the attributes and each index associating data values of its corresponding attribute with objects that have those data values of the corresponding attribute; and

a computer program operable to access the indexes and to provide a graphical user interface displaying a virtual folder corresponding to a particular one of the data values and displaying a set of object identifiers contained within that virtual folder, wherein the object identifiers represent those objects that are associated with the particular data value.