小茵：我看你簡歷上寫了MySQL，對MySQL InnoDB引擎的索引了解嗎？

小奧：嗯啊唉窃，使用索引可以加快查詢速度，其實上就是將無序的數(shù)據(jù)變成有序（有序就能加快檢索速度）

小奧：在InnoDB引擎中纹笼，索引的底層數(shù)據(jù)結(jié)構(gòu)是B+樹

小茵：那為什么不使用紅黑樹或者B樹呢纹份？

小奧：MySQL的數(shù)據(jù)是存儲在硬盤的，在查詢時一般是不能「一次性」把全部數(shù)據(jù)加載到內(nèi)存中

小奧：紅黑樹是「二叉查找樹」的變種，一個Node節(jié)點只能存儲一個Key和一個Value

小奧：B和B+樹跟紅黑樹不一樣蔓涧，它們算是「多路搜索樹」件已，相較于「二叉搜索樹」而言，一個Node節(jié)點可以存儲的信息會更多元暴，「多路搜索樹」的高度會比「二叉搜索樹」更低篷扩。

小奧：了解了區(qū)別之后，其實就很容易發(fā)現(xiàn)茉盏，在數(shù)據(jù)不能一次加載至內(nèi)存的場景下鉴未，數(shù)據(jù)需要被檢索出來，選擇B或B+樹的理由就很充分了（一個Node節(jié)點存儲信息更多（相較于二叉搜索樹）鸠姨，樹的高度更低铜秆，樹的高度影響檢索的速度）

小奧：B+樹相對于B樹而言，它又有兩種特性享怀。

小奧：一羽峰、B+樹非葉子節(jié)點不存儲數(shù)據(jù)，在相同的數(shù)據(jù)量下添瓷，B+樹更加矮壯梅屉。（這個應(yīng)該不用多解釋了，數(shù)據(jù)都存儲在葉子節(jié)點上鳞贷，非葉子節(jié)點的存儲能存儲更多的索引坯汤，所以整棵樹就更加矮壯）

小奧：二、B+樹葉子節(jié)點之間組成一個鏈表搀愧，方便于遍歷查詢（遍歷操作在MySQL中比較常見）

image.png

小奧：我稍微解釋一下吧惰聂，你可以腦補下畫面

小奧：我們在MySQL InnoDB引擎下，每創(chuàng)建一個索引咱筛，相當于生成了一顆B+樹搓幌。

小奧：如果該索引是「聚集(聚簇)索引」，那當前B+樹的葉子節(jié)點存儲著「主鍵和當前行的數(shù)據(jù)」

小奧：如果該索引是「非聚簇索引」迅箩，那當前B+樹的葉子節(jié)點存儲著「主鍵和當前索引列值」

小奧：比如寫了一句sql：select * from user where id >=10溉愁，那只要定位到id為10的記錄，然后在葉子節(jié)點之間通過遍歷鏈表(葉子節(jié)點組成的鏈表)饲趋，即可找到往后的記錄了拐揭。

小奧：由于B樹是會在非葉子節(jié)點也存儲數(shù)據(jù)，要遍歷的時候可能就得跨層檢索奕塑，相對麻煩些堂污。

小奧：基于樹的層級以及業(yè)務(wù)使用場景的特性，所以MySQL選擇了B+樹作為索引的底層數(shù)據(jù)結(jié)構(gòu)龄砰。

小奧：對于哈希結(jié)構(gòu)盟猖，其實InnoDB引擎是「自適應(yīng)」哈希索引的（hash索引的創(chuàng)建由InnoDB存儲引擎引擎自動優(yōu)化創(chuàng)建讨衣，我們是干預(yù)不了）

小茵：嗯…那我了解了，順便想問下扒披，你知道什么叫做回表嗎值依？

小奧：所謂的回表其實就是，當我們使用索引查詢數(shù)據(jù)時碟案，檢索出來的數(shù)據(jù)可能包含其他列，但走的索引樹葉子節(jié)點只能查到當前列值以及主鍵ID颇蜡，所以需要根據(jù)主鍵ID再去查一遍數(shù)據(jù)价说，得到SQL 所需的列

小奧：舉個例子，我這邊建了給訂單號ID建了個索引风秤，但我的SQL 是：select orderId,orderName from orderdetail where orderId = 123

小奧：SQL都訂單ID索引鳖目，但在訂單ID的索引樹的葉子節(jié)點只有orderId和Id，而我們還想檢索出orderName缤弦，所以MySQL 會拿到ID再去查出orderName給我們返回领迈，這種操作就叫回表

image.png

小奧：想要避免回表，也可以使用覆蓋索引（能使用就使用碍沐，因為避免了回表操作）狸捅。

小奧：所謂的覆蓋索引，實際上就是你想要查出的列剛好在葉子節(jié)點上都存在累提，比如我建了orderId和orderName聯(lián)合索引尘喝，剛好我需要查詢也是orderId和orderName，這些數(shù)據(jù)都存在索引樹的葉子節(jié)點上斋陪，就不需要回表操作了朽褪。

小茵：既然你也提到了聯(lián)合索引，我想問下你了解最左匹配原則嗎无虚？

小奧：嗯缔赠，說明這個概念，還是舉例子比較容易說明

小奧：如有索引 (a,b,c,d)友题，查詢條件 a=1 and b=2 and c>3 and d=4嗤堰，則會在每個節(jié)點依次命中a、b咆爽、c梁棠，無法命中d

小奧：先匹配最左邊的，索引只能用于查找key是否存在（相等）斗埂，遇到范圍查詢 (>符糊、<、between呛凶、like左匹配)等就不能進一步匹配了男娄，后續(xù)退化為線性查找

小奧：這就是最左匹配原則

image.png

小茵：嗯嗯，我還想問下你們主鍵是怎么生成的？

小奧：主鍵就自增的

小茵：那假設(shè)我不用MySQL自增的主鍵模闲，你覺得會有什么問題呢建瘫？

小奧：首先主鍵得保證它的唯一性和空間盡可能短吧，這兩塊是需要考慮的尸折。

小奧：另外啰脚，由于索引的特性（有序），如果生成像uuid類似的主鍵实夹，那插入的的性能是比自增的要差的

小奧：因為生成的uuid橄浓，在插入時有可能需要移動磁盤塊（比如，塊內(nèi)的空間在當前時刻已經(jīng)存儲滿了亮航，但新生成的uuid需要插入已滿的塊內(nèi)荸实，就需要移動塊的數(shù)據(jù)）

小茵：OK…

image.png

本文總結(jié)：

• 為什么B+樹？數(shù)據(jù)無法一次load到內(nèi)存缴淋，B+樹是多路搜索樹准给，只有葉子節(jié)點才存儲數(shù)據(jù)，葉子節(jié)點之間鏈表進行關(guān)聯(lián)重抖。（樹矮露氮，易遍歷）
• 什么是回表？非聚簇索引在葉子節(jié)點只存儲列值以及主鍵ID仇哆，有條件下盡可能用覆蓋索引避免回表操作沦辙，提高查詢速度
• 什么是最左匹配原則？從最左邊為起點開始連續(xù)匹配讹剔，遇到范圍查詢終止
• 主鍵非自增會有什么問題油讯？插入效率下降，存在移動塊的數(shù)據(jù)問題