IndexesRose-Hulman Institute of TechnologyCurt CliftonOverview Introduction to Indexes Index Architecture How SQL Server Retrieves Stored Data How SQL Server Maintains Index and HeapStructures Deciding Which Columns to IndexData PagesPage 7 Page 8 Page 9AkhtarFunkSmithMartin...Page 4 Page 5 Page 6 ...............ConFunkWhite......RuddWhiteBarr......SmithOtaJones......MartinPhuaJonesSmith...GanioJonesHall.................................................................................Storing and Accessing Data How Data Is Stored Rows are stored in data pages Heaps are a collection of data pages for a tableWhether to Create Indexes Why to Create an Index Speeds up data access Enforces uniqueness of rows Why Not to Create an Index Consumes disk space Incurs overheadUsing Heaps SQL Server: Uses Index Allocation Map Pages That: Contain information on where the extents of a heapare stored Navigate through the heap and find available space fornew rows being inserted Connect data pages Reclaims Space for New Rows in the Heap When aRow Is DeletedUsing Clustered Indexes Each Table Can Have Only One ClusteredIndex The Physical Row Order of the Table and theOrder of Rows in the Index Are the Same Key Value Uniqueness Is MaintainedExplicitlyor ImplicitlyUsing Nonclustered Indexes Nonclustered Indexes Are the SQL ServerDefault Existing Nonclustered Indexes AreAutomatically Rebuilt When: An existing clustered index is dropped A new clustered index is created The DROP_EXISTING option is used to changewhich columns define the clustered indexMaintaining Index andHeap StructuresPage Splits in an IndexIndex PagesNon-LeafLevelINSERT member (last name)VALUES lastname = ‘Jackson'LangSmith…AkhtarGanio…Akhtar…MartinJacksonLeaf Level(Key Value)AkhtarBarrBarrBormBuhl……………LangMartinMartinMartinMoris……………SmithSmithSmithSmithSmith……………… ……GanioHallHartJonesJones………………Leaf Level(Key Value)AkhtarBarrBarrBormBuhl……………JacksonJonesJones………LangMartinMartinMartinMoris……………SmithSmithSmithSmithSmith……………… ……GanioHallHart…………Jackson …Forwarding Pointer in a Heap Non-LeafLevelPage 12 - RootPage 37 Page 28Leaf Level(Key Value)Page 41 Page 51 Page 61 Page 71 Akhtar...MartinAkhtarBarrConFunkFunk4:706:014:705:034:704:014:706:024:704:02MartinSmith...SmithSmithSmithWhiteWhite4:706:034:708:044:707:014:704:034:705:02AkhtarGanio...GanioHallJonesJonesJones4:709:014:709:044:709:024:708:034:707:03HeapPage 707 Page 708 Page 70901020304..................AkhtarFunkSmithMartin...Page 704 Page 705 Page 706 010203.....................ConnFunkWhite......010203.....................RuddWhiteBarr......0102030405...............SmithOtaJonesCoretsNash01020304..................MartinPhuaJonesSmith...010203.....................GanioJonesHall......MartinMartinOtaPhuaRudd4:708:014:706:044:707:024:708:024:705:01NonClusteredIndexFile ID #4id indid = 2 rootsysindexes Non-LeafLevelPage 12 - RootPage 37 Page 28Leaf Level(Key Value)Page 41 Page 51 Page 61 Page 71 Akhtar...MartinAkhtarBarrConFunkFunk4:706:014:705:034:704:014:706:024:704:02MartinSmith...SmithSmithSmithWhiteWhite4:706:034:708:044:707:014:704:034:705:02AkhtarGanio...GanioHallJonesJonesJones4:709:014:709:044:709:024:708:034:707:03HeapPage 707 Page 708 Page 70901020304..................AkhtarFunkSmithMartin...Page 704 Page 705 Page 706 010203.....................ConnFunkWhite......010203.....................RuddWhiteBarr......0102030405...............SmithOtaJonesCoretsNash01020304..................MartinPhuaJonesSmith...010203.....................GanioJonesHall......MartinMartinOtaPhuaRudd4:708:014:706:044:707:024:708:024:705:01NonclusteredIndexFile ID #40202......OtaOta0202......OtaOtaMartinMartinMartinMartin0202OtaOta0404......OtaOtaOtaOta4:707:024:707:02UPDATE memberSET Address = <really long>WHERE lastname = 'Ota'Row Updates Generally do not cause rows to move Like a delete followed by an update Logically Sometimes practically Batch updates touch each index onceDeletion Deletion creates “ghost records” Reclaiming space Free pages when empty For indexed table: Can overwrite ghost records immediately For non-indexed table: Compact records when more space is needed forinsertDeciding What to IndexWhat You Need to Know Logical and Physical Database Design Data Characteristics How Data Is Used The types of queries performed The frequency of queries that are typicallyperformedIndexing Guidelines Columns to Index Primary and foreign keys Those frequently searched in ranges Those frequently accessed in sorted order Those frequently grouped together during aggregation Columns Not to Index Those seldom referenced in queries Those that contain few unique values Those defined with text, ntext, or image data typesChoosing the Clustered Index Heavily Updated Tables A clustered index with an identity column keepsupdated pages in memory Sorting A clustered index keeps the data pre-sorted Column Length and Data Type Limit the number of columns Reduce the number of characters Use the smallest data type possibleData Characteristics – Densitylast_namelast_namefirst_namefirst_nameRandall...JoshuaRandall CynthiaRandall Tristan...Ota Lani...SELECT *FROM memberWHERE last_name = ‘Ota’Low DensitySELECT *FROM memberWHERE last_name =‘Randall’High DensityData Characteristics – Selectivity How effective is a column at selecting asubset of the data A property of a given query: Rows matching property / Total number of rowsDetermining SelectivityHigh selectivitymember_nomember_no12..last_namelast_namefirst_namefirst_nameRandallFloodJoshuaKathie.10000 Anderson BillSELECT *FROM memberWHERE member_no > 8999100010000= 10%Number of rows meeting criteriaTotal number of rows in table=Low selectivitymember_nomember_no12..last_namelast_namefirst_namefirst_nameRandallFloodJoshuaKathie.10000 Anderson BillSELECT *FROM memberWHERE member_no < 9001900010000= 90%Number of rows meeting criteriaTotal number of rows in table=Indexing to Support Queries Writing Good Search Arguments Specify a WHERE clause in the query Verify that the WHERE clause limits the numberof rows Verify that an expression exists for every tablereferenced in the query Avoid using leading wildcardsIntroduction to