Data structure and search method for a data base management system

• US 4,468,728 A
• Filed: 06/25/1981
• Issued: 08/28/1984
• Est. Priority Date: 06/25/1981
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Wang, Chung C.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Mills, John G.
• Application Number:
  US06/277,103
• Time in Patent Office: 1,160 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A data structure and search method for a data base management system. The structure and method allow the locating of a stored record in a massive system in a controlled and small number of mass memory accesses. The data structure is arranged into a plurality of search trees, each defining patent nodes and terminal nodes. The nodes of a tree are hierarchically arranged, and the trees are hierarchically arranged as a whole into levels. The initial search tree and an initial subset of trees, in some cases, are designed to be maintained in a main fast access memory. The remaining trees are kept in mass memory. A plurality of first storage files maintained in the mass memory are associated with terminal nodes of each of the trees except the final trees in the hierarchical structure. Terminating storage files, which are the ultimate repository for information, are associated with terminal nodes of the final trees. An input search parameter is partitioned into a plurality of subparameters, one for each level of search trees. The subparameters are used to search a tree in each level of the data structure until the location of a terminating file is determined.

Claims

1. A data base management system including

a processor,

a main memory (2),

a large storage secondary memory (4), and

a data structure contained in the main and secondary memories comprising

a plurality of storage files (BNG pages 60, GLPAM pages 80, BNR pages 90) contained in the secondary memory, and

a plurality of search trees (bit vectors 32, 36 and 73) hierarchically arranged in a plurality of search levels beginning with an initial tree (40) contained in the main memory, each tree containing ordered data defining parent nodes and terminal nodes of the tree, wherein a numerical representation of a path through parent nodes of the tree to reach any said terminal node of the tree defines a logical memory address of one of the storage files, and each terminal node of the search trees in a last search level defines a logical memory address of a terminating one of the storage files, and in which each of the storage files associated with the terminal nodes of the search trees except the trees in the last search level contains a link to one of the search trees in the next search level and each of the storage files associated with the terminal nodes of the search trees in the last search level contains stored information pertaining to a unique input search parameter, and the processor comprises program means for partitioning an input search parameter into a subparameter for each search level and for consecutively searching a linked one of the trees in each search level, starting with the initial tree, using a different one of the subparameters for each tree search until a terminating one of the storage files associated with the last search level is found.

2. The invention of claim 1 wherein each of the search trees comprises a binary bit string having one bit per node of the search tree and in which one binary state of a said bit defines a parent node and the other binary state of a said bit defines a terminal node.

3. The invention of claim 2 in which the data structure further comprises a first translation file (root LPAM table 37 and root LPAM pages 50) in the main memory for translating a logical memory address associated with the initial search tree into a physical memory address of one of the storage files;

a plurality of second translation files (GLPAM tables 74 and GLPAM pages

     80) in the secondary memory, each for translating a logical memory address associated with one of the terminating search trees into a physical memory address of one of the terminating files.

4. The invention of claim 3 wherein each translation file comprises a table (LPAM table 37, GLPAM table 74) of physical memory addresses each pointing to a page (50, 80) containing another plurality of physical memory addresses and wherein each said table is indexable by a prescribed portion of the associated logical address to obtain an associated one of said pages, and said one page is indexable by the remaining portion of the logical address to obtain an address of a said storage file.

5. The invention of claim 1 wherein the input search parameter is a plurality of telephone number digits identifying a numbering plan area (NPA), a telephone office (XXX), and a telephone line (YYYY) within the office, a first subparameter comprises the digits NPX-XXX associated with the initial search tree, and a second subparameter comprises the digits YYYY associated with search trees in a second search level.

6. A method of searching a memory (2, 4) to locate information pertaining to an input search parameter in a data base management system, comprising the steps of

A. partitioning the search parameter into a plurality of subparameters,

B. searching a first bit vector in accordance with a first one of the subparameters to generate a logical address of a stored file pertaining to the first subparameter,

C. translating by means of a stored translation table the logical address into a physical memory address of the file,

D. obtaining from the file another bit vector,

E. repeating steps B through D for each of the remaining subparameters except the last remaining subparameter using the bit vectors obtained in step D, and repeating steps B and C for the last remaining subparameter, wherein the file whose physical address has been identified for the last remaining subparameter contains stored information pertaining to the input search parameter.

7. The invention of claim 6 further comprising the steps of

hashing each of the subparameters according to a prescribed function to generate a hashed key value (HKV) for each subparameter, and

searching each bit vector using a prescribed different one of the HKVs for each bit vector search to define the search path through the bit vector.

8. A method of searching a data structure to locate stored records pertaining to input search parameters in a data base management system having a main random access memory and a large capacity, slow access secondary memory, wherein the data structure comprises

a plurality of search trees each represented by a bit vector and each defining a plurality of terminal nodes, said search trees being arranged into a hierarchy having at least an initial level defined by an initial search tree located in the main memory, and a terminating level containing plural ones of the search trees located in the secondary memory, in which each terminal node of the initial tree contains a link to another search tree in the next successive level of the hierarchy, and each terminal node of each tree in the terminating level contains a link to a page of stored information pertaining to a different input search parameter, said method being characterized by the steps of

partitioning an input search parameter into a plurality of subparameters equal in number to the number of levels in the hierarchy of search trees,

hashing each subparameter to generate a search string for each level of the hierarchy,

searching the initial search tree using a prescribed one of the search strings to locate a terminal node,

obtaining the link associated with the last-mentioned node to a search tree in the next level of the hierarchy, and

repeating the last two steps with respect to each level in the hierarchy, using a different one of the subparameters for each level until a terminal node of a tree in the terminating level is found.

9. A method of searching a data structure to locate stored records pertaining to input search parameters in a data base management system, wherein the data structure comprises

a root page (30) containing an initial binary root bit vector (36) in which each bit defines a node of a hierarchical search tree and the state of the bit defines whether the node in a parent node or a terminal node, and a root table 37 having memory address pointers to the next mentioned root logical to physical address pages,

a plurality of root logical to physical memory address (LPAM) pages (50) each containing billing number group memory address pointers (55) to the next-mentioned pages,

a plurality of billing number group (BNG) pages (60) each containing a plurality of BNGs, each BNG having associated with it a terminating bit vector (73) and a general LPAM table (74) having a plurality of memory address pointers to ones of the next mentioned pages,

a plurality of general LPAM pages (80) each containing a plurality of memory address pointers (83) of ones of the next-mentioned pages, and

a plurality of billing number record (BNR) pages (90) each having a plurality of records of information pertaining to one of the input search parameters, and said method comprises the steps of

partitioning a said input search parameter into two subparameters,

hashing the subparameters to generate binary search strings,

interrogating ones of the bits of the initial root bit vector along a path of the vector determined by the successive bits of a prescribed one of the search strings until a terminating node is found, wherein the search string bits used in locating the terminal node defines a logical memory address,

indexing into the root LPAM table with a prescribed part of the logical address to obtain an address of one of the root LPAM pages,

indexing into said one of the LPAM pages with the remaining part of the logical address to obtain an address pointer to one of the BNG pages,

reading said one BNG page from memory, searching said one BNG page for a BNG pertaining to one of the subparameters associated with said prescribed one of the search strings,

obtaining the terminating binary bit vector from the last-mentioned BNG,

interrogating ones of the bits of the second bit vector along a path of the vector determined by the successive bits of the remaining one of the search storage until a terminating node is found, wherein the search string bits used in locating the terminal node defines a second logical memory address,

indexing into the general LPAM table of the last-mentioned BNG using a prescribed part of the second logical address to obtain a memory address to one of the general LPAM pages,

indexing into said one general LPAM pages using the remaining part of the second logical address to obtain a memory address of one of the BNR pages, and searching said one BNR page for a BNR associated with the remaining one of the subparameters.

10. The invention of claim 9 wherein the data structure is incorporated into a data base management system comprising a processor, a main random access memory, and a secondary larger storage memory, and wherein the root page and root LPAM pages are maintained in the main memory, and the remaining portions of the data structure are maintained in the secondary memory.