mysql索引初識(shí)

文章是學(xué)習(xí)了林曉斌老師在極客時(shí)間的《mysql實(shí)戰(zhàn)45講》后，根據(jù)自己的理解整理而成的。

什么是索引？

當(dāng)我們使用漢語(yǔ)字典查找某個(gè)字時(shí)，我們會(huì)先通過(guò)拼音目錄查到那個(gè)字所在的頁(yè)碼，然后直接翻到字典的那一頁(yè)，找到我們要查的字，通過(guò)拼音目錄查找比我們拿起字典從頭一頁(yè)一頁(yè)翻找要快的多，數(shù)據(jù)庫(kù)索引也一樣，索引就像書的目錄，通過(guò)索引能極大提高數(shù)據(jù)查詢的效率。

索引的實(shí)現(xiàn)方式

在數(shù)據(jù)庫(kù)中，常見的索引實(shí)現(xiàn)方式有哈希表、有序數(shù)組、搜索樹

• 哈希表
  哈希表是通過(guò)鍵值對(duì)（key-value）存儲(chǔ)數(shù)據(jù)的索引實(shí)現(xiàn)方式，可以將哈希表想象成是一個(gè)數(shù)組，將索引通過(guò)哈希函數(shù)計(jì)算得到該行數(shù)據(jù)在數(shù)組中的位置，然后將數(shù)據(jù)存到數(shù)組中，容易發(fā)現(xiàn)一個(gè)問(wèn)題，如果兩個(gè)索引通過(guò)哈希函數(shù)計(jì)算后得到的數(shù)組位置相同要怎么辦？在這里，數(shù)組的每個(gè)value都是一個(gè)鏈表，鏈表上的每個(gè)元素都是一個(gè)數(shù)據(jù)，新數(shù)據(jù)直接添加到鏈表尾部。
  
  所以數(shù)據(jù)庫(kù)查詢過(guò)程為：索引通過(guò)哈希函數(shù)計(jì)算數(shù)據(jù)所在位置--> 遍歷指定位置的鏈表，找到滿足條件的數(shù)據(jù)。
  要注意的是，鏈表上的數(shù)據(jù)元素不是有序的，每次有新數(shù)據(jù)加入時(shí)，新數(shù)據(jù)時(shí)直接添加到鏈表尾部，這樣做的好處是添加數(shù)據(jù)時(shí)很方便。
  ???????哈希表不擅長(zhǎng)進(jìn)行區(qū)間查詢，一般都用于等值查詢
  ??????????1、兩個(gè)相鄰索引通過(guò)hash函數(shù)后計(jì)算得到的數(shù)組位置不一定還保持相鄰
  ??????????2、鏈表上的數(shù)據(jù)是無(wú)序的
• 有序數(shù)組
  顧名思義，有序數(shù)組是按索引大小將數(shù)據(jù)保存在一個(gè)數(shù)組上，因?yàn)樵摂?shù)組是有序的，可以通過(guò)二分法很容易查到位置，找到第一個(gè)位置后，通過(guò)向左/向右遍歷很容易得到所求區(qū)間的數(shù)據(jù)。因此，無(wú)論是等值查詢還是區(qū)間查詢，效率都極高。
  但缺陷也是顯而易見的，當(dāng)向數(shù)組中間n位置插入一條數(shù)據(jù)時(shí)，需將n后面的數(shù)據(jù)全部往后移動(dòng)，所以，這種索引一般用于靜態(tài)存儲(chǔ)引擎。
• 搜索樹

  二叉搜索樹：一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 二叉搜索樹的左、右子樹也分別為二叉搜索樹。
  平衡二叉樹：平衡二叉樹是在二叉搜索樹的基礎(chǔ)上引入的，指的是結(jié)點(diǎn)的左子樹和右子樹的深度差不超過(guò)1.
  多叉樹：每個(gè)結(jié)點(diǎn)可以有多個(gè)子結(jié)點(diǎn)，子節(jié)點(diǎn)的大小從左到右依次遞增。

當(dāng)使用平衡二叉實(shí)現(xiàn)索引時(shí)，結(jié)構(gòu)如下圖

從圖中可發(fā)現(xiàn)，每次查詢最多需要訪問(wèn)4個(gè)節(jié)點(diǎn)必能得到所要數(shù)據(jù)。例如查詢user2時(shí)，查詢過(guò)程為：userA-->userC-->userF-->user2。
所以查詢速度很高，同時(shí)，因?yàn)樗阉鳂涞奶匦裕ㄗ笞訕湫∮谟易訕洌?，區(qū)間查詢也很方便。
<br>
如果搜索樹存于內(nèi)存中，與多叉樹相比，二叉樹的搜索速率是最高的，但實(shí)際上數(shù)據(jù)庫(kù)使用的是n叉樹而不是二叉樹。

1、索引不僅存于內(nèi)存，還是寫到磁盤上
2、搜索樹上的每個(gè)結(jié)點(diǎn)在磁盤上表現(xiàn)為一個(gè)數(shù)據(jù)塊
3、多叉樹每個(gè)結(jié)點(diǎn)下可以有多個(gè)子節(jié)點(diǎn)，所以存儲(chǔ)相同數(shù)據(jù)量時(shí)多叉樹的樹高比二叉樹小，查詢一個(gè)數(shù)據(jù)需要訪問(wèn)的結(jié)點(diǎn)數(shù)更少，即查詢過(guò)程訪問(wèn)更少的數(shù)據(jù)塊。查詢速度較高。

innodb的索引模型

innodb使用B+樹作為索引結(jié)構(gòu)。
在B+樹中，我們將節(jié)點(diǎn)分為葉子結(jié)點(diǎn)和非葉子結(jié)點(diǎn)，非葉子結(jié)點(diǎn)上保存的是索引，而且一個(gè)節(jié)點(diǎn)可以保存多個(gè)索引；數(shù)據(jù)全部存于葉子結(jié)點(diǎn)上,根據(jù)葉子結(jié)點(diǎn)的內(nèi)容不同，innodb索引分為主鍵索引和非主鍵索引。非主鍵索引也稱為二級(jí)索引。
主鍵索引的葉子結(jié)點(diǎn)中保存的數(shù)據(jù)為整行數(shù)據(jù)，而非主鍵索引葉子節(jié)點(diǎn)保存的是主鍵的值。

主鍵索引圖

非主鍵索引圖
通過(guò)主鍵索引查詢數(shù)據(jù)時(shí)，我們只需查找主鍵索引樹便可以獲取數(shù)據(jù)；通過(guò)非主鍵索引查詢數(shù)據(jù)時(shí)，我們先通過(guò)非主鍵索引樹查找到主鍵值，然后再在主鍵索引樹搜索一次，這個(gè)過(guò)程稱為回表，也就是說(shuō)非主鍵索引查詢會(huì)比主鍵查詢多搜索一棵樹。所以我們應(yīng)盡可能使用主鍵查詢。

索引維護(hù)

添加新行時(shí)，將會(huì)在索引表上添加一條記錄，如果是索引遞增插入時(shí)，數(shù)據(jù)都是追加在當(dāng)前最大索引之后，不會(huì)對(duì)樹中其他數(shù)據(jù)造成影響；如果新加入的數(shù)據(jù)的索引值位于節(jié)點(diǎn)的中間，需要挪動(dòng)部分節(jié)點(diǎn)的位置，從而保持索引樹的有序性。
而且，相鄰多個(gè)節(jié)點(diǎn)是存儲(chǔ)在同一個(gè)數(shù)據(jù)頁(yè)上的，此時(shí)，如果是在已經(jīng)存儲(chǔ)滿狀態(tài)的數(shù)據(jù)頁(yè)中插入節(jié)點(diǎn)，會(huì)申請(qǐng)新的數(shù)據(jù)頁(yè)，將部分?jǐn)?shù)據(jù)挪動(dòng)到新的數(shù)據(jù)頁(yè)，這個(gè)過(guò)程稱為頁(yè)分裂，頁(yè)分裂除了會(huì)影響性能，還會(huì)降低磁盤空間利用率。不規(guī)則數(shù)據(jù)插入時(shí),會(huì)造成頻繁的頁(yè)分裂。

當(dāng)相鄰兩個(gè)頁(yè)由于刪除了數(shù)據(jù)，利用率很低之后，會(huì)將數(shù)據(jù)頁(yè)做合并

所以，一般情況下會(huì)采用遞增主鍵，使新數(shù)據(jù)遞增插入。

使用業(yè)務(wù)邏輯字段做主鍵有什么優(yōu)缺點(diǎn)？

1、業(yè)務(wù)邏輯字段不容易保證索引樹結(jié)點(diǎn)有序插入，這樣寫入成本較高。
2、innodb默認(rèn)使用整數(shù)類型作為主鍵，主鍵長(zhǎng)度較小，二級(jí)索引的葉子結(jié)點(diǎn)中保存的是主鍵值，主鍵長(zhǎng)度越小，二級(jí)索引的葉子結(jié)點(diǎn)占用空間也就越小。
3、當(dāng)然，使用業(yè)務(wù)邏輯字段做主鍵也有好處，可以避免回表，每次只需掃描一次主鍵索引樹即可
綜上，從性能和存儲(chǔ)空間方面考量，自增主鍵往往是更合理的選擇,當(dāng)業(yè)務(wù)場(chǎng)景有且只有一個(gè)索引，而且該索引為唯一索引時(shí)，此時(shí)更適合使用業(yè)務(wù)邏輯字段作為主鍵。

因?yàn)閿?shù)據(jù)修改/刪除、頁(yè)分裂等原因，會(huì)導(dǎo)致數(shù)據(jù)頁(yè)空間利用率降低，此時(shí)，可以考慮重建索引，將數(shù)據(jù)按順序插入，提高磁盤空間利用率。但重建主鍵索引和普通索引會(huì)有不同影響，重建普通索引，可以達(dá)到提高空間利用率的目的，且不會(huì)對(duì)其他索引造成影響，但如果重建主鍵索引就不合理了，會(huì)影響所有普通索引，性能影響較大，而且無(wú)論是新建/刪除主鍵，都會(huì)重建整張表。這時(shí)我們可以使用alter table T engine=InnoDB這個(gè)語(yǔ)句代替。

查看索引利用率

查看performance_schema.table_io_waits_summary_by_index_usage表