The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 20, 1998
Filed:
Mar. 22, 1996
Thuan Quang Bui, Fremont, CA (US);
Scott Dennis Helt, Rochester, MN (US);
Balakrishna Raghavendra Iyer, San Jose, CA (US);
Gary Ross Ricard, Chatfield, MN (US);
International Business Machines Corporation, Armonk, NY (US);
Abstract
A method for partitioning keys onto radix tree logical pages and a parallel index page build algorithm in order to provide radix tree build speedup proportional to the number of processors on the system and controlled efficient page utilization. Also, since keys are intelligently partitioned so that a complete set of keys is inserted into a logical page, there is no page overflow during the tree construction and thus page splitting is eliminated. Since radix index trees are really groups of logical pages in which each logical page contains a small tree, the tree is built (with respect to the logical pages) from the bottom up, while within each individual logical page the tree is constructed from the top down. The space required for a logical page is pre-allocated to allow construction of limbs to begin without waiting for the build of their underlying pages to complete.