System and methodology for providing compact B-Tree

Details System and methodology for providing compact B-Tree System and methodology for providing compact B-Tree

2003-01-27

2004-02-17

Mizrahi, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06694323

ABSTRACT:

COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to information processing environments and, more particularly, to a database management system (DBMS) having a methodology for providing compact B-Tree indexes.
2. Description of the Background Art
Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as “records” having “fields” of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from, or updated in, such files, and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C., “An Introduction to Database Systems, Volume I and II,” Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.
DBMS systems have long since moved from a centralized mainframe environment to a decentralized or distributed environment. One or more PC “client” systems, for instance, may be connected via a network to one or more server-based database systems (SQL database server). Commercial examples of these “client/server” systems include Powersoft® clients connected to one or more Sybase® SQL Anywhere® Studio (Adaptive Server® Anywhere) database servers. Both Powersoft® and Sybase® SQL Anywhere® Studio (Adaptive Server® Anywhere) are available from Sybase, Inc. of Dublin, Calif.
In today's computing environment, database technology can be found on virtually any device, from traditional mainframe computers to cellular phones. Sophisticated applications, whether human resources information systems or sales force automation systems, can “push” much of their complexity into the database itself. Indeed, this represents one of the main benefits of database technology. The challenge, however, is to support these applications, and the complex queries they generate, on small computing devices. At the same time, users expect the productivity and reliability advantages of using a relational DBMS.
Consider, for instance, the execution of a request for information from a relational DBMS. In operation, this request is typically issued by a client system as one or more Structured Query Language or “SQL” queries for retrieving particular data (i.e., data records meeting the query condition) from database tables on a server. For example, the following simple SQL SELECT statement results in a list of the names of those employees earning $10,000, where “employees” is a table defined to include information about employees of a particular organization:
SELECT name
FROM employees
WHERE sal=10,000
The syntax of SQL is well documented, see e.g., the abovementioned “An Introduction to Database Systems.” For further information on SQL, see e.g., “Information Technology—Database languages—SQL,” published by the American National Standards Institute as American National Standard ANSI/ISO/IEC 9075: 1992, the disclosure of which is hereby incorporated by reference.
For enhancing the speed in which the DBMS stores, retrieves, and presents particular data records, the DBMS usually maintains one or more database indexes on a database table. A database index, typically maintained as a B-Tree (or B+-Tree) data structure, allows the records of a table to be organized in many different ways, depending on a particular user's needs. An index may be constructed as a single disk file storing index key values together with unique record numbers. The index key values are a data quantity composed of one or more fields from a record which are used to arrange (logically) the database file records in some desired order (index expression). The record numbers are unique pointers or identifiers to the actual storage location of each record in the database file. Both are referred to internally by the system for locating and displaying records in a database file.
Searching for a particular record in a B-Tree index occurs by traversing a particular path in the tree. To find a record with a particular key value, one would maneuver through the tree comparing key values stored at each node visited with the key value sought. The results of each comparison operation, in conjunction with the pointers stored with each node, indicate which path to take through the tree to reach the record ultimately desired. Ultimately, a search will end at a particular leaf node which will, in turn, point to (i.e., store a pointer to or identifier for) a particular data record for the key value sought. Alternatively, the leaf nodes may for “clustered indexes” store the actual data of the data records on the leaf nodes themselves.
An index allows a database server to find and retrieve specific rows much faster than it could without using the index. A sequential or linear scan from the beginning of a database table, comparing each record along the way, is exceedingly slow compared to using an index. There, all of the blocks of records would have to be visited until the record sought is finally located. For a table of even moderate size, such an approach yields unacceptable performance. As a result, virtually all modern-day relational database systems employ B-Tree indexes or a variant.
General techniques for the construction and operation of B-Trees are well documented in the technical, trade, and patent literature. For a general description, see Sedgewick, R., “Algorithms in C,” Addison-Wesley, 1990. For a survey of various B-Tree implementations, see Comer, D., “The Ubiquitous B-Tree,” Computing Surveys, Vol. 11, No. 2, June 1979, pp. 121-137. For further description of B-Tree indexes, see e.g., commonly-owned U.S. Pat. No. 6,363,376 titled “Database system providing methodology for enhancing concurrency using row update bit and deferred locking.” The disclosures of each of the foregoing references are hereby incorporated by reference.
Many B-Tree variants have been introduced in the literature and in practice. These can be classified according to the technique used for searching within a page. Most implementations are comparison-based in which searching is typically done by performing a binary search on a sorted array of keys. A variety of optimizations have been developed to improve upon this basic scheme. For an overview of such optimizations, see e.g., Graefe, G. and Larson, P. A., “B-Tree Indexes and CPU caches,” in 17th International Conference on Data Engineering (ICDE), pages 349-358, Washington-Brussels-Tokyo, April 2001, published by IEEE Computer Society Press.
Radix-based B-Tree variants are less common, with the majority intended for text indexing, not on-line transaction processing (OLTP). These radix-based variants can be further categorized as to whether they

Affiliated with

Also associated with

Rating

System and methodology for providing compact B-Tree does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and methodology for providing compact B-Tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and methodology for providing compact B-Tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3322128