很早之前，就從學校的圖書館借了MySQL技術內幕，InnoDB存儲引擎這本書，但一直草草閱讀，做的筆記也有些凌亂，趁著現在大四了，課程稍微少了一點，整理一下筆記，按照專題寫一些，加深一下印象，不枉讀了一遍書。與此同時，也加深一下對MySQL的了解，認識了原理，對優化的原則才有把握，對問題的分析才有源頭。

關于B+樹數據結構

①InnoDB存儲引擎支持兩種常見的索引。

一種是B+樹，一種是哈希。B+樹中的B代表的意思不是二叉（binary），而是平衡（balance），因為B+樹最早是從平衡二叉樹演化來的，但是B+樹又不是一個平衡二叉樹。

同時，B+樹索引并不能找到一個給定鍵值的具體行。B+樹索引只能找到的是 被查找數據行所在的頁 。然后數據庫通過把 頁 讀入內存，再在內存中進行查找，最后得到查找的數據。

先從二分查找法說起：

??? 二分查找法的基本思想是，將記錄排序（假如從小到大排序），然后采用跳躍式的方式進行查找，以有序數列的中點位置為比較對象，如果要找的元素小于該中點元素，那么查找左半部分，如果要找的元素大于該中點元素，那么久找右半部分。比如一組排好序的數：5 10 19 22 30 55 59 60 90， 如果我要查找60這個數字，那么先找30，發現30小于60，那么找30右半部分的中點59，發現59還是小了，那么找59右邊的數，從而找到了60，這樣通過不斷二分把查找需要的時間以指數級進行下降，算法效率到了Logn級別。

?

再說一下平衡二叉樹：

????

?

??????? 這是一幅平衡二叉樹，左子樹的值總是小于根的值，右子樹的值總是大于根的鍵值，因此可以通過中序遍歷（以遞歸的方式按照左中右的順序來訪問子樹），因此遍歷以后得到的輸出是9、17、28、35、39、56、65、87。這樣，如果要查找鍵值為28的記錄，先找到根，然后發現根大于28，找左子樹，發現左子樹的根17小于28，再找下一層右子樹，然后找到28。通過了3次查找找到了需要找的節點。但是如果二叉樹節點分布非常不均勻，就像第二張圖那樣，那么如果要查找39這個節點的話，查找效率和順序查找就差不多了，最差的結果就是查找65，那么二叉搜索樹就會完全退化成線性表。因此如果想要最大性能地構造一個二叉查找樹，需要這顆二叉查找樹是平衡的，平衡二叉樹對于查找的性能是比較高的，但是不是最高的，只是接近最高的性能。要達到最好的性能，需要建立一顆最優二叉樹，但是最優二叉樹的建立和維護需要大量的操作，因此用平衡 二叉樹就比較好。同時，平衡二叉樹多用于內存結構對象中，因此維護他的開銷相對較小。

②為什么使用B+樹呢？

雖然二叉查找樹和平衡二叉樹都能夠實現較快的數據查找，但是，由于數據庫的內容是存在于磁盤上，而磁盤IO與內存IO相比，比內存IO慢了10^5～10^6倍，為了減少磁盤IO，提高檢索速度，因而才用了B+樹這種數據結構。換言之，B+樹就是為磁盤或其他直接存取輔助設備而設計的一種 多路查找樹，是多叉樹 。

③什么是B+樹，其特性是什么

B+樹的概念還是過于復雜，直接上圖比較合適，來一張維基百科上的截圖：

從上面可以看出，所有記錄的節點都在頁節點中，并且是順序存放的，如果我們從最左邊的節點開始遍歷，可以得到的所有鍵值的順序是：1、2、3、4、5、6、7。

在B+樹中，所有記錄節點都是按照鍵值的大小順序存放在同一層的葉節點中，各個葉子節點通過指針進行連接。由于一個節點中存放了多條的數據，那么檢索的時候，進行的磁盤IO次數將會少掉很多。

在B+樹插入的時候，為了保持平衡，對于新插入的鍵值可能需要做大量的拆分頁操作，而B+樹主要用于磁盤，因此頁的拆分意味著 磁盤操作 ，因此應該在可能的情況下盡量減少頁的拆分。因此，B+樹提供了旋轉的功能。至于旋轉和刪除等內容，過于復雜，這篇筆記先不做記錄。只是了解使用B+樹的原因以及B+樹的特性。

關于索引

InnoDB存儲引擎使用聚集索引，實際的數據行和相關鍵值保存在一塊。因而，在InnoDB中要使用索引訪問數據始終需要兩次查找，而不是一次。因為索引葉子節點中存儲的不是行的物理位置，而是主鍵的值。即：二次索引-->主鍵-->數據的葉子-->通過數據葉字節點中的page directory找到數據行。

因為每一張InnoDB的表都會有一個主鍵索引，但是如果沒有顯式指定怎么辦？如果沒有手工去指定主鍵索引的話，那么，InnoDB引擎會指派一個unique的列作為主鍵，如果沒有unique的字段的話，那么便會自動生成一個隱含的列作為主鍵。

所以，在在InnoDB的設計中，應該盡可能的使用一個與業務無關auto_increment的自增主鍵，而不要去使用uuid之類的隨機（無序）的聚集鍵。同時，由于所有的索引都使用主鍵的索引，如果主鍵索引過長，也會使輔助索引相應的變大。

聚集索引的存儲并不是物理上的連續，而是邏輯上連續的。一方面，頁通過雙向鏈表連接，頁按照主鍵的順序排列；另一方面，每個頁中的記錄也是通過雙向鏈表進行維護，物理存儲上可以同樣不按照主鍵存儲。

對于目前的MySQL來說，所有的對于索引的添加或者刪除操作，MySQL數據庫都是要先創建一張新的臨時表，然后再把數據導入臨時表，再刪除原來的表，然后再把臨時表命名為原來的表。所以，如果一張表中數據太多的話，那么后期添加刪除索引需要花費很長的時間，因而最好在數據庫設計初期便設計好索引。

還有，雖然InnoDB存儲引擎從版本innoDB Plugin開始，支持一種稱為快速索引創建的方法，但是這種方法只限定于輔助索引，對于主鍵的創建和刪除還是需要重建一張表。

?

更好的資料：

[1] 敲代碼的張揚的《MySQL索引背后的數據結構和算法》

[2]《MySQL技術內幕：InnoDB存儲引擎》

MySQL：InnoDB存儲引擎的B+樹索引算法