MySQL索引 & B+樹

image

ZERO

????持續(xù)更新請關(guān)注：https://zorkelvll.cn/blogs/zorkelvll/articles/2019/01/18/1547796862504

一撩独、背景

????在程序員面試的世界中，凡是涉及到數(shù)據(jù)庫mysql，基本都會(huì)問索引枉昏，而問到索引更深入一點(diǎn)就都會(huì)涉及到B+樹疾宏，因此本文決定對B+樹這樣一種數(shù)據(jù)結(jié)構(gòu)進(jìn)行較為詳細(xì)的學(xué)習(xí)丹皱！

二酝静、MySQL索引

1骄蝇、索引類型

主鍵索引primary：不允許為null
普通索引normal：普通非唯一索引
唯一索引unique：表示唯一的，不允許重復(fù)的索引谷醉，可以為null
全文索引fulltext：全文搜索的索引致稀，用于搜索很長一篇文章時(shí)效果最好
空間索引spatial：

2、索引結(jié)構(gòu)

哈希索引：底層數(shù)據(jù)結(jié)構(gòu)即是哈希表俱尼，對于絕大數(shù)需求為單條記錄查詢的性能最快
BTree索引：mysql中BTree索引使用的是B樹中的B+Tree抖单，只是在兩種主要的存儲(chǔ)引擎中的實(shí)現(xiàn)方式不同而已(在適用中存在差別)

3、MyISAM B+Tree VS InnoDB B+Tree

MyISAM在B+Tree的葉節(jié)點(diǎn)存儲(chǔ)關(guān)鍵字外遇八，還存儲(chǔ)對應(yīng)數(shù)據(jù)的存放地址矛绘；主索引和輔助索引沒什么區(qū)別，只是主索引中的關(guān)鍵字一定是唯一的 =》稱之為非聚簇索引
InnoDB在B+Tree的葉節(jié)點(diǎn)不僅存儲(chǔ)關(guān)鍵字刃永，同時(shí)也將對應(yīng)數(shù)據(jù)存放在那兒（數(shù)據(jù)物理存放順序與索引順序一致） =》稱之為聚簇索引
=>對于大數(shù)據(jù)量的排序货矮、全表掃描、count之類操作斯够，MyISAM由于索引所占空間小次屠，且這些操作都是需要在內(nèi)存中完成的，因此MyISAM更具有優(yōu)勢
一言以蔽之雳刺，“MyISAM中B+Tree葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址劫灶，索引文件和數(shù)據(jù)文件是分離的”，而“InnoDB數(shù)據(jù)文件本身就是索引文件掖桦，其B+Tree葉節(jié)點(diǎn)data域保存的是完整的數(shù)據(jù)記錄”

三本昏、B+Tree

1、數(shù)據(jù)結(jié)構(gòu)

B+Tree是由一個(gè)個(gè)磁盤塊組成的樹形結(jié)構(gòu)枪汪，每個(gè)磁盤塊均由數(shù)據(jù)項(xiàng)和指針組成涌穆；
所有的數(shù)據(jù)均是存放在葉子節(jié)點(diǎn)的，非葉子節(jié)點(diǎn)不存放數(shù)據(jù)

imagepng

2雀久、查找

或者從最小關(guān)鍵字起順序查找
或者從根結(jié)點(diǎn)開始宿稀，進(jìn)行隨機(jī)查找

在查找時(shí)，若在非葉子節(jié)點(diǎn)上的關(guān)鍵值等于給定值赖捌，并不會(huì)終止祝沸，而是會(huì)繼續(xù)向下直到葉子節(jié)點(diǎn)！也即越庇，在B+樹中罩锐，無論查找成功與否，每次查找均是一條從根到葉子節(jié)點(diǎn)的路徑卤唉！

四涩惑、BTree

BTree即是B樹（不要讀成B-樹而丟人現(xiàn)眼啊ＩＧ＝咛瘛ｕ说啊）

數(shù)據(jù)庫之所以使用樹結(jié)構(gòu)進(jìn)行存儲(chǔ)，出發(fā)點(diǎn)當(dāng)然是因?yàn)榈臉涞牟樵冃实角铱梢员３钟行颍菫槭裁床皇鞘褂枚娌檎覙淠兀浚ǘ娌檎覙涞臅r(shí)間復(fù)雜度是O(logN),從算法邏輯上講楼肪，二叉查找樹的查找速度和比較次數(shù)都是最小的 => 但是，在數(shù)據(jù)庫存儲(chǔ)的查找時(shí)不得不考慮的一個(gè)因素是“磁盤IO”
=> 數(shù)據(jù)庫索引是存儲(chǔ)在磁盤中的此衅，在數(shù)據(jù)量比較大的時(shí)候，索引的大小可能會(huì)達(dá)到幾個(gè)G甚至更大
=> 因此亭螟，是不可能把整個(gè)索引都加載到內(nèi)存中的挡鞍，只能是通過逐一加載磁盤頁（也即對應(yīng)索引樹中的節(jié)點(diǎn)）
=> 因此，磁盤IO的次數(shù)预烙，在最壞的情況下是等于樹的高度的 ==》于是墨微，為了減少磁盤IO的次數(shù)，需要降低樹的高度扁掸，也即將“瘦高”的樹結(jié)構(gòu)變成“矮胖”翘县，這也是B樹的特征之一）

B樹是一種多路平衡查找樹，每一個(gè)節(jié)點(diǎn)最多包含k個(gè)孩子谴分，k稱之為B樹的階锈麸；k的大小取決于磁盤頁的大小

1、數(shù)據(jù)結(jié)構(gòu) - m階B樹

每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字
根節(jié)點(diǎn)至少有1個(gè)關(guān)鍵字牺蹄，非根節(jié)點(diǎn)至少有Math.ceil(m/2) - 1個(gè)關(guān)鍵字
每個(gè)節(jié)點(diǎn)中的關(guān)鍵字都是按照從小到大排列忘伞，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它
所有葉子節(jié)點(diǎn)均位于同一層沙兰，或者說根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的長度都相同