Editing Index locking (section)

In [[database]]s an ''[[Index (database)|index]]'' 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 [[pointer (computer programming)|pointer]]s. Changes in a database (by insert, delete, or modify operations), may require indexes to be updated  to maintain accurate user data accesses.<ref name=Weikum01>[[Gerhard Weikum]], Gottfried Vossen (2001): [http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description  ''Transactional Information Systems''] Chapter 9, Elsevier, {{ISBN|1-55860-508-8}}</ref> '''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 [[Isolation_(database_systems)#Phantom_reads|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 {{Var|r}} must update all indices to {{Var|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]] protocol must be observed.
<ref name=Weikum01/>

Specialized [[concurrency control]] 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]]s ([[B-Tree concurrency control]]<ref name=Graefe2010>Goetz Graefe (2010): [http://portal.acm.org/citation.cfm?id=1806908 "A survey of B-tree locking techniques"] ''ACM Transactions on Database Systems'' (TODS), Volume 35 Issue 3, July 2010 (also [http://www.hpl.hp.com/techreports/2010/HPL-2010-9.pdf HPL-2010-9] {{Webarchive|url=https://web.archive.org/web/20120316064807/http://www.hpl.hp.com/techreports/2010/HPL-2010-9.pdf |date=2012-03-16 }}, HP Laboratories).</ref>) which are regularly used as database indexes.

Index locks are used to coordinate [[Thread (computer science)|thread]]s accessing indexes concurrently, and typically shorter-lived than the common transaction locks on user data. In professional literature, they are often called ''[[Latch (computer science)|latches]]''.<ref name=Graefe2010/>