Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-12-06
1998-12-08
Lintz, Paul R.
Data processing: database and file management or data structures
Database design
Data structure types
G06F 1730
Patent
active
058484167
DESCRIPTION:
BRIEF SUMMARY
This application is the national phase of international application PCT/FI95/00319 filed Jun. 5, 1995 which designated the U.S.
The approach in accordance with the invention is intended for use primarily in connection with central memory databases. A suitable application is the maintenance of a subscriber database in a telephone exchange.
The prior art unidimensional directory structure termed digital trie (the word "trie" is derived from the word "retrieval" in the English language) is the underlying basis of the principle of the present invention. The digital trie is a tree-like structure composed of two types of nodes: leaf nodes containing a record, and internal nodes guiding the retrieval. An internal node is an array having a size of two by the power of k (2.sup.k) elements. If an element is in use, it refers either to an internal node at the next level in the directory tree or to a leaf node containing a record. In other cases, the element is free (empty). Conducting a search in the database proceeds by examining the search key (which in the case of a subscriber database in a telephone exchange, for instance, is typically the binary numeral corresponding to the telephone number of the subscriber) k bits at a time. The bits to be searched are selected in such a way that at the root level of the structure (in the first internal node), k leftmost bits are searched; at the second level of the structure, k bits next to the leftmost bits are searched, etc. The bits to be searched are interpreted as an unsigned binary integer that is employed directly to index the element array (the index indicates a given element in the array). If the element indicated by the index is free, the search will terminate as unsuccessful. If the element refers to an internal node at the next level, k next bits extracted from the search key are searched at that level in the manner described above. As a result of comparison, searching routine branches off either to an internal node at the next level or to a leaf node typically containing a key-pointer pair. If the element refers to a leaf node containing a record, the key stored therein is compared with the search key. The entire search key is thus compared only after the search has found a leaf node. Where the keys are equal, the search is successful, and the desired data unit is obtained at the storage address indicated by the pointer of the leaf node. Where the keys differ, the search terminates as unsuccessful.
FIG. 1 illustrates an example of a digital trie structure in which the key has a length of 4 bits and k=2, and thus each internal node has 2.sup.2 =4 elements, and two bits extracted from the key are searched at each level. Leaf nodes containing a record are denoted by references A, B, C, D. . . . . . M, N, O and P. Thus, a leaf node is a node that does not point to a lower level in the tree. The internal nodes are denoted with references V1 . . . V5 and internal node elements with reference VA in FIG. 1.
In the exemplary case shown in FIG. 1, the search keys for the leaf nodes shown are as follows: A=0000, B=0001, C=0010, . . . , H=0111, . . . and P=1111. In this case, a pointer is stored in each leaf node to that storage location in the database SD at which the actual data, e.g. the telephone number of the pertinent subscriber and other information relating to that subscriber, is to be found. The actual subscriber data may be stored in the database, for instance as a sequential file of the type shown in the figure. The search is performed on the basis of the search key of record H, for example, by first extracting from the search key the two leftmost bits (01) and interpreting them, which delivers the second element of node V1, containing a pointer to node V3 at the next level. At this level, the two next bits (11) are extracted from the search key, thus yielding the fourth element of that node, pointing to record H.
Instead of a pointer, the leaf node may contain (besides a search key) an actual data file. Thus, for example, the data relating to subscriber A (FIG. 1
REFERENCES:
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5257365 (1993-10-01), Powers et al.
patent: 5442784 (1995-08-01), Powers et al.
patent: 5463390 (1995-10-01), Whiting et al.
patent: 5521597 (1996-05-01), Dimitri
patent: 5532694 (1996-07-01), Mayers et al.
patent: 5564045 (1996-10-01), Fulling et al.
patent: 5592667 (1997-01-01), Bugajski
Ho Ruay Lian
Lintz Paul R.
Nokia Telecommunications Oy
LandOfFree
Method and apparatus for storing and retrieving data and a memor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for storing and retrieving data and a memor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for storing and retrieving data and a memor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-190520