索引與算法（INnoDB存儲(chǔ)引擎）
索引與算法
InnoDB存儲(chǔ)引擎支持&常見索引
B+樹索引
全文索引
hash索引
B+ 樹索引不能給具體行數(shù)據(jù)，索引只能找到行所在的頁，讀到內(nèi)存之后，再進(jìn)行查找
mysql5.5之前（不包括5.5）增加索引流程
創(chuàng)建臨時(shí)表
原始數(shù)據(jù)導(dǎo)入臨時(shí)表
刪除原表
修改臨時(shí)表為原來表名
缺點(diǎn)：大表的索引添加修改，需要很長(zhǎng)時(shí)間，且修改時(shí)間內(nèi)數(shù)據(jù)庫不可用
InnoDB1.0.x解決了這個(gè)痛點(diǎn)問題
解決方案：引入FIC（快速索引創(chuàng)建）
創(chuàng)建索引的表上增加S鎖（不需要重建表）
添加S鎖期間，只能讀操作
刪除索引，只需要存儲(chǔ)引擎更新內(nèi)部視圖，將輔助索引標(biāo)記為可用
FIC 僅限于輔助索引，主鍵操作依舊需要重建表
OSC（在線架構(gòu)改變）
Online DDL
FIC 可以避免InnoDB創(chuàng)建臨時(shí)表，提高索引創(chuàng)建的效率，但是會(huì)阻塞DML，OSC也沒有完美解決這個(gè)問題，mysql5.6開始支持Online DDL
輔助索引的創(chuàng)建與刪除
改變自增長(zhǎng)
添加或者刪除外鍵約束
列的重命名
MRR（減少磁盤隨機(jī)訪問，轉(zhuǎn)化為相對(duì)有序的訪問）
mysql 5.6開始支持MRR
適用范圍 range ref eq_ref
優(yōu)勢(shì)
使數(shù)據(jù)訪問相對(duì)有序，查詢輔助索引時(shí)，根據(jù)查詢結(jié)果按照主鍵排序，按照主鍵排序順序進(jìn)行查找
減少緩沖池中頁被替換的次數(shù)
批量處理對(duì)鍵值對(duì)的查詢操作
MRR工作原理
查詢得到的輔助索引放到緩存里面（根據(jù)輔助索引鍵值對(duì)排序）
緩存中鍵值對(duì)按照RowID排序
根據(jù)RowID排序順序?qū)嶋H訪問數(shù)據(jù)文件
緩沖池不夠大的時(shí)候 MRR會(huì)失效
ICP（根據(jù)索引進(jìn)行查詢的優(yōu)化模式）
mysql5.6之后開始支持
ICP工作原理
根據(jù)索引查找記錄，然后直接根據(jù)where條件過濾數(shù)據(jù)（過濾數(shù)據(jù)操作在引擎層操作）
ICP使用范圍：
myidsam引擎&InnoDB引擎
支持 range，ref，eq_ref，ref_or_null類型查詢
哈希算法
哈希表（散列表）
解決hash碰撞采用鏈表法
InnoDB存儲(chǔ)引擎的哈希算法
自適應(yīng)哈希索引
DBA無法干預(yù)
只能用來搜索等值查詢
全文檢索
InnoDB引擎1.2.x支持，myisam支持
InnoDB存儲(chǔ)全文檢索索引限制
每張表只能有一個(gè)全文索引的索引
多列組合而成的全文索引的索引列必須使用相同的字符集和排列規(guī)則
不支持沒有單詞界定符的語言（中文，日文，韓語）
倒排索引
輔助表存儲(chǔ)單詞與單詞自身在的一個(gè)或者多個(gè)所在位置的映射
位置存儲(chǔ)的是位置數(shù)組
