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

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

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

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

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

平衡樹處在任何一個左邊的不平衡狀態都可以通過相應的旋轉操作轉移到右邊的平衡狀態。

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

例如這個B+樹的例子：

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

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

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

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

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

再看InnoDB的主鍵索引，索引Key是主鍵值，索引Value是整行的數據。

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

對比MyISAM和InnoDB的索引策略：

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

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

再來看看我們插入值時會發生什么：

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

如果主鍵不是順序的，我們來看看會發生什么，因為要按主鍵順序存放，數據會被不斷地移動，調整頁面。

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

?轉自：? http://www.penglixun.com/tech/database/mysql_index_store_perfomance_effect.html

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