關於Mysql索引的數據結構_ZenDei技術網路在線

Mysql 連續數據分組思路是使用變數逐行將上行和當前行進行對比條件滿足則生成分組的編號，再根據分組條件和分組編號分組就可以。 ...

索引的數據結構

1、為什麼使用索引

概念: 索引是存儲索引用於快速找到數據記錄的一種數據結構，就好比一本書的目錄部分，通過目錄中對應的文章的頁碼，便可以快速定位到需要的文章，Mysql 中也是一樣的道理，進行數據查找時首先查看查詢條件是否命中某條索引，符合則通過索引查找相關數據，如果不符合則需要全表掃描，即需要一條條查找後記錄，直到找到與條件符合的記錄。

如果當數據沒有任何索引的情況下，數據會分佈在磁碟上不同的位置上面，當讀取數據時，磁碟擺臂需要前後擺動查找數據，這樣的操作非常消耗時間。如果數據順序擺放,那麼也需要數次IO操作，依舊非常耗時，如果不藉助任何索引結構幫助我們快速定位數據，那麼當我們查詢時需要逐行掃描、比較。當有上千萬數據時，就意味著需要做更多的磁碟IO才能找到對應的數據。

當我們需要查找一條數據時（如：Col2=89）：
CPU需要先去磁碟查找這條記錄，找到之後載入到記憶體，在對數據進行處理。這個過程最消耗時間的就是磁碟I/O（涉及到磁碟的旋轉時間[速度較快]、磁頭的尋道時間【速度慢、費時】）

假如給數據使用二叉樹（又叫搜索二叉樹、二叉搜索樹）這樣的數據結構進行存儲，如圖：

對col2 添加了索引，就相當於在硬碟上為col2維護了一個索引的數據結構，即二叉樹，二叉搜索樹的每個節點存儲的是k，v結構，key是col2，value是key所在的文件指針，那麼對col2添加了索引，這時再去查找col2=89這條記錄時，先查詢二叉搜索樹（二叉遍歷查詢）。讀34到記憶體中，進行對比 89 > 34,繼續右側查詢讀89到記憶體。比對之後返回指針數據。在根據當前的value快速定位到對應的數據地址，此時我們發現，只需要兩次I/O就可以定位到記錄，查詢的速度就提高了。

這就是我們為什麼要建索引，建索引的目的就是為了減少磁碟I/O，加快查詢效率。

2、索引及其優缺點

2.1索引概述

Mysql官方對索引的定義為：索引（index）是幫助mysql高效獲取數據的數據結構。

索引的本質 是數據結構，可以簡單的理解為‘排好序的快速查找數據結構’，滿足特定的查找演算法。這些數據結構以某種方式指向數據，這樣就可以在這些數據結構的基礎上實現高級查詢演算法。

索引是在存儲引擎中實現的,因此每種存儲引擎的索引不一定完全相同，並且每種存儲引擎不一定支持所有的索引類型。同時存儲引擎可以定義每個表的最大索引和最大索引長度,所有的存儲引擎支持每個表至少16個索引，總索引長度最大為256位元組。有些引擎支持更多的索引數和更大的長度。

2.2優點

降低資料庫的IO成本，這也是建立索引最主要的原因。
可以創建唯一索引，保證資料庫中表數據的唯一性。
在實現數據的參考完整性方面，可以加速表與表之間的連接。換句話說，對於子表和父表聯合查詢時可以提高查詢速度。
在使用分組和排序子句進行查詢時，可以顯著的減少查詢中分組和排序的時間,減少CPU消耗

2.3缺點

創建索引也有許多不利的方面，主要表現在以下幾點

創建和維護索引需要耗費時間,隨著數據的增加，耗費的時間也隨之增加。
創建索引需要占用磁碟空間, 除了數據表占據數據空間之外，每個索引還要占用一定的物理空間，存儲在磁碟上如果有大量的索引，索引文件就可能比數據文件更快達到最大文件尺寸。
雖然索引大大提高了查詢速度，同時卻也會降低更新表的速度，當對錶中的數據進行增加、刪除、修改的操作，索引也要動態維護，這樣就降低了數據的維護速度。

因此，在選擇使用索引時，需要綜合考慮使用索引的優缺點。

提示：索引可以提高查詢速度，但是會影響插入記錄的速度，在這種情況下，最好的辦法是刪除表中索引，然後插入數據，完成後在創建索引。（在頻繁的更新索引時，重新建立索引反而會消耗比較少的時間）

3、InnoDB索引的推演

3.1 索引之前的查找

一個簡單的查詢：

select 列名列表 from table where 列名 = xxx

在一個頁中查找：

假設目前表中的記錄比較少，所有的記錄都可以被放在一個頁中，在查找記錄的時候可以根據搜索條件的不同分為兩種情況
- 以主鍵為搜索條件：
  
  在頁目錄中使用二分法快速定位到對應的槽，然後便利該槽對應分組中的記錄即可快速找到制定記錄
- 以其他列作為搜索條件
  
  因為在數據頁中並沒有對非主鍵列建立所謂的頁目錄，所以無法通過二分法查找，這種情況只能從最小記錄開始依次遍歷單鏈表中的每條記錄，然後對比每條記錄是不是符合搜索條件，顯然，這種查找的方式效率是非常低的。
在很多頁中查找：

大部分情況下我們表中存放的記錄都是非常多的，需要很多的數據頁來存儲這些記錄。在很多頁中查找記錄的話可以分為兩個步驟：
- 定位到記錄所在的頁。
- 從所在的頁內中查找相應的記錄。
在沒有索引的情況下，不論是根據主鍵列或者其他列的值進行查找，由於我們並不能快速的定位到記錄所在的頁，所以只能從第一個頁沿著雙向鏈表一直往下找，在每一個頁根據上面的查找方式去查找指定的記錄。因為要遍歷所有的數據頁，所以這種方式顯然是超級耗時的，如果表有一億條數據呢，索引應運而生。

數據存儲的基本單位稱之為數據頁。

一個數據頁的大小為16kb。

3.2 設計索引

首先建立一個表：

CREATE TABLE index_demo(
	c1 int,
	c2 int,
	c3 char,
	PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

index_demo表有兩個int類型的列，1個char類型，規定了c1主鍵，使用Compact行格式來實際存儲記錄。這裡簡化了index_demo的行格式示意圖：

其中：

record_type:記錄頭信息的一項屬性，表示記錄的類型，0表示普通記錄，2表示最小記錄。3表示最大記錄、1暫時沒用過，下麵講。
next_record:記錄頭信息的一項屬性,表示下一條記錄的地址偏移量，用箭頭表示下一條記錄是誰。
各個列的值: 這個只記錄的三個列，分別是c1、c2、c3.
其他信息:除了上述三種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

把一些記錄放到數據頁的示意圖就是：

1、`一個簡單的設計方案`

我們在根據某個搜索條件查找一些記錄，為什麼要便利所有的數據頁呢？因為在各個頁中的記錄並沒有規律，我們並不知道我們的搜索條件匹配那些頁中的記錄，所以不得不依次便利所有的數據頁。所以如果我們想要快速定位到需要的記錄在那些數據頁中該怎麼辦。我們可以為快速定位記錄所在的數據頁而建立一個目錄，那建立目錄時必須完成下邊這些事:

下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值：

假設：每個數據頁只能存放三個記錄(實際非常大，可以存很多)，那麼這些記錄已經按照主鍵值的大小串聯成一個單向鏈表了。如圖：

當我們再次插入一條記錄時，因為頁10 最多放3條記錄，所以不得不再次分配一個新頁：

新分配的數據頁編號可能並不是連續的，他們只是通過維護這上一個頁和下一個頁的編號而建立了鏈表關係，另外頁10中用戶記錄最大的主鍵值是5，而頁28中有個記錄主鍵值是4，所以在插入主鍵值為4的記錄時需要伴隨著一次記錄移動，也就是需要把4和5 進行調換。

這個過程表名了在對頁中的記錄進行增刪改查時，必須通過一些諸如此類的記錄移動的操作來保持這個狀態的成立：下一個數據頁中的用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值，這個過程稱之為頁分裂。

由於數據頁的順序可能是不連續的，所以在向index_demo 中插入數據後，可能是這樣的結果：

因為這些16kb的頁在物理存儲上是不連續的，所以想要從這些頁中根據主鍵值快速定位記錄所在頁，需要給他們做個目錄。每個頁對應一個目錄項，每個目錄項包括下邊兩個部分

1. 頁的用戶記錄中最小的記錄值用key表示
2. 頁號： 用page_no表示（數據頁地址）

所以上面幾個數據頁做好的目錄就是這樣：

以頁28為例，對應目錄項2，這個目錄的包含著頁號28(也就是頁指針)以及最小主鍵值5，我們只需要把這個目錄項在物理存儲器上連續存儲（比如：數組），可以實現根據主鍵值快速查找某條記錄的功能了。

比如：查找主鍵為c1為20的記錄，具體分兩步

1. 先從目錄項根據`二分法`確定出主鍵值為20的記錄在`目錄項三`中，對應的頁是頁9
1. 在根據前邊說的在頁中查找記錄的方式去頁9中定位具體的記錄。

那上面這些個過程就是針對主鍵為c1的列建立了一個目錄項的方案，這個方案就叫做索引

2、InnoDB的索引方案

迭代一次：目錄項記錄的頁
迭代兩次：多個目錄項記錄的頁
迭代三次：目錄項記錄頁的目錄頁
B+Tree

在第0層（最底層）中存放這具體數據，數據與數據之間為單向鏈表，頁與頁之間為雙向鏈表。

B+Tree樹：不論是存放用戶記錄的數據，還是存放目錄項記錄的數據頁，我們都把他們放在b+樹這個數據結構中，所以我們也這些數據頁為節點，我們的實際用戶記錄其實都存放在b+樹最底層的節點上，這些節點也稱之為葉子節點，其餘用來存放目錄項的節點稱之為非葉子節點或者內節點，其中B+樹最上面的節點稱為跟節點。

B+Tree樹節點可以分為很多層，規定最下麵的那層，也就是存放記錄的第0層，之後依次往上加。

假設：所有存放記錄的葉子節點能存放100條用戶記錄，所有存放目錄項記錄的內節點存放100條目錄項，那麼：

通常在一般情況下，我們用到的B+樹不會超過4層. 節點層越高I/O 次數越多

3.3 常見索引概念

索引按照物理實現的方式，索引可以分為2種聚簇(聚集)索引和非聚簇(非聚集)索引，我們也把非聚集索引稱為二級索引或者輔助索引。

3.3.1 `聚簇索引`

聚簇索引並不是一種單獨的索引類型，而是一種數據存儲方式（所有的用戶記錄都存儲在了葉子節點），也就是所謂的索引即數據，數據即索引

術語聚簇表示數據行與相鄰的鍵值聚簇的存儲在一起

特點：

使用記錄主鍵值的大小進行記錄和頁的排序包括三個方面的含義

頁內的記錄是按照主鍵的大小順序排成一個單向鏈表。
各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。
存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。

B+樹的葉子節點存儲的是完整的用戶記錄。

所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。

我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個葉子節點處，這種聚簇索引應不需要們在mysql語句中顯式的使用index語句去創建，innodb存儲索引會自動的為我們創建局促索引。

優點：

數據訪問更快，因為聚簇索引將索引和數據保存在同一個B+樹中，因此從聚簇索引中獲取數據比非聚簇索引更快。
聚簇索引對於主鍵的排序查找和範圍查找速度非常快。
按照聚簇索引排列順序，查詢顯示一定範圍數據的時候，由於數據都是緊密相連，資料庫不用從多個數據塊中提取數據，所以節省了大量的io操作

缺點：

插入速度嚴重依賴於插入順序，按照主鍵的順序插入是最快的方式，否則出現頁分裂，嚴重影響性能，因此，對於innodb表，我們一般會定義一個字增的id列為主鍵。
更新主鍵的代價很高，因為會導致被更新的行移動，因此對於innodb表我們一般定義主鍵為不可更新。
二級索引訪問需要兩次索引查找，第一次找到主鍵值，第二次根據主鍵找到行數據。

限制：

對於Mysql 資料庫目前只有innodb數據引擎支持聚簇索引，而myisam並不支持聚簇索引。
由於數據物理存儲排序方式只有一種，所以每個Mysql的表只能有一個聚簇索引。一般情況下就是該表的主鍵
如果沒有定義主鍵，innodb就是選擇非空的唯一索引代替，如果沒有這樣的索引，innodb會隱式的定義一個主鍵來作為聚簇索引。
為了充分利用聚簇索引的聚簇特性，所以inndodb表的主鍵列儘量選用有序的順序id，而不建議用無序的id，比如uid、md5、hash等作為主鍵，無法保證數據的順序增長。

3.3.2 `二級索引`

上面介紹的聚簇索引只能是在搜索條件上是主鍵值時才能發揮作用，因為B+樹中的數據都是按照主鍵進行排序的，那如果我們以別的列來作為搜索條件該怎麼辦。肯定不能從頭到尾沿著鏈表一次遍歷記錄。

可以多建幾顆b+樹，不同的b+樹採用不同的排序規則，比如說c2列的大小作為數據頁、頁中記錄的排序規則在建立一顆B+樹。效果如圖：

這個B+樹與上面的介紹的聚簇索引有幾處不同：

使用記錄c2列的大小進行記錄和頁的排序，這包括三個方面的含義：
- 頁內記錄是按照c2的大小順序進行一個單向鏈表。
- 各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成一個雙向鏈表。
- 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的c2列順序排成一個雙向鏈表。
B+樹的葉子節點存儲的並不是完整的用戶記錄，而是c2列(當前二級索引列)+主鍵這兩個列的值。
目錄項記錄頁中不在是主鍵+頁號的搭配，而是c2列+頁號的搭配。

所以如果我們想通過c2列的值查找某些記錄的話就可以使用剛纔建立的B+樹，查詢c2=4的記錄，過程如下：

確定目錄項頁

從根頁44 快速定位目錄記錄所在的頁42上面（二級索引列c2。2<4<9 ）
通過目錄項記錄頁確定用戶記錄真實的頁

在頁42中，可以快速定位到實際存儲用戶記錄的頁，但是由於c2列並沒有唯一約束，所以c2值可能分佈在多個數據頁，所以可以確定在頁34和頁35中
在真實存儲用戶記錄的頁中定位到具體的記錄

在頁34和35中定位到具體的c2列和主鍵的記錄。
但是這個B+樹中葉子節點只存儲了c2（二級索引）和c1（主鍵）兩個列，所以我們必須在根據主鍵值去聚簇索引中再次查詢一次完整的用戶記錄。

概念：回表

我們根據這個以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們根據c2列查詢完整的記錄的話，仍然需要在聚簇索引中在查一遍，這個過程稱之為回表,也就是根據c2列的值查詢一條完整的用戶記錄需要用到兩顆B+樹。

小結：聚簇索引和非聚簇索引的原理不同，在使用上也有一些區別

聚簇索引的葉子節點存儲的就是我們的數據記錄，非聚簇索引的葉子節點存儲的是數據位置。非聚簇索引會影響數據表的物理存儲順序。
一個表只能有一個聚簇索引，因為只能有一個排序存儲的方式，但是可以有多個非聚簇索引，也就是多個索引目錄提供數據檢索。
使用聚簇索引的時候，數據查詢效率高,但是如果對數據進行插入、刪除更新等操作，效率會比非聚簇索引低。

3.3.3 `聯合索引`

我們頁可以同時以多個列的大小作為排序規則，也就是同時為多個列建立索引，比方說我們想讓B+樹按照c2和c3列的大小進行排序，這個包含兩層含義：

先把各個記錄和頁按照c2排序
在記錄的c2列相同的情況下，採用c3列進行排序

為c2和c3列建立的索引示意圖如下：

如圖所示：

每條目錄項記錄都由c2、c3、頁號三個部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同則按照c3值排序
B+樹葉子節點處的用戶記錄由c2、c3和主鍵c1列組成。

註意一點，以c2、c3的大小為排序規則建立的b+樹稱為聯合索引，本質也是一個二級索引，與普通的二級索引不同的是：

建立聯合索引只會建立如上圖一樣的一顆B+樹。
為c2和c3分別建立索引會分別以c2和c3的大小排序規則建立兩顆b+樹

3.4 InnoDB引擎的B+樹索引的註意事項

3.4.1 根頁面位置萬年不動

實際上B+樹的形成過程是這樣的：

每當為某個表創建一個B+數索引的時候，都會為這個索引創建一個根節點頁面，最開始沒有數據的時候，B+樹索引對應的根節點中既沒有用戶記錄，也沒有目錄項記錄
隨後向表中插入用戶記錄時，先把用戶記錄存儲到這個根節點中。
當根節點中的可用空間用完繼續插入記錄，此時會將根節點中的所有記錄複製到一個新分配的頁，比如頁a中。然後對這個新頁進行頁分裂操作，得到另一個新頁，比如頁b。這時新插入的記錄根據鍵值(也就是聚簇索引中的主鍵值，二級索引中對應索引列的值)的大小就會被分配到頁a或者頁b中，而根節點便升級為目錄項記錄的頁。

特別註意的是：一個B+數自誕生起，便不會在移動，這樣只要我們對錶進行建立索引，那麼他的根節點的頁號便會被記錄到某個地方，然後凡是InnoDB存儲引擎需要用的索引的時候，都會從那個固定的地方取出根節點的頁號。從而訪問這個索引。

3.4.2 內節點中目錄項唯一性

為了讓新加入的記錄找到自己在哪個數據頁里，我們必須要保證在B+樹里的同一層內的目錄項記錄除了頁號這個欄位以外是唯一的，所以對於二級索引的內節點的目錄項記錄的內容實際上是由三個部分構成的。

索引列的值
主鍵值
頁號

也就是我們把主鍵值頁添加到二級索引內節點中的目錄項記錄了，這樣就能保證B+樹每一層節點中各條目錄項記錄除頁號這個欄位以外是唯一的。所以最後肯定能定位唯一的一條目錄項記錄。

3.4.3一個頁面最少兩條記錄

一個B+樹只需要很少的層級就可以輕鬆存儲數億條記錄，查詢速度相當不錯！這是因為B+樹本質就是一個大的多層目錄，每經過一個目錄時就會過濾掉很多無效子目錄，知道最後訪問到存儲真實數據的目錄。

那如果一個大的目錄中只存放一個子目錄是什麼效果呢？那就是目錄層級非常多，而且最後那個存放真實數據的目錄中只能存放一條記錄，查詢時間很長只為了一條記錄，所以InnoDB的一個數據頁至少存放兩條記錄。

4、MyISAM中的索引方案

`B樹索引適用存儲引擎如表所示：`

索引	MyISAM	InnoDB	Memory
B-Tree	支持	支持	支持

即使多個存儲引擎支持同一種索引，但是他們實現的原理是不同的。InnoDB和MyISAM預設的索引是Btree索引，而Memory預設索引是HASH索引。

MyISAM引擎使用B+tree作為索引結構，葉子節點的data域存放的是數據記錄的地址

4.1 MyISAM索引的原理

我們都知道InnoDB引擎中索引即數據，也就是聚簇索引的那顆B+樹葉子節點中已經把所有完整的用戶記錄都包含了，而MyISAM的索引方案雖然頁使用樹形結構，但是卻將索引和數據分開存儲:

將表中記錄按照記錄的插入順序單獨存儲在一個文件中，稱之為數據文件。這個文件並不劃分為若幹個數據頁。有多少記錄就往這個文件中塞多少記錄，由於插入數據的時候並不需要刻意按照主鍵大小排序，所以我們並不能在這些數據上使用二分法查找。
使用MyISAM存儲引擎的表會把索引信息另外存儲到一個稱為索引文件的另一個文件中。MyISAM會單獨為表的主鍵創建一個索引，只不過在索引的葉子節點中存儲的不是完整的用戶記錄，而是主鍵值+數據記錄地址的組合。

MyISAM的索引文件僅僅保存數據記錄的地址，在MyISAM中主鍵索引和二級索引在結構沒任何區別，註視主鍵索引要求key是唯一，而二級索引的key是可以重覆的。

同樣是一顆B+樹，MyISAM存儲引擎中data域保存的並非具體的用戶結構，而是數據記錄的地址。因此MyISAM中索引檢索的演算法為：首先按照B+樹搜索演算法來進行搜索索引，如果指定的key存在，則取出data域的值,然後以data域的值為地址，讀取對應地址的數據記錄。

4.2 MyISAM和InnoDB對比

MyISAM的索引方式都是"非聚簇"的，與innodb包含一個聚簇索引是不同的.

在InnoDB中，我們只需要根據主鍵值對聚簇索引進行一次查找就能找到對應的記錄，而在MyISAM中卻需要一次回表的操作，意味著MyISAM中建立的索引相當於全是二級索引。
InnoBD的數據文件本身就是索引文件,而MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。
InnoDB的非聚簇索引data域存儲對應的主鍵值，而MyISAM存儲對應記錄的地址。換句話說，InnoDB的所有非聚簇索引都引用主鍵作為data域。
MyISAM的回表操作是十分快的，因為它拿到的是地址的偏移量去獲取數據的，反觀InnoDB是通過獲取主鍵之後在去簇聚索引中獲取記錄，雖然說不頁不慢，也比不上直接地址去訪問。
InnoDB要求必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則Mysql會自動選擇一個可以非空且唯一的數據記錄的列作為主鍵，如果沒有，則會自動為InnoDB生成一個隱式的欄位作為主鍵，這個長度為6個位元組，類型為長整型。

小結：

瞭解不同的存儲引擎的索引實現方式對於正確使用和優化索引都是非常有幫助的。比如：

當我們知道innodb索引的實現後，就很容易明白不建議使用過長欄位作為主鍵，因為所有的二級索引都是引用的主鍵索引，過長的主鍵會令二級索引變得過大。
用非單調的欄位作為主鍵在innodb中也不好，因為innodb本身就是一個b+樹，非單調主鍵會造成在插入新紀錄時，數據為了維持B+tree的特性而頻繁的分裂調整，十分低效。而使用自增欄位作為主鍵式非常好的方式。

5、索引的代價

索引是個好東西，但是不能亂建，他在空間和時間上都會有消耗。

空間上的代價
- 每次建立索引都要為它建一顆B+樹，每一顆B+樹的每個節點都是數據頁，一個頁預設會占用16KB的空間，一顆很大的B+樹由許多數據頁組成，那就是一片很大的存儲空間
時間上的代價
- 每次對錶的數據進行增刪改查，都需要去修改各個B+樹索引。而我們說過，B+樹每層節點都是按照索引列的順序排序組成的雙向鏈表。不論是葉子節點的記錄，還是內節點的記錄都是按照索引列的值從小到大的順序形成了一個單向鏈表，而增刪改的操作可能會對節點和記錄的排序造成破壞，所以存儲引擎需要額外的時間進行一些記錄移位、頁面分裂、頁面回收等的操作來維護好節點和記錄的排序。如果我們建立了許多索引，每個索引對應B+樹都要進行相關的維護，給性能拖後腿.

一個表的索引建立的越多，就占用越多的存儲空間。再增刪改的時候性能就會越差，為了建立又好又少的索引，我們得學學這些索引是在那些條件下起作用的。

6、MySQL數據結構選擇的合理性

從MySQL的角度來講，不得不考慮的一個現實的問題就是磁碟的IO，如果我們能讓索引的數據結構儘量的減少硬碟的IO操作，所消耗的時間也就越少，可以說磁碟的IO操作次數對索引的使用效率至關重要。

查找都是索引操作，一般來說索引非常大，尤其是關係型資料庫，當數據量比較大的時候，索引的大小有可能幾個G甚至更多，為了減少索引在記憶體中的占用，資料庫索引是存儲在外部磁碟的，當我們利用索引是不可能把整個索引全部載入到記憶體，只能逐一載入，那麼Mysql衡量查詢效率的標準就是IO次數。

6.1 全表遍歷

進行順序的全表掃描每行數據

6.2 Hash結構

hash本身是一個函數，又被稱為散列函數，它可以幫助我們大幅提升檢索數據的效率。

Hash演算法是通過某種確定性的演算法（如：MD5、SHA1、SAH2、SAH3）講輸入轉變為輸入。相同的輸入永遠可以得到相同的輸出，假設輸入內容有微小的偏差，在輸出種通常都會有不同的結果。

加速查找速度的數據結構，常見的有兩類：

樹,例如平衡二叉樹，查詢插入修改和刪除的平均時間複雜度都是o(log2n);
哈希，例如HashMap(無序)，查詢插入修改刪除的平均時間複雜度是都o(1);

採用Hash進行檢索效率非常高，基本上一次檢索就可以找到數據，而B+樹需要自頂向下一次查找，多次訪問節點才能找到數據，中間需要多次IO，從效率來講Hash比B+樹更快。

Hash結構效率高，那麼為什麼索引結構要設計成樹型呢？原因如下：

Hash索引僅能滿足（=、<>）和in查詢。如果進行範圍查詢，哈希型索引，時間複雜化會退化為O（n）而樹型的有序特性，依然能保持O（log2n）的高效率。
Hash索引還有一個缺陷，數據的存儲是沒有順序的，在OrderBy的情況下，使用Hash索引還需要對數據進行重新排序。
對於聯合索引的情況，Hash值是將聯合索引鍵合併後一起計算的，無法對單獨的一個鍵或者幾個索引鍵來查詢。
對於等值查詢來說，通常Hash索引的效率更高，不過也存在一種情況，就是索引列的重覆值如果很多，效率就會降低。這是因為遇到Hash衝突時，需要遍歷桶中的行指針來比較，找到查詢的關鍵字，非常耗時。所以Hash索引通常不會用到重覆值多的列上，比如列為性別、年齡的情況

6.3 二叉搜索樹

我們利用二叉樹來作為搜索條件，那麼磁碟的IO次數和索引樹的高度是相關的。

二叉搜索樹的特點
- 一個節點只能有兩個子節點，也就是一個節點度不能超過2
- 左子節點< 本節點;右子節點>=本節點，比我大的向右，比我小的向左。
查找規則

我們先來看看最基礎的二叉搜索樹，搜索某個節點和插入節點的規則一樣，我們也假設搜索插入的數據為key：
- 如果key大於根節點，則在右子樹查找；
- 如果key小於根節點，則在左子樹查找；
- 如果key等於根節點，直接返回根節點。

我們對一個數列（34,22,89,5,23,77,91）創造出來的一個二分查找樹如下：

二叉樹搜索也存在特殊情況，有時候二叉樹的搜索深度非常大，比如我們給的數列的順序是（2,22,23,34,77,89,91）如圖：

雖然也屬於二分查找樹，但是性能上已經退化成一個鏈表，那麼查詢的數據的時間複雜度變成了O(n). 為了提高查詢效率，就需要減少磁碟的IO數，為了減少磁碟的io，就需要降低樹的高度，需要把原來瘦高的樹結構變得矮胖，樹的每層分叉越多越好。

引入AVL樹。

6.4 AVL樹

為瞭解決上面二叉樹退化成鏈表的問題，人們提出了平衡二叉搜索樹，又稱為AVL樹，它在二叉搜索樹的基礎上增加了約束，具有一下特點：

它是一顆空樹或它的左右子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一個平衡二叉樹

這裡說一下，常見的平衡二叉樹有多種，包括平衡二叉搜索樹、紅黑樹、數堆、伸展樹。平衡二叉搜索樹是最早提出來的自平衡二叉樹,當我們提到平衡二叉樹時，一般是指的平衡二叉搜索樹。事實上第一棵樹就屬於平衡二叉搜索樹，搜索時間複雜度就是O(log2n)。

數據查詢的時間主要依賴於磁碟Io的次數，如果我們採用二叉樹的形式，即使通過平衡二叉搜索樹進行了改進，樹的深度也是O(log2n)，當n比較大時深度也是比較高的。如圖所示：

每訪問一次節點就需要對磁碟進行一次IO，對於上面的樹來說，我們需要進行5次IO 雖然平衡二叉樹的效率高，但是樹的深度也很高，就意味著io的次數多，會影響整體的一個效率。

針對同樣的數據，如果我們把二叉樹改成M叉樹(M>2)呢當m=3時，同樣的31個節點可以有下麵的三叉樹來進行存儲：

你能看到此時樹的高度降低了，當數據量n大的時候，以及樹的分叉樹M大的時候，M叉樹的高度會遠小於二叉樹的高度(M>2).所以，我們需要把樹從瘦高變成矮胖。

引入B樹。

6.5 B-Tree

B樹的英文是Balance tree，也就是多路平衡查找樹。簡寫就是B-Tree。他的高度遠遠小於平衡二叉樹的高度。B樹的結構如圖：

B樹作為多路平衡查找樹,它的每一個節點最多包括M個子節點，M稱為B樹的階。每個磁碟種包括了關鍵字和子節點的指針 。如果一個磁碟塊中包括了x個關鍵字，那麼指針樹就是x+1。對於一個100階的B樹來說，如果有三層的話最多可以存儲大約100萬的索引數據。對於大量的索引數據來說，採用b樹的結構是非常適合的，因為樹的高度遠小於二叉樹的高度。

B樹在插入和刪除節點的適合如果導致樹不平衡，就通過自動調整節點的位置來保持樹的自平衡。
關鍵字集合分佈在整個樹中，即葉子節點和非葉子節點都存放數據。搜索有可能在非葉子節點結束。
其搜索性能等價於在關鍵字全集內做一次二分查找。

與B+樹的區別在於，B+樹的所有數據都在葉子節點存儲，而B樹則葉子節點和非葉子節點都存放數據。

6.6 B+Tree

B+ 樹也是一種多路平衡查找樹,基於B樹做出了改進，主流的DBMS都支持B+樹的索引方式，比如Mysql。相比較B-Tree，B+Tree更適合文件索引系統。

B+樹和B樹的差異在於以下幾點：

有k個孩子(葉子節點數據頁)的節點就有k個關鍵字(目錄項記錄)。也就是孩子數量=關鍵字，而B樹中，孩子數量=關鍵字+1。
B+樹中非葉子節點的關鍵字也會同時存在子節點中，並且是子節點中所有關鍵字的最大（或最小）。
非葉子節點僅僅用於索引，不保存數據記錄，跟記錄有關的信息都存放在葉子節點中。而B樹中非葉子節點即保存索引，也保存數據記錄。
所有關鍵字都在葉子節點出現。葉子節點構成一個有序鏈表，而且葉子節點本身按照關鍵字從小到大順序鏈接。

B+樹和B樹有個根本性的差異在於,B+樹的中間節點並不直接存儲數據。這樣有什麼好處呢？

首先，B+樹查詢效率更穩定。因為B+樹每次只有訪問到葉子節點才能找到對應的數據，而在B樹種，非葉子節點也會存數據，這樣就會造成查詢效率不穩定的情況，有時候訪問到非葉子節點就能找到數據，而有時候需要訪問到葉子節點。

其次。B+樹的查詢效率更高，這是因為通常B+樹比B樹更加的矮胖(階數更大，深度更低)，查詢所需要的磁碟IO也會更少，同樣的磁碟頁大小，B+樹可以存儲更多的節點關鍵字。

不僅是對單個關鍵字的查詢上，在查詢範圍上B+樹的效率也比B樹高，，這是因為所有關鍵字都出現在B+樹的葉子節點，葉子節點之間會有指針，數據又是遞增的，這使得我們範圍查找可以通過指針鏈接查詢。而在B樹中則需要中序遍歷才能完成查詢範圍的查找，效率要低很多。

B樹和B+樹都可以作為索引的數據結構，在Mysql 中採用的是B+樹。

但是B樹和B+樹都有自己的應用場景，也不能說B+樹就一定比B樹好。

思考：為了減少io ，索引樹會一次性載入嗎？

資料庫索引是建立在磁碟上的，如果數據量很大，必然導致索引的大小也會很大，超過幾個G。
當我們利用索引查詢的時候，是不可能講全部的幾個G的索引都載入進記憶體的，我們能做的只能是，逐一載入每個磁碟頁，因為磁碟頁對應著索引樹的節點

思考： B+樹的存儲能力如何？為何說一般查找行記錄，最多只需要1~3次磁碟I/O?

InnoDB存儲中頁的大小為16KB，一般表的主鍵類型為int(4個位元組)或BIGINT(8個位元組),指針類型也一般為4或8個位元組，也就是一個數據頁中大概存儲16KB/(8b+8b)= 1k 個鍵值，因為是一個估值，為了方便計算，這裡的K取值為10^3. 也就是說一個深度為3的B+Tree索引可以維護10^3 * 10^3 * 10^3=10億條記錄。在實際情況中 每個節點可能不能填充滿，因此在資料庫中，B+Tree的高度一般是1~4層。Mysql的InnoDB存儲引擎在設計時是講根節點常駐記憶體的，也就是在查找時最多再進行1-3次磁碟的IO。

思考:為什麼說B+樹比B樹更適合實際應用中操作系統的文件索引和資料庫索引？

B+樹的磁碟讀寫代價更低。
B+樹的查詢效率更穩定。

思考:Hash索引與B+樹索引的區別？

Hash索引不能進行範圍性的一個查找，因為hash指向的數據是無序的，而B+樹的葉子節點是個有序的鏈表。
Hash索引不支持聯合索引的最左側原則(即聯合索引的部分索引無法使用)，而B+樹可以。對於聯合索引來說，Hash索引在計算Hash值得時候將索引鍵合併後再一起計算Hash值，所以不會針對每個索引單獨計算hash值。因此如果用到聯合索引的一個或者多個索引時，無法被利用。
Hash不支持OrderBy排序，以為Hash索引指向的數據無序，因此無法起到排序的作用。而B+樹索引數據是有序的，可以起到對該欄位order by排序優化的作用，同理，我們也無法對hash索引進行模糊查找,而B+樹使用模糊查詢的方式時，like後面後模糊查詢的話就可以起到優化作用。
InnoDB不支持Hash索引。

6.8 小結

使用索引可以幫助我們從海量的數據中快速的定位到我們想要的數據，不過索引也存在一定的不足，比如占用存儲空間、降低資料庫寫操作的性能等，如果有多個索引還會增加索引選擇的時間。當我們使用索引時，需要平衡索引的利(查詢效率)和弊(維護索引的代價)。

在實際工作中，我們還需要基於需求和數據本身的分佈情況來確定是否使用索引，儘管索引不是萬能，但是數據量大的時候不使用索引是不可想象的，畢竟索引的本質，是幫助們提升數據檢索的效率。

本文來自博客園，作者：酷酷的sinan，轉載請註明原文鏈接：https://www.cnblogs.com/Kuju/p/16205921.html

關於Mysql索引的數據結構