概述

本質(zhì)：數(shù)據(jù)庫(kù)維護(hù)某種數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)

索引取舍原則：索引的結(jié)構(gòu)組織要盡量減少查找過(guò)程中磁盤(pán)I/O的存取次數(shù)

B樹(shù)

滿足的條件

d為大于1的一個(gè)正整數(shù)，稱(chēng)為B-Tree的度

h為一個(gè)正整數(shù)，稱(chēng)為B-Tree的高度

每個(gè)非葉子節(jié)點(diǎn)由n-1個(gè)key和n個(gè)指針組成，其中d《=n《=2d

每個(gè)葉子節(jié)點(diǎn)最少包含一個(gè)key和兩個(gè)指針，最多包含2d-1個(gè)key和2d個(gè)指針，葉節(jié)點(diǎn)的指針均為null

所有葉節(jié)點(diǎn)具有相同的深度，等于樹(shù)高h(yuǎn)

key和指針互相間隔，節(jié)點(diǎn)兩端是指針

一個(gè)節(jié)點(diǎn)中的key從左到右非遞減排列

所有節(jié)點(diǎn)組成樹(shù)結(jié)構(gòu)

每個(gè)指針要么為null，要么指向另外一個(gè)節(jié)點(diǎn)

一個(gè)度為d的B-Tree，設(shè)其索引N個(gè)key，則其樹(shù)高h(yuǎn)的上限為logd（（N+1）/2），檢索一個(gè)key查找節(jié)點(diǎn)的個(gè)數(shù)的漸進(jìn)復(fù)雜度為logd（N）

更新后的操作

插入刪除新的數(shù)據(jù)記錄會(huì)破壞B-Tree的性質(zhì)，因此在插入刪除時(shí)，需要對(duì)樹(shù)進(jìn)行一個(gè)分裂、合并、轉(zhuǎn)移等操作以保持B-Tree性質(zhì)

B+樹(shù)

每個(gè)節(jié)點(diǎn)的指針上限為2d而不是2d+1

內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key

葉子節(jié)點(diǎn)不存儲(chǔ)指針

在經(jīng)典B+樹(shù)的基礎(chǔ)上，增加了順序訪問(wèn)指針--》提高區(qū)間訪問(wèn)的性能

為什么使用B/B+樹(shù)？

主存讀取

當(dāng)系統(tǒng)需要讀取主存時(shí)，則將地址信號(hào)放到地址總線上傳給主存

主存讀到地址信號(hào)后，解析信號(hào)并定位到指定存儲(chǔ)單元，然后將此存儲(chǔ)單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取

主存存取的時(shí)間僅與存取次數(shù)呈線性關(guān)系，因?yàn)椴淮嬖?a target="_blank">機(jī)械操作，兩次存取的數(shù)據(jù)的“距離”不會(huì)對(duì)時(shí)間有任何影響

磁盤(pán)存取原理

磁盤(pán)轉(zhuǎn)動(dòng)，每個(gè)磁頭不動(dòng)，負(fù)責(zé)讀取內(nèi)容

不過(guò)已經(jīng)有了多磁頭獨(dú)立技術(shù)

局部性原理

磁盤(pán)預(yù)讀：長(zhǎng)度一般以頁(yè)的整數(shù)倍為單位

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

使用B+樹(shù)作為索引結(jié)構(gòu)，data存放數(shù)據(jù)記錄的地址

索引文件與數(shù)據(jù)文件分離

主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒(méi)有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)

非聚集：MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄

.MYI文件的組成

整個(gè)索引文件的基本信息state

各索引的限制信息base

各索引的定義信息keydef

各索引記錄的概要信息recinfo

讀取索引的流程

query請(qǐng)求，直接讀取key cache中的cache block，有就返回

沒(méi)有就到.MYI文件中以file block方式讀取數(shù)據(jù)

再以相同的格式存取key cache

再將key cache中的數(shù)據(jù)返回

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

也是使用B+樹(shù)

第一個(gè)與MyISAM的不同點(diǎn)

第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)

InnoDB的數(shù)據(jù)文件本身要按主鍵聚集

所以InnoDB要求表必須有主鍵（MyISAM可以沒(méi)有）

沒(méi)有顯式指定，自動(dòng)選擇唯一標(biāo)識(shí)列

不存在的話，生成6個(gè)字節(jié)長(zhǎng)整型的隱含字段

第二個(gè)與MyISAM的不同點(diǎn)

InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址

換句話說(shuō)，InnoDB的所有輔助索引都引用主鍵作為data域

輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄

得出的優(yōu)化點(diǎn)

不建議使用過(guò)長(zhǎng)的字段作為主鍵，因?yàn)樗休o助索引都引用主索引，過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大

用非單調(diào)的字段作為主鍵在InnoDB中也不好，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵就很不錯(cuò)了

聚簇索引鍵被更新造成的成本除了索引數(shù)據(jù)可能會(huì)移動(dòng)，相關(guān)的所有記錄數(shù)據(jù)也要移動(dòng)

索引使用策略及優(yōu)化

全列匹配

按照索引中所有列進(jìn)行精確匹配（這里精確匹配指“=”或“IN”匹配）時(shí)，索引可以被用到

理論上索引對(duì)順序是敏感的，但是由于MySQL的查詢優(yōu)化器會(huì)自動(dòng)調(diào)整where子句的條件順序以使用適合的索引

最左前綴匹配

當(dāng)查詢條件精確匹配索引的左邊連續(xù)一個(gè)或幾個(gè)列時(shí)，索引可以被用到

查詢條件用到了索引中列的精確匹配，但是中間某個(gè)條件未提供

只能用到索引中，從中間斷開(kāi)前的列

應(yīng)對(duì)

可以增加輔助索引

當(dāng)中間條件選項(xiàng)較少時(shí)，用隔離列的方式，使用IN包含

看情況，比較建立

查詢條件沒(méi)有指定索引第一列

不滿足使用索引的條件

匹配某列的前綴字符串

可以使用索引

如果通配符%不出現(xiàn)在開(kāi)頭，則可以用到索引，但根據(jù)具體情況不同可能只會(huì)用其中一個(gè)前綴

范圍查詢

范圍列可以用到索引（必須是最左前綴），但是范圍列后面的列無(wú)法用到索引

同時(shí)，索引最多用于一個(gè)范圍列，因此如果查詢條件中有兩個(gè)范圍列則無(wú)法全用到索引

僅用explain可能無(wú)法區(qū)分范圍索引和多值匹配

查詢條件中含有函數(shù)/表達(dá)式

一般不使用哦

手工算好再代入

索引選擇性與前綴索引

MyISAM與InnoDB基數(shù)統(tǒng)計(jì)方式

MyisAM索引的基數(shù)值（Cardinality，show index 命令可以看見(jiàn)）是精確的，InnoDB則是估計(jì)值

MyisAM統(tǒng)計(jì)信息是保存磁盤(pán)中，在alter表或Analyze table操作更新此信息

而InnoDB則是在表第一次打開(kāi)的時(shí)候估計(jì)值保存在緩存區(qū)內(nèi)

不建議建立索引的情況

表記錄比較少

索引的選擇性低：不重復(fù)的索引值（也叫基數(shù)，Cardinality）與表記錄數(shù)（#T）的比值

前綴索引

用列的前綴代替整個(gè)列作為索引key，當(dāng)前綴長(zhǎng)度合適時(shí)，可以做到既使得前綴索引的選擇性接近全列索引，同時(shí)因?yàn)樗饕齥ey變短而減少了索引文件的大小和維護(hù)開(kāi)銷(xiāo)

缺點(diǎn)

不能用于ORDER BY和GROUP BY操作

也不能用于Covering index（即當(dāng)索引本身包含查詢所需全部數(shù)據(jù)時(shí)，不再訪問(wèn)數(shù)據(jù)文件本身）

InnoDB主鍵選擇與插入優(yōu)化

如果沒(méi)有特別的需要，請(qǐng)永遠(yuǎn)使用一個(gè)與業(yè)務(wù)無(wú)關(guān)的自增字段作為主鍵

InnoDB使用聚集索引，數(shù)據(jù)記錄本身被存于主索引（一顆B+Tree）的葉子節(jié)點(diǎn)上

這就要求同一個(gè)葉子節(jié)點(diǎn)內(nèi)（大小為一個(gè)內(nèi)存頁(yè)或磁盤(pán)頁(yè)）的各條數(shù)據(jù)記錄按主鍵順序存放，因此每當(dāng)有一條新的記錄插入時(shí)，MySQL會(huì)根據(jù)其主鍵將其插入適當(dāng)?shù)墓?jié)點(diǎn)和位置，如果頁(yè)面達(dá)到裝載因子（InnoDB默認(rèn)為15/16），則開(kāi)辟一個(gè)新的頁(yè)（節(jié)點(diǎn)）

如果使用非自增主鍵，每次插入近似隨機(jī)，容易引起數(shù)據(jù)的移動(dòng)，重新讀目標(biāo)頁(yè)面，碎片也多了，雖然也可以用OPTIMIZE TABLE重建優(yōu)化，但麻煩啊

參考資料

圖片來(lái)源網(wǎng)絡(luò)

《高性能MySQL》

作者：AnnsShadoW

https://www.cnblogs.com/annsshadow/p/5355090.html

編輯：jq