關于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

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/468085.html

標籤：MySQL

上一篇：Mysql 連續時間分組

下一篇：MySQL 事務和鎖

關于Mysql索引的資料結構