Indexing techniques

Database course

1. Indexing Techniques
Assistant Lecturer Huda A. Alameen
[email protected]

2. Indexing Techniques
Adatabaseindexisadatastructurethatimprovesthespeedofdataretrieval
operationsonadatabasetableatthecostofslowerwritesandincreasedstorage
space.Indexescanbecreatedusingoneormorecolumnsofadatabasetable,
providingthebasisforbothrapidrandomlookupsandefficientaccessofordered
records.
Inarelationaldatabase,anindexisacopyofonepartofatable.Somedatabases
extendthepowerofindexingbyallowingindicestobecreatedonfunctionsor
expressions.Forexample,anindexcouldbecreatedonupper(last_name),which
wouldonlystoretheuppercaseversionsofthelast_namefieldintheindex.

3. Index architecture :Non-clustered
Thedataispresentinarbitraryorder,butthelogicalorderingisspecifiedbythe
index.Thedatarowsmaybespreadthroughoutthetableregardlessofthevalue
oftheindexedcolumnorexpression.Thenon-clusteredindextreecontainsthe
indexkeysinsortedorder,withtheleafleveloftheindexcontainingthepointer
totherecord(pageandtherownumberinthedatapageinpage-organized
engines;rowoffsetinfile-organizedengines).
Inanon-clusteredindex:
1.Thephysicalorderoftherowsisnotthesameastheindexorder.
2.Typicallycreatedonnon-primarykeycolumnsusedinJOIN,WHERE,andORDERBY
clauses.
Therecanbemorethanonenon-clusteredindexonadatabasetable.

4. Index architecture :Clustered
Clusteringaltersthedatablockintoacertaindistinctordertomatchtheindex,
resultingintherowdatabeingstoredinorder.Therefore,onlyoneclustered
indexcanbecreatedonagivendatabasetable.Clusteredindicescangreatly
increaseoverallspeedofretrieval,butusuallyonlywherethedataisaccessed
sequentiallyinthesameorreverseorderoftheclusteredindex,orwhenarange
ofitemsisselected.

5. Cluster
Whenmultipledatabasesandmultipletablesarejoined,it'sreferredtoasa
cluster(nottobeconfusedwithclusteredindexdescribedabove).The
recordsforthetablessharingthevalueofaclusterkeyshallbestored
togetherinthesameornearbydatablocks.Thismayimprovethejoinsof
thesetablesontheclusterkey,sincethematchingrecordsarestored
togetherandlessI/Oisrequiredtolocatethem.Thedatalayoutinthetables
whicharepartsoftheclusterisdefinedbytheclusterconfiguration.Acluster
canbekeyedwithaB-Treeindexorahashtable.Thedatablockinwhichthe
tablerecordwillbestoredisdefinedbythevalueoftheclusterkey.

6. Column order
Theorderinwhichcolumnsarelistedintheindexdefinitionisimportant.It
ispossibletoretrieveasetofrowidentifiersusingonlythefirstindexed
column.However,itisnotpossibleorefficient(onmostdatabases)to
retrievethesetofrowidentifiersusingonlythesecondorgreaterindexed
column.
Forexample,imagineaphonebookthatisorganizedbycityfirst,thenbylast
name,andthenbyfirstname.Ifyouaregiventhecity,youcaneasilyextract
thelistofallphonenumbersforthatcity.However,inthisphonebookit
wouldbeverytedioustofindallthephonenumbersforagivenlastname.
Youwouldhavetolookwithineachcity'ssectionfortheentrieswiththatlast
name.Somedatabasescandothis,othersjustwon’tusetheindex.

7. Types of indexes
Bitmap index:
A bitmap index is a special kind of index that stores the bulk of its data as bit arrays
(bitmaps) and answers most queries by performing bitwise logical operations on these
bitmaps. The most commonly used index, such as B+trees, are most efficient if the
values it indexes do not repeat or repeat a smaller number of times.
Dense index:
A dense index in databases is a file with pairs of keys and pointers for every record in
the data file. Every key in this file is associated with a particular pointer to a record
in the sorted data file. In clustered indices with duplicate keys, the dense index
points to the first record with that key.

8. Types of indexes
Sparse index:
Asparseindexindatabasesisafilewithpairsofkeysandpointersforevery
blockinthedatafile.Everykeyinthisfileisassociatedwithaparticularpointer
totheblockinthesorteddatafile.Inclusteredindiceswithduplicatekeys,the
sparseindexpointstothelowestsearchkeyineachblock.
Reverse index:
A reverse key index reverses the key value before entering it in the index. E.g.,
the value 24538 becomes 83542 in the index. Reversing the key value is
particularly useful for indexing data such as sequence numbers, where new key
values monotonically increase.

9. Index implementations
Indices can be implemented using a variety of data structures. Popular indices
include balanced trees, B+ trees and hashes.
In Microsoft SQL Server, the leaf node of the clustered index corresponds to
the actual data, not simply a pointer to data that resides elsewhere, as is the
case with a non-clustered index. Each relation can have a single clustered
index and many unclusteredindices.