索引(收集自互聯(lián)網(wǎng))

1.索引是什么

? ?索引，類似于書籍的目錄，想找到一本書的某個特定的主題，需要先找到書的目錄，定位對應(yīng)的頁碼。MySQL 中存儲引擎使用類似的方式進行查詢，先去索引中查找對應(yīng)的值，然后根據(jù)匹配的索引找到對應(yīng)的數(shù)據(jù)行。

索引有什么好處？

提高數(shù)據(jù)的檢索速度，降低數(shù)據(jù)庫IO成本：使用索引的意義就是通過縮小表中需要查詢的記錄的數(shù)目從而加快搜索的速度。

降低數(shù)據(jù)排序的成本，降低CPU消耗：索引之所以查的快，是因為先將數(shù)據(jù)排好序，若該字段正好需要排序，則正好降低了排序的成本。

索引有什么壞處？

占用存儲空間：索引實際上也是一張表，記錄了主鍵與索引字段，一般以索引文件的形式存儲在磁盤上。

降低更新表的速度：表的數(shù)據(jù)發(fā)生了變化，對應(yīng)的索引也需要一起變更，從而減低的更新速度。否則索引指向的物理數(shù)據(jù)可能不對，這也是索引失效的原因之一。

?索引的使用場景？

1、對非常小的表，大部分情況下全表掃描效率更高。

2、對中大型表，索引非常有效。

3、特大型的表，建立和使用索引的代價隨著增長，可以使用分區(qū)技術(shù)來解決。

?索引的類型？

索引，都是實現(xiàn)在存儲引擎層的。主要有：

1、普通索引：最基本的索引，沒有任何約束。

2、唯一索引：與普通索引類似，但具有唯一性約束。

3、主鍵索引：特殊的唯一索引，不允許有空值。（innodb主鍵索引的葉子節(jié)點存的是整行數(shù)據(jù)，也叫聚簇索引）

4、復(fù)合索引：將多個列組合在一起創(chuàng)建索引，可以覆蓋多個列。

5、外鍵索引：只有InnoDB類型的表才可以使用外鍵索引，保證數(shù)據(jù)的一致性、完整性和實現(xiàn)級聯(lián)操作。

6、全文索引：MySQL 自帶的全文索引只能用于 InnoDB、MyISAM ，并且只能對英文進行全文檢索，一般使用全文索引引擎。

7、二級索引：非主鍵索引叫二級索引，或者輔助索引（innodb與myisam葉子節(jié)點存儲的東西不一致。注意區(qū)別）

其他定義：

覆蓋索引：在查詢里，索引已經(jīng)覆蓋了我們需要查詢的數(shù)據(jù)，這樣我們就不需要再回表了。叫做覆蓋索引。

索引下推：?在索引遍歷過程中，對索引中包含的字段先做判斷，直接過濾掉不滿足條件的記錄，減少回表次數(shù)。

2.索引原理-b樹與b+樹的區(qū)別

一，b樹

b樹（balance tree）和b+樹應(yīng)用在數(shù)據(jù)庫索引，可以認(rèn)為是m叉的多路平衡查找樹，但是從理論上講，二叉樹查找速度和比較次數(shù)都是最小的，為什么不用二叉樹呢？

因為我們要考慮磁盤IO的影響，它相對于內(nèi)存來說是很慢的。數(shù)據(jù)庫索引是存儲在磁盤上的，當(dāng)數(shù)據(jù)量大時，就不能把整個索引全部加載到內(nèi)存了，只能逐一加載每一個磁盤頁（對應(yīng)索引樹的節(jié)點）。所以我們要減少IO次數(shù)，對于樹來說，IO次數(shù)就是樹的高度，而“矮胖”就是b樹的特征之一，它的每個節(jié)點最多包含m個孩子，m稱為b樹的階，m的大小取決于磁盤頁的大小。

一個M階的b樹具有如下幾個特征：

1.每個結(jié)點最多有m-1個關(guān)鍵字。

2.根結(jié)點最少可以只有1個關(guān)鍵字。

3.非根結(jié)點至少有Math.ceil(m/2)-1個關(guān)鍵字。

4.每個結(jié)點中的關(guān)鍵字都按照從小到大的順序排列，每個關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它。

5.所有葉子結(jié)點都位于同一層，或者說根結(jié)點到每個葉子結(jié)點的長度都相同。

有關(guān)b樹的一些特性，注意與后面的b+樹區(qū)分：

1.關(guān)鍵字集合分布在整顆樹中；

2.任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；

3.搜索有可能在非葉子結(jié)點結(jié)束；

4.其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找；

b樹的查詢：

如圖是一個3階b樹，順便講一下查詢元素5的過程：

1，第一次磁盤IO，把9所在節(jié)點讀到內(nèi)存，把目標(biāo)數(shù)5和9比較，小，找小于9對應(yīng)的節(jié)點；

2，第二次磁盤IO，還是讀節(jié)點到內(nèi)存，在內(nèi)存中把5依次和2、6比較，定位到2、6中間區(qū)域?qū)?yīng)的節(jié)點；

3，第三次磁盤IO就不上圖了，跟第二步一樣，然后就找到了目標(biāo)5。

可以看到，b樹在查詢時的比較次數(shù)并不比二叉樹少，尤其是節(jié)點中的數(shù)非常多時，但是內(nèi)存的比較速度非?？欤臅r可以忽略，所以只要樹的高度低，IO少，就可以提高查詢性能，這是b樹的優(yōu)勢之一。

b樹的插入元素操作：

? 插入操作是指插入一條記錄，即（key, value）的鍵值對。如果B樹中已存在需要插入的鍵值對，則用需要插入的value替換舊的value。若B樹不存在這個key,則一定是在葉子結(jié)點中進行插入操作。

1，根據(jù)要插入的key的值，找到葉子結(jié)點并插入。

2，判斷當(dāng)前結(jié)點key的個數(shù)是否小于等于m-1，若滿足則結(jié)束，否則進行第3步。

3，以結(jié)點中間的key為中心分裂成左右兩部分，然后將這個中間的key插入到父結(jié)點中，這個key的左子樹指向分裂后的左半部分，這個key的右子支指向分裂后的右半部分，然后將當(dāng)前結(jié)點指向父結(jié)點，繼續(xù)進行第3步。

b樹的刪除元素操作：

? 刪除操作是指，根據(jù)key刪除記錄，如果B樹中的記錄中不存對應(yīng)key的記錄，則刪除失敗。?

1）如果當(dāng)前需要刪除的key位于非葉子結(jié)點上，則用后繼key（這里的后繼key均指后繼記錄的意思）覆蓋要刪除的key，然后在后繼key所在的子支中刪除該后繼key。此時后繼key一定位于葉子結(jié)點上，這個過程和二叉搜索樹刪除結(jié)點的方式類似。刪除這個記錄后執(zhí)行第2步

2）該結(jié)點key個數(shù)大于等于Math.ceil(m/2)-1，結(jié)束刪除操作，否則執(zhí)行第3步。

3）如果兄弟結(jié)點key個數(shù)大于Math.ceil(m/2)-1，則父結(jié)點中的key下移到該結(jié)點，兄弟結(jié)點中的一個key上移，刪除操作結(jié)束。

否則，將父結(jié)點中的key下移與當(dāng)前結(jié)點及它的兄弟結(jié)點中的key合并，形成一個新的結(jié)點。原父結(jié)點中的key的兩個孩子指針就變成了一個孩子指針，指向這個新結(jié)點。然后當(dāng)前結(jié)點的指針指向父結(jié)點，重復(fù)上第2步。

有些結(jié)點它可能即有左兄弟，又有右兄弟，那么我們?nèi)我膺x擇一個兄弟結(jié)點進行操作即可。

參考：https://www.cnblogs.com/nullzx/p/8729425.html

二，b+樹

?b+樹，是b樹的一種變體，查詢性能更好。m階的b+樹的特征：

1.有k個子樹的中間節(jié)點包含有k個元素（B樹中是k-1個元素），每個元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點。

2.所有的葉子結(jié)點中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。

3.所有的中間節(jié)點元素都同時存在于子節(jié)點，在子節(jié)點元素中是最大（或最?。┰亍?/p>

b+樹相比于b樹的查詢優(yōu)勢：

1.b+樹的中間節(jié)點不保存數(shù)據(jù)，所以磁盤頁能容納更多節(jié)點元素，更“矮胖”；

2.b+樹查詢必須查找到葉子節(jié)點，b樹只要匹配到即可不用管元素位置，因此b+樹查找更穩(wěn)定（并不慢）；

3.對于范圍查找來說，b+樹只需遍歷葉子節(jié)點鏈表即可，b樹卻需要重復(fù)地中序遍歷;

參考：http://www.itdecent.cn/p/1f2560f0e87f

3.myisam與innodb索引的區(qū)別

一，MyISAM索引的實現(xiàn)

? MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存記錄所在頁的指針（物理位置），通過這些地址來讀取頁，進而讀取被索引的行。下圖是MyISAM的索引原理圖：（為了簡化，一個頁內(nèi)只存放了兩條記錄。）

??????上圖所提供的示例表字段有Col1（ID）、Col2(age)、Col3（name）三個，其中Col1為Primary Key（主鍵），上圖很好地說明了樹中葉子保存的是對應(yīng)行的物理位置。通過該值，存儲引擎能順利地進行回表查詢，得到一行完整記錄。同時，每個葉子頁也保存了指向下一個葉子頁的指針。從而方便葉子節(jié)點的范圍遍歷。

??????而對于二級索引，在 MyISAM存儲引擎中以與上圖同樣的方式實現(xiàn)，可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。

二，InnoDB索引的實現(xiàn)

1.聚集索引

? ?與 MyISAM相同的一點是，InnoDB 也采用 B+Tree這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn) B-Tree索引。而很大的區(qū)別在于，InnoDB 存儲引擎采用“聚集索引”的數(shù)據(jù)存儲方式實現(xiàn)B-Tree索引，所謂“聚集”，就是指數(shù)據(jù)行和相鄰的鍵值緊湊地存儲在一起，注意 InnoDB 只能聚集一個葉子頁（16K）的記錄（即聚集索引滿足一定的范圍的記錄），因此包含相鄰鍵值的記錄可能會相距甚遠(yuǎn)。

注意: innodb來說,

1: 主鍵索引 既存儲索引值,又在葉子中存儲行的數(shù)據(jù)

2: 如果沒有主鍵, 則會Unique key做主鍵

3: 如果沒有unique,則系統(tǒng)生成一個內(nèi)部的rowid做主鍵.

4: 像innodb中,主鍵的索引結(jié)構(gòu)中,既存儲了主鍵值,又存儲了行數(shù)據(jù),這種結(jié)構(gòu)稱為”聚簇索引”

??????下圖說明了 InnoDB聚集索引的實現(xiàn)方式，同時也體現(xiàn)了一張 innoDB表的結(jié)構(gòu)，可以看到，InnoDB 中，主鍵索引和數(shù)據(jù)是一體的，沒有分開。

? 這種實現(xiàn)方式，給予了 InnoDB 按主鍵檢索的超高性能?？梢杂心康男缘剡x擇聚集索引，比如一個郵件表，可以選擇用戶ID來聚集數(shù)據(jù)，這樣只需要從磁盤讀取較少并且連續(xù)的數(shù)據(jù)頁就能獲得某個id的用戶全部的郵件，避免了讀取分散頁時所耗費的隨機I/O

2.二級索引

? ??而對于二級索引，InnoDB采用的方式是在葉子頁中保存主鍵值，通過這個主鍵值來回表（上圖）查詢到一條完整記錄，因此按輔助索引檢索實際上進行了二次查詢，效率肯定是沒有按照主鍵檢索高的。下圖是輔助索引的實現(xiàn)方式：

? ? 由于每個二級索引都包含主鍵索引，因此，為了減小二級索引所占空間，我們通常希望 InnoDB 表中的主鍵索引盡量定義得小一些（值得一提的是，MySIAM會使用前綴壓縮技術(shù)使得索引變小，而InnoDB按照原數(shù)據(jù)格式進行存儲。），并且希望InnoDB的主鍵是自增長的，因為如果主鍵并非自增長，插入時，由于寫入時亂序的，會使得插入效率變低。

4.innodb主鍵索引和普通索引的區(qū)別

如果語句是select * from T where ID=500，即主鍵查詢方式，則只需要搜索ID這棵B+樹；

如果語句是select * from T where k=5，即普通索引查詢方式，則需要先搜索k索引樹，得到ID的值為500，再到ID索引樹搜索一次。這個過程稱為回表。

也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應(yīng)用中應(yīng)該盡量使用主鍵查詢。

5.普通索引和唯一索引的區(qū)別

從查詢上來說：

?對于普通索引來說，查找到滿足條件的第一個記錄后，需要查找下一個記錄，直到碰到第一個不滿足條件的記錄。

?對于唯一索引來說，由于索引定義了唯一性，查找到第一個滿足條件的記錄后，就會停止繼續(xù)檢索。

從更新上來說

1.如果目標(biāo)頁在內(nèi)存中：

?對于唯一索引來說，找到3和5之間的位置，判斷有沒有沖突，插入這個值，語句執(zhí)行結(jié)束；

?對于普通索引來說，找到3和5之間的位置，插入這個值，語句執(zhí)行結(jié)束。

2.如果目標(biāo)頁在不在內(nèi)存中：

?對于唯一索引來說，需要將數(shù)據(jù)頁讀入內(nèi)存，判斷到?jīng)]有沖突，插入這個值，語句執(zhí)行結(jié)束；

?對于普通索引來說，則是將更新記錄在change buffer，語句執(zhí)行就結(jié)束了。

從這里可以看到，查詢上普通索引只是比唯一索引多了一個一次指針尋找和一次計算，由于數(shù)據(jù)是按頁讀取的，數(shù)據(jù)幾乎都在內(nèi)存中，所以性能相差不大。但從更新上來看，如果數(shù)據(jù)不在內(nèi)存中，唯一索引需要將數(shù)據(jù)從磁盤上讀取到內(nèi)存中，這樣會引發(fā)隨機讀，導(dǎo)致IO消耗增多，而普通索引可以利用changebuffer，IO上邊要節(jié)省很多。性能相差會很多，所以如果可以在業(yè)務(wù)端保證數(shù)據(jù)的唯一性，那就可以使用普通索引。

唯一索引為什么不能使用changebuffer？

對于唯一索引來說，所有的更新操作都要先判斷這個操作是否違反唯一性約束。比如，要插入(4,400)這個記錄，就要先判斷現(xiàn)在表中是否已經(jīng)存在k=4的記錄，而這必須要將數(shù)據(jù)頁讀入內(nèi)存才能判斷。如果都已經(jīng)讀入到內(nèi)存了，那直接更新內(nèi)存會更快，就沒必要使用change buffer了。

6.?MySQL 索引的“創(chuàng)建”原則？

1、最適合索引的列是出現(xiàn)在?WHERE?子句中的列，或連接子句中的列，而不是出現(xiàn)在?SELECT?關(guān)鍵字后的列。

2、索引列的基數(shù)越大，索引效果越好。https://blog.csdn.net/mingyundezuoan/article/details/79038989

3、根據(jù)情況創(chuàng)建復(fù)合索引，復(fù)合索引可以提高查詢效率。因為復(fù)合索引的基數(shù)會更大。

4、避免創(chuàng)建過多的索引，索引會額外占用磁盤空間，降低寫操作效率。

5、主鍵盡可能選擇較短的數(shù)據(jù)類型，可以有效減少索引的磁盤占用提高查詢效率。

6、對字符串進行索引，應(yīng)該定制一個前綴長度，可以節(jié)省大量的索引空間。

7.索引的使用事項

1、應(yīng)盡量避免在?WHERE?子句中使用?!=?或?<>?操作符，否則將引擎放棄使用索引而進行全表掃描。優(yōu)化器將無法通過索引來確定將要命中的行數(shù),因此需要搜索該表的所有行。

注意，column IS NULL?也是不可以使用索引的。

2、應(yīng)盡量避免在?WHERE?子句中使用?OR?來連接條件，否則將導(dǎo)致引擎放棄使用索引而進行全表掃描，如：SELECT id FROM t WHERE num = 10 OR num = 20?。

3、應(yīng)盡量避免在?WHERE?子句中對字段進行表達式操作，這將導(dǎo)致引擎放棄使用索引而進行全表掃描。

4、應(yīng)盡量避免在?WHERE?子句中對字段進行函數(shù)操作，這將導(dǎo)致引擎放棄使用索引而進行全表掃描。

5、不要在?WHERE?子句中的?=?左邊進行函數(shù)、算術(shù)運算或其他表達式運算，否則系統(tǒng)將可能無法正確使用索引。

6、復(fù)合索引遵循前綴原則。

7、如果 MySQL 評估使用索引比全表掃描更慢，會放棄使用索引。如果此時想要索引，可以在語句中添加強制索引。

8、列類型是字符串類型，查詢時一定要給值加引號，否則索引失效。

9、LIKE?查詢，%?不能在前，因為無法使用索引。如果需要模糊匹配，可以使用全文索引。