索引： https://mp.weixin.qq.com/s/NDktOXaObJYQ1dM49oi9HA 面試題： https://mp.weixin.qq.com/s/aiD91w3ez48o-SiOAOSK-A # MySQL 數據庫面試題 https://mp.weixin.qq.com/s/8uMUu5vqPShVv4LatCD5qg [TOC] ## 各種樹的形式？ 1、二叉樹  **特點：** * 所有的非葉子節點最多擁有兩個子節點樹（左子樹和右子樹）。 * 所有結點存儲一個關鍵字。 * 節點的左右兒子，左邊是比該節點小的，右邊是比該節點大的。 **缺點：** 因為二叉搜索樹不存在平衡算法，所以在某些特殊的情況下，二叉搜索樹等同于線性。  紅黑樹和AVL樹是在二叉樹的基礎上機上加上平衡算法，紅黑樹確保沒有一條路徑會比其它路徑長出兩倍，它是弱平衡樹而AVL是嚴格的平衡，所以相對于二叉樹的蹩腳情況做了很大的改進，加入了平衡算法：  但是，同樣還是存在數據量大導致樹非常高的問題，所以現在的目標就是壓縮樹的高度。 ## 為什么要用 B+ 樹，為什么不用普通二叉樹？ 可以從幾個維度去看這個問題，查詢是否夠快，效率是否穩定，存儲數據多少，以及查找磁盤次數，為什么不是普通二叉樹，為什么不是平衡二叉樹，為什么不是B樹，而偏偏是 B+ 樹呢？ >為什么不是普通二叉樹？ 如果二叉樹特殊化為一個鏈表，相當于全表掃描。平衡二叉樹相比于二叉查找樹來說，查找效率更穩定，總體的查找速度也更快。 >為什么不是平衡二叉樹呢？ 我們知道，在內存比在磁盤的數據，查詢效率快得多。如果樹這種數據結構作為索引，那我們每查找一次數據就需要從磁盤中讀取一個節點，也就是我們說的一個磁盤塊，但是平衡二叉樹可是每個節點只存儲一個鍵值和數據的，如果是B樹，可以存儲更多的節點數據，樹的高度也會降低，因此讀取磁盤的次數就降下來啦，查詢效率就快啦。 >為什么不是 B 樹而是 B+ 樹呢？ B+ 樹非葉子節點上是不存儲數據的，僅存儲鍵值，而B樹節點中不僅存儲鍵值，也會存儲數據。innodb中頁的默認大小是16KB，如果不存儲數據，那么就會存儲更多的鍵值，相應的樹的階數（節點的子節點樹）就會更大，樹就會更矮更胖，如此一來我們查找數據進行磁盤的IO次數有會再次減少，數據查詢的效率也會更快。 B+ 樹索引的所有數據均存儲在葉子節點，而且數據是按照順序排列的，鏈表連著的。那么 B+ 樹使得范圍查找，排序查找，分組查找以及去重查找變得異常簡單。 > 為何不采用Hash方式？ 因為Hash索引底層是哈希表，哈希表是一種以key-value存儲數據的結構，所以多個數據在存儲關系上是完全沒有任何順序關系的，所以，對于區間查詢是無法直接通過索引查詢的，就需要全表掃描。所以，哈希索引只適用于等值查詢的場景。而B+ Tree是一種多路平衡查詢樹，所以他的節點是天然有序的（左子節點小于父節點、父節點小于右子節點），所以對于范圍查詢的時候不需要做全表掃描。 哈希索引不支持多列聯合索引的最左匹配規則，如果有大量重復鍵值得情況下，哈希索引的效率會很低，因為存在哈希碰撞問題。