零、什么是索引？
- 索引是幫助MySQL 高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)
- 索引存儲(chǔ)在文件系統(tǒng)中
- 索引的文件存儲(chǔ)形式與存儲(chǔ)引擎有關(guān)
- 索引的文件結(jié)構(gòu)
4.1 hash
4.2 二叉樹(shù)
4.3 B樹(shù)
4.4 B+ 樹(shù)
一、索引的常見(jiàn)模型
hash：鍵值對(duì)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（實(shí)現(xiàn)方式：數(shù)組+鏈表），值放在數(shù)組中，用hash 函數(shù)把key 換算成一個(gè)確定的位置，然后把value 放在數(shù)組的這個(gè)位置。
哈希碰撞：不同的key 值通過(guò)hash 函數(shù)算出的值相同，處理方式就是在數(shù)組的該位置拉出一個(gè)鏈表。
hash 存儲(chǔ)只適合等值查詢，不適合范圍查詢，實(shí)際工作中范圍查詢的情況更多，所以hash 存儲(chǔ)更適合一些NoSQL 引擎。
hash 索引并不是按照索引順序存儲(chǔ)的，無(wú)法排序。當(dāng)存在hash 沖突，維護(hù)操作的成本也會(huì)增加。-
BST樹(shù)（二叉搜索樹(shù)）：二叉搜索樹(shù)的特點(diǎn)是：每個(gè)節(jié)點(diǎn)的左兒子小于父節(jié)點(diǎn)，父節(jié)點(diǎn)又小于右兒子。二叉樹(shù)的查詢效率挺高的（時(shí)間復(fù)雜度是O(log2(n))），但是有可能出現(xiàn)一條鏈?zhǔn)浇Y(jié)構(gòu)。
-
AVL 樹(shù)（自平衡二叉搜索樹(shù)）：AVL樹(shù)定義是任意節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)高度差不超過(guò)1。AVL樹(shù)本質(zhì)上是帶了平衡功能的二叉搜索樹(shù)。
解決上圖的辦法：通過(guò) 左旋維護(hù)去維護(hù)平衡。
也就是說(shuō)AVL樹(shù)維護(hù)平衡的成本很高，每次增加或刪除一個(gè)節(jié)點(diǎn)需要多次左旋或者右旋去維護(hù)樹(shù)的平衡。如果節(jié)點(diǎn)多的情況下AVL 樹(shù)的高度還是會(huì)比較高且查詢不穩(wěn)定（看運(yùn)氣）。
AVL 樹(shù)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)內(nèi)容太少，在二叉樹(shù)每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)只能保存一個(gè)關(guān)鍵字，一個(gè)數(shù)據(jù)區(qū)，兩個(gè)子節(jié)點(diǎn)的引用，并不能填滿4k的內(nèi)容，即每次IO操作系統(tǒng)會(huì)將4k 數(shù)據(jù)加載到內(nèi)存。 B 樹(shù)：有序數(shù)組+ 平衡二叉樹(shù)；B樹(shù)每個(gè)節(jié)點(diǎn)都存儲(chǔ)了key和data，B樹(shù)提高了磁盤(pán)IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題。
B+ 樹(shù)：有序數(shù)組鏈表+平衡多叉樹(shù)；B+ 樹(shù)的data 存儲(chǔ)在葉子節(jié)點(diǎn)上，B+樹(shù)能夠很好地配合磁盤(pán)的讀寫(xiě)特性，減少單次查詢的磁盤(pán)訪問(wèn)次數(shù)。每一個(gè)索引在InnoDB里面對(duì)應(yīng)一棵B+樹(shù)，主鍵索引的葉子節(jié)點(diǎn)存的是整行數(shù)據(jù)，在InnoDB里，主鍵索引也被稱(chēng)為聚簇索引。非主鍵索引的葉子節(jié)點(diǎn)內(nèi)容是主鍵的值，在InnoDB里，非主鍵索引也被稱(chēng)為二級(jí)索引。
二、MySQL索引類(lèi)型
Normal 普通索引
Unique 唯一索引：表示唯一的，不允許重復(fù)的索引。添加唯一性索引的數(shù)據(jù)列可以為空，但是只要存在數(shù)據(jù)值，就必須是唯一的。創(chuàng)建唯一索引的目的不是為了提高訪問(wèn)速度，而只是為了避免數(shù)據(jù)出現(xiàn)重復(fù)。
Full Text 全文索引：MySQL5.6.24上InnoDB引擎也加入了全文索引。全文索引的運(yùn)用見(jiàn)《https://blog.csdn.net/yygg329405/article/details/97110984
》SPATIAL 空間索引：空間索引是對(duì)空間數(shù)據(jù)類(lèi)型的字段建立的索引，MYSQL中的空間數(shù)據(jù)類(lèi)型有4種。
btree索引和hash索引的區(qū)別：BTREE（B樹(shù)（可以是多叉樹(shù)）） {主流使用}；HASH（key,value） 這種方式對(duì)范圍查詢支持得不是很好《https://blog.csdn.net/guo_qiangqiang/article/details/88794971
》
三、索引的技術(shù)名稱(chēng)
- 回表：回到主鍵索引樹(shù)搜索的過(guò)程，我們稱(chēng)為回表。
- 索引覆蓋：不需要回表操作，如通過(guò)二級(jí)索引查詢主鍵，二級(jí)索引的葉子節(jié)點(diǎn)已經(jīng)存儲(chǔ)了主鍵值，所以不需要回表，減少樹(shù)的搜索次數(shù)。
- 最左匹配：創(chuàng)建一個(gè)組合索引，最左前綴可以是聯(lián)合索引的最左N個(gè)字段，也可以是字符串索引的最左M個(gè)字符。
聯(lián)合索引為key idx_a_b_c(a,b,c)
是否使用索引
where a = x and b = x and c = x 是
where a = x and b = x 是，部分索引
where a = x 是，部分索引
where b = x 否，不包含最左列a
where b = x and c = x 否，不包含最左列a
MySQL中，有兩種方式生成有序結(jié)果集：
1. 通過(guò)有序索引順序掃描直接返回有序數(shù)據(jù)
2. Filesort排序，對(duì)返回的數(shù)據(jù)進(jìn)行排序
可以用export 命令查看Extra列是否有Using filesort進(jìn)行了額外排序
假如說(shuō)有如下聯(lián)合索引，key idx_a_b_c(a,b,c)
order by 能使用索引排序
order by a
order by a,b
order by a,b,c
order by a desc, b desc, c desc
where a = const order by b,c
where a = const and b = const order by c
where a = const and b > const order by b,c
order by 不能使用索引進(jìn)行排序
rder by b
order by c
order by b, c
order by a asc, b desc, c desc //排序不一致
where g = const order by b,c //丟失a索引
where a = const order by c //丟失b索引
where a = const order by a,d //d不是索引的一部分
where a in (...) order by b,c //范圍查詢
建一個(gè)聯(lián)合索引(col1,col2,col3)，實(shí)際相當(dāng)于建了(col1),(col1,col2),(col1,col2,col3)三個(gè)索引。
每多一個(gè)索引，都會(huì)增加寫(xiě)操作的開(kāi)銷(xiāo)和磁盤(pán)空間的開(kāi)銷(xiāo)。對(duì)于大量數(shù)據(jù)的表，使用聯(lián)合索引會(huì)大大增加開(kāi)銷(xiāo)！
- 索引下推：對(duì)于不符合最左前綴的部分在索引遍歷過(guò)程中，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。
建一個(gè)聯(lián)合索引（name, age）
SQL語(yǔ)句是這么寫(xiě)：
mysql> select * from tuser where name like '張%' and age=10 and ismale=1;
根據(jù)最左前綴索引規(guī)則，搜索索引樹(shù)的時(shí)候，只能用 “張”。MySQL 5.6之前只能從匹配出的數(shù)據(jù)一個(gè)一個(gè)的回表再對(duì)比字段值。
MySQL 5.6 引入的索引下推優(yōu)化， 可以在索引遍歷過(guò)程中，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。
