本文配圖來(lái)自《高性能MySQL(第二版)》。

在數(shù)據(jù)庫(kù)中，對(duì)性能影響最大的幾個(gè)策略包括數(shù)據(jù)庫(kù)的鎖策略、緩存策略、索引策略、存儲(chǔ)策略、執(zhí)行計(jì)劃優(yōu)化策略。
索引策略決定數(shù)據(jù)庫(kù)快速定位數(shù)據(jù)的效率，存儲(chǔ)策略決定數(shù)據(jù)持久化的效率。
MySQL中兩大主要存儲(chǔ)引擎MyISAM和InnoDB采用了不同的索引和存儲(chǔ)策略，本文將分析它們的異同和性能。

MySQL主要提供2種方式的索引：B-Tree（包括B+Tree）索引，Hash索引。
B樹(shù)索引具有范圍查找和前綴查找的能力，對(duì)于N節(jié)點(diǎn)的B樹(shù)，檢索一條記錄的復(fù)雜度為O(LogN)。
哈希索引只能做等于查找，但是無(wú)論多大的Hash表，查找復(fù)雜度都是O(1)。
顯然，如果值的差異性大，并且以等于查找為主，Hash索引是更高效的選擇，它有O(1)的查找復(fù)雜度。如果值的差異性相對(duì)較差，并且以范圍查找為主，B樹(shù)是更好的選擇，它支持范圍查找。

Hash索引各種引擎大同小異，沒(méi)有太多可探討性，本文主要討論不同形式的B樹(shù)索引。

B樹(shù)屬于二叉平衡樹(shù)，平衡樹(shù)就是任何一個(gè)節(jié)點(diǎn)的左右節(jié)點(diǎn)高度差距不能超過(guò)1的樹(shù)，這才是絕對(duì)平衡的樹(shù)。
平衡樹(shù)比較好的算法是AVL，它通過(guò)左旋、右旋及其組合的操作可以保證樹(shù)絕對(duì)平衡。
下面是AVL算法中的全部旋轉(zhuǎn)操作：

平衡樹(shù)處在任何一個(gè)左邊的不平衡狀態(tài)都可以通過(guò)相應(yīng)的旋轉(zhuǎn)操作轉(zhuǎn)移到右邊的平衡狀態(tài)。

數(shù)據(jù)庫(kù)采用的B樹(shù)只在葉子節(jié)點(diǎn)記錄信息，非葉子節(jié)點(diǎn)記錄的是范圍信息，這是與一般搜索樹(shù)不同的地方（一般搜索樹(shù)非葉子節(jié)點(diǎn)也記錄信息）。
這是一個(gè)B+樹(shù)的結(jié)構(gòu)，InnoDB的索引都采取了這種形式，它在B-樹(shù)的基礎(chǔ)上為每個(gè)葉子節(jié)點(diǎn)加了一個(gè)指針指向下一個(gè)葉子節(jié)點(diǎn)，這樣可以快速的進(jìn)行范圍查找。
MyISAM是否也是B+樹(shù)我還不能確定，但是B-樹(shù)我沒(méi)有想到可以快速進(jìn)行范圍查找的方法，應(yīng)該也是B+樹(shù)。

例如這個(gè)B+樹(shù)的例子：

如果我要查找名字以A開(kāi)頭的全部信息，我只要獲取第一個(gè)葉子節(jié)點(diǎn)，然后順序沿著指向下一個(gè)葉子的指針，直到發(fā)現(xiàn)當(dāng)年葉子節(jié)點(diǎn)已經(jīng)不是以A開(kāi)頭則中止，這樣只要搜索到第一個(gè)葉子節(jié)點(diǎn)(O(LogN))再沿著指針檢索(O(N))，就可以獲取全部索引，如果N個(gè)節(jié)點(diǎn)的表掃描M個(gè)連續(xù)值，就是O(LogN)+O(M)，如果B-樹(shù)則需要回溯到上層節(jié)點(diǎn)，這樣最差的效率是O(LogN)*M。

對(duì)于InnoDB，使用了一種改進(jìn)的B+樹(shù)索引，稱為聚集索引（Clustered Index），它的不同之處在于索引上不僅有索引值的信息，還有整個(gè)索引值所在行的信息，免去了一次通過(guò)索引值上的位置去取整行的操作。

假設(shè)我們有個(gè)表有(col1,col2)列，col1是主鍵，col2也建立索引。那么在MyISAM引擎中，文件會(huì)被這樣記錄，因?yàn)镸yISAM是按插入順序把數(shù)據(jù)寫(xiě)入文件。如果有刪除則空出位置，再次插入如果可以放下則會(huì)填充空白，對(duì)于不定長(zhǎng)的行，存儲(chǔ)引擎都會(huì)在分頁(yè)中預(yù)留位置，以供更新更長(zhǎng)的值（一般是VARCHAR），放不下則會(huì)添加到文件結(jié)尾，并從原位置刪除。所以有時(shí)候會(huì)有空間浪費(fèi)，需要Optimize Table來(lái)優(yōu)化。
因此： 定長(zhǎng)的行比不定長(zhǎng)的行效率高！把定長(zhǎng)數(shù)據(jù)和不定長(zhǎng)數(shù)據(jù)分開(kāi)存儲(chǔ)，很多時(shí)候可以提高效率。

再來(lái)看MyISAM的主鍵索引，索引Key是主鍵值，索引Value是行的文件位置，通過(guò)這個(gè)位置可以直接讀取行。從這個(gè)圖上來(lái)看，MyISAM也是采用B+樹(shù)。

MyISAM的非主鍵索引，跟逐漸索引沒(méi)有不同，也是索引行的文件位置。

再看InnoDB的主鍵索引，索引Key是主鍵值，索引Value是整行的數(shù)據(jù)。

InnoDB的非主鍵索引，索引Key是列值，索引Value是主鍵值。

對(duì)比MyISAM和InnoDB的索引策略：

可以發(fā)現(xiàn)MyISAM所有列的索引都是一樣，索引Key是列值，索引Value是行的文件位置。
InnoDB的主鍵索引包含了行的全部信息，索引Key是主鍵值，索引Value是整行的值。而非主鍵索引索引Key是列值，索引Value是主鍵值，取數(shù)據(jù)時(shí)到主鍵索引中取。

并且在InnoDB中，一個(gè)聚集索引是必須的，如果沒(méi)有定義主鍵，InnoDB也會(huì)自己隱含的建立一個(gè)聚集索引作為主鍵，因?yàn)镮nnoDB的主鍵索引還有個(gè)重要的功能就是行鎖，這在我的 另一篇文章 中分析過(guò)。

再來(lái)看看我們插入值時(shí)會(huì)發(fā)生什么：

InnoDB會(huì)按主鍵索引順序組織文件，如果按主鍵順序插入，可以直接在最尾部加入。并且只填充頁(yè)面的15/16，這樣可以預(yù)留部分空間以供行修改，這樣組織的數(shù)據(jù)是非常緊湊的。

如果主鍵不是順序的，我們來(lái)看看會(huì)發(fā)生什么，因?yàn)橐粗麈I順序存放，數(shù)據(jù)會(huì)被不斷地移動(dòng)，調(diào)整頁(yè)面。

所以： InnoDB引擎按主鍵順序插入記錄是非常必要的，否則性能將會(huì)面臨很大風(fēng)險(xiǎn)。

?轉(zhuǎn)自：? http://www.penglixun.com/tech/database/mysql_index_store_perfomance_effect.html

MySQL索引與存儲(chǔ)方式對(duì)性能的影響