2018-10-08

數(shù)據(jù)庫(kù)索引

索引的優(yōu)點(diǎn)：

通過創(chuàng)建唯一索引，可以保證數(shù)據(jù)庫(kù)表中每行數(shù)據(jù)的唯一性
可以加快查詢速度
在實(shí)現(xiàn)數(shù)據(jù)的參考完整性方面，可以加速表和表之間的連接
在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，同樣可以顯著減少查詢中分組和排序的時(shí)間
通過使用索引，可以在查詢中使用優(yōu)化隱藏器，提高系統(tǒng)的性能

索引缺點(diǎn)：

創(chuàng)建和維護(hù)索引要耗費(fèi)時(shí)間，并其隨著數(shù)據(jù)量的增加耗費(fèi)時(shí)間也增加
索引占用空間內(nèi)存
在對(duì)表中數(shù)據(jù)進(jìn)行增加刪除和修改的時(shí)候，索引也需要?jiǎng)討B(tài)維護(hù)，降低了數(shù)據(jù)維護(hù)速度

索引分類：
普通索引
唯一索引
復(fù)合索引：多個(gè)列上建立索引，叫做復(fù)合索引(組合索引)
聚集索引：表中行的物理順序與邏輯順序相同，一個(gè)表只能包含一個(gè)聚集索引
非聚集索引

索引失效：

WHERE字句的查詢條件里有不等于號(hào)，mysql將無法索引
WHERE字句的查詢條件里使用了函數(shù)
在JOIN操作中，mysql只有在主鍵和外鍵的數(shù)據(jù)類型相同時(shí)才能使用索引
如果WHERE子句的查詢條件里使用了比較操作符LIKE和REGEXP，mysql只有在搜索模板的第一個(gè)字符不是通配符的情況下才能使用索引
在ORDER BY操作中，MYSQL只有在排序條件不是一個(gè)查詢條件表達(dá)式的情況下才使用索引。盡管如此，在涉及多個(gè)數(shù)據(jù)表的查詢里，即使有索引可用，那些索引在加快ORDER BY操作方面也沒什么作用。
如果某個(gè)數(shù)據(jù)列里包含著許多重復(fù)的值，就算為它建立了索引也不會(huì)有很好的效果。比如說，如果某個(gè)數(shù)據(jù)列里包含了凈是些諸如“0/1”或“Y/N”等值，就沒有必要為它創(chuàng)建一個(gè)索引。
如果條件中有or(并且其中有or的條件是不帶索引的)，即使其中有條件帶索引也不會(huì)使用(這也是為什么盡量少用or的原因)。注意：要想使用or，又想讓索引生效，只能將or條件中的每個(gè)列都加上索引。
如果列類型是字符串，那一定要在條件中將數(shù)據(jù)使用引號(hào)引用起來,否則不使用索引。
如果mysql估計(jì)使用全表掃描要比使用索引快,則不使用索引。

什么情況下適合建立索引：
經(jīng)常用作查詢的字段
在經(jīng)常用作表連接的屬性上，加快連接速度
在經(jīng)常使用where子句中的列上創(chuàng)建索引，加快條件的判斷速度
在經(jīng)常需要排序的列上創(chuàng)建索引
在經(jīng)常需要根據(jù)范圍進(jìn)行搜索的列上創(chuàng)建索引
考慮使用索引覆蓋，對(duì)數(shù)據(jù)很少被更新的表，如果用戶經(jīng)常只查詢其中的幾個(gè)字段，可以考慮在這幾個(gè)字段上建立索引

索引的實(shí)現(xiàn)：
InnoDB：B+Tree
數(shù)據(jù)文件本身就是索引文件
聚集索引：表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄
必須有主鍵，如果沒有顯式指定，系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以作為唯一標(biāo)識(shí)數(shù)據(jù)
所有的輔助索引都引用主鍵作為data域

MyISAM：B+Tree
葉子節(jié)點(diǎn)的data域存放的數(shù)據(jù)記錄的地址
索引算法為按照B+Tree搜索算法搜索索引，如果指定的key存在，則取出data域的值，然后以data域的值為地址，讀取相應(yīng)的數(shù)據(jù)記錄
主索引和輔助索引的存儲(chǔ)結(jié)構(gòu)沒有任何區(qū)別
索引文件和數(shù)據(jù)文件是分開的，索引文件僅保存數(shù)據(jù)記錄的地址

memory：適用于快速訪問數(shù)據(jù)的場(chǎng)景。內(nèi)部基于哈希表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，只包含哈希值和行指針。為了解決多個(gè)hash沖突問題，采用了鏈地址法來解決沖突問題

B樹和B+樹：
B樹：
B樹中每個(gè)結(jié)點(diǎn)包含了鍵值和鍵值對(duì)于數(shù)據(jù)對(duì)象存放地址的指針，所以成功搜索一個(gè)對(duì)象可以不用到達(dá)樹的葉節(jié)點(diǎn)
在B樹中查找給定關(guān)鍵字的方法：首先把根節(jié)點(diǎn)取出，在根節(jié)點(diǎn)所包含的關(guān)鍵字k1....kj查找給定的關(guān)鍵字，若找到則查找成功，若未找到，則確定要查找的關(guān)鍵字在某個(gè)k1或ki+1之間，于是取pi所指的下一層索引結(jié)點(diǎn)繼續(xù)查找，直到找到或者直到為空

B+樹：
非葉節(jié)點(diǎn)中存放的關(guān)鍵碼并不指示數(shù)據(jù)對(duì)象的地址指針，非葉節(jié)點(diǎn)指示索引部分，所有葉節(jié)點(diǎn)在同一層上，包含全部關(guān)鍵碼和相應(yīng)數(shù)據(jù)對(duì)象的存放地址指針，且葉節(jié)點(diǎn)按關(guān)鍵碼從小到大順序連接
有兩個(gè)指針，一個(gè)是樹的根節(jié)點(diǎn)，一個(gè)是最小關(guān)鍵碼的葉節(jié)點(diǎn)
有兩種搜索方式：
按葉節(jié)點(diǎn)進(jìn)行鏈表的順序搜索
從根節(jié)點(diǎn)開始搜索，和B樹類似，無論搜索成功與否，都將走完樹的所有層
數(shù)據(jù)對(duì)象的插入和刪除僅僅在葉節(jié)點(diǎn)上進(jìn)行

區(qū)別：
B樹中同一鍵值不會(huì)出現(xiàn)多次，并且它有可能出現(xiàn)在葉結(jié)點(diǎn)，也有可能出現(xiàn)在非葉結(jié)點(diǎn)中。而B+樹的鍵一定會(huì)出現(xiàn)在葉節(jié)點(diǎn)中，并且有可能在非葉節(jié)點(diǎn)中也有可能重復(fù)出現(xiàn)，以維持B+樹的平衡
因?yàn)锽樹鍵位置不定，且在整個(gè)樹結(jié)構(gòu)中只出現(xiàn)一次，雖然可以節(jié)省存儲(chǔ)空間，但使得在插入、刪除操作復(fù)雜度明顯增加。B+樹相比來說是一種較好的折中
B樹的查詢效率與鍵在數(shù)中的位置有關(guān)，最大時(shí)間復(fù)雜度與B+樹相同(在葉節(jié)點(diǎn)的時(shí)候)，最小時(shí)間復(fù)雜度為1(在根節(jié)點(diǎn)的時(shí)候)。而B+樹的時(shí)間復(fù)雜度對(duì)某建成的樹是固定的