前言
本篇基于上一篇MySql性能調(diào)優(yōu)一（存儲(chǔ)引擎InnoDB，MyISAM）颂翼，本篇繼續(xù)學(xué)習(xí)Mysql性能調(diào)優(yōu)晃洒，關(guān)于BTree、B+Tree與mysql索引數(shù)據(jù)結(jié)構(gòu)理解朦乏。
BTree特性
BTree又叫多路平衡查找樹球及，一顆m叉的BTree特性如下：
- 樹中每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子。
- 除根節(jié)點(diǎn)與葉子節(jié)點(diǎn)外呻疹，每個(gè)節(jié)點(diǎn)至少有[ceil(m/2)]個(gè)孩子吃引。
- 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有兩個(gè)孩子刽锤。
- 所有的葉子節(jié)點(diǎn)都在同一層镊尺。
- 每個(gè)非葉子節(jié)點(diǎn)由n個(gè)key與n+1個(gè)指針組成，其中[ceil(m/2)-1] <= n <= m-1 并思。
BTree插入
以5叉BTree為例庐氮，key的數(shù)量：公式推導(dǎo)[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4宋彼。當(dāng)n>4時(shí)弄砍，中間節(jié)點(diǎn)分裂到父節(jié)點(diǎn)，兩邊節(jié)點(diǎn)分裂输涕。
- 以插入C N G A H E K Q M F W L T Z D P R X Y S為例音婶，前4個(gè)字母沒什么好說的。
- 插入H莱坎，n>4衣式，中間元素G字母向上分裂到新的節(jié)點(diǎn)。
- 插入E型奥，K瞳收，Q不需要分裂。
- 插入M厢汹，中間元素M字母向上分裂到父節(jié)點(diǎn)G。
- 插入F谐宙，W烫葬，L，T不需要分裂。
- 插入Z搭综，中間元素T向上分裂到父節(jié)點(diǎn)中垢箕。
- 插入D，中間元素D向上分裂到父節(jié)點(diǎn)中兑巾。然后插入P条获，R，X蒋歌，Y不需要分裂帅掘。
- 最后插入S，NPQR節(jié)點(diǎn)n>5堂油，中間節(jié)點(diǎn)Q向上分裂修档，但分裂后父節(jié)點(diǎn)DGMT的n>5，中間節(jié)點(diǎn)M向上分裂府框。需要注意的是吱窝，原BTree第三個(gè)子節(jié)點(diǎn)HKL會(huì)包含DG節(jié)點(diǎn)中。
到此迫靖，一個(gè)BTree的構(gòu)建就完成了院峡，怎么樣？是不是很簡(jiǎn)單系宜。刪除操作比插入略微復(fù)雜照激，鑒于篇幅，不做敘述蜈首。
B+Tree
B+Tree為BTree的變種实抡，B+Tree與BTree的區(qū)別為：
- 有n棵子樹的B+Tree最多含有n個(gè)key，而BTree最多含有n-1個(gè)key欢策。
- B+Tree的葉節(jié)點(diǎn)保存所有的key信息吆寨，依key大小順序排列。
- 所有的非葉子節(jié)點(diǎn)都可以看作是key的索引部分踩寇，節(jié)點(diǎn)中只含有其子節(jié)點(diǎn)的最大（或最凶那濉）key。
由于B+Tree只有葉子節(jié)點(diǎn)保存key信息俺孙，查詢?nèi)魏蝛ey都要從root走到葉子辣卒。所以B+Tree的查詢效率更加穩(wěn)定。
帶有順序指針的B+Tree
MySql索引數(shù)據(jù)結(jié)構(gòu)對(duì)經(jīng)典的B+Tree進(jìn)行了優(yōu)化睛榄。
在原B+Tree的基礎(chǔ)上荣茫，增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，就形成了帶有順序指針的B+Tree场靴，提高區(qū)間訪問的性能啡莉。
如上圖訪問18-49的元素港准，只需要順著18的指針走向49即可。
MySql索引數(shù)據(jù)結(jié)構(gòu)
在mysql中咧欣，索引的實(shí)現(xiàn)方式與存儲(chǔ)引擎相關(guān)浅缸，MySql支持多種索引類型，如B+Tree魄咕、Hash索引衩椒、全文索引等等。在此只關(guān)注MyISAM與InnoDB的B+Tree索引數(shù)據(jù)結(jié)構(gòu)哮兰。
MyISAM的B+Tree索引
MyISAM的主鍵索引與輔助索引在結(jié)構(gòu)上沒有任何區(qū)別毛萌，只是主鍵索引要求key唯一〉斓牛可以看出朝聋，MyISAM的索引葉節(jié)點(diǎn)保存的是表的行的物理地址值。
MyISAM的索引是“非聚集”的囤躁，這么稱呼只是為了與InnoDB的聚集索引相區(qū)分冀痕。
InnoDB的B+Tree索引
InnoDB的索引實(shí)現(xiàn)方式與MyISAM截然不同，InnoDB的B+Tree葉子節(jié)點(diǎn)保存有完整的記錄信息狸演。這也解釋了上篇所說的InnoDB的索引與數(shù)據(jù)文件是同一個(gè)文件言蛇。
圖1是B+tree的主鍵索引，這種索引也叫做聚集索引宵距。InnoDB索引必須按照主鍵聚集腊尚，所有InnoDB必須要包含有主鍵。如果沒有顯示指定满哪，MySql會(huì)自動(dòng)選擇一個(gè)唯一標(biāo)識(shí)列或生成一個(gè)隱含字段作為主鍵婿斥。
圖2是InnoDB的B+Tree輔助索引，B+Tree的葉子節(jié)點(diǎn)只保存主鍵的值而不是行的地址值哨鸭。所以輔助索引的檢索需要檢索兩遍索引民宿。
因此，對(duì)于InnoDB的B+Tree索引使用有兩個(gè)注意點(diǎn)：
- 建議使用主鍵自增像鸡。由于B+Tree的特性活鹰，非自增的主鍵在插入時(shí)會(huì)造成B+Tree頻繁的分裂。
- 不建議主鍵字段過長(zhǎng)只估。由于所有的輔助索引都會(huì)檢索主鍵索引志群，過長(zhǎng)的主鍵索引會(huì)使輔助索引過大。
