面試官：我看你簡歷上寫了MySQL，對MySQL InnoDB引擎的索引了解嗎？
候選者：嗯啊，使用索引可以加快查詢速度，其實上就是將無序的資料變成有序（有序就能加快檢索速度）
候選者：在InnoDB引擎中，索引的底層資料結構是B+樹
面試官：那為什么不使用紅黑樹或者B樹呢？
候選者：MySQL的資料是存盤在硬碟的，在查詢時一般是不能「一次性」把全部資料加載到記憶體中
候選者：紅黑樹是「二叉查找樹」的變種，一個Node節點只能存盤一個Key和一個Value
候選者：B和B+樹跟紅黑樹不一樣，它們算是「多路搜索樹」，相較于「二叉搜索樹」而言，一個Node節點可以存盤的資訊會更多，「多路搜索樹」的高度會比「二叉搜索樹」更低，
候選者：了解了區別之后，其實就很容易發現，在資料不能一次加載至記憶體的場景下，資料需要被檢索出來，選擇B或B+樹的理由就很充分了（一個Node節點存盤資訊更多（相較于二叉搜索樹），樹的高度更低，樹的高度影響檢索的速度）
候選者：B+樹相對于B樹而言，它又有兩種特性，
候選者：一、B+樹非葉子節點不存盤資料，在相同的資料量下，B+樹更加矮壯，（這個應該不用多解釋了，資料都存盤在葉子節點上，非葉子節點的存盤能存盤更多的索引，所以整棵樹就更加矮壯）
候選者：二、B+樹葉子節點之間組成一個鏈表，方便于遍歷查詢（遍歷操作在MySQL中比較常見）
候選者：我稍微解釋一下吧，你可以腦補下畫面
候選者：我們在MySQL InnoDB引擎下，每創建一個索引，相當于生成了一顆B+樹，
候選者：如果該索引是「聚集(聚簇)索引」，那當前B+樹的葉子節點存盤著「主鍵和當前行的資料」
候選者：如果該索引是「非聚簇索引」，那當前B+樹的葉子節點存盤著「主鍵和當前索引列值」
候選者：比如寫了一句sql：select * from user where id >=10，那只要定位到id為10的記錄，然后在葉子節點之間通過遍歷鏈表(葉子節點組成的鏈表)，即可找到往后的記錄了，
候選者：由于B樹是會在非葉子節點也存盤資料，要遍歷的時候可能就得跨層檢索，相對麻煩些，
候選者：基于樹的層級以及業務使用場景的特性，所以MySQL選擇了B+樹作為索引的底層資料結構，
候選者：對于哈希結構，其實InnoDB引擎是「自適應」哈希索引的（hash索引的創建由InnoDB存盤引擎引擎自動優化創建，我們是干預不了）
面試官：嗯...那我了解了，順便想問下，你知道什么叫做回表嗎？
候選者：所謂的回表其實就是，當我們使用索引查詢資料時，檢索出來的資料可能包含其他列，但走的索引樹葉子節點只能查到當前列值以及主鍵ID，所以需要根據主鍵ID再去查一遍資料，得到SQL 所需的列
候選者：舉個例子，我這邊建了給訂單號ID建了個索引，但我的SQL 是：select orderId,orderName from orderdetail where orderId = 123
候選者：SQL都訂單ID索引，但在訂單ID的索引樹的葉子節點只有orderId和Id，而我們還想檢索出orderName，所以MySQL 會拿到ID再去查出orderName給我們回傳，這種操作就叫回表
候選者：想要避免回表，也可以使用覆寫索引（能使用就使用，因為避免了回表操作），
候選者：所謂的覆寫索引，實際上就是你想要查出的列剛好在葉子節點上都存在，比如我建了orderId和orderName聯合索引，剛好我需要查詢也是orderId和orderName，這些資料都存在索引樹的葉子節點上，就不需要回表操作了，
面試官：既然你也提到了聯合索引，我想問下你了解最左匹配原則嗎？
候選者：嗯，說明這個概念，還是舉例子比較容易說明
候選者：如有索引 (a,b,c,d)，查詢條件 a=1 and b=2 and c>3 and d=4，則會在每個節點依次命中a、b、c，無法命中d
候選者：先匹配最左邊的，索引只能用于查找key是否存在（相等），遇到范圍查詢 (>、<、between、like左匹配)等就不能進一步匹配了，后續退化為線性查找
候選者：這就是最左匹配原則
面試官：嗯嗯，我還想問下你們主鍵是怎么生成的？
候選者：主鍵就自增的
面試官：那假設我不用MySQL自增的主鍵，你覺得會有什么問題呢？
候選者：首先主鍵得保證它的唯一性和空間盡可能短吧，這兩塊是需要考慮的，
候選者：另外，由于索引的特性（有序），如果生成像uuid類似的主鍵，那插入的的性能是比自增的要差的
候選者：因為生成的uuid，在插入時有可能需要移動磁盤塊（比如，塊內的空間在當前時刻已經存盤滿了，但新生成的uuid需要插入已滿的塊內，就需要移動塊的資料）
面試官：OK...
本文總結：
- 為什么B+樹？資料無法一次load到記憶體，B+樹是多路搜索樹，只有葉子節點才存盤資料，葉子節點之間鏈表進行關聯，（樹矮，易遍歷）
- 什么是回表？非聚簇索引在葉子節點只存盤列值以及主鍵ID，有條件下盡可能用覆寫索引避免回表操作，提高查詢速度
- 什么是最左匹配原則？從最左邊為起點開始連續匹配，遇到范圍查詢終止
- 主鍵非自增會有什么問題？插入效率下降，存在移動塊的資料問題
歡迎關注我的微信公眾號【Java3y】來聊聊Java面試
【對線面試官-移動端】系列 一周兩篇持續更新中！
【對線面試官-電腦端】系列 一周兩篇持續更新中！
原創不易！！求三連！！
更多的文章可往：文章的目錄導航轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/296713.html
標籤：Java
上一篇：面試官：你說你精通Redis，你看過持久化的配置嗎？
下一篇：java修飾符