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:
Aug. 08, 1995
Filed:
Feb. 05, 1993
David B Lomet, Westford, MA (US);
Russell J Green, Edinburgh, GB;
Digital Equipment Corp., Pat. Law Gr., Maynard, MA (US);
Abstract
A database-management system (10) generates bounded-disorder indexes on its database keys. In such an index, the leaf nodes (51, 62) are large and are divided into a number of buckets (52, 54, 56, 58), only one of which ordinarily is accessed in any given single-record database operation. The key values in a leaf node are distributed among the leaf node's buckets in accordance with a hashing function. The lockable ranges locked for scanning functions are defined in accordance with key-valued locking, in which each lockable range is bounded by successive key values that exist in the database. But the multiple-bucket accesses that would otherwise be required, because of the hash-function distribution of key values among a node's several buckets, are avoided because the lockable ranges are defined by the sequence of key values in the bucket rather than in the node. In addition to the existing key values, moreover, the buckets' key-value limits are also employed to bound lockable ranges, even if no database records contain those key-value limits. This prevents end-of-bucket insertions and deletions from needing further I/O operations in order to identify the lockable ranges that those insertions and deletions modify.