索引

MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

我們知道，數(shù)據(jù)庫(kù)查詢(xún)是數(shù)據(jù)庫(kù)的最主要功能之一。我們都希望查詢(xún)數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者會(huì)從查詢(xún)算法的角度進(jìn)行優(yōu)化。最基本的查詢(xún)算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如二分查找（binary search）、二叉樹(shù)查找（binary tree search）等。如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹(shù)查找只能應(yīng)用于二叉查找樹(shù)上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿(mǎn)足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿(mǎn)足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。
看一個(gè)例子：

圖1.png

B-Tree和B+Tree

目前大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)，在本文的下一節(jié)會(huì)結(jié)合存儲(chǔ)器原理及計(jì)算機(jī)存取原理討論為什么B-Tree和B+Tree在被如此廣泛用于索引，這一節(jié)先單純從數(shù)據(jù)結(jié)構(gòu)角度描述它們。

B-Tree

是一種多路搜索樹(shù)（并不是二叉的）：
1.定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子；且M>2；
2.根結(jié)點(diǎn)的兒子數(shù)為[2, M]；
3.除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]；
4.每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字；（至少2個(gè)關(guān)鍵字）
5.非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1；
6.非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的
子樹(shù)，P[M]指向關(guān)鍵字大于K[M-1]的子樹(shù)，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹(shù)；
8.所有葉子結(jié)點(diǎn)位于同一層；
9.每個(gè)k對(duì)應(yīng)一個(gè)data。
如：（M=3）相當(dāng)于一個(gè)2–3樹(shù)，2–3樹(shù)是一個(gè)這樣的一棵樹(shù)， 它的每個(gè)節(jié)點(diǎn)要么有2個(gè)孩子和1個(gè)數(shù)據(jù)元素，要么有3個(gè)孩子和2個(gè)數(shù)據(jù)元素，葉子節(jié)點(diǎn)沒(méi)有孩子，并且有1個(gè)或2個(gè)數(shù)據(jù)元素。

B-樹(shù)的搜索，從根結(jié)點(diǎn)開(kāi)始，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束，否則進(jìn)入查詢(xún)關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)；重復(fù)，直到所對(duì)應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)；B-Tree上查找算法的偽代碼如下：

BTree_Search(node, key) { if(node == null) return null; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i+1]->node); } data = BTree_Search(root, my_key);

• B-樹(shù)的特性：
  1.關(guān)鍵字集合分布在整顆樹(shù)中；
  2.任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；
  3.搜索有可能在非葉子結(jié)點(diǎn)結(jié)束；
  4.其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找；
  5.自動(dòng)層次控制；

• B-樹(shù)的自控制:
  B樹(shù)中每一個(gè)內(nèi)部節(jié)點(diǎn)會(huì)包含一定數(shù)量的鍵值。通常，鍵值的數(shù)量被選定在d和2d之間。在實(shí)際中，鍵值占用了節(jié)點(diǎn)中大部分的空間。因數(shù)2將保證節(jié)點(diǎn)可以被拆分或組合。如果一個(gè)內(nèi)部節(jié)點(diǎn)有2d個(gè)鍵值，那么添加一個(gè)鍵值給此節(jié)點(diǎn)的過(guò)程，將會(huì)拆分2d鍵值為2個(gè)d鍵值的節(jié)點(diǎn)，并把此鍵值添加給父節(jié)點(diǎn)。每一個(gè)拆分的節(jié)點(diǎn)需要最小數(shù)目的鍵值。相似地，如果一個(gè)內(nèi)部節(jié)點(diǎn)和他的鄰居兩者都有d個(gè)鍵值，那么將通過(guò)它與鄰居的合并來(lái)刪除一個(gè)鍵值。刪除此鍵值將導(dǎo)致此節(jié)點(diǎn)擁有d-1個(gè)鍵值;與鄰居的合并則加上d個(gè)鍵值，再加上從鄰居節(jié)點(diǎn)的父節(jié)點(diǎn)移來(lái)的一個(gè)鍵值。結(jié)果為完全填充的2d個(gè)鍵值。

• B-樹(shù)的構(gòu)造過(guò)程：
  下面是往B樹(shù)中依次插入
  6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

  
  
  btreebuild.gif

B+Tree

B-Tree有許多變種，其中最常見(jiàn)的是B+Tree，例如MySQL就普遍使用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

• 與B-Tree相比，B+Tree有以下不同點(diǎn)：
  1.非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同；
  2.非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù)（B-樹(shù)是開(kāi)區(qū)間）；
  3.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；
  4.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；
  5.內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key
  如：（M=3）

  
  
  Paste_Image.png

B+的搜索與B-樹(shù)也基本相同，區(qū)別是B+樹(shù)只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹(shù)可以在非葉子結(jié)點(diǎn)命中），其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；

• B+的特性：
  1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；
  2.不可能在非葉子結(jié)點(diǎn)命中；
  3.非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
  4.更適合文件索引系統(tǒng)；

• B+樹(shù)的構(gòu)造過(guò)程：
  下面是往B+樹(shù)中依次插入
  6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

  
  
  Bplustreebuild.gif

索引的物理存儲(chǔ)

一般來(lái)說(shuō)，索引本身也很大，不可能全部存儲(chǔ)在內(nèi)存中，因此索引往往以索引文件的形式存儲(chǔ)的磁盤(pán)上。這樣的話(huà)，索引查找過(guò)程中就要產(chǎn)生磁盤(pán)I/O消耗，相對(duì)于內(nèi)存存取，I/O存取的消耗要高幾個(gè)數(shù)量級(jí)，所以評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過(guò)程中磁盤(pán)I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話(huà)說(shuō)，索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤(pán)I/O的存取次數(shù)。

B-tree

Paste_Image.png

假如每個(gè)盤(pán)塊可以正好存放一個(gè)B樹(shù)的結(jié)點(diǎn)（正好存放2個(gè)文件名）。那么一個(gè)BTNODE結(jié)點(diǎn)就代表一個(gè)盤(pán)塊，而子樹(shù)指針就是存放另外一個(gè)盤(pán)塊的地址。

• 下面，咱們來(lái)模擬下查找文件29的過(guò)程：
  1.根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤(pán)塊1，將其中的信息導(dǎo)入內(nèi)存?！敬疟P(pán)IO操作 1次】
  2.此時(shí)內(nèi)存中有兩個(gè)文件名17、35和三個(gè)存儲(chǔ)其他磁盤(pán)頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：17<29<35，因此我們找到指針p2。
  3.根據(jù)p2指針，我們定位到磁盤(pán)塊3，并將其中的信息導(dǎo)入內(nèi)存?！敬疟P(pán)IO操作 2次】
  4.此時(shí)內(nèi)存中有兩個(gè)文件名26，30和三個(gè)存儲(chǔ)其他磁盤(pán)頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：26<29<30，因此我們找到指針p2。
  5.根據(jù)p2指針，我們定位到磁盤(pán)塊8，并將其中的信息導(dǎo)入內(nèi)存?！敬疟P(pán)IO操作 3次】
  6.此時(shí)內(nèi)存中有兩個(gè)文件名28，29。根據(jù)算法我們查找到文件名29，并定位了該文件內(nèi)存的磁盤(pán)地址。
  分析上面的過(guò)程，發(fā)現(xiàn)需要3次磁盤(pán)IO操作和3次內(nèi)存查找操作。關(guān)于內(nèi)存中的文件名查找，由于是一個(gè)有序表結(jié)構(gòu)，可以利用折半查找提高效率。至于IO操作是影響整個(gè)B樹(shù)查找效率的決定因素。

當(dāng)然，如果我們使用平衡二叉樹(shù)的磁盤(pán)存儲(chǔ)結(jié)構(gòu)來(lái)進(jìn)行查找，磁盤(pán)4次，最多5次，而且文件越多，B樹(shù)比平衡二叉樹(shù)所用的磁盤(pán)IO操作次數(shù)將越少，效率也越高。

B+tree

Paste_Image.png

• B+tree的優(yōu)點(diǎn)：

1. B+-tree的磁盤(pán)讀寫(xiě)代價(jià)更低
   ****B+-tree****的內(nèi)部結(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹(shù)更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來(lái)說(shuō)IO讀寫(xiě)次數(shù)也就降低了。
   舉個(gè)例子，假設(shè)磁盤(pán)中的一個(gè)盤(pán)塊容納16bytes，而一個(gè)關(guān)鍵字2bytes，一個(gè)關(guān)鍵字具體信息指針2bytes。一棵9階B-tree(一個(gè)結(jié)點(diǎn)最多8個(gè)關(guān)鍵字)的內(nèi)部結(jié)點(diǎn)需要2個(gè)盤(pán)快。而****B+
   ****樹(shù)內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤(pán)快。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候，B 樹(shù)就比****B+ ****樹(shù)多一次盤(pán)塊查找時(shí)間(在磁盤(pán)中就是盤(pán)片旋轉(zhuǎn)的時(shí)間)。
2. B+-tree的查詢(xún)效率更加穩(wěn)定
   由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢(xún)的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢(xún)效率相當(dāng)。

mysql的兩種存儲(chǔ)引擎的索引存儲(chǔ)機(jī)制

MyISAM索引實(shí)現(xiàn)

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM索引的原理圖：

Paste_Image.png

這里設(shè)表一共有三列，假設(shè)我們以Col1為主鍵，則上圖是一個(gè)MyISAM表的主索引（Primary key）示意?？梢钥闯鯩yISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。在MyISAM中，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒(méi)有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)。如果我們?cè)贑ol2上建立一個(gè)輔助索引，則此索引的結(jié)構(gòu)如下圖所示：

Paste_Image.png

InnoDB索引實(shí)現(xiàn)

雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同。

第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹(shù)的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

Paste_Image.png

上圖是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒(méi)有），如果沒(méi)有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類(lèi)型為長(zhǎng)整形。

第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。換句話(huà)說(shuō)，InnoDB的所有輔助索引都引用主鍵作為data域。例如，定義在Col3上的一個(gè)輔助索引：

Paste_Image.png

這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。

了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助，例如知道了InnoDB的索引實(shí)現(xiàn)后，就很容易明白為什么不建議使用過(guò)長(zhǎng)的字段作為主鍵，因?yàn)樗休o助索引都引用主索引，過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大。再例如，用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵則是一個(gè)很好的選擇。

ps引用：
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
http://blog.csdn.net/zhangliangzi/article/details/51367639
http://www.cnblogs.com/vincently/p/4526560.html