Method and apparatus for fast accessing of data items from a sorted list for use with such method and/or apparatus

• US 5,592,665 A
• Filed: 09/29/1994
• Issued: 01/07/1997
• Est. Priority Date: 10/04/1993
• Status: Expired due to Term

• Current Assignee: Continental Automotive GmbH (Continental AG)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Lahaije, Paul D. M. E.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/315,156
• Time in Patent Office: 831 Days
• Field of Search: 395/600, 395/404, 364/DIG. 1
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for accessing a data item from a data base has the full data base contained in a plurality of blocks in a slow background memory and furthermore has a faster foreground memory. Each data item has a label containing one or more elements. The data base furthermore has an index containing a second multiplicity of treewise organized index items each comprising an initial part of its label header, one or more secondary pointers and an indication of whether all data items having that initial part are contained in only one or in a plurality of blocks. First the index is accessed with the initial part of the label. If the index item pertaining to the latter initial part signals is contained in only a single block, the pointer in that index item points to that single block and the block is stored in the foreground memory. Extending the initial part to a full header identifies an intended subset of data items for accessing through its completed label. If the data items having the initial part are contained in a plurality of blocks, the pointer of the current index item points to a further index item of the tree having the current initial part extended by a next successor label element, whereupon the process repeats for the extended label header.

Claims

1. A method for accessing a particular subset of data items from among a multiplicity of data items of a data base contained in a relatively slow background memory, each data item comprising a string of label elements, and said data base comprising a sequence of blocks together containing said data items and furthermore comprising an index containing a second multiplicity of treewise organized index items each comprising an initial part of a label header of an associated subset of data items, one or more pointers and an indication of whether all data items associated to that initial part are contained in only a single said block or in a plurality of said blocks, said method comprising the steps of:

storing said index in a relatively fast foreground memory;

with respect to said index detecting of a particular such initial part being called;

then upon finding with respect to the latter initial part said subset being contained in only a single block, reading the pointer contained in said index item as primary pointer to an associated single block and storing that block in said foreground memory while enabling extending said initial part to a full header for identifying said associated subset, and accessing such subset in the single block through its eventually completed label;

but upon finding with respect to the latter initial part said being contained in a plurality of blocks reading any pointer contained in said index item as secondary pointer to a further index item of said tree having the current initial part extended by a next successor label element while enabling selective extending of the current initial part by such next successor label element.

2. A method as claimed in claim 1, and comprising upon detecting extending by an incongruous element an error signalizing step.

3. An apparatus for accessing a particular subset of data items from among a multiplicity of data items each provided with a string of label elements of a data base, said apparatus containing a relatively slow background memory with first access means and having said data base that comprises a sequence of storage blocks containing said data items and furthermore an index containing a second multiplicity of treewise organized index items each comprising an initial part of its label header, one or more pointers and an indication of whether all data items pertaining to that initial part are contained in only a single said block or in a plurality of said blocks, said apparatus comprising:

a relatively fast foreground memory with second access means;

control means for activating said first access means for storing said index in said foreground memory;

first detecting means for detecting a particular such initial part being called;

second detecting means for detecting with respect to the latter initial part said subset being contained in only a single block, and thereupon under control of a pointer contained in said index item accessing the associated single block and storing that block in said foreground memory while enabling extending said initial part to a said full header of a subset identified thereby and thereupon activating second accessing means for accessing such identified subset of data items;

but for upon finding with respect to the latter initial part said being contained in a plurality of blocks reading any pointer contained in said index item to a further index item of said tree pertaining to the current initial part extended by a next successor label element while enabling selective extending of the current initial part by such next successor label element.

4. An apparatus as claimed in claim 3, wherein said background storage means is an optical disc.

5. Method for accessing a data base comprising the steps of

a. maintaining the data base in a relatively slow background memory, the data base comprising a multiplicity of data items organized into a sequence of blocks, each data item comprising a label header which includes a string of label items;

b. maintaining an index in a relatively fast foreground memory, the index containing index items organized as a tree, each index item including

i. at least one respective label item that is a respective initial part of the label header of an associated subset of data items in the data base;

ii. at least one respective pointer that points either directly to the associated subset of data items or to another index item; and

iii. a respective indication of whether all data items associated with the initial part are contained within a single block of the data base;

detecting calling of a particular one of the respective initial parts in a call for a desired data item;

d. determining from the respective indication whether the particular one is associated with data items contained within a single block;

e. upon a positive result of the determining step,

i. reading the respective pointer for the particular one of the respective initial parts;

ii. copying, to the foreground memory, the single block containing the desired data item;

iii. detecting additional label items for locating the desired data item within the single block; and

iv. locating the desired data item in the foreground memory, based on the additional label items and the index; and

f. upon a negative result of the determining step,

i. detecting an additional label item in the call; and

ii. identifying a path along the tree using the particular one of the respective initial parts and an additional index item specified by the additional label item, the path leading to a block containing the desired data item.

6. The method of claim 5 wherein step f, further comprises

iii. iteratively

A. extending a detected label header by detecting label items in the call;

B. identifying further index items upon extensions of the detected label header, based on pointers in previous index items;

v. copying, to the foreground memory, an appropriate single block containing the desired data item, as soon as the appropriate single block is unambiguously identified by the detected label header;

vi. detecting additional label items in the call for locating the desired data item within the appropriate single block; and

vii. locating the desired data item in the foreground memory, based on the additional label items and the index.

7. The method of claim 5 wherein the label items contained in at least one index item do not constitute a complete label header.

8. The method of claim 5 wherein the single block is copied to the foreground memory while characters in the call are still being received.

9. Apparatus for accessing a data base comprising:

a. a relatively slow background memory containing a stored data base, the data base comprising a multiplicity of data items organized into a sequence of blocks, each data item comprising a label header which includes a string of label items;

b. a relatively fast foreground memory for storing

i. a retrieved block of the data base and

ii an index containing index items organized as a tree, each index item including

A. at least one respective label item that is a respective initial part of the label header of an associated subset of data items in the data base;

at least one respective pointer that points either to the associated subset of data items or to another index item; and

C. a respective indication of whether all data items associated with the initial part are contained within a single block of the data base;

c. a processor which is programmed for

i. detecting calling of a particular one of the respective initial parts in a call for a desired data item;

ii. determining from the respective indication whether the particular one is associated with data items contained within a single block;

iii. upon a positive result of the determining step,

A. reading the respective pointer for the particular one of the respective initial parts;

B. copying, to the foreground memory, the single block containing the desired data item;

C. detecting additional label items for locating the desired data item within the single block; and

D. locating the desired data item in the foreground memory, based on the additional label items and the index; and

iv. upon a negative result of the determining step,

A. detecting an additional label item in the call; and

B. identifying a path along the tree using the particular one of the respective initial parts and an additional index item specified by the additional label item, the path leading to a block containing the desired data item.

10. The apparatus of claim 9 wherein the processor is further programmed for, upon a negative result of the determining step

C. iteratively

I extending a detected label header by detecting label items in the call;

and

II. identifying further index items upon extensions of the detected label header, by following pointers from previous index items;

D. copying, to the foreground memory, an appropriate single block containing the desired data item, as soon as the appropriate single block is unambiguously identified by the detected label header;

E. detecting additional label items in the call for locating the desired data item within the appropriate single block; and

F. locating the desired data item in the foreground memory, based on the additional label items and the index.

11. The apparatus of claim 9 wherein the background memory is a CD-ROM or other optical disk.

12. The apparatus of claim 9 wherein the label items contained in at least one index do not consitute a complete label header.

13. The apparatus of claim 9 wherein the single block is copied to the forward memory while characters in the call are still being received.

14. Computer storage medium comprising

a. a stored data base, the data base comprising a multiplicity of data items organized into a sequence of blocks, each data item comprising a label header which includes a string of label items;

and

b. an index, for uploading into a foreground memory, the index containing index items organized as a tree, each index item including

i. at least one respective label item that is a respective initial part of the label header of an associated subset of data items in the data base;

ii. at least one respective pointer which points either directly to the associated subset of data items or to another index item; and

iii. a respective indication of whether all data items associated with the initial part are contained within a single block of the data base.

15. The medium of claim 14 comprising a CD-ROM or other optical disk.

16. The medium of claim 14 wherein the at least one respective label item of the other index item includes the respective initial part of the index item pointing to the other index item plus at least one additional label item.