數據庫索引，終於懂了
不少朋友留言問 MySQL 索引底層的實現，讓我講講 B + 樹。知其然，知其所以然，講懂 B + 樹其實不難，今天更多聊聊 “數據庫索引，爲什麼設計成這樣”。
問題 1. 數據庫爲什麼要設計索引？
圖書館存了 1000W 本圖書，要從中找到《架構師之路》，一本本查，要查到什麼時候去？
於是，圖書管理員設計了一套規則：
（1）一樓放歷史類，二樓放文學類，三樓放 IT 類…
（2）IT 類，又分軟件類，硬件類…
（3）軟件類，又按照書名排序…
以便快速找到一本書。
與之類比，數據庫存儲了 1000W 條數據，要從中找到 name=”shenjian” 的記錄，一條條查，要查到什麼時候去？
於是，要有索引，用於提升數據庫的查找速度。
問題 2. 哈希 (hash) 比樹 (tree) 更快，索引結構爲什麼要設計成樹型？
加速查找速度的數據結構，常見的有兩類：
（1）哈希，例如 HashMap，查詢 / 插入 / 修改 / 刪除的平均時間複雜度都是 O(1)；
（2）樹，例如平衡二叉搜索樹，查詢 / 插入 / 修改 / 刪除的平均時間複雜度都是 O(lg(n))；
可以看到，不管是讀請求，還是寫請求，哈希類型的索引，都要比樹型的索引更快一些，那爲什麼，索引結構要設計成樹型呢？
畫外音：80% 的同學，面試都答不出來。
索引設計成樹形，和 SQL 的需求相關。
對於這樣一個單行查詢的 SQL 需求：
select * from t where name=”shenjian”;
確實是哈希索引更快，因爲每次都只查詢一條記錄。
畫外音：所以，如果業務需求都是單行訪問，例如 passport，確實可以使用哈希索引。
但是對於排序查詢的 SQL 需求：
（1）分組：group by
（2）排序：order by
（3）比較：<、>
（4）…
哈希型的索引，時間複雜度會退化爲 O(n)，而樹型的 “有序” 特性，依然能夠保持 O(log(n)) 的高效率。
任何脫離需求的設計都是耍流氓。
多說一句，InnoDB 並不支持手動建立哈希索引。
畫外音：自適應 hash 索引，是 InnoDB 內核機制。
問題 3. 數據庫索引爲什麼使用 B + 樹？
爲了保持知識體系的完整性，簡單介紹下幾種樹。
第一種：二叉搜索樹
二叉搜索樹，如上圖，是最爲大家所熟知的一種數據結構，就不展開介紹了，它爲什麼不適合用作數據庫索引？
（1）當數據量大的時候，樹的高度會比較高，數據量大的時候，查詢會比較慢；
（2）每個節點只存儲一個記錄，可能導致一次查詢有很多次磁盤 IO；
畫外音：這個樹經常出現在大學課本里，所以最爲大家所熟知。
第二種：B 樹
B 樹，如上圖，它的特點是：
（1）不再是二叉搜索，而是 m 叉搜索；
（2）葉子節點，非葉子節點，都存儲數據；
（3）中序遍歷，可以獲得所有節點；
畫外音，實在不想介紹這個特性：非根節點包含的關鍵字個數 j 滿足，(┌m/2┐)-1 <= j <= m-1，節點分裂時要滿足這個條件。
B 樹被作爲實現索引的數據結構被創造出來，是因爲它能夠完美的利用 “局部性原理”。
什麼是局部性原理？
局部性原理的邏輯是這樣的：
（1）內存讀寫塊，磁盤讀寫慢，而且慢很多；
（2）磁盤預讀：磁盤讀寫並不是按需讀取，而是按頁預讀，一次會讀一頁的數據，每次加載更多的數據，如果未來要讀取的數據就在這一頁中，可以避免未來的磁盤 IO，提高效率；
畫外音：通常，操作系統一頁數據是 4K，MySQL 的一頁是 16K。
（3）局部性原理：軟件設計要儘量遵循 “數據讀取集中” 與“使用到一個數據，大概率會使用其附近的數據”，這樣磁盤預讀能充分提高磁盤 IO；
B 樹爲何適合做索引？
（1）由於是 m 分叉的，高度能夠大大降低；
（2）每個節點可以存儲 j 個記錄，如果將節點大小設置爲頁大小，例如 4K，能夠充分的利用預讀的特性，極大減少磁盤 IO；
第三種：B + 樹
B + 樹，如上圖，仍是 m 叉搜索樹，在 B 樹的基礎上，做了一些改進：
（1）非葉子節點不再存儲數據，數據只存儲在同一層的葉子節點上；
畫外音：B + 樹中根到每一個節點的路徑長度一樣，而 B 樹不是這樣。
（2）葉子之間，增加了鏈表，獲取所有節點，不再需要中序遍歷；
這些改進讓 B + 樹比 B 樹有更優的特性：
（1）範圍查找，定位 min 與 max 之後，中間葉子節點，就是結果集，不用中序回溯；
畫外音：範圍查詢在 SQL 中用得很多，這是 B + 樹比 B 樹最大的優勢。
（2）葉子節點存儲實際記錄行，記錄行相對比較緊密的存儲，適合大數據量磁盤存儲；非葉子節點存儲記錄的 PK，用於查詢加速，適合內存存儲；
（3）非葉子節點，不存儲實際記錄，而只存儲記錄的 KEY 的話，那麼在相同內存的情況下，B + 樹能夠存儲更多索引；
最後，量化說下，爲什麼 m 叉的 B + 樹比二叉搜索樹的高度大大大大降低？
大概計算一下：
（1）局部性原理，將一個節點的大小設爲一頁，一頁 4K，假設一個 KEY 有 8 字節，一個節點可以存儲 500 個 KEY，即 j=500；
（2）m 叉樹，大概 m/2<= j <=m，即可以差不多是 1000 叉樹；
（3）那麼：
一層樹：1 個節點，1*500 個 KEY，大小 4K
二層樹：1000 個節點，1000500=50W 個 KEY，大小 10004K=4M
三層樹：10001000 個節點，10001000500=5 億個 KEY，大小 10001000*4K=4G
畫外音：額，幫忙看下有沒有算錯。
可以看到，存儲大量的數據（5 億），並不需要太高樹的深度（高度 3），索引也不是太佔內存（4G）。
總結
（1）數據庫索引用於加速查詢；
（2）雖然哈希索引是 O(1)，樹索引是 O(log(n))，但 SQL 有很多 “有序” 需求，故數據庫使用樹型索引；
（3）InnoDB 不支持手動創建哈希索引；
（4）數據預讀的思路是：磁盤讀寫並不是按需讀取，而是按頁預讀，一次會讀一頁的數據，每次加載更多的數據，以便未來減少磁盤 IO
（5）局部性原理：軟件設計要儘量遵循 “數據讀取集中” 與“使用到一個數據，大概率會使用其附近的數據”，這樣磁盤預讀能充分提高磁盤 IO
（5）數據庫的索引最常用 B + 樹：
- 很適合磁盤存儲，能夠充分利用局部性原理，磁盤預讀；
- 很低的樹高度，能夠存儲大量數據；
- 索引本身佔用的內存很小；
- 能夠很好的支持單點查詢，範圍查詢，有序性查詢；
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/0x5T-wbAoNVHkKTT61lIUQ