參考地址：
javaGuide
數(shù)據(jù)庫兩大神器【索引和鎖】
# MySQL B+樹索引和哈希索引的區(qū)別
淺談MySQL的B樹索引與索引優(yōu)化

1.索引的基礎(chǔ)知識

首先Mysql的基本存儲結(jié)構(gòu)是頁(記錄都存在頁里邊)：

image.png

image.png

• 各個數(shù)據(jù)頁可以組成一個雙向鏈表
• 而每個數(shù)據(jù)頁中的記錄又可以組成一個單向鏈表
  • 每個數(shù)據(jù)頁都會為存儲在它里邊兒的記錄生成一個頁目錄埂材，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應(yīng)的槽伞租，然后再遍歷該槽對應(yīng)分組中的記錄即可快速找到指定的記錄
  • 以其他列(非主鍵)作為搜索條件：只能從最小記錄開始依次遍歷單鏈表中的每條記錄备恤。

所以說，如果我們寫select * from user where username = 'Java3y'這樣沒有進行任何優(yōu)化的sql語句菱父，默認會這樣做：

• 定位到記錄所在的頁
  • 需要遍歷雙向鏈表驱富，找到所在的頁
• 從所在的頁內(nèi)中查找相應(yīng)的記錄
  • 由于不是根據(jù)主鍵查詢镊讼，只能遍歷所在頁的單鏈表了

很明顯，在數(shù)據(jù)量很大的情況下這樣查找會很慢揩徊！

2.索引提高搜索速度

索引做了些什么可以讓我們查詢加快速度呢腰鬼？

其實就是將無序的數(shù)據(jù)變成有序(相對)：

image.png

要找到id為8的記錄簡要步驟：

image.png

很明顯的是：沒有用索引我們是需要遍歷雙向鏈表來定位對應(yīng)的頁藐握，現(xiàn)在通過“目錄”就可以很快地定位到對應(yīng)的頁上了！

其實底層結(jié)構(gòu)就是B+樹垃喊，B+樹作為樹的一種實現(xiàn)猾普，能夠讓我們很快地查找出對應(yīng)的記錄。

索引實現(xiàn)參考地址

3.索引降低增刪改的速度

B+樹是平衡樹的一種本谜。

平衡樹：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1初家，并且左右兩個子樹都是一棵平衡二叉樹。

如果一棵普通的樹在極端的情況下乌助，是能退化成鏈表的(樹的優(yōu)點就不復(fù)存在了)

image.png

B+樹是平衡樹的一種溜在，是不會退化成鏈表的，樹的高度都是相對比較低的(基本符合矮矮胖胖(均衡)的結(jié)構(gòu))【這樣一來我們檢索的時間復(fù)雜度就是O(logn)】他托！從上一節(jié)的圖我們也可以看見掖肋，建立索引實際上就是建立一顆B+樹。

• B+樹是一顆平衡樹赏参，如果我們對這顆樹增刪改的話志笼，那肯定會破壞它的原有結(jié)構(gòu)。
• 要維持平衡樹把篓，就必須做額外的工作纫溃。正因為這些額外的工作開銷，導(dǎo)致索引會降低增刪改的速度韧掩。

4.B+樹索引和哈希索引的區(qū)別

一個經(jīng)典的B+樹索引數(shù)據(jù)結(jié)構(gòu)見下圖：

image

image

從上面的圖來看律姨，B+樹索引和哈希索引的明顯區(qū)別是：

如果是等值查詢，那么哈希索引明顯有絕對優(yōu)勢臼疫，因為只需要經(jīng)過一次算法即可找到相應(yīng)的鍵值择份；當(dāng)然了，這個前提是烫堤，鍵值都是唯一的荣赶。如果鍵值不是唯一的，就需要先找到該鍵所在位置鸽斟，然后再根據(jù)鏈表往后掃描拔创，直到找到相應(yīng)的數(shù)據(jù)；

從示意圖中也能看到富蓄，如果是范圍查詢檢索剩燥，這時候哈希索引就毫無用武之地了，因為原先是有序的鍵值立倍，經(jīng)過哈希算法后灭红，有可能變成不連續(xù)的了，就沒辦法再利用索引完成范圍查詢檢索帐萎；

同理比伏，哈希索引也沒辦法利用索引完成排序，以及l(fā)ike ‘xxx%’ 這樣的部分模糊查詢（這種部分模糊查詢疆导，其實本質(zhì)上也是范圍查詢）；

哈希索引也不支持多列聯(lián)合索引的最左匹配規(guī)則葛躏；

B+樹索引的關(guān)鍵字檢索效率比較平均澈段，不像B樹那樣波動幅度大，在有大量重復(fù)鍵值情況下舰攒，哈希索引的效率也是極低的败富，因為存在所謂的哈希碰撞問題。

5.B樹與B+樹

1.B樹解決了什么問題

如果拋開維護操作摩窃，那么B樹就像一棵“m叉搜索樹”（m是子樹的最大個數(shù)）兽叮，時間復(fù)雜度為O(logm(n))。然而猾愿，B樹設(shè)計了一種高效簡單的維護操作鹦聪，使B樹的深度維持在約log(ceil(m/2))(n)~logm(n)之間，大大降低樹高蒂秘。

image.png

再次強調(diào)：

不要糾結(jié)于時間復(fù)雜度泽本，與單純的算法不同，磁盤IO次數(shù)才是更大的影響因素姻僧。讀者可以推導(dǎo)看看规丽，B樹與AVL的時間復(fù)雜度是相同的蒲牧，但由于B樹的層數(shù)少，磁盤IO次數(shù)少赌莺，實踐中B樹的性能要優(yōu)于AVL等二叉樹冰抢。

同二叉搜索樹類似，每個節(jié)點存儲了多個key和子樹艘狭，子樹與key按順序排列挎扰。

頁表的目的是擴展內(nèi)存+加速磁盤讀寫。一個頁（Page）通常4K（等于磁盤數(shù)據(jù)塊block的大小缓升，見inode與block的分析）鼓鲁，從磁盤讀寫的角度出發(fā)，操作系統(tǒng)每次以頁為單位將內(nèi)容從磁盤加載到內(nèi)存（以攤分尋道成本）港谊，修改頁后骇吭，再擇期將該頁寫回磁盤∑缢拢考慮到頁表的良好性質(zhì)燥狰，可以使每個節(jié)點的大小約等于一個頁（使m非常大），這每次加載的一個頁就能完整覆蓋一個節(jié)點斜筐，以便選擇下一層子樹龙致；對子樹同理。對于頁表來說顷链，AVL（或RBT）相當(dāng)于1個key+2個子樹的B樹目代，由于邏輯上相鄰的節(jié)點，物理上通常不相鄰嗤练，因此榛了，讀入一個4k頁，頁面內(nèi)絕大部分空間都將是無效數(shù)據(jù)煞抬。

假設(shè)key霜大、子樹節(jié)點指針均占用4B，則B樹節(jié)點最大m * (4 + 4) = 8m B革答；頁面大小4KB战坤。則m = 4 * 1024 / 8 = 512，一個512叉的B樹残拐，1000w的數(shù)據(jù)途茫，深度最大 log(512/2)(10^7) = 3.02 ~= 4。對比二叉樹如AVL的深度為log(2)(10^7) = 23.25 ~= 24蹦骑，相差了5倍以上慈省。震驚！B樹索引深度竟然如此！

另外边败，B樹對局部性原理非常友好袱衷。如果key比較小（比如上面4B的自增key）笑窜，則除了頁表的加成致燥，緩存還能進一步預(yù)讀加速。美滋滋~

2.B樹的剩余問題

然而排截，如果要實際應(yīng)用到數(shù)據(jù)庫的索引中嫌蚤，B樹還有一些問題：

1. 未定位數(shù)據(jù)行
2. 無法處理范圍查詢

問題1

數(shù)據(jù)表的記錄有多個字段，僅僅定位到主鍵是不夠的断傲，還需要定位到數(shù)據(jù)行脱吱。有3個方案解決：

1. 直接將key對應(yīng)的數(shù)據(jù)行（可能對應(yīng)多行）存儲在節(jié)點中。
2. 數(shù)據(jù)行單獨存儲认罩；節(jié)點中增加一個字段箱蝠，定位key對應(yīng)數(shù)據(jù)行的位置。
3. 修改key與子樹的判斷邏輯垦垂，使子樹大于等于上一key小于下一key宦搬，最終所有訪問都將落于葉子節(jié)點；葉子節(jié)點中直接存儲數(shù)據(jù)行或數(shù)據(jù)行的位置劫拗。

方案1中间校，數(shù)據(jù)行通常非常大，存儲數(shù)據(jù)行將減少頁面中的子樹個數(shù)页慷，m減小樹高增大憔足。假設(shè)數(shù)據(jù)行占用200B，可忽略組織B樹的指針酒繁，則新的m = 4 * 1024 / 200 = 20.48 ~= 21四瘫，深度最大 log(21/2)(10^7) ~= 7。增加了一倍以上的IO欲逃，不考慮。

方案2中饼暑，節(jié)點增加了一個字段稳析。假設(shè)是4B的指針，則新的m = 4 * 1024 / 12 = 341.33 ~= 341弓叛，深度最大 log(341/2)(10^7) = 3.14 ~= 4彰居。與3差別不大，可以考慮撰筷。

方案3的節(jié)點m與深度不變陈惰，但時間復(fù)雜度變?yōu)榉€(wěn)定的O(logm(n))”献眩考慮抬闯。

問題2

實際業(yè)務(wù)中井辆，范圍查詢的頻率非常高，B樹只能定位到一個索引位置（可能對應(yīng)多行）溶握，很難處理范圍查詢杯缺。給出2種方案：

1. 不改動：查詢的時候先查到左界，再查到右界睡榆，然后DFS（或BFS）遍歷左界萍肆、右界之間的節(jié)點。
2. 在“問題1-方案3”的基礎(chǔ)上胀屿，由于所有數(shù)據(jù)行都存儲在葉子節(jié)點塘揣，B樹的葉子節(jié)點本身也是有序的，可以增加一個指針宿崭，指向當(dāng)前葉子節(jié)點按主鍵順序的下一葉子節(jié)點亲铡；查詢時先查到左界，再查到右界劳曹，然后從左界到有界線性遍歷奴愉。

乍一看感覺方案1比方案2好——時間復(fù)雜度和常數(shù)項都一樣，方案1還不需要改動铁孵。但是別忘了局部性原理锭硼，不管節(jié)點中存儲的是數(shù)據(jù)行還是數(shù)據(jù)行位置，方案2的好處在于蜕劝，葉子節(jié)點連續(xù)存儲檀头，對頁表和緩存友好。而方案1則面臨節(jié)點邏輯相鄰岖沛、物理分離的缺點暑始。

3.B+樹

綜上，問題1的方案2與問題2的方案1可整合為一種方案（基于B樹的索引）婴削，問題1的方案3與問題2的方案2可整合為一種（基于B+樹的索引）廊镜。實際上，數(shù)據(jù)庫唉俗、文件系統(tǒng)有些采用了B樹嗤朴，有些采用B+樹。

image.png

主要變動如上所述：

修改key與子樹的組織邏輯虫溜，將索引訪問都落到葉子節(jié)點
按順序?qū)⑷~子節(jié)點串起來（方便范圍查詢）

6.索引優(yōu)化

1.優(yōu)先使用自增key作為主鍵

前面的分析中雹姊，假設(shè)用4B的自增key作為索引，則m可達到512衡楞，層高僅有3吱雏。使用自增的key有兩個好處：

1.自增key一般為int等整數(shù)型，key比較緊湊，這樣m可以非常大歧杏，而且索引占用空間小镰惦。最極端的例子，如果使用50B的varchar（包括長度）得滤，那么m = 4 * 1024 / 54m = 75.85 ~= 76陨献，深度最大 log(76/2)(10^7) = 4.43 ~= 5，再加上cache缺失懂更、字符串比較的成本眨业，時間成本增加較大。同時沮协，key由4B增長到50B龄捡，整棵索引樹的空間占用增長也是極為恐怖的（如果二級索引使用主鍵定位數(shù)據(jù)行，則空間增長更加嚴(yán)重）慷暂。

2.自增的性質(zhì)使得新數(shù)據(jù)行的插入請求必然落到索引樹的最右側(cè)聘殖，發(fā)生節(jié)點分裂的頻率較低，理想情況下行瑞，索引樹可以達到“滿”的狀態(tài)奸腺。索引樹滿，一方面層高更低血久，一方面刪除節(jié)點時發(fā)生節(jié)點合并的頻率也較低突照。

2.最左前綴匹配

在mysql建立聯(lián)合索引時會遵循最左前綴匹配的原則，即最左優(yōu)先氧吐，在檢索數(shù)據(jù)時從聯(lián)合索引的最左邊開始匹配讹蘑，示例：
對列col1、列col2和列col3建一個聯(lián)合索引

KEY index_col1_col2_col3 on test(col1,col2,col3);

聯(lián)合索引 index_col1_col2_col3 實際建立了(col1)筑舅、(col1,col2)座慰、(col,col2,col3)三個索引。

SELECT * FROM table WHERE col1="1" AND clo2="2" AND clo4="4"

上面這個查詢語句執(zhí)行時會依照最左前綴匹配原則翠拣，檢索時會使用索引(col1,col2)進行數(shù)據(jù)匹配版仔。索引的字段可以是任意順序的。

3.=误墓、in自動優(yōu)化順序

不需要考慮=邦尊、in等的順序，mysql會自動優(yōu)化這些條件的順序优烧，以匹配盡可能多的索引列。

如有索引(a, b, c, d)链峭，查詢條件c > 3 and b = 2 and a = 1 and d < 4與a = 1 and c > 3 and b = 2 and d < 4等順序都是可以的畦娄，MySQL會自動優(yōu)化為a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b熙卡、c杖刷。

4.索引列不能參與計算

有索引列參與計算的查詢條件對索引不友好（甚至無法使用索引），如from_unixtime(create_time) = '2014-05-29'驳癌。

原因很簡單滑燃，如何在節(jié)點中查找到對應(yīng)key？如果線性掃描颓鲜，則每次都需要重新計算表窘，成本太高；如果二分查找甜滨，則需要針對from_unixtime方法確定大小關(guān)系乐严。

因此，索引列不能參與計算衣摩。上述from_unixtime(create_time) = '2014-05-29'語句應(yīng)該寫成create_time = unix_timestamp('2014-05-29')昂验。

5.能擴展就不要新建索引

如果已有索引(a)，想建立索引(a, b)艾扮，盡量選擇修改索引(a)為索引(a, b)既琴。

新建索引的成本很容易理解。而基于索引(a)修改為索引(a, b)的話泡嘴，MySQL可以直接在索引a的B+樹上甫恩，經(jīng)過分裂、合并等修改為索引(a, b)磕诊。

6.不需要建立前綴有包含關(guān)系的索引

如果已有索引(a, b)填物，則不需要再建立索引(a)，但是如果有必要霎终，則仍然需考慮建立索引(b)滞磺。

7.選擇區(qū)分度高的列作索引

很容易理解。如莱褒，用性別作索引击困，那么索引僅能將1000w行數(shù)據(jù)劃分為兩部分（如500w男，500w女）广凸，索引幾乎無效阅茶。

區(qū)分度的公式是count(distinct <col>) / count(*)，表示字段不重復(fù)的比例谅海，比例越大區(qū)分度越好脸哀。唯一鍵的區(qū)分度是1，而一些狀態(tài)扭吁、性別字段可能在大數(shù)據(jù)面前的區(qū)分度趨近于0撞蜂。