??索引設(shè)計是數(shù)據(jù)庫設(shè)計中比較重要的一個環(huán)節(jié)，對數(shù)據(jù)庫的性能其中至關(guān)重要的作用，但是索引的設(shè)計卻又不是那么容易的事情，性能也不是那么輕易就獲取到的，很多的技術(shù)人員因為不恰當(dāng)?shù)膭?chuàng)建索引，最后使得其效果適得其反，可以說“成也索引，敗也索引”。????????

????本系列文章來自Stairway to SQL Server Indexes，然后經(jīng)過我們團隊的理解和整理發(fā)布在agilesharp，希望對廣大的技術(shù)朋友在如何使用索引上有所幫助????
????

系列文章索目錄：

SQL Server索引進階第一篇：索引介紹
SQL Server索引進階第二篇：深入非聚集索引
SQL Server索引進階第三篇：聚集索引
SQL Server索引進階第四篇：頁和區(qū)

SQL Server索引進階第五篇：索引包含列
SQL Server索引進階第六篇：書簽
SQL Server索引進階第七篇：過濾的索引

SQL Server索引進階第八篇：唯一索引
SQL Server索引進階第九篇：解讀執(zhí)行計劃
SQL Server索引進階第十篇：索引的內(nèi)部結(jié)構(gòu)
SQL Server索引進階第十一篇：索引碎片分析與解決（上）
SQL Server索引進階第十一篇：索引碎片分析與解決（中）-碎片發(fā)生原理深度剖析
SQL Server索引進階第十二篇：索引的創(chuàng)建，修改和刪除
SQL Server索引進階第十三篇：Insert,Update,Delete語句
SQL Server索引進階第十四篇：索引統(tǒng)計
SQL Server索引進階第十五篇：索引的最佳實踐

????在前一系列文章中我們著重講述了有關(guān)索引各種比較虛的概念，比如索引可以做什么，索引的邏輯結(jié)構(gòu)，接下來是時候來講述比較實在的東西了，也就是索引的物理結(jié)構(gòu)。理解索引的內(nèi)部結(jié)構(gòu)對于整體的理解索引是至關(guān)重要的，只有理解了索引的內(nèi)部結(jié)構(gòu)以及SQL Server是如何維護索引的，你才能理解數(shù)據(jù)插入，刪除，更新，索引的創(chuàng)建、修改、刪除所帶來的成本。

葉子層級和非葉子層級????

????所有的索引都是由葉子層級和非葉子層級組成的。前面的文章主要關(guān)注了索引的葉子層級。對于聚集索引來說，葉子節(jié)點就是索引本身，每一個葉子節(jié)點所包含的條目其實就是表中的行。對于非聚集索引來說，葉子節(jié)點每一個葉子包含的一行就是一個條目。每一個條目由索引鍵列，可選的包含列以及書簽構(gòu)成，而書簽又由聚集索引鍵或RID構(gòu)成。????????????????無論索引中條目是來自表行（聚集索引葉子節(jié)點），指向表行(非聚集索引葉子節(jié)點)或是指向低層級的節(jié)點(非葉子節(jié)點)，索引條目都可以被稱為索引行。??
???? 非葉子節(jié)點是葉子節(jié)點層級的上層，SQL Server使用非葉子節(jié)點來:

• ????使得索引按照索引鍵聚集有序
• ????根據(jù)索引鍵快速找到葉子節(jié)點

????在本系列第一篇文章中，我們使用電話本的類比來解釋為什么索引能夠帶來性能的提升。用戶知道電話本是按照姓氏進行排序的，因此如果需要找”Meyer, Helen”根據(jù)首字母M知道這個人大概在電話本的中間位置，用戶直接翻開大約一半電話本開始查找。但對于SQL Server來說,可并不知道什么是按字母表排序，也不知道哪一些頁是所謂的中間頁，除非把索引中的所有頁掃描一遍。為了不用掃描所有的頁來找到所需條目，SQL Server為在葉子節(jié)點之上增加了額外的頁。

非葉子層級??

????這些額外的頁也就是所謂的非葉子節(jié)點，或被稱為索引的節(jié)點層級,是建立在葉子層級之上的層級。非葉子層級的作用是使得SQL Server對于特定的索引進行查找時，不僅有了統(tǒng)一的入口頁，并且不再需要掃描所有的頁。??????????
???? 在索引中的所有頁，無論哪個層級，都包含索引條目。正如文章中不斷重復(fù)說的，對于聚集索引來說，葉子節(jié)點的條目包含實際的行，所以如果一個表中包含了10億行，那么葉子節(jié)點包含了10億個條目。????在葉子節(jié)點之上的層級,也就是非葉子節(jié)點的最底層，非葉子節(jié)點的最底層每一個索引條目都指向葉子節(jié)點。如果說表中每一頁能容納100個條目，那么剛才的十億行需要1000000000/100=1000萬個頁，與之對應(yīng)的是，那么最底層的非葉子節(jié)點就包含了1000萬的條目，也就是分布在1000萬/100=10萬個頁中。（譯者注:原作者這里沒說全，通常來說非葉子節(jié)點只包含索引鍵，因此每個條目的大小會遠遠小于葉子節(jié)點的條目大小，因此每頁可以容納更多的行，所以這里非葉子節(jié)點應(yīng)該遠遠小于10W個頁,后面的段落我們先不管這個，還是按照10W個頁算）。??

???? 再上一層的非葉子節(jié)點包含了指向這10萬個頁的條目，也就是10萬個條目，這10W個索引條目分布在10萬/1000=1000頁中。根據(jù)這個規(guī)律，我們知道再上一層包含10個頁，直至最上層的節(jié)點只有一個頁了。
??
???? 索引中最上層的節(jié)點被稱為根頁。剩下的除了根頁和葉子之外的層級就是所謂的中間層級。層級的編號是從葉子節(jié)點以0開始向上增長的，因此中間層級是以1開始的。????非葉子節(jié)點僅僅包含索引鍵，對于擁有包含列的索引來說，包含列僅僅存在于葉子節(jié)點。
????
????索引中的頁，除了根頁之外，都含有兩個額外的指針，分別指向按照索引順序當(dāng)前頁之前和之后的頁。這種雙向鏈表結(jié)構(gòu)使得SQL Server在索引掃描的時候更加有效。

一個簡單的例子 ??

????讓我們通過一個簡單的圖示來真正理解索引的內(nèi)部結(jié)構(gòu)吧，如下圖1所示。我們在Personnel.Employee表上創(chuàng)建了一個非聚集索引，代碼如下:

??CREATE NONCLUSTERED INDEX IX_Full_Name ON Personnel.Employee ( LastName, FirstName, ) GO??

復(fù)制代碼

圖例注釋:???? 指向頁的指針包含了文件號和頁號。比如說5:4567指向的就是第5個文件的4567個頁。

1001.jpg(81.01 K)
9/9/2012 11:19:21 AM

圖1.索引的豎切圖????
????值得說明的是，上面的圖只是一個樣子，正常的情況下一個頁中會包含遠多于上面例子的行，并且頁也會遠遠多于上面的例子。????
????實際在頁中索引條目并不是有序的，而是靠偏移指針進行定位的，這個頁尾的偏移表是有序的。????
????很多情況下，頁中并不像上面圖中所展現(xiàn)的那樣,頁之間物理上是連續(xù)的，但它們之間邏輯上是連續(xù)的，邏輯和物理上的差異被稱之為碎片。??
???? 正如我們之前所說，每一個索引可以包含不止一層的中間頁。????
????繼續(xù)使用我們之前電話本的類比。比如你查找名為Helen Meyer的聯(lián)系人，打開電話本找到第一頁，對于在區(qū)間 “Fernandez, Zelda”和 “Olsen, Karl”之間的名字，去看頁5:431.然后你找到431頁，這頁告訴你對于Kumar, Kevin”和“Nara, Alison”之間的名字，去找頁5:2006。然后你找到5:2006就找到了你所需的聯(lián)系人。

索引深度????

????索引的根頁以及相關(guān)信息是存在系統(tǒng)表中的。每當(dāng)SQL Server進行頁查找時，SQL Server都會從根頁開始查找，經(jīng)過中間節(jié)點，直到找到葉子節(jié)點，然后從葉子中找到需要的索引條目。對于我們10億行的表來說，從根節(jié)點到葉子節(jié)點共需要讀取5層。而對圖1所示的節(jié)點來說，只需要讀取3次IO。????
????上面所說的層數(shù)，也被成為索引深度。取決于索引鍵的大小和數(shù)量。在AdventureWorks示例數(shù)據(jù)庫中，沒有哪個索引的層級超過3層。但對于其它索引鍵寬或是數(shù)據(jù)量大的表，就會有更深的層級。????sys.dm_db_index_physical_stats函數(shù)可以展示索引的詳細信息,深度和大小。這是一個表值函數(shù)，比如下面代碼我們可以找到SalesOrderDetai表相關(guān)的索引信息。

SELECT??OBJECT_NAME(P.OBJECT_ID) AS 'Table' ,

????????I.name AS 'Index' ,

????????P.index_id AS 'IndexID' ,

????????P.index_type_desc ,

????????P.index_depth ,

????????P.page_count

FROM????sys.dm_db_index_physical_stats(DB_ID(),

?????????????????????????????????????? OBJECT_ID('Sales.SalesOrderDetail'),

?????????????????????????????????????? NULL, NULL, NULL) P

????????JOIN sys.indexes I ON I.OBJECT_ID = P.OBJECT_ID

??????????????????????????????AND I.index_id = P.index_id ;

復(fù)制代碼

得到的結(jié)果如圖2所示。

index1002.jpg(29.54 K)
9/9/2012 11:19:21 AM

圖2.查詢sys.dm_db_index_physical_stats函數(shù)得到的結(jié)果
????
????通過如下代碼我們可以看到更詳細的層級信息.SELECT??OBJECT_NAME(P.OBJECT_ID) AS 'Table' ,

????????I.name AS 'Index' ,

????????P.index_id AS 'IndexID' ,

????????P.index_type_desc ,

????????P.index_level ,

????????P.page_count

FROM????sys.dm_db_index_physical_stats(DB_ID(),

?????????????????????????????????????? OBJECT_ID('Sales.SalesOrderDetail'), 2,

?????????????????????????????????????? NULL, 'DETAILED') P

????????JOIN sys.indexes I ON I.OBJECT_ID = P.OBJECT_ID

??????????????????????????????AND I.index_id = P.index_id ;

復(fù)制代碼

得到的結(jié)果如圖3所示。

1003.jpg(23.53 K)
9/9/2012 11:19:21 AM

圖3.查詢索引的詳細信息通過圖3所示結(jié)果，可以看出

• ????葉子節(jié)點的條目分布在407頁中
• ????中間節(jié)點僅僅需要2頁
• ????根節(jié)點只有1頁

????根據(jù)索引鍵的選擇，書簽的大小的不同，葉子節(jié)點通常是非葉子節(jié)點大小的上百倍。根據(jù)具體的數(shù)據(jù)不同而不同。????
????記住包含列僅僅適用在非聚集索引并且只存在于葉子節(jié)點中，包含列對于上層的層級是透明的，這也是為什么包含列不會增加非葉子節(jié)點鍵的大小。????
????因為聚集索引的葉子節(jié)點是表數(shù)據(jù)本身，所以除了葉子節(jié)點的數(shù)據(jù)是表數(shù)據(jù)本身之外，還需要存儲一些額外的非葉子層級。因為無論是否有聚集索引數(shù)據(jù)本身都是存在的，所以創(chuàng)建聚集索引的時候不僅需要花費一些時間和資源，創(chuàng)建成功后還需要一些額外的空間存儲非葉子節(jié)點。

總結(jié)????

????索引的結(jié)構(gòu)使得SQL Server可以根據(jù)鍵值快速找到所需的列,一旦找到所需的列之后，SQL Server可以:

• ????直接訪問所需的行
• ????從找到的數(shù)據(jù)位置開始，根據(jù)雙向鏈表找相鄰的頁

????索引樹結(jié)構(gòu)早已經(jīng)在沒有關(guān)系數(shù)據(jù)庫時就開始被使用了，事實證明，這是一種優(yōu)秀的結(jié)構(gòu)。

?

轉(zhuǎn)載于:https://www.cnblogs.com/lteal/archive/2012/12/03/2799321.html

總結(jié)

以上是生活随笔為你收集整理的SQL Server索引进阶第十篇：索引的内部结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。