In
database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
s an ''
index
Index (or its plural form indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on a Halo megastru ...
'' is a data structure, part of the database, used by a database system to efficiently navigate access to ''user data''. Index data are system data distinct from user data, and consist primarily of
pointers. Changes in a database (by insert, delete, or modify operations), may require indexes to be updated to maintain accurate user data accesses.
Gerhard Weikum
Gerhard Weikum is a Research Director at the Max Planck Institute for Informatics in Saarbrücken, Germany, where he is leading the databases and information systems department. His current research interests include transactional and distributed ...
, Gottfried Vossen (2001)
''Transactional Information Systems''
Chapter 9, Elsevier, Index locking is a technique used to maintain index integrity. A portion of an index is locked during a database transaction when this portion is being accessed by the transaction as a result of attempt to access related user data. Additionally, special database system transactions (not user-invoked transactions) may be invoked to maintain and modify an index, as part of a system's self-maintenance activities. When a portion of an index is locked by a transaction, other transactions may be blocked from accessing this index portion (blocked from modifying, and even from reading it, depending on lock type and needed operation). Index Locking Protocol guarantees that
phantom read phenomenon won't occur.
Index locking protocol states:
* Every relation must have at least one index.
* A transaction can access tuples only after finding them through one or more indices on the relation
* A transaction Ti that performs a lookup must lock all the index leaf nodes that it accesses, in S-mode, even if the leaf node does not contain any tuple satisfying the index lookup (e.g. for a range query, no tuple in a leaf is in the range)
* A transaction Ti that inserts, updates or deletes a tuple ti in a relation r must update all indices to r and it must obtain exclusive locks on all index leaf nodes affected by the insert/update/delete
* The rules of the
two-phase locking
In databases and transaction processing, two-phase locking (2PL) is a concurrency control method that guarantees serializability.Phil Bernstein, Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987) ''Concurrency Control and Recovery in Dat ...
protocol must be observed.
[
Specialized ]concurrency control
In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for Concurrent computing, concurrent operations a ...
techniques exist for accessing indexes. These techniques depend on the index type, and take advantage of its structure. They are typically much more effective than applying to indexes common concurrency control methods applied to user data. Notable and widely researched are specialized techniques for B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for n ...
s ( B-Tree concurrency control[Goetz Graefe (2010)]
"A survey of B-tree locking techniques"
''ACM Transactions on Database Systems'' (TODS), Volume 35 Issue 3, July 2010 (als
HPL-2010-9
HP Laboratories).) which are regularly used as database indexes.
Index locks are used to coordinate threads accessing indexes concurrently, and typically shorter-lived than the common transaction locks on user data. In professional literature, they are often called '' latches''.[
]
See also
*Database index
A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without ...
*Concurrency control
In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for Concurrent computing, concurrent operations a ...
*Lock (database)
Record locking is the technique of preventing simultaneous access to data in a database, to prevent inconsistent results.
The classic example is demonstrated by two bank clerks attempting to update the same bank account for two different transacti ...
* B-Tree concurrency control
References
Databases
Transaction processing
Concurrency control
{{Database-stub