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

關(guān)于B+樹數(shù)據(jù)結(jié)構(gòu)

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

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

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

先從二分查找法說起：

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

?

再說一下平衡二叉樹：

????

?

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

②為什么使用B+樹呢？

雖然二叉查找樹和平衡二叉樹都能夠?qū)崿F(xiàn)較快的數(shù)據(jù)查找，但是，由于數(shù)據(jù)庫的內(nèi)容是存在于磁盤上，而磁盤IO與內(nèi)存IO相比，比內(nèi)存IO慢了10^5～10^6倍，為了減少磁盤IO，提高檢索速度，因而才用了B+樹這種數(shù)據(jù)結(jié)構(gòu)。換言之，B+樹就是為磁盤或其他直接存取輔助設(shè)備而設(shè)計的一種 多路查找樹，是多叉樹 。

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

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

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

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

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

關(guān)于索引

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

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

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

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

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

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

?

更好的資料：

[1] 敲代碼的張揚的《MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)和算法》

[2]《MySQL技術(shù)內(nèi)幕：InnoDB存儲引擎》

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