前言

這篇文章的題目，是我真實在面試過程中遇到的問題，某互聯(lián)網(wǎng)眾籌公司在考察面試者MySQL相關知識的第一個問題，我當時還是比較懵的，沒想到這年輕人不講武德，不按套路出牌，一般的問MySQL的相關知識的時候，不都是問索引優(yōu)化以及索引失效等相關問題嗎？怎么還出來了，存儲文件的不同？哪怕考察個MVCC機制也行啊。所以這次我就好好總結總結這部分知識點。

為什么需要建立索引

首先，我們都知道建立索引的目的是為了提高查詢速度，那么為什么有了索引就能提高查詢速度呢？
我們來看一下，一個索引的示意圖。

如果我有一個SQL語句是：select * from Table where id = 15 那么在沒有索引的情況下其實是會進行全表掃描的，就是挨個去找，直到找到id=15的這條記錄，時間復雜度是O(n)；

如果在有索引的情況下去進行查詢呢。首先會根據(jù)id=15，在索引值里面進行二分查找，二分查找的效率是很高的，它的時間復雜度是O(logn)；

這就是索引為什么能提高查詢效率了，但是索引數(shù)據(jù)的量也是比較大的，所以一般并不是存儲在內(nèi)存中的，都是直接存儲在磁盤中的，所以對磁盤中的文件內(nèi)容進行讀取，免不了要進行磁盤IO。

MySQL的索引為什么使用B+Tree

上面我們也說了，索引數(shù)據(jù)一般是存儲在磁盤中的，但是計算數(shù)據(jù)都是要在內(nèi)存中進行的，如果索引文件很大的話，并不能一次都加載進內(nèi)存，所以在使用索引進行數(shù)據(jù)查找的時候是會進行多次磁盤IO，將索引數(shù)據(jù)分批的加載到內(nèi)存中，因此一個好的索引的數(shù)據(jù)結構，在得到正確的結果前提下，一定是磁盤IO次數(shù)最少的。

Hash類型

目前MySQL其實是有兩種索引數(shù)據(jù)類型可以選擇的，一個是BTree（實際是B+Tree）、一個Hash。

但是為什么在實際的使用過程中，基本上大部分都是選擇BTree呢？

因為如果使用Hash類型的索引，MySQL在創(chuàng)建索引的時候，會對索引數(shù)據(jù)進行一次Hash運算，這樣根據(jù)Hash值就能快速的定位到磁盤指針了，就算數(shù)據(jù)量很大，也能快速精準的定位到數(shù)據(jù)。

• 但是像select * from Table where id > 15這種范圍查詢，Hash類型的索引就搞不定了，對這種范圍查詢，會直接全表掃描，另外Hash類型的索引也搞不定排序。
• 還有就是雖然MySQL底層做了一系列的處理，但還是不能完全的保證，不產(chǎn)生Hash碰撞。

二叉樹

那MySQL為什么沒有二叉樹作為它的索引數(shù)據(jù)結構呢？我們都知道，二叉樹是通過二分查找來進行定位數(shù)據(jù)的，所以效果還是不錯的，時間復雜度是O(logn)；

但是二叉樹有個問題，就是在特殊情況下，它會退化成一根棍子，也就是一個單向鏈表。這個時候，它的時間復雜度就會退化成O(n)；

所以當我們要查詢id=50的記錄時，其實和全表掃描是一樣的了。所以因為存在這種情況，二叉樹不適合作為索引的數(shù)據(jù)結構。

平衡二叉樹

那么既然二叉樹，在特殊情況下會退化成鏈表，那么平衡二叉樹為什么不可以呢？

平衡二叉樹的子節(jié)點高度差不能超過1，像下圖中的二叉樹，關鍵字為15的節(jié)點，它的左子節(jié)點高度為0，右子節(jié)點高度為1，高度差不超過1，所以下面這棵樹是一棵平衡二叉樹。

因為能保持平衡，所以它的查詢時間復雜度為O(logN)，至于怎么保持平衡的，主要是做一些左旋，右旋等，具體保持平衡的細節(jié)不是本文主要內(nèi)容，想了解的可自行搜索。

用這個數(shù)據(jù)結構來做MySQL的索引會有 什么問題呢？

• 磁盤IO過多：在MySQL當中，一次IO操作只讀取一個節(jié)點，那么一個節(jié)點若是最多就兩個子節(jié)點的話，那么就只有這兩個子節(jié)點的查詢范圍，所以要精確到具體的數(shù)據(jù)時，就需要進行多次讀取，如果樹非常深的話，那么將會進行大量的磁盤IO。性能自然下降了。
• 空間利用率低：對于平衡二叉樹來說，每個節(jié)點值保存一個關鍵字，一個數(shù)據(jù)區(qū)，兩個子節(jié)點的指針。這樣導致了，一次辛辛苦苦的IO操作就只加載這么點數(shù)據(jù)，實在是有點殺雞用牛刀了。
• 查詢效果不穩(wěn)定：如果在一個高度很深的平衡二叉樹中，若是查詢的數(shù)據(jù)正好是根節(jié)點，那么就會很快的查到，若是查詢的數(shù)據(jù)正好是葉子節(jié)點，那么會進行多次磁盤IO后才能返回，響應時間有可能和根節(jié)點的不在一個數(shù)量級上。

雖然說二叉樹解決的平衡的問題，但是也帶來了新的問題，那就是由于它本身樹的深度的，會造成一系列的效率問題。

那么為了解決平衡二叉樹的這類問題，平衡多叉樹（Balance Tree）就成為了更好的選擇。

平衡多叉樹（Balance Tree--B-Tree）

B-Tree的意思是平衡多叉樹，一般B-Tree中的一個節(jié)點有多少個子節(jié)點，我們就稱為多少階的B-Tree。通常用m表示階數(shù)，當m為2的時候，就是平衡二叉樹。

一棵B-Tree的每個節(jié)點上最多能有m-1個關鍵字，最少要存放Math.ceil(m/2)-1個關鍵字，所有的葉子節(jié)點都在同一層。如下圖就是一個4階的B-Tree。

那么我們看一下B-Tree是如何進行查找數(shù)據(jù)的：

• 若是查詢id=7的數(shù)據(jù)，先將關鍵字20的節(jié)點加載進內(nèi)存，判斷出7比20小；
• 那么加載第一個子節(jié)點，若查詢的數(shù)據(jù)等于12或17則直接返回，不等于就繼續(xù)向下找，發(fā)現(xiàn)7小于12；
• 那么繼續(xù)加載第一個子節(jié)點中去，找到7之后，直接將7下面的data數(shù)據(jù)返回。

這樣整個操作其實進行了3次IO操作，但實際上一般的B-Tree每層都是有很多分支（通常都大于100）。

MySQL為了能更好的利用磁盤的IO能力，將操作頁的大小設置為了16K，即每個節(jié)點的大小為16K。如果每個節(jié)點中的關鍵字都是int類型的，那么就是4個字節(jié)，若數(shù)據(jù)區(qū)的大小為8個字節(jié)，節(jié)點指針再占4個字節(jié)，那么B-Tree的每個節(jié)點中可以保存的關鍵字個數(shù)為：(16*1000) / (4+8+4)=1000，每個節(jié)點最多可存儲1000個關鍵字，每一個節(jié)點最多可以有1001個分支節(jié)點。

這樣在查詢索引數(shù)據(jù)的時候，一次磁盤IO操作可以將1000個關鍵字，讀取到內(nèi)存中進行計算，B-Tree的一次磁盤IO的操作，頂上平衡二叉數(shù)據(jù)的N次磁盤IO操作了。

要注意的是：B-Tree為了保證數(shù)據(jù)的平衡，會做一系列的操作，這個保持平衡的過程比較耗時間，所以在創(chuàng)建索引的時候，要選擇合適的字段，并且不要過多的創(chuàng)建索引，創(chuàng)建索引過多的話，在更新數(shù)據(jù)的時候，更新索引的過程也比較耗時。

還有就是不要選擇低區(qū)分度字段值作為索引，例如性別字段，總共就兩個值，那么就有可能會造成B-Tree的深度過大，索引效率降低。

B+Tree

B-Tree已經(jīng)很好的解決平衡二叉樹的問題了，并且也能保證查詢效率了，那么為什么會有B+Tree呢？

我們先來B+Tree是什么樣子的。

B+Tree是B-Tree的變種，B+Tree的每個節(jié)點關鍵字和m階的公式關系和B-Tree的不一樣了。

首先每個節(jié)點的子節(jié)點數(shù)量和每個節(jié)點可存儲的關鍵字比例是1:1，其次就是查詢數(shù)據(jù)的時候采用的是左閉合區(qū)間進行查詢，還有就是分支節(jié)點中沒有數(shù)據(jù)了只保存關鍵字和子節(jié)點指向，數(shù)據(jù)都存儲在葉子節(jié)點。

那么來看一下在B+Tree中是如何進行數(shù)據(jù)查詢的。

例如：

• 現(xiàn)在要查詢id=2的數(shù)據(jù)，那么會先將根節(jié)點取出，加載到內(nèi)存中，發(fā)現(xiàn)id=2存在于根節(jié)點，因為是左閉合區(qū)間存儲數(shù)據(jù)，所以id<=2的都在根節(jié)點的第一個子節(jié)點上；
• 那么取出第一個子節(jié)點，加載到內(nèi)存中，發(fā)現(xiàn)當前節(jié)點存在id=2的關鍵字，并且已經(jīng)到了葉子節(jié)點了，那么直接取出葉子節(jié)點中的數(shù)據(jù)返回。

現(xiàn)在來看一下B-Tree和B+Tree的區(qū)別

• B+Tree的查詢采用的左閉合區(qū)間，這樣能更好的支持了自增索引的查詢效果，所以一般在創(chuàng)建主鍵的時候通常都是自增的。這一點和B-Tree是不一樣的。
• B+Tree中的根節(jié)點和分支節(jié)點上是不保存數(shù)據(jù)的，關鍵字相關的數(shù)據(jù)只保存在葉子節(jié)點上，這樣保證了查詢效果的穩(wěn)定，任何查詢都要走到葉子節(jié)點才能獲取數(shù)據(jù)。而B-Tree在分支節(jié)點中保存了數(shù)據(jù)，若是命中關鍵字則直接返回數(shù)據(jù)。
• B+Tree的葉子節(jié)點是順序排列的，并且相鄰的兩個葉子節(jié)點中具有順序引用的關系，這樣能更好的支持了范圍查詢。而B-Tree是沒有這個順序關系的。

MySQL的索引為什么選擇了B+Tree

經(jīng)過上面的層層分析，現(xiàn)在我們可以總結一下MySQL為什么選擇了B+Tree作為它索引的數(shù)據(jù)結構呢。

1. 首先和平衡二叉樹相比，B+Tree的深度更低，節(jié)點保存關鍵字更多，磁盤IO次數(shù)更少，查詢計算效率更好。

2. B+Tree的全局掃描能力更強，若是想根據(jù)索引數(shù)據(jù)對數(shù)據(jù)表進行全局掃描，B-Tree會將整棵樹進行掃描，然后逐層遍歷。而B+Tree呢，只需要遍歷葉子節(jié)點即可，因為葉子節(jié)點之間存在順序引用的關系。

3. B+Tree的磁盤IO讀寫能力更強，因為B+Tree的每個分支節(jié)點上只保存了關鍵字，這樣每次磁盤IO在讀寫的時候，一頁16K數(shù)據(jù)量可以存儲更多的關鍵字了，每個節(jié)點上保存的關鍵字也比B-Tree更多了。這樣B+Tree的一次磁盤IO加載的數(shù)據(jù)比B-Tree的多很多了。

4. B+Tree數(shù)據(jù)結構中有天然的排序能力，比其他數(shù)據(jù)結構排序能力更強而且排序時，是通過分支節(jié)點來進行的，若是需要將分支節(jié)點加載到內(nèi)存中排序，一次加載的數(shù)據(jù)更多。

5. B+Tree的查詢效果更穩(wěn)定，因為所有的查詢都是需要掃描到葉子節(jié)點才將數(shù)據(jù)返回的。效果只是穩(wěn)定而不一定是最優(yōu)，若是直接查詢B-Tree的根節(jié)點數(shù)據(jù)，那么B-Tree只需要一次磁盤IO就可以直接將數(shù)據(jù)返回，反而是效果最優(yōu)。

經(jīng)過以上幾點的分析，MySQL最終選擇了B+Tree作為了它的索引的數(shù)據(jù)結構。

InnDB的數(shù)據(jù)存儲文件和MyISAM的有何不同？

上面總結了MySQL的索引的數(shù)據(jù)結構，這次就可以說第二個問題了，因為這個問題其實和MySQL的索引還是有一定的關系的。
下面來看一下，先找到服務器上MySQL存儲數(shù)據(jù)的目錄：
登錄MySQL，打開MySQL的命令行界面：輸入show variables like '%datadir%';，就能看到存儲數(shù)據(jù)的目錄了。
我的服務器中MySQL的存儲數(shù)據(jù)的目錄是在：

/var/lib/mysql/

進入到這個目錄里后，能看到所有數(shù)據(jù)庫的目錄，新建一個study_test的數(shù)據(jù)庫。
然后就進入

/var/lib/mysql/study_test

這個目錄下，目前就只有一個文件，這個文件是用來記錄創(chuàng)建數(shù)據(jù)庫時配置的字符集的內(nèi)容。

-rw-r----- 1 mysql mysql     60 1月  31 10:28 db.opt

現(xiàn)在新建兩個表，第一個表的引擎類型選擇InnoDB，第二個表的引擎類型選擇MyISAM。

student_innodb：

CREATE TABLE `student_innodb` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `address` varchar(100) COLLATE utf8mb4_bin DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) USING BTREE COMMENT 'name索引'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='innodb引擎表';

student_myisam：

CREATE TABLE `student_myisam` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `address` varchar(100) COLLATE utf8mb4_bin DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) USING BTREE COMMENT 'name索引'
) ENGINE=MyISAM DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin COMMENT='myISAM引擎類型表';

將兩個表創(chuàng)建完成后，我們再進入到/var/lib/mysql/study_test看一下：

-rw-r----- 1 mysql mysql     60 1月  31 10:28 db.opt
-rw-r----- 1 mysql mysql   8650 1月  31 10:41 student_innodb.frm
-rw-r----- 1 mysql mysql 114688 1月  31 10:41 student_innodb.ibd
-rw-r----- 1 mysql mysql   8650 1月  31 10:58 student_myisam.frm
-rw-r----- 1 mysql mysql      0 1月  31 10:58 student_myisam.MYD
-rw-r----- 1 mysql mysql   1024 1月  31 10:58 student_myisam.MYI

通過目錄中的文件可看到創(chuàng)建表之后多了幾個文件，這樣也看出來了，InnoDB引擎類型的表和MyISAM引擎類型的表的文件差異。

這幾個文件每個都是有自己的作用：

• InnoDB引擎的表文件，一共有兩個：
  • *.frm 這類文件是表的定義文件。
  • *.ibd 這類文件是數(shù)據(jù)和索引存儲文件。表數(shù)據(jù)和索引聚集存儲，通過索引能直接查詢到數(shù)據(jù)。
• MyIASM引擎的表文件，一共有三個：
  • *.frm 這類文件是表的定義文件。
  • *.MYD 這類文件是表數(shù)據(jù)文件，表中的所有數(shù)據(jù)都保存在此文件中。
  • *.MYI 這類文件是表的索引文件，MyISAM存儲引擎的索引數(shù)據(jù)單獨存儲。

MyISAM數(shù)據(jù)存儲引擎，索引與數(shù)據(jù)的存儲結構

MyISAM存儲引擎在存儲索引的時候，是將索引數(shù)據(jù)單獨存儲，并且索引的B+Tree最終指向的是數(shù)據(jù)存在的物理地址，而不是具體的數(shù)據(jù)。然后再根據(jù)物理地址去數(shù)據(jù)文件（*.MYD）中找到具體的數(shù)據(jù)。

如下圖所示：

那么當存在多個索引時，多個索引都指向相同的物理地址。
如下圖所示：

通過這個結構，我們可以看出來，MyISAM的存儲引擎的索引都是同級別的，主鍵和非主鍵索引結構和查詢方式完全一樣。

InnoDB數(shù)據(jù)存儲引擎，索引與數(shù)據(jù)的存儲結構

首先InnoDB的索引分為聚簇索引和非聚簇索引，聚簇索引即保存關鍵字又保存數(shù)據(jù)，在B+Tree的每個分支節(jié)點上保存關鍵字，葉子節(jié)點上保存數(shù)據(jù)。
“聚簇”的意思是數(shù)據(jù)行被按照一定順序一個個緊密地排列在一起存儲。一個表只能有一個聚簇索引，因為在一個表中數(shù)據(jù)的存放方式只有一種，一般是主鍵作為聚簇索引，如果沒有主鍵，InnoDB會默認生成一個隱藏的列作為主鍵。

如下圖所示：

非聚簇索引，又稱為二級索引，雖然也是在B+Tree的每個分支節(jié)點上保存關鍵字，但是葉子節(jié)點不是保存的數(shù)據(jù)，而是保存的主鍵值。通過二級索引去查詢數(shù)據(jù)會先查詢到數(shù)據(jù)對應的主鍵，然后再根據(jù)主鍵查詢到具體的數(shù)據(jù)行。

如下圖所示：

由于非聚簇索引的設計結構，導致了，非聚簇索引在查詢的時候要進行兩次索引檢索，這樣設計的好處，可以保證了一旦發(fā)生數(shù)據(jù)遷移的時候，只需要更新主鍵索引即可，非聚簇索引并不用動，而且也規(guī)避了像MyISAM的索引那樣存儲物理地址，在數(shù)據(jù)遷移的時候的需要重新維護所有索引的問題。

總結

這次把MySQL的索引的數(shù)據(jù)結構，以及文件存儲結構，總結清楚了，后面在實際的工作過程中，設計索引的時候能夠考慮的更全了，通過了解了索引的數(shù)據(jù)結構，也能讓自己在實際寫SQL的時候，能考慮到哪些情況走索引哪些不走索引了。

• MySQL使用B+Tree作為索引的數(shù)據(jù)結構，因為B+Tree的深度低，節(jié)點保存的關鍵字多，磁盤IO次數(shù)少，從而保證了查詢效率更高。
• B+Tree能夠保證MySQL無論是主鍵索引還是非主鍵索引的查詢效果都是穩(wěn)定的，每次都要查詢到葉子節(jié)點才能返回數(shù)據(jù)，B+Tree的葉子節(jié)點的深度是一樣的，而且為了更好的支持自增主鍵，B+Tree的查詢節(jié)點范圍是左閉合右開放。
• MySQL的MyISAM存儲引擎，表數(shù)據(jù)和索引數(shù)據(jù)是分別放到兩個文件中進行存儲的，由于它本身的索引的B+Tree的葉子節(jié)點指向的表數(shù)據(jù)所在的磁盤地址，而且索引沒有主鍵和非主鍵之分，所以分開存儲，能夠更好的統(tǒng)一管理索引；
• MySQL的InnoDB存儲引擎，表數(shù)據(jù)和索引數(shù)據(jù)是存儲在一個文件中的，因為InnoDB的聚簇索引的葉子節(jié)點指向的具體的數(shù)據(jù)行，而且為了保證查詢效果的穩(wěn)定，InnoDB表中必須要有一個聚簇索引，二級索引在進行索引檢索時，會先通過二級索引檢索到數(shù)據(jù)的主鍵值，再根據(jù)主鍵去聚簇索引中檢索到具體的數(shù)據(jù)。