InnoDB索引實作

         對于InnoDB存儲引擎的表，記錄預設會按一定順序儲存，如果有明确定義的主鍵，則按照主鍵順序儲存。如果沒有主鍵，但是有唯一索引，就按照唯一索引的順序儲存。如果既沒有主鍵也沒有唯一索引，表中會自動生成一個内部列，按照這個列的順序儲存。按照主鍵或内部列的通路是最快的，索引InnoDB表盡量自己指定主鍵，當表中同時有幾個列都是唯一的，都可以作為主鍵的時候，要選擇最常作為通路條件的列作為主鍵，提高查詢效率。另外，InnoDB表的普通索引都會儲存主鍵的鍵值，這樣通過對索引加鎖就可以實作行級鎖。

         可以說資料庫必須有索引，沒有索引則檢索過程變成了順序查找，O(n)的時間複雜度幾乎是不能忍受的。我們非常容易想象出一個隻有單關鍵字組成的表如何使用B+樹進行索引，隻要将關鍵字存儲到樹的節點即可。當資料庫一條記錄裡包含多個字段時，一棵B+樹就隻能存儲主鍵，如果檢索的是非主鍵字段，則主鍵索引失去作用，又變成順序查找了。這時應該在第二個要檢索的列上建立第二套索引。  這個索引由獨立的B+樹來組織。有兩種常見的方法可以解決多個B+樹通路同一套表資料的問題，一種叫做聚簇索引（clustered index ），一種叫做非聚簇索引（secondary index）。這兩個名字雖然都叫做索引，但這并不是一種單獨的索引類型，而是一種資料存儲方式。對于聚簇索引存儲來說，行資料和主鍵B+樹存儲在一起，輔助鍵B+樹隻存儲輔助鍵和主鍵，主鍵和非主鍵B+樹幾乎是兩種類型的樹。對于非聚簇索引存儲來說，主鍵B+樹在葉子節點存儲指向真正資料行的指針，而非主鍵。

      InnoDB使用的是聚簇索引，将主鍵組織到一棵B+樹中，而行資料就儲存在葉子節點上，若使用"where id =

14"這樣的條件查找主鍵，則按照B+樹的檢索算法即可查找到對應的葉節點，之後獲得行資料。若對Name列進行條件搜尋，則需要兩個步驟：第一步在輔助索引B+樹中檢索Name，到達其葉子節點擷取對應的主鍵。第二步使用主鍵在主索引B+樹種再執行一次B+樹檢索操作，最終到達葉子節點即可擷取整行資料。

      MyISM使用的是非聚簇索引，非聚簇索引的兩棵B+樹看上去沒什麼不同，節點的結構完全一緻隻是存儲的内容不同而已，主鍵索引B+樹的節點存儲了主鍵，輔助鍵索引B+樹存儲了輔助鍵。表資料存儲在獨立的地方，這兩顆B+樹的葉子節點都使用一個位址指向真正的表資料，對于表資料來說，這兩個鍵沒有任何差别。由于索引樹是獨立的，通過輔助鍵檢索無需通路主鍵的索引樹。

         為了更形象說明這兩種索引的差別，我們假想一個表如下圖存儲了4行資料。其中Id作為主索引，Name作為輔助索引。圖示清晰的顯示了聚簇索引和非聚簇索引的差異。

聚簇索引優點：

1 查詢速度更快：由于行資料和葉子節點存儲在一起，這樣主鍵和行資料是一起被載入記憶體的，找到葉子節點就可以立刻将行資料傳回了，如果按照主鍵Id來組織資料，獲得資料更快。

2 減少索引維護：輔助索引使用主鍵作為"指針" 而不是使用位址值作為指針的好處是，減少了當出現行移動或者資料頁分裂時輔助索引的維護工作，使用主鍵值當作指針會讓輔助索引占用更多的空間，換來的好處是InnoDB在移動行時無須更新輔助索引中的這個"指針"。也就是說行的位置（實作中通過16K的Page來定位，後面會涉及）會随着資料庫裡資料的修改而發生變化（前面的B+樹節點分裂以及Page的分裂），使用聚簇索引就可以保證不管這個主鍵B+樹的節點如何變化，輔助索引樹都不受影響。

InnoDB行鎖的實作：

InnoDB的行鎖是加在索引上的，實作過程如下：