08.13 深入理解MySQL的索引（二）

耐心看。。。。。

MySQL實現

對B-樹，B+樹和散列等數據結構的基本概念有了一些瞭解之後，我們就可以開始討論MySQL通過支持它們的存儲引擎如何實現不同的算法。同時每種實現也對磁盤和內存使用情況有不同的影響，這一點在大型數據庫系統中是非常重要的考慮因素。

1.MyISAM的B-樹

MyISAM存儲引擎使用B-樹數據結構來實現主碼索引、唯一索引以及非主碼索引。在MyISAM實現數據目錄和數據庫模式子目錄中，用戶可以找到和每個MySQL表對應的.MYD和.MYI文件。數據庫表上定義的索引信息就存儲在MYI文件中，該文件的塊大小是1024字節。這個大小是可以通過myisam-block-size系統變量分配。

$ ls -1h /var/lib/mysql/book/source_words.MY*

-rw-rw---- 1 mysql mysql 9.2M 2015-05-07 19:08

source_words.MYD

-rw-rw---- 1 mysql mysql 7.8M 2015-05-07 19:08

source_words.MYI

這些文件結構的內部格式可以從MySQL免費源代碼中找到，也可以查看MySQL內部手冊。

在MyISAM中，非主碼索引的B-樹結構存儲索引值和一個指向主碼數據的指針，這是MyISAM和InnoDB的一個顯著區別。這一點導致了兩個存儲引擎的索引的不同工作方式。

MyISAM索引是在內存的一個公共緩存中管理的，這個緩存的大小可以通過key_buffer_size或者其他命名鍵緩存來定義。這是根據統計和規劃的表索引的大小來設定緩存大小時主要的考慮因素。

2. InnoDB的B+樹聚簇主碼

InnoDB存儲引擎在它的主碼索引（也被稱為聚簇主碼）中使用了B+樹，這種結構把所有數據都和對應的主碼組織在一起，並且在葉子節點這一層上添加額外的向前和向後的指針，這樣就可以更方便地進行範圍掃描。

在文件系統層面，所有InnoDB數據和索引信息都默認在公共InnoDB表空間中管理，否則管理員就通過innodb_data_file_path這個變量指定文件路徑。這是一個叫ibdatal文件。

由於InnoDB用聚簇主碼存儲數據，底層信息佔用的磁盤空間的大小很大程度上取決於頁面的填充因子。對於按序排列的主碼，InnoDB會用16K頁面的15/16作為填充因子。對於不是按序排列的主碼，默認情況下InnoDB會插入初始數據的時候為每一個頁面分配50%作為填充因子。

在改索引的實現方式中B+樹的葉子節點上是data就是數據本身，key為主鍵，如果是一般索引的話，data便會指向對應的主索引。在B+樹的每一個葉子節點上面增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的B+樹。其目的是提高區間訪問的性能。

InnoDB中的非主碼索引使用了B-樹數據結構，但InnoDB中的B-樹結構實現和MyISAM中並不一樣。在InnoDB中，非主碼索引存儲的是主碼的實際值。而MyISAM中，非主碼索引存儲的包含主碼值的數據指針。這一點很重要。首先，當定義很大的主碼的時候，InnoDB的非主碼索引可能回更大，隨著非主碼索引數量的增加，索引之間大小差別可能會變得很大。另一個不同點在於非主碼索引當前可以包含主鍵的值，並且可以不是索引必須有的部分。

4.內存散列索引

在默認MySQL的引擎索引中，只有MEMORY引擎支持散列數據結構，散列結構的強度可以表示為直接鍵查找的簡單性，散列索引的相似度模式匹配查詢比直接查詢慢。也可以為MEMORY引擎指定一個B-樹索引實現。

5.內存B-樹索引

對於大型MEMORY表來說，使用散列索引進行索引範圍搜索的效率很低，B-樹索引在執行直接鍵查詢時確實比使用默認的散列索引快。根據B-樹的不同深度，B-樹索引在個別操作中的確可能比散列算法快。

6.InnoDB內部散列索引

InnoDB存儲引擎在聚簇B+樹索引中存儲主碼：但在InnoDB內部還是使用內存中的散列表來更高效地進行主碼查詢。這個機制有InnoDB存儲引擎來管理，用戶只能通過innodb_adaptive_hash_index配置項來選擇是否啟用這個唯一的配置選項。

學習源自：https://mp.weixin.qq.com/s/fPM4FbICN9ZZzf_3Tk38Gw