Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-08-30
2003-05-27
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06571250
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a data management technology, and more particularly to an effective technology applied for management of plural pieces of data for an index key.
Recently, with the strong propagation of work systems operable through Internet, applications of database management systems (DBMS) supporting the systems are proceeding on a widening front. In this connection, the amount of data processed by the DBMS is increasing year by year. In the systems, a number of applications use a B-tree index which is a typical and the highest-speed retrieval means for the DBMS on the data having a narrow range of values such as ‘work transition state’, etc. in a work flow. Thus, the stable performance of the B-tree index becomes very important.
The B-tree index is disclosed by, for example, the document (Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers, 1993) basically about the data structure, the concurrent accessing method from a plurality of processes, and the basic system for recovery.
To realize a high-speed B-tree index as a practical system, the following problems have to be solved.
(i) Improving the Concurrent Executability of Plural Processes
A problem occurs when a plurality of transactions simultaneously access a database table containing records. Practically, when a transaction tries to update a record, and when another transaction simultaneously tries to access the same record, a conflict occurs. One of the solutions to the conflict is a locking system (exclusive access system) for a portion (the entire B-tree index, a node, an index entry, a key value, etc.) of a record or a B-tree index. In the locking system, a transaction is forced to obtain a lock before accessing data. If a lock has already been obtained by another transaction, there arises a conflict for a lock, and a necessary lock may not be obtained. Although the locking system guarantees an update result and a reference result of the current transaction, it keeps the access of a transaction waiting until another transaction which has previously obtained a lock releases the lock. Therefore, it is important to minimize the number of locks simultaneously obtained by one transaction and the range (granularity) of the influence of the lock to improve the multiplicity (concurrency) of the system and throughput.
(ii) Recovery Process Control
In an actual system, it is necessary to guarantee the atomicity of a transaction, and the consistency of the data in the B-tree index in case of various failures such as an interruption of a transaction, a system failure, a medium failure, etc. To attain this, a log record obtaining system and recovery process control using a log record are important. A log record obtaining system can be a physical log system in which a physical image before and after an update of the node forming an index is obtained according to log record information. In the recovery process performed using a physical image, access to a page for other transaction is limited until a transaction completes update. That is, the recovery process control closely relates to exclusive control, and also affects concurrent executability.
FIG. 11
shows a structure of a conventional typical B-tree index.
A B-tree index can be set such that a number of nodes at various levels are branched from a root node. An end node in the branched nodes is referred to as a leaf node. Nodes other than the leaf node including the root node are referred to as upper nodes. Each node has a plurality of index entries each comprising the following information. An index entry in a leaf node is configured by a pointer to a record (table data) in a database, and a key value indicating one of the features of the record (table data). An index entry in an upper node is configured by a pointer to a node (child node) at a level immediately below, and a key value indicating the range of the key value managed finally by the leaf node branched from the child node. The key value in an upper index entry functions as a sign (determination element) when an access program to a B-tree index traces the path from the root node to the leaf node in which an index entry containing a pointer to a target record is stored and managed. Normally, a node in a B-tree index is realized by a page as an access unit in a database.
SUMMARY OF THE INVENTION
One of the exclusive control systems for a B-tree index can be a key value exclusive system or a key range exclusive system using the granularity of the exclusive resources of an index as a ‘key’. When the exclusive control of an index key is performed, the retrieving and updating process on the data (rows) having the same key are serialized by index key exclusive control, thereby lowering the concurrency. A transaction processed in a WEB environment which has recently been more and more popular is larger than a transaction of a conventional OLTP, and it is difficult to provide a high-throughput service in an exclusive control system on a key.
As shown in
FIG. 11
, there are the following problems with the B-tree index having a number of same keys. In the B-tree index shown in
FIG. 11
, table data information relating a key is managed by one leaf entry
16
. The leaf entry
16
includes a key
14
, table data information
18
(data record identifier) relating to the key value, and a number
17
(number of duplication) of pieces of table data information
18
relating to the key value. The table data information
18
is arranged in an ascending order in a list form of duplication. In this storage system, when the number of duplication of a key increases, the length of a leaf entry cannot be stored in a leaf node
12
. As a result, the table data information for one key has to be divided into a plurality of leaf entries, and stored in a plurality of nodes. In the example shown in
FIG. 11
, the entries of the keys ‘
28
’ are stored separately in three nodes, that is, leaf nodes N
4
, N
5
, and N
6
. In this structure, the entries of the keys ‘
28
’ are bottlenecks in scanning leaf nodes using a pointer in the horizontal direction corresponding to the range search. Furthermore, the key
14
contained in an upper node
13
stored in the root node
10
and the upper node
13
has also to be a key in the table data information in addition to ‘
28
’, thereby causing the problem that the number of a root node
10
and the upper node
13
increases. As a result, a duplicate key lowers not only the performance of the access process on a duplication key itself, but also the access performance of the entire B-tree index, and the storage efficiency.
Gray discloses a method of managing table data information with the data structure other than the B-tree index, but does not disclose a method for concurrent execution control and recovery control. Furthermore, a recovery process system using a physical log is disclosed, but the above mentioned concurrent execution cannot be realized on the same page. These problems normally occur when index access is tried on the same key.
The object of the present invention is to solve the above mentioned problems, and provide a technology of performing index access on the same key in an environment where a plurality of access processing operations are performed.
The above mentioned problems are solved by the following means.
The problems are solved in an environment where a plurality of users gain access, and in a method for managing a B-tree index having a number of the same keys, with the data structure with which a plurality of data pointers relating to a key are stored, which is different from that of the leaf node storing an index entry containing the key, and in which data can be pointed to from an index entry containing the key to realize concurrent access in a plurality of processes. When a data pointer relating to a key is added or deleted, the first log record containing the information about adding or deleting the data pointer to or from the data structure storing the plurality of data pointers re
Ali Mohammad
Antonelli Terry Stout & Kraus LLP
Breene John
LandOfFree
Method and system for processing queries in a data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for processing queries in a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for processing queries in a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3003300