MySql MyISAM與InnoDB的索引結構

Mysql索引結構

Mysql非常普遍的使用在互聯網公司的大大小小的業務上，而這些業務的許多性能問題都數據的查詢。如果進行高質量的SQL查詢，如何有效的創建索引，隨用索引成為了很多復雜業務的重點關鍵問題。由于索引是在存儲引擎層面實現的，而不是服務器層，所以索引并非標準化的，每種存儲引擎的索引的工作方式都略有不同。本文將主要圍繞我們最常用的MyISAM和InnoDB進行索引的介紹。

1 存儲引擎：

1.1 MyISAM：

MyISAM的布局其實非常簡單，它是按照插入順序在磁盤是存儲數據。如下：

因為每一行的大小固定，索引MyISAM可以很容易從標的開始位置找到某一行的位置。其Primary Key 的結構大致如下：

而如果在其它的列上創建索引，其索引的形式與Primary Key 的結構也是相同的，可以認為Primary Key 是一個非NULL的位置索引。

1.2、InnoDB存儲引擎：

InnoDB與MyISAM不同的是其支持聚集索引（后面介紹）。它存儲表的結構大致如下：

聚簇索引中的每個葉子節點包含primary key的值，事務ID和回滾指針(rollback pointer)——用于事務和MVCC，和余下的列。 乍看上去InnoDB和MyISAM沒什么不同，但是仔細看我們應該主要到改圖顯示的是整個表的結構，而不只是索引。由于聚集索引索引的是整個表，所以每行不需要像MyISAM那樣需要單獨存儲空間。聚集索引中的每一個葉子節點都包含主鍵值、事務ID、用于食物MVCC的會滾指針以及余下的所有列。如果主鍵被創建在列的前綴上，InnoDB也會包含整列及剩下的所有列。InnoDB默認的Primary Key索引即是聚集索引，既然如此，那么InnoDB的第二索引必然與主鍵索引不同（數據已經保存了，自然不需要另外保存一份）

通過命令查看索引：

• Non_unique ： 表示數據是否唯一，0表示唯一，1表示不唯一
• Key_name : 索引名稱
• Seq in index : 字段在索引中的順序。例如（key name 為idx supplier provider 的索引包含兩個字段：supplier id、provider_id）。索引字段的順序非常重要。
• Collation： 列以什么方式存儲在索引中。在MySQL中，有值‘A’（升序）或NULL（無分類）。
• Cardinality： 索引中唯一值的數目的估計值。通過運行ANALYZE TABLE或myisamchk -a可以更新。基數根據被存儲為整數的統計數據來計數，所以即使對于小型表，該值也沒有必要是精確的。基數越大，當進行聯合時，MySQL使用該索引的機會就越大。平均數值組=索引基數/表總數據行，平均數值組越接近1就越有可能利用索引。
• Sub_part: 如果列只是被部分地編入索引，則為被編入索引的字符的數目。如果整列被編入索引，則為NULL。
• Packed : 指示關鍵字如何被壓縮。如果沒有被壓縮，則為NULL。
• Null : 如果列含有NULL，則含有YES。如果沒有，則該列含有NO。一般來說不建議存儲NULL, 這回導致索引非常難查找
• Index_type： 索引的方式：BTREE, FULLTEXT, HASH, RTREE
• Comment ：多種評注，您可以使用db name.tbl name作為tbl name FROM db name語法的另一種形式

2 數據庫索引：

Mysql的索引方式有多種，比如B－Tree索引、Hash索引、R－Tree索引等，本文主要介紹B－Tree索引、Hash索引。

2.1 B-Tree：

B-Tree 索引是 MySQL 數據庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。不僅僅在 MySQL 中是如此，實際上在其他的很多數據庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結構在數據庫的數據檢 索中有非常優異的表現。 一般來說，Mysql 中的B-Tree 索引的物理文件大多以Balance Tree的結構來存儲的，也就是說所有實際需要的數據都存放與Tree的Leaf Node，而且到任何一個Leaf Node的最短路徑的長度都是完全相同的。而部分存儲引擎在存放自己的B-Tree索引的時候會對存儲結構進行稍作修改，例如InnoDB的B-Tree索引實際使用的存儲結構是B+Tree。與B-Tree 不同的是在每一個Leaf Node上面除了存放索引鍵的相關信息外，還存出了指向該Leaf Node 相鄰的后一個Leaf Node的指針信息，這主要是為了加快索引相鄰Leaf Node 的效率考慮。

2.1.1 MyISAM上的B－Tree索引：

MyisAM索引用的B+tree來儲存數據，按照插入的順序在磁盤上存儲數據：

MyisAM索引的指針指向的是鍵值的地址，地址存儲的是數據，并且是按照順序存儲，如下圖

由于每個索引存儲的都是地址信息，所以MyISAM中的Primary Key與其它的索引沒有區別，Primary Key僅僅只是一個叫做PRIMARY 的唯一非空索引而已。

2.1.2 InnoDB上的B－Tree：

InnoDB的數據布局：

下圖是B－Tree索引在InnoDB和MyISAM上的結構圖：

InnoDB的數據就存儲在Primary Key的索引葉子頁上，而其它的索引都只是記錄了索引的值和主鍵等其它的信息。這樣在InnoDB使用主鍵查找一般速度會高于其它索引查找的速度。

而MyISAM索引則是想之前所過的，葉子節點上存儲的是每行數據的地址，Primary Key 索引和其它索引沒有本質區別。

現在我們把InnoDB的這種索引的存儲數據的方式就叫做聚集索引。注意聚集索引并不是一種索引類型，而只是存儲方式，具體細節依賴于聚集索引的實現。但其基本的思想就是將數據實際保存在葉子頁上。"聚集"的意思是指實際的數據行和相關的鍵值都保存在一起，但是每個表只能有一個聚集索引，不能把一行數據保存在兩個地方。

聚集索引的優點：

1. 可以把相關數據保存在一起。例如，當查找用戶信息的時候，可以按照user_id進行聚集，這樣從磁盤上提取幾個頁面的數據就能把某個用戶的郵件全部抓取出來。如果沒有使用聚集，讀取每個郵件都會訪問磁盤。
2. 數據訪問快。聚集索引把索引和數據保存在同一棵B-Tree中，因此從聚集索引中取得數據通常比非聚集索引進行查找的要快。
3. 使用覆蓋索引的查詢可以使用包含在葉子葉子節點的主鍵值。

聚集索引的缺點：

• 聚集能最大地提升I/O密集負載的性能。如果數據能裝入內存，那么其順序也就無所謂了，這樣聚集就沒什么用處。
• 插入速度嚴重以來與插入的順序，按照主鍵的順序插入行是吧數據裝入InnoDB表的最快方法。如果沒有使用按照主鍵順序插入數據，那么插入之后最好使用OPTIMIZE TABLE重新組織一下。
• 更新索引列是昂貴的，因為它強制把每個更新行移動到新的位置。
• 建立在聚集索引上的表在插入新行，或者在行的主鍵被更新，改行必須被移動的時候會進行分頁。分頁放生在行的鍵值要求行必須唄放到一個放滿數據的頁的時候，此時存儲引擎必須進行重新分頁才能容納下改行。分頁會導致表占用更多的磁盤空間。
• 聚集表可能會比全表掃描慢，尤其在表存儲的比較稀疏或因為分頁而沒有順序存儲的時候。
• 第二（非聚集）索引可能會比預想大，因為他們的葉子節點暴行了被引用行的主鍵。
• 第二索引訪問需要兩次索引查詢，而非一次。

2.2 Hash索引：

Hash索引是建立在Hash表的基礎上，它只對使用索引中每一列的精確查找有用。對于每一行數據，存儲引擎計算出被索引列的Hash Code，計算出來的Hash Code是一個非常小的值。存儲引擎將Hash Code保存在索引中，并且保存了一個指向Hash表每一行的指針。由于Hash的存儲方式不同于B-Tree，所以在查找速度上Hash索引的速度是大大的優于B-Tree。但是據我們所知Hash索引很少在創建數據庫索引中使用，究其原因就是在于它的索引方式所導致的一些局限性，有的時候這些局限性甚至是致命的。

Hash索引的局限性如下：

• 因為索引只包含了哈戲碼和行指針，而不是值自身，Mysql不能使用索引的值來避免讀取行。幸運的是訪問內存的行很快，因此折衣板不會降低性能。
• Mysql 不能使用Hash索引進行排序，因為他不會按序保存。
• 哈希索引不支持部分鍵匹配，因為他們是由唄索引的全部值計算出來的。也就是說如果在（A B）兩列上有索引，WHERE語句只是用了A，那么索引就不會起作用。
• 哈希索引只支持使用了=、IN 和<=> 的相等比較（注意<> 和<=> 不是相同的運算符）。它們不能加快范圍查詢，列入Where age > 20。
• 訪問哈希索引中的數據非常快，除非碰撞率恒高（很多值相同的Hash碼）。當發生碰撞的時候，存儲引擎必須訪問鏈表中的每一個行指針，然后逐行進行數據比較，以確定正確的數據。
• 如果有很多碰撞，一些索引維護操作就有可能會變慢，如果在一個選擇性很低（很多碰撞）的列上創建hash索引，然后從表中刪除一行，那么從索引中會找到行的代價會很高。存儲引擎不得不檢查Hash鏈表中的每一行，以找到和一處被刪除行的索引。

看了這些問題，是不是會發現Hash索引在建數據表的時候為什么不被提倡的原因了。

綜述：

數據庫的索引的目的無非就是為了提升查詢的效率，但在我們往往會發現查詢和修改的效率往往是相反的。MyISAM的數據是順序存儲的，所以這個優勢基本上就注定了MyISAM的查詢的快速，但是也恰恰由于此，其更新的時候往往要調整頁的結構，所以速度比較慢。而我們經常在項目中使用的InnoDB存儲則使用了聚集索引的方式，將查詢與更新的速度做了平衡，這也就是為什么更多的大型項目采用InnoDB的存儲方式。

原文鏈接： https://github.com/yushanzh/blog/issues/1