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

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

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

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

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

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

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

例如這個B+樹的例子：

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

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

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

再來看MyISAM的主鍵索引，索引Key是主鍵值，索引Value是行的文件位置，通過這個位置可以直接讀取行。從這個圖上來看，MyISAM也是采用B+樹。

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

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

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

對比MyISAM和InnoDB的索引策略：

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

并且在InnoDB中，一個聚集索引是必須的，如果沒有定義主鍵，InnoDB也會自己隱含的建立一個聚集索引作為主鍵，因為InnoDB的主鍵索引還有個重要的功能就是行鎖，這在我的 另一篇文章 中分析過。

再來看看我們插入值時會發(fā)生什么：

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

如果主鍵不是順序的，我們來看看會發(fā)生什么，因為要按主鍵順序存放，數(shù)據(jù)會被不斷地移動，調(diào)整頁面。

所以： InnoDB引擎按主鍵順序插入記錄是非常必要的，否則性能將會面臨很大風險。

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

MySQL索引與存儲方式對性能的影響