資料庫索引，到底是什麼做的？ 問題1. 資料庫為什麼要設計索引？ 圖書館存了1000W本圖書，要從中找到《架構師之路》，一本本查，要查到什麼時候去？ 於是，圖書管理員設計了一套規則： (1)一樓放歷史類，二樓放文學類，三樓放IT類… (2)IT類，又分軟體類，硬體類… (3)軟體類，又按照書名音序排 ...
資料庫索引，到底是什麼做的？
問題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需求：
-
分組：group by
-
排序：order by
-
比較：<、>
-
…
哈希型的索引，時間複雜度會退化為O(n)，而樹型的“有序”特性，依然能夠保持O(log(n)) 的高效率。
任何脫離需求的設計都是耍流氓。
多說一句，InnoDB並不支持哈希索引。
問題3. 資料庫索引為什麼使用B+樹？
為了保持知識體系的完整性，簡單介紹下幾種樹。
第一種：二叉搜索樹
二叉搜索樹，如上圖，是最為大家所熟知的一種數據結構，就不展開介紹了，它為什麼不適合用作資料庫索引？
(1)當數據量大的時候，樹的高度會比較高，數據量大的時候，查詢會比較慢；
(2)每個節點只存儲一個記錄，可能導致一次查詢有很多次磁碟IO；
畫外音：這個樹經常出現在大學課本里，所以最為大家所熟知。
第二種：B樹
B樹，如上圖，它的特點是：
(1)不再是二叉搜索，而是m叉搜索；
(2)葉子節點，非葉子節點，都存儲數據；
(3)中序遍歷，可以獲得所有節點；
畫外音，實在不想介紹這個特性：非根節點包含的關鍵字個數j滿足，(┌m/2┐)-1 <= j <= m-1，節點分裂時要滿足這個條件。
B樹被作為實現索引的數據結構被創造出來，是因為它能夠完美的利用“局部性原理”。
什麼是局部性原理？
局部性原理的邏輯是這樣的：
(1)記憶體讀寫塊，磁碟讀寫慢，而且慢很多；
(2)磁碟預讀：磁碟讀寫並不是按需讀取，而是按頁預讀，一次會讀一頁的數據，每次載入更多的數據，如果未來要讀取的數據就在這一頁中，可以避免未來的磁碟IO，提高效率；
畫外音：通常，一頁數據是4K。
(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個節點，1000*500=50W個KEY，大小1000*4K=4M
三層樹：1000*1000個節點，1000*1000*500=5億個KEY，大小1000*1000*4K=4G
畫外音：額，幫忙看下有沒有算錯。
可以看到，存儲大量的數據（5億），並不需要太高樹的深度（高度3），索引也不是太占記憶體（4G）。
總結
-
資料庫索引用於加速查詢
-
雖然哈希索引是O(1)，樹索引是O(log(n))，但SQL有很多“有序”需求，故資料庫使用樹型索引
-
InnoDB不支持哈希索引
-
數據預讀的思路是：磁碟讀寫並不是按需讀取，而是按頁預讀，一次會讀一頁的數據，每次載入更多的數據，以便未來減少磁碟IO
-
局部性原理：軟體設計要儘量遵循“數據讀取集中”與“使用到一個數據，大概率會使用其附近的數據”，這樣磁碟預讀能充分提高磁碟IO
-
資料庫的索引最常用B+樹：
(1)很適合磁碟存儲，能夠充分利用局部性原理，磁碟預讀；
(2)很低的樹高度，能夠存儲大量數據；
(3)索引本身占用的記憶體很小；
(4)能夠很好的支持單點查詢，範圍查詢，有序性查詢；
