前幾天下班回到家后正在處理一個(gè)白天沒(méi)解決的bug，廁所突然傳來(lái)對(duì)象的聲音：
??對(duì)象：xx，你有《時(shí)間簡(jiǎn)史》嗎？
??我：我去！妹子，你這啥癖好啊，我有時(shí)間也不會(huì)去撿屎啊！
??對(duì)象：...人家說(shuō)的是霍金的科普著作《時(shí)間簡(jiǎn)史》，是一本書啦！
??我：哦，那我沒(méi)有...
??對(duì)象：人家想看誒，你明天幫我去圖書館借一本吧...
??我：我明天還要改...
??對(duì)象：你是不是不愛(ài)我了，分手！
??我：我一大早就去~

??第二天一大早我就到了圖書館，剛進(jìn)門就看到一個(gè)索引牌，標(biāo)識(shí)著不同樓層的功能，這樣我很快能定位到我要找的目標(biāo)所在的樓層了。

??

??我到樓上后又看到每排的書架上又對(duì)書的分類進(jìn)行了細(xì)分，這樣我能更快的定位到我要找的書具體在哪個(gè)書架！

??并且每個(gè)樓層都有一臺(tái)查詢終端，輸入書名就能查到對(duì)應(yīng)的唯一標(biāo)識(shí)“索書號(hào)”，類似于P159-49/164這樣的一個(gè)編碼，書架上的書都是按照這個(gè)編碼進(jìn)行排序的！有了這個(gè)編碼再去對(duì)應(yīng)的書架上，很快就能找到對(duì)應(yīng)的書在書架的具體位置了。

??

??不到十分鐘，我就從圖書館借好書出來(lái)了。

??這么大的圖書館，我為什么能在這么短的時(shí)間內(nèi)找到我要的書？如果這些書是雜亂無(wú)章的堆放，或者沒(méi)有任何標(biāo)識(shí)的放在書架，我還能這么快的找到嗎？

??這不禁讓我想到了我們開(kāi)發(fā)中用到的數(shù)據(jù)庫(kù)，圖書館的書就類似我們數(shù)據(jù)表中的數(shù)據(jù)，樓層索引牌、書架分類標(biāo)識(shí)、索書號(hào)就類似我們查找數(shù)據(jù)的索引。

??那我們常用的數(shù)據(jù)庫(kù)的索引底層的一個(gè)數(shù)據(jù)結(jié)構(gòu)是什么樣的呢？想到這里我又回到圖書館借了一本《數(shù)據(jù)庫(kù)從入門到放棄》！

??要了解數(shù)據(jù)庫(kù)索引的底層原理，我們就得先了解一種叫樹(shù)的數(shù)據(jù)結(jié)構(gòu)，而樹(shù)中很經(jīng)典的一種數(shù)據(jù)結(jié)構(gòu)就是二叉樹(shù)！所以下面我們就從二叉樹(shù)到平衡二叉樹(shù)，再到B-樹(shù)，最后到B+樹(shù)來(lái)一步一步了解數(shù)據(jù)庫(kù)索引底層的原理！

二叉查找樹(shù)（Binary Search Trees）

??二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）。二叉樹(shù)常被用于實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。二叉樹(shù)有如下特性：

1、每個(gè)結(jié)點(diǎn)都包含一個(gè)元素以及n個(gè)子樹(shù)，這里0≤n≤2。
2、左子樹(shù)和右子樹(shù)是有順序的，次序不能任意顛倒。左子樹(shù)的值要小于父結(jié)點(diǎn)，右子樹(shù)的值要大于父結(jié)點(diǎn)。

??光看概念有點(diǎn)枯燥，假設(shè)我們現(xiàn)在有這樣一組數(shù)[35 27 48 12 29 38 55]，順序的插入到一個(gè)數(shù)的結(jié)構(gòu)中，步驟如下

??好了，這就是一棵二叉樹(shù)啦！我們能看到，經(jīng)通過(guò)一系列的插入操作之后，原本無(wú)序的一組數(shù)已經(jīng)變成一個(gè)有序的結(jié)構(gòu)了，并且這個(gè)樹(shù)滿足了上面提到的兩個(gè)二叉樹(shù)的特性！

??但是如果同樣是上面那一組數(shù)，我們自己升序排列后再插入，也就是說(shuō)按照[12 27 29 35 38 48 55]的順序插入，會(huì)怎么樣呢？

??由于是升序插入，新插入的數(shù)據(jù)總是比已存在的結(jié)點(diǎn)數(shù)據(jù)都要大，所以每次都會(huì)往結(jié)點(diǎn)的右邊插入，最終導(dǎo)致這棵樹(shù)嚴(yán)重偏科?。。∩蠄D就是最壞的情況，也就是一棵樹(shù)退化為一個(gè)線性鏈表了，這樣查找效率自然就低了，完全沒(méi)有發(fā)揮樹(shù)的優(yōu)勢(shì)了呢！
為了較大發(fā)揮二叉樹(shù)的查找效率，讓二叉樹(shù)不再偏科，保持各科平衡，所以有了平衡二叉樹(shù)！

平衡二叉樹(shù) (AVL Trees)

??平衡二叉樹(shù)是一種特殊的二叉樹(shù)，所以他也滿足前面說(shuō)到的二叉樹(shù)的兩個(gè)特性，同時(shí)還有一個(gè)特性：

它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

??大家也看到了前面[35 27 48 12 29 38 55]插入完成后的圖，其實(shí)就已經(jīng)是一顆平衡二叉樹(shù)啦。

??那如果按照[12 27 29 35 38 48 55]的順序插入一顆平衡二叉樹(shù)，會(huì)怎么樣呢？我們看看插入以及平衡的過(guò)程：

??這棵樹(shù)始終滿足平衡二叉樹(shù)的幾個(gè)特性而保持平衡！這樣我們的樹(shù)也不會(huì)退化為線性鏈表了！我們需要查找一個(gè)數(shù)的時(shí)候就能沿著樹(shù)根一直往下找，這樣的查找效率和二分法查找是一樣的呢！

??一顆平衡二叉樹(shù)能容納多少的結(jié)點(diǎn)呢？這跟樹(shù)的高度是有關(guān)系的，假設(shè)樹(shù)的高度為h，那每一層最多容納的結(jié)點(diǎn)數(shù)量為2(n-1)，整棵樹(shù)最多容納節(jié)點(diǎn)數(shù)為20+21+22+...+2^(h-1)。這樣計(jì)算，100w數(shù)據(jù)樹(shù)的高度大概在20左右，那也就是說(shuō)從有著100w條數(shù)據(jù)的平衡二叉樹(shù)中找一個(gè)數(shù)據(jù)，最壞的情況下需要20次查找。如果是內(nèi)存操作，效率也是很高的！但是我們數(shù)據(jù)庫(kù)中的數(shù)據(jù)基本都是放在磁盤中的，每讀取一個(gè)二叉樹(shù)的結(jié)點(diǎn)就是一次磁盤IO，這樣我們找一條數(shù)據(jù)如果要經(jīng)過(guò)20次磁盤的IO？那性能就成了一個(gè)很大的問(wèn)題了！那我們是不是可以把這棵樹(shù)壓縮一下，讓每一層能夠容納更多的節(jié)點(diǎn)呢？雖然我矮，但是我胖啊...

B-Tree

??這顆矮胖的樹(shù)就是B-Tree，注意中間是杠精的杠而不是減，所以也不要讀成B減Tree了~

??那B-Tree有哪些特性呢？一棵m階的B-Tree有如下特性：

1、每個(gè)結(jié)點(diǎn)最多m個(gè)子結(jié)點(diǎn)。
2、除了根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最少有m/2（向上取整）個(gè)子結(jié)點(diǎn)。
3、如果根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，那根結(jié)點(diǎn)至少包含兩個(gè)子結(jié)點(diǎn)。
4、所有的葉子結(jié)點(diǎn)都位于同一層。
5、每個(gè)結(jié)點(diǎn)都包含k個(gè)元素（關(guān)鍵字），這里m/2≤k<m，這里m/2向下取整。
6、每個(gè)節(jié)點(diǎn)中的元素（關(guān)鍵字）從小到大排列。
7、每個(gè)元素（關(guān)鍵字）字左結(jié)點(diǎn)的值，都小于或等于該元素（關(guān)鍵字）。右結(jié)點(diǎn)的值都大于或等于該元素（關(guān)鍵字）。

??是不是感覺(jué)跟丈母娘張口問(wèn)你要彩禮一樣，列一堆的條件，而且每一條都讓你很懵逼！下面我們以一個(gè)[0,1,2,3,4,5,6,7]的數(shù)組插入一顆3階的B-Tree為例，將所有的條件都串起來(lái)，你就明白了！

??那么，你是否對(duì)B-Tree的幾點(diǎn)特性都清晰了呢？在二叉樹(shù)中，每個(gè)結(jié)點(diǎn)只有一個(gè)元素。但是在B-Tree中，每個(gè)結(jié)點(diǎn)都可能包含多個(gè)元素，并且非葉子結(jié)點(diǎn)在元素的左右都有指向子結(jié)點(diǎn)的指針。

??如果需要查找一個(gè)元素，那流程是怎么樣的呢？我們看下圖，如果我們要在下面的B-Tree中找到關(guān)鍵字24，那流程如下

??從這個(gè)流程我們能看出，B-Tree的查詢效率好像也并不比平衡二叉樹(shù)高。但是查詢所經(jīng)過(guò)的結(jié)點(diǎn)數(shù)量要少很多，也就意味著要少很多次的磁盤IO，這對(duì)
性能的提升是很大的。

??前面對(duì)B-Tree操作的圖我們能看出來(lái)，元素就是類似1、2、3這樣的數(shù)值，但是數(shù)據(jù)庫(kù)的數(shù)據(jù)都是一條條的數(shù)據(jù)，如果某個(gè)數(shù)據(jù)庫(kù)以B-Tree的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，那數(shù)據(jù)怎么存放的呢？我們看下一張圖

??普通的B-Tree的結(jié)點(diǎn)中，元素就是一個(gè)個(gè)的數(shù)字。但是上圖中，我們把元素部分拆分成了key-data的形式，key就是數(shù)據(jù)的主鍵，data就是具體的數(shù)據(jù)。這樣我們?cè)谡乙粭l數(shù)的時(shí)候，就沿著根結(jié)點(diǎn)往下找就ok了，效率是比較高的。

B+Tree

??B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)。B+Tree與B-Tree的結(jié)構(gòu)很像，但是也有幾個(gè)自己的特性：

1、所有的非葉子節(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字信息。
2、所有衛(wèi)星數(shù)據(jù)（具體數(shù)據(jù)）都存在葉子結(jié)點(diǎn)中。
3、所有的葉子結(jié)點(diǎn)中包含了全部元素的信息。
4、所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針。

??如果上面B-Tree的圖變成B+Tree，那應(yīng)該如下：

??大家仔細(xì)對(duì)比于B-Tree的圖能發(fā)現(xiàn)什么不同？
??1、非葉子結(jié)點(diǎn)上已經(jīng)只有key信息了，滿足上面第1點(diǎn)特性！
??2、所有葉子結(jié)點(diǎn)下面都有一個(gè)data區(qū)域，滿足上面第2點(diǎn)特性！
??3、非葉子結(jié)點(diǎn)的數(shù)據(jù)在葉子結(jié)點(diǎn)上都能找到，如根結(jié)點(diǎn)的元素4、8在最底層的葉子結(jié)點(diǎn)上也能找到，滿足上面第3點(diǎn)特性！
??4、注意圖中葉子結(jié)點(diǎn)之間的箭頭，滿足滿足上面第4點(diǎn)特性！

B-Tree or B+Tree？

??在講這兩種數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)庫(kù)中的選擇之前，我們還需要了解的一個(gè)知識(shí)點(diǎn)是操作系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存是以磁盤塊（block）為基本單位的，位于同一個(gè)磁盤塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái)，而不是需要什么取什么。即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理： 當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。
??預(yù)讀的長(zhǎng)度一般為頁(yè)（page）的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)（在許多操作系統(tǒng)中，頁(yè)得大小通常為4k）。

??B-Tree和B+Tree該如何選擇呢？都有哪些優(yōu)劣呢？
??1、B-Tree因?yàn)榉侨~子結(jié)點(diǎn)也保存具體數(shù)據(jù)，所以在查找某個(gè)關(guān)鍵字的時(shí)候找到即可返回。而B(niǎo)+Tree所有的數(shù)據(jù)都在葉子結(jié)點(diǎn)，每次查找都得到葉子結(jié)點(diǎn)。所以在同樣高度的B-Tree和B+Tree中，B-Tree查找某個(gè)關(guān)鍵字的效率更高。
??2、由于B+Tree所有的數(shù)據(jù)都在葉子結(jié)點(diǎn)，并且結(jié)點(diǎn)之間有指針連接，在找大于某個(gè)關(guān)鍵字或者小于某個(gè)關(guān)鍵字的數(shù)據(jù)的時(shí)候，B+Tree只需要找到該關(guān)鍵字然后沿著鏈表遍歷就可以了，而B(niǎo)-Tree還需要遍歷該關(guān)鍵字結(jié)點(diǎn)的根結(jié)點(diǎn)去搜索。
??3、由于B-Tree的每個(gè)結(jié)點(diǎn)（這里的結(jié)點(diǎn)可以理解為一個(gè)數(shù)據(jù)頁(yè)）都存儲(chǔ)主鍵+實(shí)際數(shù)據(jù)，而B(niǎo)+Tree非葉子結(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字信息，而每個(gè)頁(yè)的大小有限是有限的，所以同一頁(yè)能存儲(chǔ)的B-Tree的數(shù)據(jù)會(huì)比B+Tree存儲(chǔ)的更少。這樣同樣總量的數(shù)據(jù)，B-Tree的深度會(huì)更大，增大查詢時(shí)的磁盤I/O次數(shù)，進(jìn)而影響查詢效率。
??鑒于以上的比較，所以在常用的關(guān)系型數(shù)據(jù)庫(kù)中，都是選擇B+Tree的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)！下面我們以mysql的innodb存儲(chǔ)引擎為例講解，其他類似sqlserver、oracle的原理類似！

innodb引擎數(shù)據(jù)存儲(chǔ)

??在InnoDB存儲(chǔ)引擎中，也有頁(yè)的概念，默認(rèn)每個(gè)頁(yè)的大小為16K，也就是每次讀取數(shù)據(jù)時(shí)都是讀取4*4k的大小！假設(shè)我們現(xiàn)在有一個(gè)用戶表，我們往里面寫數(shù)據(jù)

??這里需要注意的一點(diǎn)是，在某個(gè)頁(yè)內(nèi)插入新行時(shí)，為了不減少數(shù)據(jù)的移動(dòng)，通常是插入到當(dāng)前行的后面或者是已刪除行留下來(lái)的空間，所以在某一個(gè)頁(yè)內(nèi)的數(shù)據(jù)并不是完全有序的（后面頁(yè)結(jié)構(gòu)部分有細(xì)講），但是為了為了數(shù)據(jù)訪問(wèn)順序性，在每個(gè)記錄中都有一個(gè)指向下一條記錄的指針，以此構(gòu)成了一條單向有序鏈表，不過(guò)在這里為了方便演示我是按順序排列的！

??由于數(shù)據(jù)還比較少，一個(gè)頁(yè)就能容下，所以只有一個(gè)根結(jié)點(diǎn)，主鍵和數(shù)據(jù)也都是保存在根結(jié)點(diǎn)（左邊的數(shù)字代表主鍵，右邊名字、性別代表具體的數(shù)據(jù)）。假設(shè)我們寫入10條數(shù)據(jù)之后，Page1滿了，再寫入新的數(shù)據(jù)會(huì)怎么存放呢？我們繼續(xù)看下圖

??有個(gè)叫“秦壽生”的朋友來(lái)了，但是Page1已經(jīng)放不下數(shù)據(jù)了，這時(shí)候就需要進(jìn)行頁(yè)分裂，產(chǎn)生一個(gè)新的Page。在innodb中的流程是怎么樣的呢？

1、產(chǎn)生新的Page2，然后將Page1的內(nèi)容復(fù)制到Page2。
2、產(chǎn)生新的Page3，“秦壽生”的數(shù)據(jù)放入Page3。
3、原來(lái)的Page1依然作為根結(jié)點(diǎn)，但是變成了一個(gè)不存放數(shù)據(jù)只存放索引的頁(yè)，并且有兩個(gè)子結(jié)點(diǎn)Page2、Page3。

??這里有兩個(gè)問(wèn)題需要注意的是
??1、為什么要復(fù)制Page1為Page2而不是創(chuàng)建一個(gè)新的頁(yè)作為根結(jié)點(diǎn)，這樣就少了一步復(fù)制的開(kāi)銷了？
??如果是重新創(chuàng)建根結(jié)點(diǎn)，那根結(jié)點(diǎn)存儲(chǔ)的物理地址可能經(jīng)常會(huì)變，不利于查找。并且在innodb中根結(jié)點(diǎn)是會(huì)預(yù)讀到內(nèi)存中的，所以結(jié)點(diǎn)的物理地址固定會(huì)比較好！

??2、原來(lái)Page1有10條數(shù)據(jù)，在插入第11條數(shù)據(jù)的時(shí)候進(jìn)行裂變，根據(jù)前面對(duì)B-Tree、B+Tree特性的了解，那這至少是一顆11階的樹(shù)，裂變之后每個(gè)結(jié)點(diǎn)的元素至少為11/2=5個(gè)，那是不是應(yīng)該頁(yè)裂變之后主鍵1-5的數(shù)據(jù)還是在原來(lái)的頁(yè)，主鍵6-11的數(shù)據(jù)會(huì)放到新的頁(yè)，根結(jié)點(diǎn)存放主鍵6？
??如果是這樣的話新的頁(yè)空間利用率只有50%，并且會(huì)導(dǎo)致更為頻繁的頁(yè)分裂。所以innodb對(duì)這一點(diǎn)做了優(yōu)化，新的數(shù)據(jù)放入新創(chuàng)建的頁(yè)，不移動(dòng)原有頁(yè)面的任何記錄。

??隨著數(shù)據(jù)的不斷寫入，這棵樹(shù)也逐漸枝繁葉茂，如下圖

??每次新增數(shù)據(jù)，都是將一個(gè)頁(yè)寫滿，然后新創(chuàng)建一個(gè)頁(yè)繼續(xù)寫，這里其實(shí)是有個(gè)隱含條件的，那就是主鍵自增！主鍵自增寫入時(shí)新插入的數(shù)據(jù)不會(huì)影響到原有頁(yè)，插入效率高！且頁(yè)的利用率高！但是如果主鍵是無(wú)序的或者隨機(jī)的，那每次的插入可能會(huì)導(dǎo)致原有頁(yè)頻繁的分裂，影響插入效率！降低頁(yè)的利用率！這也是為什么在innodb中建議設(shè)置主鍵自增的原因！

??這棵樹(shù)的非葉子結(jié)點(diǎn)上存的都是主鍵，那如果一個(gè)表沒(méi)有主鍵會(huì)怎么樣？在innodb中，如果一個(gè)表沒(méi)有主鍵，那默認(rèn)會(huì)找建了唯一索引的列，如果也沒(méi)有，則會(huì)生成一個(gè)隱形的字段作為主鍵！

??有數(shù)據(jù)插入那就有刪除，如果這個(gè)用戶表頻繁的插入和刪除，那會(huì)導(dǎo)致數(shù)據(jù)頁(yè)產(chǎn)生碎片，頁(yè)的空間利用率低，還會(huì)導(dǎo)致樹(shù)變的“虛高”，降低查詢效率！這可以通過(guò)索引重建來(lái)消除碎片提高查詢效率！

innodb引擎數(shù)據(jù)查找

??數(shù)據(jù)插入了怎么查找呢？

1、找到數(shù)據(jù)所在的頁(yè)。這個(gè)查找過(guò)程就跟前面說(shuō)到的B+Tree的搜索過(guò)程是一樣的，從根結(jié)點(diǎn)開(kāi)始查找一直到葉子結(jié)點(diǎn)。
2、在頁(yè)內(nèi)找具體的數(shù)據(jù)。讀取第1步找到的葉子結(jié)點(diǎn)數(shù)據(jù)到內(nèi)存中，然后通過(guò)分塊查找的方法找到具體的數(shù)據(jù)。

??這跟我們?cè)谛氯A字典中找某個(gè)漢字是一樣的，先通過(guò)字典的索引定位到該漢字拼音所在的頁(yè)，然后到指定的頁(yè)找到具體的漢字。innodb中定位到頁(yè)后用了哪種策略快速查找某個(gè)主鍵呢？這我們就需要從頁(yè)結(jié)構(gòu)開(kāi)始了解。

??左邊藍(lán)色區(qū)域稱為Page Directory，這塊區(qū)域由多個(gè)slot組成，是一個(gè)稀疏索引結(jié)構(gòu)，即一個(gè)槽中可能屬于多個(gè)記錄，最少屬于4條記錄，最多屬于8條記錄。槽內(nèi)的數(shù)據(jù)是有序存放的，所以當(dāng)我們尋找一條數(shù)據(jù)的時(shí)候可以先在槽中通過(guò)二分法查找到一個(gè)大致的位置。

??右邊區(qū)域?yàn)閿?shù)據(jù)區(qū)域，每一個(gè)數(shù)據(jù)頁(yè)中都包含多條行數(shù)據(jù)。注意看圖中最上面和最下面的兩條特殊的行記錄Infimum和Supremum，這是兩個(gè)虛擬的行記錄。在沒(méi)有其他用戶數(shù)據(jù)的時(shí)候Infimum的下一條記錄的指針指向Supremum，當(dāng)有用戶數(shù)據(jù)的時(shí)候，Infimum的下一條記錄的指針指向當(dāng)前頁(yè)中最小的用戶記錄，當(dāng)前頁(yè)中最大的用戶記錄的下一條記錄的指針指向Supremum，至此整個(gè)頁(yè)內(nèi)的所有行記錄形成一個(gè)單向鏈表。

??行記錄被Page Directory邏輯的分成了多個(gè)塊，塊與塊之間是有序的，也就是說(shuō)“4”這個(gè)槽指向的數(shù)據(jù)塊內(nèi)最大的行記錄的主鍵都要比“8”這個(gè)槽指向的數(shù)據(jù)塊內(nèi)最小的行記錄的主鍵要小。但是塊內(nèi)部的行記錄不一定有序。

??每個(gè)行記錄的都有一個(gè)n_owned的區(qū)域（圖中粉紅色區(qū)域），n_owned標(biāo)識(shí)這個(gè)這個(gè)塊有多少條數(shù)據(jù)，偽記錄Infimum的n_owned值總是1，記錄Supremum的n_owned的取值范圍為[1,8]，其他用戶記錄n_owned的取值范圍[4,8]，并且只有每個(gè)塊中最大的那條記錄的n_owned才會(huì)有值，其他的用戶記錄的n_owned為0。

??所以當(dāng)我們要找主鍵為6的記錄時(shí)，先通過(guò)二分法在稀疏索引中找到對(duì)應(yīng)的槽，也就是Page Directory中“8”這個(gè)槽，“8”這個(gè)槽指向的是該數(shù)據(jù)塊中最大的記錄，而數(shù)據(jù)是單向鏈表結(jié)構(gòu)所以無(wú)法逆向查找，所以需要找到上一個(gè)槽即“4”這個(gè)槽，然后通過(guò)“4”這個(gè)槽中最大的用戶記錄的指針沿著鏈表順序查找到目標(biāo)記錄。

聚集索引&非聚集索引

??前面關(guān)于數(shù)據(jù)存儲(chǔ)的都是演示的聚集索引的實(shí)現(xiàn)，如果上面的用戶表需要以“用戶名字”建立一個(gè)非聚集索引，是怎么實(shí)現(xiàn)的呢？我們看下圖：

??非聚集索引的存儲(chǔ)結(jié)構(gòu)與前面是一樣的，不同的是在葉子結(jié)點(diǎn)的數(shù)據(jù)部分存的不再是具體的數(shù)據(jù)，而數(shù)據(jù)的聚集索引的key。所以通過(guò)非聚集索引查找的過(guò)程是先找到該索引key對(duì)應(yīng)的聚集索引的key，然后再拿聚集索引的key到主鍵索引樹(shù)上查找對(duì)應(yīng)的數(shù)據(jù)，這個(gè)過(guò)程稱為回表！

??圖中的這些名字均來(lái)源于網(wǎng)絡(luò)，希望沒(méi)有誤傷正在看這篇文章的你~_

innodb與MyISAM兩種存儲(chǔ)引擎對(duì)比

??上面包括存儲(chǔ)和搜索都是拿的innodb引擎為例，那MyISAM與innodb在存儲(chǔ)上有啥不同呢？憋縮話，看圖：

??上圖為MyISAM主鍵索引的存儲(chǔ)結(jié)構(gòu)，我們能看到的不同是

1、主鍵索引樹(shù)的葉子結(jié)點(diǎn)的數(shù)據(jù)區(qū)域沒(méi)有存放實(shí)際的數(shù)據(jù)，存放的是數(shù)據(jù)記錄的地址。
2、數(shù)據(jù)的存儲(chǔ)不是按主鍵順序存放的，按寫入的順序存放。

??也就是說(shuō)innodb引擎數(shù)據(jù)在物理上是按主鍵順序存放，而MyISAM引擎數(shù)據(jù)在物理上按插入的順序存放。并且MyISAM的葉子結(jié)點(diǎn)不存放數(shù)據(jù)，所以非聚集索引的存儲(chǔ)結(jié)構(gòu)與聚集索引類似，在使用非聚集索引查找數(shù)據(jù)的時(shí)候通過(guò)非聚集索引樹(shù)就能直接找到數(shù)據(jù)的地址了，不需要回表，這比innodb的搜索效率會(huì)更高呢！

索引優(yōu)化建議？

??大家經(jīng)常會(huì)在很多的文章或書中能看到一些索引的使用建議，比如說(shuō)

1、like的模糊查詢以%開(kāi)頭，會(huì)導(dǎo)致索引失效。
2、一個(gè)表建的索引盡量不要超過(guò)5個(gè)。
3、盡量使用覆蓋索引。
4、盡量不要在重復(fù)數(shù)據(jù)多的列上建索引。
5、。。。。。。。。。。。
6、。。。。。。。。。。。

??很多這里就不一一列舉了！那看完這篇文章，我們能否帶著疑問(wèn)去分析一下為什么要有這些建議？為什么like的模糊查詢以%開(kāi)頭，會(huì)導(dǎo)致索引失效？為什么一個(gè)表建的索引盡量不要超過(guò)5個(gè)？為什么？ 為什么？？為什么？？？相信看到這里的你再加上自己的一些思考應(yīng)該有答案了吧？