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

    本系列文章來(lái)自Stairway to SQL Server Indexes，翻譯和整理后發(fā)布在agilesharp和博客園，希望對(duì)廣大的技術(shù)朋友在如何使用索引上有所幫助

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

葉子層級(jí)和非葉子層級(jí)

    所有的索引都是由葉子層級(jí)和非葉子層級(jí)組成的。前面的文章主要關(guān)注了索引的葉子層級(jí)。對(duì)于聚集索引來(lái)說(shuō)，葉子節(jié)點(diǎn)就是索引本身，每一個(gè)葉子節(jié)點(diǎn)所包含的條目其實(shí)就是表中的行。對(duì)于非聚集索引來(lái)說(shuō)，葉子節(jié)點(diǎn)每一個(gè)葉子包含的一行就是一個(gè)條目。每一個(gè)條目由索引鍵列，可選的包含列以及書(shū)簽構(gòu)成，而書(shū)簽又由聚集索引鍵或RID構(gòu)成。

    無(wú)論索引中條目是來(lái)自表行（聚集索引葉子節(jié)點(diǎn)），指向表行(非聚集索引葉子節(jié)點(diǎn))或是指向低層級(jí)的節(jié)點(diǎn)(非葉子節(jié)點(diǎn))，索引條目都可以被稱(chēng)為索引行。

    非葉子節(jié)點(diǎn)是葉子節(jié)點(diǎn)層級(jí)的上層，SQL Server使用非葉子節(jié)點(diǎn)來(lái):

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

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

非葉子層級(jí)

    這些額外的頁(yè)也就是所謂的非葉子節(jié)點(diǎn)，或被稱(chēng)為索引的節(jié)點(diǎn)層級(jí),是建立在葉子層級(jí)之上的層級(jí)。非葉子層級(jí)的作用是使得SQL Server對(duì)于特定的索引進(jìn)行查找時(shí)，不僅有了統(tǒng)一的入口頁(yè)，并且不再需要掃描所有的頁(yè)。

    在索引中的所有頁(yè)，無(wú)論哪個(gè)層級(jí)，都包含索引條目。正如文章中不斷重復(fù)說(shuō)的，對(duì)于聚集索引來(lái)說(shuō)，葉子節(jié)點(diǎn)的條目包含實(shí)際的行，所以如果一個(gè)表中包含了10億行，那么葉子節(jié)點(diǎn)包含了10億個(gè)條目。

    在葉子節(jié)點(diǎn)之上的層級(jí),也就是非葉子節(jié)點(diǎn)的最底層，非葉子節(jié)點(diǎn)的最底層每一個(gè)索引條目都指向葉子節(jié)點(diǎn)。如果說(shuō)表中每一頁(yè)能容納100個(gè)條目，那么剛才的十億行需要1000000000/100=1000萬(wàn)個(gè)頁(yè)，與之對(duì)應(yīng)的是，那么最底層的非葉子節(jié)點(diǎn)就包含了1000萬(wàn)的條目，也就是分布在1000萬(wàn)/100=10萬(wàn)個(gè)頁(yè)中。（譯者注:原作者這里沒(méi)說(shuō)全，通常來(lái)說(shuō)非葉子節(jié)點(diǎn)只包含索引鍵，因此每個(gè)條目的大小會(huì)遠(yuǎn)遠(yuǎn)小于葉子節(jié)點(diǎn)的條目大小，因此每頁(yè)可以容納更多的行，所以這里非葉子節(jié)點(diǎn)應(yīng)該遠(yuǎn)遠(yuǎn)小于10W個(gè)頁(yè),后面的段落我們先不管這個(gè)，還是按照10W個(gè)頁(yè)算）。

    再上一層的非葉子節(jié)點(diǎn)包含了指向這10萬(wàn)個(gè)頁(yè)的條目，也就是10萬(wàn)個(gè)條目，這10W個(gè)索引條目分布在10萬(wàn)/1000=1000頁(yè)中。根據(jù)這個(gè)規(guī)律，我們知道再上一層包含10個(gè)頁(yè)，直至最上層的節(jié)點(diǎn)只有一個(gè)頁(yè)了。

    索引中最上層的節(jié)點(diǎn)被稱(chēng)為根頁(yè)。剩下的除了根頁(yè)和葉子之外的層級(jí)就是所謂的中間層級(jí)。層級(jí)的編號(hào)是從葉子節(jié)點(diǎn)以0開(kāi)始向上增長(zhǎng)的，因此中間層級(jí)是以1開(kāi)始的。

    非葉子節(jié)點(diǎn)僅僅包含索引鍵，對(duì)于擁有包含列的索引來(lái)說(shuō)，包含列僅僅存在于葉子節(jié)點(diǎn)。

    索引中的頁(yè)，除了根頁(yè)之外，都含有兩個(gè)額外的指針，分別指向按照索引順序當(dāng)前頁(yè)之前和之后的頁(yè)。這種雙向鏈表結(jié)構(gòu)使得SQL Server在索引掃描的時(shí)候更加有效。

一個(gè)簡(jiǎn)單的例子

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

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

    圖例注釋:

     指向頁(yè)的指針包含了文件號(hào)和頁(yè)號(hào)。比如說(shuō)5:4567指向的就是第5個(gè)文件的4567個(gè)頁(yè)。

圖1.索引的豎切圖

    值得說(shuō)明的是，上面的圖只是一個(gè)樣子，正常的情況下一個(gè)頁(yè)中會(huì)包含遠(yuǎn)多于上面例子的行，并且頁(yè)也會(huì)遠(yuǎn)遠(yuǎn)多于上面的例子。

    實(shí)際在頁(yè)中索引條目并不是有序的，而是靠偏移指針進(jìn)行定位的，這個(gè)頁(yè)尾的偏移表是有序的。

    很多情況下，頁(yè)中并不像上面圖中所展現(xiàn)的那樣,頁(yè)之間物理上是連續(xù)的，但它們之間邏輯上是連續(xù)的，邏輯和物理上的差異被稱(chēng)之為碎片。

    正如我們之前所說(shuō)，每一個(gè)索引可以包含不止一層的中間頁(yè)。

    繼續(xù)使用我們之前電話(huà)本的類(lèi)比。比如你查找名為Helen Meyer的聯(lián)系人，打開(kāi)電話(huà)本找到第一頁(yè)，對(duì)于在區(qū)間 “Fernandez, Zelda”和 “Olsen, Karl”之間的名字，去看頁(yè)5:431.然后你找到431頁(yè)，這頁(yè)告訴你對(duì)于Kumar, Kevin”和“Nara, Alison”之間的名字，去找頁(yè)5:2006。然后你找到5:2006就找到了你所需的聯(lián)系人。

索引深度

    索引的根頁(yè)以及相關(guān)信息是存在系統(tǒng)表中的。每當(dāng)SQL Server進(jìn)行頁(yè)查找時(shí)，SQL Server都會(huì)從根頁(yè)開(kāi)始查找，經(jīng)過(guò)中間節(jié)點(diǎn)，直到找到葉子節(jié)點(diǎn)，然后從葉子中找到需要的索引條目。對(duì)于我們10億行的表來(lái)說(shuō)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)共需要讀取5層。而對(duì)圖1所示的節(jié)點(diǎn)來(lái)說(shuō)，只需要讀取3次IO。

    上面所說(shuō)的層數(shù)，也被成為索引深度。取決于索引鍵的大小和數(shù)量。在AdventureWorks示例數(shù)據(jù)庫(kù)中，沒(méi)有哪個(gè)索引的層級(jí)超過(guò)3層。但對(duì)于其它索引鍵寬或是數(shù)據(jù)量大的表，就會(huì)有更深的層級(jí)。

    sys.dm_db_index_physical_stats函數(shù)可以展示索引的詳細(xì)信息,深度和大小。這是一個(gè)表值函數(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 ;

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

   
圖2.查詢(xún)sys.dm_db_index_physical_stats函數(shù)得到的結(jié)果

通過(guò)如下代碼我們可以看到更詳細(xì)的層級(jí)信息.

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 ; 

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

圖3.查詢(xún)索引的詳細(xì)信息

   通過(guò)圖3所示結(jié)果，可以看出

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

    根據(jù)索引鍵的選擇，書(shū)簽的大小的不同，葉子節(jié)點(diǎn)通常是非葉子節(jié)點(diǎn)大小的上百倍。根據(jù)具體的數(shù)據(jù)不同而不同。

     記住包含列僅僅適用在非聚集索引并且只存在于葉子節(jié)點(diǎn)中，包含列對(duì)于上層的層級(jí)是透明的，這也是為什么包含列不會(huì)增加非葉子節(jié)點(diǎn)鍵的大小。

     因?yàn)榫奂饕娜~子節(jié)點(diǎn)是表數(shù)據(jù)本身，所以除了葉子節(jié)點(diǎn)的數(shù)據(jù)是表數(shù)據(jù)本身之外，還需要存儲(chǔ)一些額外的非葉子層級(jí)。因?yàn)闊o(wú)論是否有聚集索引數(shù)據(jù)本身都是存在的，所以創(chuàng)建聚集索引的時(shí)候不僅需要花費(fèi)一些時(shí)間和資源，創(chuàng)建成功后還需要一些額外的空間存儲(chǔ)非葉子節(jié)點(diǎn)。

總結(jié)

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

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

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