一、mysql索引是怎么實(shí)現(xiàn)的

MySQL索引有哪些實(shí)現(xiàn)方式

MySQL索引實(shí)現(xiàn)方式有：B+tree索引、Hash索引、Full-text索引。

我們最常用的是B+tree索引，主鍵索引（也叫聚簇索引）本身就是一個(gè)B+tree索引樹(shù)，非葉子節(jié)點(diǎn)存儲(chǔ)主鍵id，葉子節(jié)點(diǎn)為一整行數(shù)據(jù)，葉子節(jié)點(diǎn)之間通過(guò)雙向鏈表連接支持范圍掃描，一般加的少數(shù)索引，普通索引都是B+tree索引。

Hash索引只能在memory存儲(chǔ)引擎下使用，這里不過(guò)多描述，優(yōu)點(diǎn)是查詢(xún)快，hash取模O(1)檢索，缺點(diǎn)不支持范圍查詢(xún)，出現(xiàn)hash沖突性能會(huì)降低。

Full-text索引主要對(duì)varchar,text加索引，使用倒排索引的方式，與搜索引擎實(shí)現(xiàn)方式相似。

為什么使用B+tree索引

先說(shuō)結(jié)論，主要因?yàn)榇疟P(pán)讀寫(xiě)速度遠(yuǎn)遠(yuǎn)低于內(nèi)存速度，傳統(tǒng)的機(jī)械硬盤(pán)大概慢一萬(wàn)倍，固態(tài)硬盤(pán)慢100倍，故減少磁盤(pán)I/O次數(shù)是提升索引性能的重點(diǎn)。

根據(jù)局部性原理和磁盤(pán)預(yù)讀，Linux操作系統(tǒng)進(jìn)行磁盤(pán)I/O時(shí)，一般順序讀寫(xiě)4KB到內(nèi)存的Page Cache中，之后再在內(nèi)存中找到對(duì)應(yīng)的數(shù)據(jù)返回回去，Mysql的B+tree每個(gè)節(jié)點(diǎn)為16KB，我們可以把16kb當(dāng)作磁盤(pán)IO的最小單元。

局部性原理表現(xiàn)為：時(shí)間局部性和空間局部性。時(shí)間局部性是指如果程序中的某條指令一旦執(zhí)行，則不久之后該指令可能再次被執(zhí)行；如果某數(shù)據(jù)被訪問(wèn)，則不久之后該數(shù)據(jù)可能再次被訪問(wèn)。空間局部性是指一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，則不久之后，其附近的存儲(chǔ)單元也將被訪問(wèn)。

那么為什么選擇B+tree作為索引呢，B+tree降低了磁盤(pán)IO次數(shù)嗎？為什么不用紅黑樹(shù)或者h(yuǎn)ash索引呢。

紅黑樹(shù)每個(gè)節(jié)點(diǎn)容納1個(gè)key，樹(shù)的高度為O(log? N)，查詢(xún)復(fù)雜度也是O(log? N)，1000000條數(shù)據(jù)，樹(shù)的高度為1000，最差需要掃描1000次才能查詢(xún)到對(duì)應(yīng)數(shù)據(jù)。

B+tree每個(gè)節(jié)點(diǎn)容納M個(gè)key，樹(shù)的高度為O(logm N)，m越大，樹(shù)高度越低，按照mysql一個(gè)page節(jié)點(diǎn)存儲(chǔ)16kb來(lái)算，一個(gè)bigint主鍵是8個(gè)字節(jié)，一個(gè)節(jié)點(diǎn)可以容納大概1000個(gè)主鍵（每個(gè)節(jié)點(diǎn)還存儲(chǔ)了其他隱藏信息幫助節(jié)點(diǎn)內(nèi)部檢索），m就是1000，一千萬(wàn)條數(shù)據(jù)，樹(shù)的高度大概是3層，只需要3次磁盤(pán)I/O加上幾百次內(nèi)存遍歷查找，就可以快速定位到數(shù)據(jù)，這對(duì)查詢(xún)性能的提升的巨大的，如果沒(méi)有索引而進(jìn)行全表掃描的話，大概需要上萬(wàn)次磁盤(pán)I/O。

故基于局部性原理和磁盤(pán)預(yù)讀，B+tree適合在磁盤(pán)文件系統(tǒng)中做檢索，紅黑樹(shù)更適合在內(nèi)存中檢索（比如java的hashmap，網(wǎng)絡(luò)epoll的連接節(jié)點(diǎn)存儲(chǔ)）。

為什么推薦使用自增ID作為主鍵呢，B+tree的構(gòu)建過(guò)程是通過(guò)分裂和合并保持樹(shù)的穩(wěn)定的，如上圖，若不是順序插入的，樹(shù)會(huì)進(jìn)行頻繁的分裂，導(dǎo)致額外的磁盤(pán)IO和CPU使用，可以使用此網(wǎng)站數(shù)據(jù)結(jié)構(gòu)構(gòu)建過(guò)程手動(dòng)測(cè)試下。

另外mysql的除主鍵外的普通索引的葉子節(jié)點(diǎn)都是id，故id越小普通索引的占用磁盤(pán)空間越小，故推薦使用int或bigint來(lái)做主鍵（下文詳細(xì)講）。

延伸閱讀：

二、索引分類(lèi)

索引按照索引列是否是主鍵，分為主鍵索引和輔助索引（除主鍵列索引外，其他列的索引都是輔助索引）

輔助索引又可分為少數(shù)索引，普通索引，全文索引

主鍵索引：即主索引，根據(jù)主鍵建立索引，不允許重復(fù)，不允許空值；

少數(shù)索引：用來(lái)建立索引的列的值必須是少數(shù)的，允許空值；

普通索引：用表中的普通列構(gòu)建的索引，沒(méi)有任何限制；

全文索引：用大文本對(duì)象的列構(gòu)建的索引，在MySQL5.6以下，只有MyISAM表支持全文檢索。在MySQL5.6以上Innodb引擎表也提供支持全文檢索。