多版本並發控制

mysql的大多數事務型儲存引擎實現的都不是簡單的行級鎖定。基於提升並發性能的考慮，它們一般都同時實現了多版本並發控制。

可以認為MVCC是行級鎖定的變種，但是它很多情況下避免了加鎖操作，因為開銷更低。

InnoDB的MVCC，是透過在每行記錄最後保存的兩個隱藏的列來實現，這兩個列，一個保存了行的創建時間，一個保存行的過期時間（或刪除時間），當然儲存的並不是實際的時間值，而是系統版本好。每開始一個新的事務，系統版本號就會自動遞增。事務開始時刻的系統版本號碼會作為交易的版本號，用來查詢到的每行版本號進行比較。

REPEATABLE READ隔離等級下，MVCC的實作：

#SELECT

InnoDB之查找版本早於目前事務版本號碼的資料行，這樣可以確保事務讀取的行，要么是在事務開始前已經存在，要么是事務本身插入或修改過的。
行的刪除版本要么未定義，要么大於當前事務版本號，這可以確保事務讀取到的行在事務開始之前未被刪除。

INSERT

#InnoDB為新插入的每一行儲存目前系統版本號碼作為行版本號。

DELETE

#InnoDB為刪除的每一行儲存目前系統版本號碼作為行刪除標識。

UPDATE

#InnoDB為插入一航新記錄，儲存目前系統版本號作為行版本號，同時儲存目前系統版本號到原來的行作為行刪除版本號。

MVCC只在REPEATABLE READ跟READ COMMITED兩個隔離等級工作。其他兩個隔離等級都和MVCC不相容。因為READ UNCOMMITED總是會讀取最新的資料行，而不是符合目前交易版本的資料行。而SERIALIZABLE則會對所有讀取的資料的行都加鎖。

儲存引擎

InnoDB儲存引擎

InnoDB是MYSQL的預設事務型引擎，也是最重要、使用最廣泛的儲存引擎。除非有非常特別的原因需要使用其他的儲存引擎，否則應該優先考慮InnoDB引擎。

InnoDB採用MVCC來支援高並發，並且實現了四個標準的隔離等級。預設等級是REPEATABLE READ（可重複讀取），並且透過間隙鎖定MVCC策略來防止幻讀的實現，間隙鎖使得InnoDB不僅鎖定查詢設計的行，還會對索引中的間隙進行鎖定，以防止幻影行的插入。

間隙鎖：當我們用範圍條件而不是相等條件檢索數據，並請求共享或排他鎖時，InnoDB會為符合條件的已有數據記錄的索引項加鎖；對於鍵值在條件範圍內但不存在的記錄，稱為“間隙（GAP)”，InnoDB也會對這個“間隙”加鎖，這種鎖機制就是所謂的間隙鎖（Next-Key鎖）。
參考：間隙鎖（Next-Key鎖定）

主索引是叢集索引，在索引中保存了數據，從而避免直接讀取磁碟，因此對查詢效能有很大的提升。

InnoDB內部做了很多優化，包括從磁碟讀取資料時採用的可預測性預讀，能夠自動在記憶體中創建hash索引以加速度操作的自適應雜湊索引，以及能夠加速插入操作的插入緩衝區等。

MyISAM儲存引擎

在mysql5.1以及之前的版本，MyISAM是預設的儲存引擎。 MyISAM提供了大量的特性，包括全文索引、壓縮、空間函數等，但是不支援事務和行級鎖，而且有一個毫無疑問的缺陷是崩潰之後無法安全恢復。

對於唯讀的資料、或表格比較小、可以忍受修復操作，則依然可以使用MyISAM引擎。

建立MyISAM表的時候，如果指定了DELAY_KEY_WRITE選項，在每次修改執行完成時，不會立刻將修改的索引資料寫入磁碟，而是會寫入記憶體中的鍵緩衝區，只有在清理鍵緩衝區或關閉表的時候才會將對應的索引區塊寫入到磁碟。這種方式可以大幅提升寫入效能，但是在資料庫或主機崩潰時會造成索引損壞，需要執行修復操作。

比較

交易：InnoDB支援事務，MyISAM不支援交易。
鎖定粒度：InnoDB支援表級鎖定行級鎖定，而MyISAM只支援表級鎖定。
外鍵：InnoDB支援外鍵。
備份：InnoDB支援熱備份，但需要工具。
崩潰復原：MyISAM崩潰後發生損壞的機率比InnoDB高很多，而且復原的速度也比較慢。
其他功能：MyISAM支援全文索引、壓縮、空間函數等特性。

備份的類型

冷備（cold backup）：需要關mysql服務，讀寫請求都不允許狀態下進行；
溫備（warm backup）：服務在線，但僅支援讀取請求，不允許寫入請求；
熱備（hot backup）：備份的同時，業務不受影響。

索引

##（也稱為「鍵(key)」）是儲存引擎用於快速尋找記錄中的一種資料結構。

B-Tree索引

大多數mysql引擎都支援這種索引。

雖然使用術語「B-Tree"，但不同的儲存引擎可能使用不同的儲存結構，NDB叢集儲存引擎內部實際使用的是T-Tree，InnoDB則使用B Tree。

B-Tree索引能夠加快存取數據的速度，因為儲存引擎不需要進行全表掃描來獲取需要的數據，取而代之的是從索引的根節點開始搜索，因此查找速度會快很多。

B-Tree對索引列是順序組織儲存的，很適合尋找範圍資料。因為索引樹是有順序的，所以除了使用者查找，還可以用來排序和分組。

可以指定多個欄位作為索引列，多個索引列共同組成索引鍵。 B-Tree索引適用於全鍵值、鍵值範圍或鍵前綴查找，其中鍵前綴查找只適用與根據最左前綴查找。查找一定得按照索引的最左列開始。

B-Tree索引的資料結構

B-Tree

為了描述B-Tree，先定義一條數據記錄為二元組[key,data]，key作為記錄的鍵值，對於不同資料記錄，key是互不相同的，data為資料記錄除key外的資料。

所有節點具有相同的深度，也就是說B-Tree是平衡的。
一個節點中的key從左到右非遞減排列。
如果某個指標的左右相鄰 key 分別是 keyi 和 keyi 1，且不為 null，則該指標指向節點的所有 key 大於等於 keyi 且小於等於 keyi 1。

查找演算法：首先在根節點進行二分查找，如果找到則傳回對應節點的data，否則在對應區間的指標指向的節點遞迴進行查找。

由於插入刪除新的資料記錄會破壞B-Tree的性質，因此在插入刪除時，需要對樹進行一個分裂、合併、旋轉等操作以保持 B-Tree 性質。

MYSQL_多版本並發控制、儲存引擎、索引簡介

B Tree

與B-Tree相比，B Tree有以下特點：

#每個節點的指標上限為2d而不是2d 1（d為B-Tree的度數）。
內節點不儲存data，只儲存key；外節點不儲存指標。

MYSQL_多版本並發控制、儲存引擎、索引簡介

#有順序存取指標的B Tree

一般在資料庫系統或檔案系統中使用的B Tree結構都在經典B Tree的基礎上進行了優化，增加了順序存取指標。

MYSQL_多版本並發控制、儲存引擎、索引簡介

這個最佳化的目的是為了提供區間存取的效能，例如圖中如果要查詢key為18到49的所有記錄。

優勢

紅黑樹等平衡樹也可以用來實現索引，但是檔案系統及資料庫系統普遍採用B-Tree作為索引結構，主要有以下兩個原因：

更好的檢索次數：平衡樹檢索資料的時間複雜度等於樹高h，而樹高大致為O(h) = O(logN)，其中d為每個節點的出度。紅黑樹的出度為2，而B-Tree的出度一般都很大，紅黑樹的樹高h明顯比B-Tree打非常多，因此檢索次數也就更多。 B Tree相比較B-Tree比較適合外存索引，因為B Tree內節點去掉了data域，因此可以有更大的出度，檢索效率會更高。
利用電腦預讀特性：為了減少磁碟 I/O，磁碟往往不是嚴格按需讀取，而是每次都會預讀。這樣做的理論基礎是電腦科學中著名的局部性原理：當一個資料被用到時，其附近的資料也通常會馬上被使用。預讀過程中，磁碟進行順序讀取，順序讀取不需要進行磁碟尋道，並且只需要很短的旋轉時間，因此速度會非常快。作業系統一般將記憶體和磁碟分割成固態大小的區塊，每一塊稱為一頁，記憶體與磁碟以頁為單位交換資料。資料庫系統將索引的一個節點的大小設定為頁的大小，使得一次 I/O 就能完全載入一個節點，並且可以利用預讀特性，相鄰的節點也能夠被預先載入。

參考：MySQL索引背後的資料結構及演算法原理