一. 索引

　　在上一章節(jié)中健哥講解了索引的基本入門(mén)和使用進(jìn)階。那么在這一節(jié)中我們來(lái)探討下索引的深層原理。各位小伙伴準(zhǔn)備好了嗎，我們開(kāi)始嘍!

　　索引的實(shí)現(xiàn)原理

　　索引是在MySQL的存儲(chǔ)引擎中實(shí)現(xiàn)的，所以每種存儲(chǔ)引擎的索引也就各不相同了，不同的存儲(chǔ)引擎支持不同類(lèi)型的索引。這里我們主要研究InnoDB引擎實(shí)現(xiàn)的B+樹(shù)索引。

　　B+樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)。通常使用在數(shù)據(jù)庫(kù)和操作系統(tǒng)中的文件系統(tǒng)，特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，還能夠加快查詢速度，我們一起來(lái)看下吧。

　　磁盤(pán)存儲(chǔ)

　　系統(tǒng)從磁盤(pán)讀取數(shù)據(jù)到內(nèi)存時(shí)是以磁盤(pán)塊(block)為基本單位的。

　　位于同一個(gè)磁盤(pán)塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái)，而不是需要什么取什么。

　　InnoDB存儲(chǔ)引擎中有頁(yè)(Page)的概念，頁(yè)是其磁盤(pán)管理的最小單位。InnoDB存儲(chǔ)引擎中默認(rèn)每個(gè)頁(yè)的大小為16KB。

　　InnoDB引擎將若干個(gè)地址連接磁盤(pán)塊，以此來(lái)達(dá)到頁(yè)的大小16KB，在查詢數(shù)據(jù)時(shí)如果一個(gè)頁(yè)中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會(huì)減少磁盤(pán)I/O次數(shù)，提高查詢效率。

　　BTree

　　BTree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤(pán)塊。為了描述BTree，首先定義一條記錄為一個(gè)二元組[key, data] ，key為記錄的鍵值，對(duì)應(yīng)表中的主鍵值，data為一行記錄中除主鍵外的數(shù)據(jù)。對(duì)于不同的記錄，key值互不相同。BTree中的每個(gè)節(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支，如下圖所示為一個(gè)3階的BTree：

　　根據(jù)圖中結(jié)構(gòu)顯示，每個(gè)節(jié)點(diǎn)占用一個(gè)盤(pán)塊的磁盤(pán)空間，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹(shù)根節(jié)點(diǎn)的指針，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤(pán)塊的地址。兩個(gè)關(guān)鍵詞劃分成的三個(gè)范圍域?qū)?yīng)三個(gè)指針指向的子樹(shù)的數(shù)據(jù)的范圍域。以根節(jié)點(diǎn)為例，關(guān)鍵字為17和35，P1指針指向的子樹(shù)的數(shù)據(jù)范圍為小于17，P2指針指向的子樹(shù)的數(shù)據(jù)范圍為17~35，P3指針指向的子樹(shù)的數(shù)據(jù)范圍為大于35。

　　查找順序,模擬查找15的過(guò)程 ：

　　● 根節(jié)點(diǎn)找到磁盤(pán)塊1，讀入內(nèi)存?！敬疟P(pán)I/O操作第1次】比較關(guān)鍵字15在區(qū)間(<17)，找到磁盤(pán)塊1的指針P1。

　　● P1指針找到磁盤(pán)塊2，讀入內(nèi)存。【磁盤(pán)I/O操作第2次】比較關(guān)鍵字15在區(qū)間(>12)，找到磁盤(pán)塊2的指針P3。

　　● P3指針找到磁盤(pán)塊7，讀入內(nèi)存?！敬疟P(pán)I/O操作第3次】 在磁盤(pán)塊7中找到關(guān)鍵字15。

　　● 分析:

　　○ 發(fā)現(xiàn)需要3次磁盤(pán)I/O操作，和3次內(nèi)存查找操作。

　　○ 由于內(nèi)存中的關(guān)鍵字是一個(gè)有序表結(jié)構(gòu)，可以利用二分法查找提高效率。而3次磁盤(pán)I/O操作是影響整個(gè)BTree查找效率的決定因素。BTree使用較少的節(jié)點(diǎn)個(gè)數(shù)，使每次磁盤(pán)I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率。

　　4. B+Tree

　　B+Tree是在BTree基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)，InnoDB存儲(chǔ)引擎就是用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

　　從上一節(jié)中的BTree結(jié)構(gòu)圖中可以看到每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值，還有data值。而每一個(gè)頁(yè)的存儲(chǔ)空間是有限的，如果data數(shù)據(jù)較大時(shí)將會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)(即一個(gè)頁(yè))能存儲(chǔ)的key的數(shù)量很小，當(dāng)存儲(chǔ)的數(shù)據(jù)量很大時(shí)同樣會(huì)導(dǎo)致B-Tree的深度較大，增大查詢時(shí)的磁盤(pán)I/O次數(shù)，進(jìn)而影響查詢效率。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲(chǔ)key值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲(chǔ)的key值數(shù)量，降低B+Tree的高度。

　　B+Tree相對(duì)于BTree區(qū)別：

　　● 非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息。

　　● 所有葉子節(jié)點(diǎn)之間都有一個(gè)連接指針。

　　● 數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中。

　　通常在B+Tree上有兩個(gè)頭指針，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有葉子節(jié)點(diǎn)(即數(shù)據(jù)節(jié)點(diǎn))之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。

　　對(duì)B+Tree進(jìn)行兩種查找運(yùn)算：

　　● 【有范圍】對(duì)于主鍵的范圍查找和分頁(yè)查找。

　　● 【有順序】從根節(jié)點(diǎn)開(kāi)始，進(jìn)行隨機(jī)查找。

　　實(shí)際情況中每個(gè)節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫(kù)中，B+Tree的高度一般都在24層。MySQL的InnoDB存儲(chǔ)引擎在設(shè)計(jì)時(shí)是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要13次磁盤(pán)I/O操作。