Method and apparatus for fast accessing of data items from a sorted list for use with such method and/or apparatus
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2)
-
-
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. - View Dependent Claims (4)
-
-
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. - View Dependent Claims (6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16)
- and
Specification