Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-05-18
2003-07-08
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06591269
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
The present invention relates generally to information processing environments and, more particularly, to maintenance and processing of indexes (e.g., B+-tree indexes) in a data processing system, such as a Database Management System (DBMS).
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 de-centralized 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 Adaptive Server™ database servers. Both Powersoft™ and Sybase Adaptive Server™ (formerly Sybase SQL Server™) are available from Sybase, Inc. of Emeryville, Calif.
For enhancing the speed in which a database stores, retrieves, and presents particular data records, DBMS systems employ one or more database indexes on database tables. A database index, typically maintained as a 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 former is a data quantity composed of one or more fields from a record; the values are used to arrange (logically) the database file records by some desired order (index expression). The latter are unique pointers or identifiers to the actual storage location of each record in the database file. B-tree variants also exist, including B+-tree and B*-tree variants. In a B+-tree, the search keys are stored twice; each of the search keys is found in some leaf nodes.
Today, B+-trees are one of the main indexing methods used in commercial database systems. B+-tree indexes or similar to B-tree indexes. A primary B+-tree index has data records in the leaf pages while a secondary B+-tree index has only the index keys in the leaf pages, where a key consists of a key value and the row ID (ROWID) of the data record. For an introduction to B-tree structures and general methodology, see, e.g., Comer, D.,
The Ubiquitous
B-Tree, Computing Surveys, Vol. 11, No. 2, June 1979, the disclosure of which is hereby incorporated by reference.
Over time, insertion and deletion database operations may cause allocations and deallocations of index pages. As mentioned by Gray et al., most practical implementations of B-trees (e.g., Sybase Adaptive Server Enterprise™) do not merge index nodes upon underflow; see, e.g., Gray, J. et al.,
Transaction Processing: Concepts and Techniques
, Morgan Kaufmann Publishers, Inc., 1993, the disclosure of which is hereby incorporated by reference. Index pages may become less than half full causing a drop in the space utilization and also an increase in the number of disk reads required to read the same number of index keys. Further, the index may become “declustered” (i.e., index keys within a key range may not be in contiguous disk space), thereby degrading the performance of range queries. To restore the clustering, users can drop and recreate the index. However, that typically requires holding a shared table lock on the table thereby making the table inaccessible to OLTP transactions, which may not be acceptable. Accordingly, a better solution is sought.
Each day more and more businesses are run from mission-critical systems which store information on server-based SQL database systems, such as Sybase Adaptive Server Enterprise™. As a result, increasingly higher demands are being placed on server-based SQL database systems to provide enterprise-wide decision support. Accordingly, there is much interest in improving the performance of such system, particularly in terms of execution speed and reliability.
SUMMARY OF THE INVENTION
The present invention comprises a Client/Server Database System with improved methodology for performing online rebuild of indexes. In an exemplary embodiment, the system includes one or more Clients (e.g., Terminals or PCs) connected via a Network to a Server. The Server, operating under a server operating system (e.g., UNIX) includes a Database Server System, such as Sybase Adaptive Server. In general operation, Clients store data in and retrieve data from one or more database tables resident on the Server. Each table itself comprises one or more horizontal rows or records divided into columns or fields of information. For enhancing the speed in which the Database Server stores, retrieves, and processes particular data records, the Server maintains one or more database indexes on each table. A database index, which in an exemplary embodiment is maintained as a B-Tree data structure (specifically, B+-tree variant), allows the records of a table to be organized in many different ways, depending on a particular user's needs, with the speed of retrieving any particular data record significantly improved.
Methodology is provided which provides an efficient methodology for performing an online rebuild of a B+-tree index. From a high-level perspective, the method operates by copying the index rows to newly-allocated pages in the key order so that good space utilization and clustering are achieved. The old pages are deallocated during the process. This approach differs from the previously-published online index rebuild algorithms in two ways. First, it rebuilds multiple leaf pages and then propagates the changes to higher levels. Also, while propagating the leaf level changes to higher levels, level 1 pages (i.e., the level immediately above the leaf level) are reorganized, eliminating the need for a separate pass. The methodology provides high concurrency, does minimal amount of logging, has good performance and does not deadlock with other index operations. Performance study shows that the approach results in significant reduction in logging and CPU time. Also, the approach uses the same concurrency control mechanism as split and shrink operations, which made it attractive for implementation.
REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4677
Smart John A.
Sybase Inc.
LandOfFree
Database system with methodology for online index rebuild does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database system with methodology for online index rebuild, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with methodology for online index rebuild will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3045079