索引是幫助mysql高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
1.數(shù)據(jù)結(jié)構(gòu)
二叉排序樹
右孩子總比左孩子大 索引如圖所示旬痹，所以可能變?yōu)楹荛L的鏈表
紅黑樹 會平衡 找到6需要3次
做索引的的不太好的原因：插入的時候需要平衡消耗性能，樹的深度會很深
B樹 頁面大小 16Kb
B-Tree
8+6=14個字節(jié)
16MB/14字節(jié)
<meta charset="utf-8">
幾個概念：
InnoDB的行鎖是建立在索引的基礎之上的讨越，行鎖鎖的是索引两残，不是數(shù)據(jù)，所以提高并發(fā)寫的能力要在查詢字段添加索引
主索引和輔助索引：主索引就是主鍵索引把跨，輔助索引就是根據(jù)業(yè)務需要人弓，自己設置的普通的非主鍵的索引。這個在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ù)的物理存儲順序睬罗，所以一個表最多只能有一個聚簇索引，因為物理存儲只能有一個順序彤避。正因為一個表最多只能有一個聚簇索引傅物，所以它顯得更為珍貴，一個表設置什么為聚簇索引對性能很關(guān)鍵
舉例：主鍵為id的表中琉预，范圍查找 where id<1000 and id>200
則只需要找到ID=200和 ID=1000的葉子節(jié)點對應的位置董饰，撈取數(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ù)組爆袍，因為只需要再對應的節(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ù)倍蒙谓。
假設B+Tree的高度為h，一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存）训桶，復雜度O(h) = O(logmN)累驮，m指的是一個節(jié)點存儲的數(shù)據(jù)的個數(shù)。實際應用場景中舵揭，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)存當中炊林，而B+樹只需要根據(jù)匹配規(guī)則選擇對應的葉子數(shù)據(jù)加載即可
- 另外B+樹引入了緩存機制 和 數(shù)據(jù)頁技術(shù)來提升性能（不過理論上來說，這兩個特性Hash索引也可以實現(xiàn)）
