一、mysql索引是怎么實現的

MySQL索引有哪些實現方式

MySQL索引實現方式有：B+tree索引、Hash索引、Full-text索引。

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

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

Full-text索引主要對varchar,text加索引，使用倒排索引的方式，與搜索引擎實現方式相似。

為什么使用B+tree索引

先說結論，主要因為磁盤讀寫速度遠遠低于內存速度，傳統的機械硬盤大概慢一萬倍，固態硬盤慢100倍，故減少磁盤I/O次數是提升索引性能的重點。

根據局部性原理和磁盤預讀，Linux操作系統進行磁盤I/O時，一般順序讀寫4KB到內存的Page Cache中，之后再在內存中找到對應的數據返回回去，Mysql的B+tree每個節點為16KB，我們可以把16kb當作磁盤IO的最小單元。

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

那么為什么選擇B+tree作為索引呢，B+tree降低了磁盤IO次數嗎？為什么不用紅黑樹或者hash索引呢。

紅黑樹每個節點容納1個key，樹的高度為O(log? N)，查詢復雜度也是O(log? N)，1000000條數據，樹的高度為1000，最差需要掃描1000次才能查詢到對應數據。

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

故基于局部性原理和磁盤預讀，B+tree適合在磁盤文件系統中做檢索，紅黑樹更適合在內存中檢索（比如java的hashmap，網絡epoll的連接節點存儲）。

為什么推薦使用自增ID作為主鍵呢，B+tree的構建過程是通過分裂和合并保持樹的穩定的，如上圖，若不是順序插入的，樹會進行頻繁的分裂，導致額外的磁盤IO和CPU使用，可以使用此網站數據結構構建過程手動測試下。

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

延伸閱讀：

二、索引分類

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

輔助索引又可分為少數索引，普通索引，全文索引

主鍵索引：即主索引，根據主鍵建立索引，不允許重復，不允許空值；

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

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

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