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

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

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

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

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

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

為什么使用B+tree索引

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

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

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

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

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

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

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

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

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

延伸閱讀：

二、索引分類

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

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

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

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

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

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