一 .索引的概念,？

一般的應(yīng)用系統(tǒng)，讀寫(xiě)比例在10:1左右,，而且插入操作和一般的更新操作很少出現(xiàn)性能問(wèn)題，在生產(chǎn)環(huán)境中,，我們遇到最多的,，也是最容易出問(wèn)題的，還是一些復(fù)雜的查詢操作,，因此對(duì)查詢語(yǔ)句的優(yōu)化顯然是重中之重,。說(shuō)起加速查詢，就不得不提到索引了,。

2.為什么要有索引呢,？

索引在MySQL中也叫做“鍵”，是存儲(chǔ)引擎用于快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu),。索引對(duì)于良好的性能
非常關(guān)鍵,，尤其是當(dāng)表中的數(shù)據(jù)量越來(lái)越大時(shí)，索引對(duì)于性能的影響愈發(fā)重要,。
索引優(yōu)化應(yīng)該是對(duì)查詢性能優(yōu)化最有效的手段了,。索引能夠輕易將查詢性能提高好幾個(gè)數(shù)量級(jí)。
索引相當(dāng)于字典的音序表,，如果要查某個(gè)字,，如果不使用音序表，則需要從幾百頁(yè)中逐頁(yè)去查,。

二,、索引的原理

索引的目的在于提高查詢效率，與我們查閱圖書(shū)所用的目錄是一個(gè)道理：先定位到章,，然后定位到該章下的一個(gè)小節(jié),，然后找到頁(yè)數(shù)。相似的例子還有：查字典,，查火車(chē)車(chē)次,，飛機(jī)航班等

本質(zhì)都是：通過(guò)不斷地縮小想要獲取數(shù)據(jù)的范圍來(lái)篩選出最終想要的結(jié)果，同時(shí)把隨機(jī)的事件變成順序的事件,，也就是說(shuō),，有了這種索引機(jī)制，我們可以總是用同一種查找方式來(lái)鎖定數(shù)據(jù),。

數(shù)據(jù)庫(kù)也是一樣,，但顯然要復(fù)雜的多，因?yàn)椴粌H面臨著等值查詢,，還有范圍查詢(>,、<,、between、in),、模糊查詢(like),、并集查詢(or)等等。數(shù)據(jù)庫(kù)應(yīng)該選擇怎么樣的方式來(lái)應(yīng)對(duì)所有的問(wèn)題呢,？我們回想字典的例子,，能不能把數(shù)據(jù)分成段，然后分段查詢呢,？最簡(jiǎn)單的如果1000條數(shù)據(jù),，1到100分成第一段，101到200分成第二段,，201到300分成第三段......這樣查第250條數(shù)據(jù),，只要找第三段就可以了，一下子去除了90%的無(wú)效數(shù)據(jù),。但如果是1千萬(wàn)的記錄呢,，分成幾段比較好？稍有算法基礎(chǔ)的同學(xué)會(huì)想到搜索樹(shù),，其平均復(fù)雜度是lgN,，具有不錯(cuò)的查詢性能。但這里我們忽略了一個(gè)關(guān)鍵的問(wèn)題,，復(fù)雜度模型是基于每次相同的操作成本來(lái)考慮的,。而數(shù)據(jù)庫(kù)實(shí)現(xiàn)比較復(fù)雜，一方面數(shù)據(jù)是保存在磁盤(pán)上的,，另外一方面為了提高性能,，每次又可以把部分?jǐn)?shù)據(jù)讀入內(nèi)存來(lái)計(jì)算，因?yàn)槲覀冎涝L問(wèn)磁盤(pán)的成本大概是訪問(wèn)內(nèi)存的十萬(wàn)倍左右,，所以簡(jiǎn)單的搜索樹(shù)難以滿足復(fù)雜的應(yīng)用場(chǎng)景,。

 二 磁盤(pán)IO與預(yù)讀

考慮到磁盤(pán)IO是非常高昂的操作，計(jì)算機(jī)操作系統(tǒng)做了一些優(yōu)化,，當(dāng)一次IO時(shí),，不光把當(dāng)前磁盤(pán)地址的數(shù)據(jù)，而是把相鄰的數(shù)據(jù)也都讀取到內(nèi)存緩沖區(qū)內(nèi),，因?yàn)榫植款A(yù)讀性原理告訴我們,，當(dāng)計(jì)算機(jī)訪問(wèn)一個(gè)地址的數(shù)據(jù)的時(shí)候，與其相鄰的數(shù)據(jù)也會(huì)很快被訪問(wèn)到,。每一次IO讀取的數(shù)據(jù)我們稱之為一頁(yè)(page),。具體一頁(yè)有多大數(shù)據(jù)跟操作系統(tǒng)有關(guān)，一般為4k或8k,，也就是我們讀取一頁(yè)內(nèi)的數(shù)據(jù)時(shí)候,，實(shí)際上才發(fā)生了一次IO,，這個(gè)理論對(duì)于索引的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)非常有幫助

索引的數(shù)據(jù)結(jié)構(gòu)

索引的目的在于提高查詢效率，與我們查閱圖書(shū)所用的目錄是一個(gè)道理：先定位到章,，然后定位到該章下的一個(gè)小節(jié),，然后找到頁(yè)數(shù)。相似的例子還有：查字典,，查火車(chē)車(chē)次,，飛機(jī)航班等

如上圖，是一顆b 樹(shù),，關(guān)于b 樹(shù)的定義可以參見(jiàn)B 樹(shù)，這里只說(shuō)一些重點(diǎn),，淺藍(lán)色的塊我們稱之為一個(gè)磁盤(pán)塊,，可以看到每個(gè)磁盤(pán)塊包含幾個(gè)數(shù)據(jù)項(xiàng)（深藍(lán)色所示）和指針（黃色所示），如磁盤(pán)塊1包含數(shù)據(jù)項(xiàng)17和35,，包含指針P1,、P2、P3,，P1表示小于17的磁盤(pán)塊,，P2表示在17和35之間的磁盤(pán)塊，P3表示大于35的磁盤(pán)塊,。真實(shí)的數(shù)據(jù)存在于葉子節(jié)點(diǎn)即3,、5、9,、10,、13、15,、28,、29、36,、60,、75、79,、90,、99。非葉子節(jié)點(diǎn)只不存儲(chǔ)真實(shí)的數(shù)據(jù),，只存儲(chǔ)指引搜索方向的數(shù)據(jù)項(xiàng),，如17、35并不真實(shí)存在于數(shù)據(jù)表中,。

###b 樹(shù)的查找過(guò)程
如圖所示,，如果要查找數(shù)據(jù)項(xiàng)29,，那么首先會(huì)把磁盤(pán)塊1由磁盤(pán)加載到內(nèi)存，此時(shí)發(fā)生一次IO,，在內(nèi)存中用二分查找確定29在17和35之間,，鎖定磁盤(pán)塊1的P2指針，內(nèi)存時(shí)間因?yàn)榉浅６蹋ㄏ啾却疟P(pán)的IO）可以忽略不計(jì),，通過(guò)磁盤(pán)塊1的P2指針的磁盤(pán)地址把磁盤(pán)塊3由磁盤(pán)加載到內(nèi)存,，發(fā)生第二次IO，29在26和30之間,，鎖定磁盤(pán)塊3的P2指針,，通過(guò)指針加載磁盤(pán)塊8到內(nèi)存，發(fā)生第三次IO,，同時(shí)內(nèi)存中做二分查找找到29,，結(jié)束查詢，總計(jì)三次IO,。真實(shí)的情況是,，3層的b 樹(shù)可以表示上百萬(wàn)的數(shù)據(jù)，如果上百萬(wàn)的數(shù)據(jù)查找只需要三次IO,，性能提高將是巨大的,，如果沒(méi)有索引，每個(gè)數(shù)據(jù)項(xiàng)都要發(fā)生一次IO,，那么總共需要百萬(wàn)次的IO,，顯然成本非常非常高。

###b 樹(shù)性質(zhì)
1.索引字段要盡量的小：通過(guò)上面的分析,，我們知道IO次數(shù)取決于b 數(shù)的高度h,，假設(shè)當(dāng)前數(shù)據(jù)表的數(shù)據(jù)為N，每個(gè)磁盤(pán)塊的數(shù)據(jù)項(xiàng)的數(shù)量是m,，則有h=㏒(m 1)N,，當(dāng)數(shù)據(jù)量N一定的情況下，m越大,，h越?。欢鴐 = 磁盤(pán)塊的大小 / 數(shù)據(jù)項(xiàng)的大小,，磁盤(pán)塊的大小也就是一個(gè)數(shù)據(jù)頁(yè)的大小,，是固定的，如果數(shù)據(jù)項(xiàng)占的空間越小,，數(shù)據(jù)項(xiàng)的數(shù)量越多,，樹(shù)的高度越低。這就是為什么每個(gè)數(shù)據(jù)項(xiàng),，即索引字段要盡量的小,，比如int占4字節(jié),，要比bigint8字節(jié)少一半。這也是為什么b 樹(shù)要求把真實(shí)的數(shù)據(jù)放到葉子節(jié)點(diǎn)而不是內(nèi)層節(jié)點(diǎn),，一旦放到內(nèi)層節(jié)點(diǎn),，磁盤(pán)塊的數(shù)據(jù)項(xiàng)會(huì)大幅度下降，導(dǎo)致樹(shù)增高,。當(dāng)數(shù)據(jù)項(xiàng)等于1時(shí)將會(huì)退化成線性表,。
2.索引的最左匹配特性（即從左往右匹配）：當(dāng)b 樹(shù)的數(shù)據(jù)項(xiàng)是復(fù)合的數(shù)據(jù)結(jié)構(gòu)，比如(name,age,sex)的時(shí)候,，b 數(shù)是按照從左到右的順序來(lái)建立搜索樹(shù)的,，比如當(dāng)(張三,20,F)這樣的數(shù)據(jù)來(lái)檢索的時(shí)候，b 樹(shù)會(huì)優(yōu)先比較name來(lái)確定下一步的所搜方向,，如果name相同再依次比較age和sex,，最后得到檢索的數(shù)據(jù)；但當(dāng)(20,F)這樣的沒(méi)有name的數(shù)據(jù)來(lái)的時(shí)候,，b 樹(shù)就不知道下一步該查哪個(gè)節(jié)點(diǎn)，因?yàn)榻⑺阉鳂?shù)的時(shí)候name就是第一個(gè)比較因子,，必須要先根據(jù)name來(lái)搜索才能知道下一步去哪里查詢,。比如當(dāng)(張三,F)這樣的數(shù)據(jù)來(lái)檢索時(shí)，b 樹(shù)可以用name來(lái)指定搜索方向,，但下一個(gè)字段age的缺失,，所以只能把名字等于張三的數(shù)據(jù)都找到，然后再匹配性別是F的數(shù)據(jù)了,， 這個(gè)是非常重要的性質(zhì),，即索引的最左匹配特性。