mysql中的索引
MySQL中普遍使用B+Tree做索引，但在實現(xiàn)上又根據(jù)聚簇索引和非聚簇索引而不同。
所謂聚簇索引，就是指主索引文件和數(shù)據(jù)文件為同一份文件，聚簇索引主要用在Innodb存儲引擎中。在該索引實現(xiàn)方式中B+Tree的葉子節(jié)點上的data就是數(shù)據(jù)本身，key為主鍵，如果是一般索引的話，data便會指向?qū)?yīng)的主索引，如下圖所示：
在B+Tree的每個葉子節(jié)點增加一個指向相鄰葉子節(jié)點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優(yōu)化的目的是為了提高區(qū)間訪問的性能，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點，極大提到了區(qū)間查詢效率。
非聚簇索引就是指B+Tree的葉子節(jié)點上的data，并不是數(shù)據(jù)本身，而是數(shù)據(jù)存放的地址。主索引和輔助索引沒啥區(qū)別，只是主索引中的key一定得是唯一的。主要用在MyISAM存儲引擎中，如下圖：
非聚簇索引比聚簇索引多了一次讀取數(shù)據(jù)的IO操作，所以查找性能上會差。
MyisAM支持全文索引（FULLTEXT）、壓縮索引，InnoDB不支持；
InnoDB支持事務(wù)，MyisAM不支持；
MyisAM順序儲存數(shù)據(jù)，索引葉子節(jié)點保存對應(yīng)數(shù)據(jù)行地址，輔助索引很主鍵索引相差無幾；InnoDB主鍵節(jié)點同時保存數(shù)據(jù)行，其他輔助索引保存的是主鍵索引的值；
MyisAM鍵值分離，索引載入內(nèi)存（key_buffer_size），數(shù)據(jù)緩存依賴操作系統(tǒng)；InnoDB鍵值一起保存，索引與數(shù)據(jù)一起載入InnoDB緩沖池；MyisAM主鍵（唯一）索引按升序來存儲存儲，InnoDB則不一定
MyisAM索引的基數(shù)值（Cardinality，show index命令可以看見）是精確的，InnoDB則是估計值。這里涉及到信息統(tǒng)計的知識，MyisAM統(tǒng)計信息是保存磁盤中，在alter表或Analyze table操作更新此信息，而InnoDB則是在表第一次打開的時候估計值保存在緩存區(qū)內(nèi)；
MyisAM處理字符串索引時用增量保存的方式，如第一個索引是‘preform’，第二個是‘preformence’，則第二個保存是‘7，ance’，這個明顯的好處是縮短索引，但是缺陷就是不支持倒序提取索引，必須順序遍歷獲取索引
一般來說，索引本身也很大，不可能全部存儲在內(nèi)存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對于內(nèi)存存取，I/O存取的消耗要高幾個數(shù)量級，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進復(fù)雜度。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)。
簡單點說說內(nèi)存讀取，內(nèi)存是由一系列的存儲單元組成的，每個存儲單元存儲固定大小的數(shù)據(jù)，且有一個唯一地址。當(dāng)需要讀內(nèi)存時，將地址信號放到地址總線上傳給內(nèi)存，內(nèi)存解析信號并定位到存儲單元，然后把該存儲單元上的數(shù)據(jù)放到數(shù)據(jù)總線上，回傳。
寫內(nèi)存時，系統(tǒng)將要寫入的數(shù)據(jù)和單元地址分別放到數(shù)據(jù)總線和地址總線上，內(nèi)存讀取兩個總線的內(nèi)容，做相應(yīng)的寫操作。
內(nèi)存存取效率，跟次數(shù)有關(guān)，先讀取A數(shù)據(jù)還是后讀取A數(shù)據(jù)不會影響存取效率。而磁盤存取就不一樣了，磁盤I/O涉及機械操作。磁盤是由大小相同且同軸的圓形盤片組成，磁盤可以轉(zhuǎn)動(各個磁盤須同時轉(zhuǎn)動)。磁盤的一側(cè)有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負(fù)責(zé)存取一個磁盤的內(nèi)容。磁頭不動，磁盤轉(zhuǎn)動，但磁臂可以前后動，用于讀取不同磁道上的數(shù)據(jù)。磁道就是以盤片為中心劃分出來的一系列同心環(huán)(如圖標(biāo)紅那圈)。磁道又劃分為一個個小段，叫扇區(qū)，是磁盤的最小存儲單元。
磁盤讀取時，系統(tǒng)將數(shù)據(jù)邏輯地址傳給磁盤，磁盤的控制電路會解析出物理地址，即哪個磁道哪個扇區(qū)。于是磁頭需要前后移動到對應(yīng)的磁道，消耗的時間叫尋道時間，然后磁盤旋轉(zhuǎn)將對應(yīng)的扇區(qū)轉(zhuǎn)到磁頭下，消耗的時間叫旋轉(zhuǎn)時間。所以，適當(dāng)?shù)牟僮黜樞蚝蛿?shù)據(jù)存放可以減少尋道時間和旋轉(zhuǎn)時間。為了盡量減少I/O操作，磁盤讀取每次都會預(yù)讀，大小通常為頁的整數(shù)倍。即使只需要讀取一個字節(jié)，磁盤也會讀取一頁的數(shù)據(jù)(通常為4K)放入內(nèi)存，內(nèi)存與磁盤以頁為單位交換數(shù)據(jù)。因為局部性原理認(rèn)為，通常一個數(shù)據(jù)被用到，其附近的數(shù)據(jù)也會立馬被用到。
B-Tree：如果一次檢索需要訪問4個節(jié)點，數(shù)據(jù)庫系統(tǒng)設(shè)計者利用磁盤預(yù)讀原理，把節(jié)點的大小設(shè)計為一個頁，那讀取一個節(jié)點只需要一次I/O操作，完成這次檢索操作，最多需要3次I/O(根節(jié)點常駐內(nèi)存)。數(shù)據(jù)記錄越小，每個節(jié)點存放的數(shù)據(jù)就越多，樹的高度也就越小，I/O操作就少了，檢索效率也就上去了。
B+Tree：非葉子節(jié)點只存key，大大滴減少了非葉子節(jié)點的大小，那么每個節(jié)點就可以存放更多的記錄，樹更矮了，I/O操作更少了。所以B+Tree擁有更好的性能。
