前幾天在看 2018 雲棲大會，來自中科院計算所的陳世敏研究員在“資料庫內核專場”做了一場《NVM在資料庫領域的研究和探索 》的報告演講。在30分鐘的演講中，其中有近10頁PPT的內容和B+Tree這種索引有關。 例如其中的兩頁 為此，將自己對索引相關的理解梳理如下： 1.什麼是索引？ 索引是磁碟上 ...
前幾天在看 2018 雲棲大會，來自中科院計算所的陳世敏研究員在“資料庫內核專場”做了一場《NVM在資料庫領域的研究和探索 》的報告演講。在30分鐘的演講中，其中有近10頁PPT的內容和B+Tree這種索引有關。
例如其中的兩頁
為此，將自己對索引相關的理解梳理如下：
1.什麼是索引？
索引是磁碟上組織數據記錄的一種數據結構，它用來優化某類數據查詢的操作。索引使得我們能夠有效地查詢滿足索引的查詢碼（搜索碼）欄位上的查詢條件的那些記錄。可以在一個給定的數據記錄集合上創建多個索引，每個索引有不同的查詢碼（搜索碼）。
2.主鍵 與 聚集索引
主鍵是一種約束，主要用來保證數據的完整性，而聚集索引是一種文件（數據記錄）的組織形式，索引的目的是查詢優化，兩者是不同的概念。
但兩者並非完全沒有聯繫，比如SQL SERVER預設是在主鍵上建立聚集索引的。在大多數情況下，預設建立的聚集索引是不起作用的，還是需要結合實際的業務場景來考慮，特別是在選擇自增ID或GUID這種主鍵的情況。
創建主鍵,不可以再允許為Null值的列上創建,並且既有的數據記錄中不可以有重覆值,否則報錯。聚集索引沒有限制建立聚集索引的列一定必須 not null ，並且數據即可以唯一，也可以不唯一。
3.聚集索引 與 非聚集索引
聚集索引葉子層：具體的數據，按照聚集鍵順序存儲
非聚集索引葉子層：指針，指針有2類數據 RID或者是聚集鍵。
- RID（堆表） RID【文件號：頁號：槽號 8 bytes — 文件號（4 bytes）：頁號（2 bytes）：槽號（2 bytes）】
- 聚集鍵（聚集表） 聚集鍵（聚集索引主鍵）
聚集鍵與非聚集索引有緊密的依賴關係,聚集鍵在每個非聚集索引葉子層都保存，慎重選擇聚集鍵。
非聚集索引是第二索引， 對提高查詢性能至關重要。
4.什麼是書簽查找
非聚集索引不包含查詢需要的列，需要通過書簽查找來獲取所查詢列信息。常見的書簽查找有兩種：一個是鍵查找（key lookup，聚簇索引的表），還有一個就是RID查找（RID lookup，堆表）。
使用覆蓋索引，讓非聚集索引包含查詢列，從而避免書簽查找。但是非聚集索引最大鍵列數為16，最大索引鍵大小為900位元組，所以覆蓋索引還是有限制的，此時可以考慮 使用include屬性來包含非鍵列。
5.二叉樹 與 B-樹
索引的存放為什麼不用大家熟悉的二叉樹，從數據結構上來講 二叉樹的查找速度最快和比較次數最少。主要考慮的因此是I/O的次數。查找時，在某非葉子節點決定下一步向左（小於）還是向右（大於或等於）的判斷比較時，都需要將節點數據I/O到記憶體中，即需要發生一次I/O。所以最壞的情況下磁碟IO的次數有數的高度來決定（最壞的情況可以理解為想要查找的數在葉子節點上）。所以減少磁碟I/O的次數就必須要壓縮樹的高度。從資料庫的基本原理，我們就知道，頁I/O（從磁碟輸入到主存及從主存輸出到磁碟）的代價代表了典型的資料庫操作代價，因此需要十分小心地優化資料庫系統來減少這個代價。而B-樹正好瞞住了這個要求。在B-樹中，每一個非葉子節點可以容納很多節點指針，從而樹的高度在實際中很少超過3或4.一個平衡數的高度是從根到葉子的路徑長度。實際上，根通常是存放在緩衝池中，因為它要被頻繁的訪問，所以一個高度為3的樹，其實只需要3次I/O。
非葉子節點的平均孩子樹稱為樹的扇出（fan-out）。如果每一個非葉子節點有n個孩子，則高度為h的樹有nh葉子頁。實際 上 ，節點並沒有相同數量的孩子，但是用n的平均數值F，我們可以獲得葉子頁數量的很好的近似結果Fh。在實際情況中，F至少為100，這意味著高度為4的樹包含1億個葉子頁。因此，可以只用4次I/O就從有1億個葉子頁的文件中搜索到想要的頁。與之相似，採用二分法搜索同樣的文件則需要花費log2100000000 （超過25）次I/0
6.B-樹 與 B+樹
與B-Tree相比，B+Tree有以下不同點：
每個節點的指針上限為2d而不是2d+1。
B+樹是一種保證在一顆給定樹中從根到葉所有路徑都等長的索引結構，即，這種樹的高度總是平衡的。
內節點不存儲data，只存儲key。 B+Tree的搜索與B-Tree也基本相同，區別是B+Tree只有達到葉子結點才命中（B-Tree可以在非葉子結點命中）。
在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，形成了帶有順序訪問指針的B+Tree。因此在搜索中出現的磁碟I/O數就等於從根節點到頁節點的路徑長加上滿足條件的數據項的葉子頁的個數。
優化的目的是為了提高區間訪問的性能，只需順著節點和指針順序遍歷就可以一次性訪問到所有數據節點，極大提到了區間查詢效率。
7.B+樹 與 InnoDB
在MySQL InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含欄位作為主鍵，這個欄位長度為6個位元組，類型為長整形。InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域。聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
