Data structure and search method for a data base management system

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.

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.

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.