Data structure and search method for a data base management system
First Claim
1. A data base management system includinga processor,a main memory (2),a large storage secondary memory (4), anda data structure contained in the main and secondary memories comprisinga plurality of storage files (BNG pages 60, GLPAM pages 80, BNR pages 90) contained in the secondary memory, anda 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
10 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.
-
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.
-
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.
Specification