參考出處

陳Chuan大佬系列隧膘，簡書過500贊的博客
http://www.reibang.com/p/d7665192aaaf

一文看懂聚簇索引脖律、非聚簇索引和InnoDB和Myisam的區(qū)別
https://blog.csdn.net/lisuyibmd/article/details/53004848

Mysql B+樹的插入刪除示损，看這一篇就夠了崭倘，有圖有真想
https://blog.csdn.net/sunshine_lyn/article/details/82747596

概論

image

幾個概念：

InnoDB的行鎖是建立在索引的基礎(chǔ)之上的聊替，行鎖鎖的是索引，不是數(shù)據(jù)开财，所以提高并發(fā)寫的能力要在查詢字段添加索引
主索引和輔助索引：主索引就是主鍵索引汉柒，輔助索引就是根據(jù)業(yè)務(wù)需要，自己設(shè)置的普通的非主鍵的索引床未。這個在Myisam里面區(qū)別不大竭翠，但是在Innodb的時候差別很大
聚簇索引：Innodb的主索引采用的是聚簇索引振坚，一個表只能有1個聚簇索引薇搁，因為表數(shù)據(jù)存儲的物理位置是唯一的。聚簇索引的value存的就是真實的數(shù)據(jù)渡八，不是數(shù)據(jù)的地址啃洋。主索引樹里面包含了真實的數(shù)據(jù)。key是主鍵值屎鳍，value值就是data宏娄，key值按照B+樹的規(guī)則分散排布的葉子節(jié)點。
非聚簇索引：Myisam的主索引和輔助索引都采用的是非聚簇索引逮壁，索引和表數(shù)據(jù)是分離的孵坚，索引的value值指向的物理的存儲地址。
Innodb的索引：主索引采用聚簇索引，葉子節(jié)點的value值卖宠，直接存儲的真實的數(shù)據(jù)巍杈。輔助索引是非聚簇索引，value值指向主索引的位置扛伍。所以Innodb中筷畦，根據(jù)輔助索引查詢值需要遍歷2次B+樹，同時主鍵的長度越短越好刺洒，越短副主索引的value值就越小鳖宾。但是Innodb中根據(jù)主鍵進行范圍查詢，會特別快逆航。
Myisam的索引：主索引和輔助索引都是非聚簇索引
B+樹：不管是什么索引鼎文，在mysql中的數(shù)據(jù)結(jié)構(gòu)都是B+樹的結(jié)構(gòu)，可以充分利用數(shù)據(jù)塊因俐，來減少IO查詢的次數(shù)漂问，提升查詢的效率，如圖所示女揭，一個數(shù)據(jù)塊data里面蚤假，存儲了很多個相鄰key的value值，所有的非葉子節(jié)點都不存儲數(shù)據(jù)吧兔，都是指針磷仰。
Mysql采用B+樹的優(yōu)點：IO讀取次數(shù)少（每次都是頁讀取）境蔼，范圍查找更快捷（相鄰頁之間有指針）

聚集索引

聚集索引就是葉子節(jié)點的順序和物理存儲的順序是一樣的灶平，所以范圍查找的時候效率很高，但是DML操作的時候箍土，為了維護物理存儲的順序和葉子節(jié)點一樣逢享，涉及到大量的數(shù)據(jù)位移調(diào)整。
聚簇索引的順序就是數(shù)據(jù)的物理存儲順序吴藻，所以一個表最多只能有一個聚簇索引瞒爬，因為物理存儲只能有一個順序。正因為一個表最多只能有一個聚簇索引沟堡，所以它顯得更為珍貴侧但，一個表設(shè)置什么為聚簇索引對性能很關(guān)鍵

舉例：主鍵為id的表中，范圍查找 where id<1000 and id>200
則只需要找到ID=200和 ID=1000的葉子節(jié)點對應(yīng)的位置航罗，撈取數(shù)據(jù)塊中間的所有的數(shù)據(jù)禀横，就是要查找的范圍數(shù)據(jù)了。但是如果以前沒有ID=300這個數(shù)據(jù)粥血，現(xiàn)在新增一個ID=300的數(shù)據(jù)柏锄，那么 ID>300的所有的數(shù)據(jù)都要往后挪一個位置酿箭。

樹形結(jié)構(gòu)科普

https://blog.csdn.net/zwz2011303359/article/details/63262541

傳說中的葉子節(jié)點，指的是最外層的節(jié)點趾娃，就像一棵樹七问，只有最外層的節(jié)點才長葉子
二叉搜索樹的特點：

所有結(jié)點至多擁有兩個兒子（Left和Right）；
所有結(jié)點只存儲一個關(guān)鍵字（可以理解為索引茫舶，比如ID值）械巡；
非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹饶氏；
二叉搜索樹如果是滿二叉樹時讥耗，查找的性能逼近有序數(shù)組的二分查找，同時插入的性能遠遠高于有序數(shù)組疹启，因為只需要再對應(yīng)的節(jié)點添加引用古程，而不需要移動任何老的節(jié)點

B-Tree的特點

所有鍵值分布在整個樹中（區(qū)別與B+樹，B+樹的值只分部在葉子節(jié)點上）
任何關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個節(jié)點中（區(qū)別與B+樹）
搜索有可能在非葉子節(jié)點結(jié)束（區(qū)別與B+樹喊崖，因為值都在葉子節(jié)點上挣磨，只有搜到葉子節(jié)點才能拿到值）
在關(guān)鍵字全集內(nèi)做一次查找，性能逼近二分查找算法

B+樹的結(jié)構(gòu)特點

B+樹索引并不能找到一個給定鍵值的具體行荤懂，它找到的只是被查找數(shù)據(jù)行所在的頁茁裙，接著數(shù)據(jù)庫會把頁讀入到內(nèi)存，再在內(nèi)存中進行查找节仿，最后得到要查找的數(shù)據(jù)晤锥。數(shù)據(jù)的讀取是精確到頁的，因為頁是計算機管理存儲器的邏輯塊廊宪，IO的磁盤讀取矾瘾，每次都讀取數(shù)據(jù)的大小是一個頁大小的整數(shù)倍。
假設(shè)B+Tree的高度為h箭启，一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存）壕翩，復(fù)雜度O(h) = O(logmN)，m指的是一個節(jié)點存儲的數(shù)據(jù)的個數(shù)傅寡。實際應(yīng)用場景中放妈，M通常較大，常常超過100赏僧，因此樹的高度一般都比較小大猛，通常不超過3。

B+樹與B樹的不同在于：

所有關(guān)鍵字存儲在葉子節(jié)點淀零，非葉子節(jié)點不存儲真正的data
為所有葉子節(jié)點（左右相鄰的節(jié)點之間）增加了一個鏈指針

為什么數(shù)據(jù)庫使用B+而不使用紅黑樹呢？

計算器在IO磁盤讀取的時候膛壹，為了降低讀取的次數(shù)驾中，默認一次會讀取一個頁的數(shù)據(jù)量唉堪，MySQL(默認使用InnoDB引擎),將記錄按照頁的方式進行管理,每頁大小默認為16K(這個值可以修改)。linux 默認頁大小為4K肩民。所以每次IO讀取唠亚，都是讀取一個頁的數(shù)據(jù)量，所以B樹的節(jié)點都是存儲一個頁的節(jié)點持痰，這樣的查詢效率才是最高的
每次新建節(jié)點時灶搜，直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里工窍，加之計算機存儲分配都是按頁對齊的割卖，就實現(xiàn)了一個結(jié)點只需一次I/O。這樣大大降低了樹的高度

為什么mysql的索引使用B+樹而不是B樹呢患雏？

范圍查找更快鹏溯，mysql是關(guān)系型數(shù)據(jù)庫，經(jīng)常會按照區(qū)間來訪問某個索引列淹仑，B+樹的葉子節(jié)點間按順序建立了鏈指針丙挽，加強了區(qū)間訪問性，所以B+樹對索引列上的區(qū)間范圍查詢很友好匀借。而B樹的數(shù)據(jù)有一部分存在在非葉子節(jié)點上面颜阐，而且默認的B樹的相鄰的葉子節(jié)點之間是沒有指針的，所以范圍查找相對更慢吓肋。

降低樹的高度瞬浓，但是最底下一層的節(jié)點會更多，因為所有的數(shù)據(jù)都堆積在最底下一層了蓬坡，用空間換速度猿棉。B+樹更適合外部存儲(一般指磁盤存儲),由于內(nèi)節(jié)點(非葉子節(jié)點)不存儲data，所以一個節(jié)點可以存儲更多的內(nèi)節(jié)點屑咳，每個節(jié)點能索引的范圍更大更精確萨赁。也就是說使用B+樹單次磁盤IO的信息量相比較B樹更大，IO效率更高

B+樹插入和刪除的邏輯

https://blog.csdn.net/sunshine_lyn/article/details/82747596

插入：和紅黑樹特別像兆龙，新數(shù)據(jù)插入到一個滿了的節(jié)點中時杖爽，會優(yōu)先進行左旋右旋，如果鄰近的節(jié)點都滿了的話,會取中間的一個key往上一個層級插入紫皇，直至到Root節(jié)點,樹的高度的增加慰安，都是通過根節(jié)點的拆分來完成的，這保證了所有左右節(jié)點的高度差不超過1
刪除：會進行調(diào)整優(yōu)化樹形結(jié)構(gòu)聪铺，使樹的數(shù)據(jù)更分散化焕，以及降低樹的高度。比如如果該節(jié)點的數(shù)據(jù)過少铃剔，可以從鄰近的節(jié)點左旋右旋數(shù)據(jù)來填充撒桨〔榭蹋可能的話，降低一個樹的高度凤类。

為什么Mysql不選擇Hash索引穗泵？

Hash索引的優(yōu)勢是精確查找的話，速度會更快谜疤，為什么不選擇Hash索引

Hash索引不適合范圍查找佃延，而B+樹特別適合范圍查找（特別是聚簇索引的時候）
Hash索引每次查詢要加載所有的索引數(shù)據(jù)到內(nèi)存當(dāng)中，而B+樹只需要根據(jù)匹配規(guī)則選擇對應(yīng)的葉子數(shù)據(jù)加載即可
另外B+樹引入了緩存機制和數(shù)據(jù)頁技術(shù)來提升性能（不過理論上來說夷磕，這兩個特性Hash索引也可以實現(xiàn)）

Mysql索引原理