一、索引是什么

MySQL官方對索引的定義為：索引(Index)是幫助MySQL 高效 獲取數據的數據結構，而MYSQL使用的數據結構是：B+樹

在這里推薦大家看一本書，《深入理解計算機系統的書》

1.1 局部性原理

程序和數據的訪問都有聚集成群的傾向，在一個時間段內，僅使用其中一小部分，在最近的將來將用到的信息很可能與現在正在使用的信息在空間地址上是臨近的(稱空間局部性)，或者最近訪問過的程序代碼和數據，很快又被訪問的可能性很大(稱時間局部性)。

1.2 磁盤預讀

預讀的長度一般為頁(page)的整數倍頁是存儲器的邏輯塊，操作系統往往將主存和磁盤存儲區分割成連續的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統中，頁大小通常為4K)，主存和磁盤以頁為單位交換數據

1.3 簡介

在使用數據庫中，通常數據庫查詢是數據庫的最主要功能之一。但每種查找算法都只能應用于特定的數據結構之上。

• 例如二分查找要求被檢索數據有序
• 而二叉樹查找只能應用于二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構(例如，理論上不可能同時將兩列都按順序進行組織)，所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。索引一般以文件形式存儲在磁盤上，索引檢索需要磁盤I/O操作。所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。

1. 索引是幫助 MYSQL 高效獲取數據的數據結構
2. 索引存儲在文件系統中
3. 索引的 文件存儲形式與存儲引擎有關
4. 索引文件的結構：hash、二叉樹、B樹、B+樹

二、索引的分類

2.1 hash

這里有一個mysql數據文件，有Id和name兩個列，如果我們用hash格式存儲的話(hash表)，我們只要計算出某一個列的hash值，把它按照按照數組的長度取一個模，就可以取到從0-7n個下標的位置，這樣的話效率其實是比較高的，但是用hash表存儲，它具備一定的缺點 ：

1. 利用hash存儲的話需要將所有的數據文件添加到內存中，比較耗費內存空間
2. 如果所有的查詢都是等值查詢，那么hash確實很快，但是在企業或者實際工作環境中范圍查找的數據更多，而不是等值查詢，因為hash就不太適合了，因此在mysql里面并沒有選擇hash存儲的格式2.2 二叉樹

索引格式：

對于樹有他是有一個更新跌過的順序在里面，不要一上來就看結構，先是了解什么樹，樹都是由一個樹根，然后有n多個分支組成，這些分支就是一些樹形結構，多你有多個樹分支(多元素)的時候，這個時候查找效率就會比較低，因此就有了二叉樹的東西，二叉樹為什么會好用一點，因為二叉樹它是都有兩個分支，但是兩個分支的話，會導致一個效果，就是每次我們在查找數據的時候，類似于二分查找的，但是二叉樹也有自己不太好的地方，大家可以看我們上圖中的二叉樹的索引格式，在左邊的節點會比較短一點(只需要讀三次)，而右邊的節點會長很多(需要讀五次)，會導致樹的深度比較深，每一次樹的節點讀取，都會有一次IO，深度越高，IO越高，會影響我們數據讀取的效率，因此也有了(平衡二叉樹)和(紅黑樹)

平衡二叉樹： 維護一個平衡，就是左子樹和右子樹高度之差，不能大于1，但是對于我們上面的格式就不太適合，因為他已經超過1了，但是AVL樹也會有一個問題就是調整的次數太頻繁了，它里面涉及到了一個操作就是旋轉，一種左旋，一個右旋，為了保持平衡需要N多次的旋轉，這樣的旋轉其實是很浪費時間的，每次新增或者刪除的時候，都要經歷N多次旋轉，效率太低了

推薦大家一個網站，可以直接看到AVL樹操作過程，有不了解的同學可以去看一看，很形象：AVL Trees (Balanced binary search trees)

紅黑樹： 本身也是一個平衡樹，但是它從中間做了一個權衡，就是損失一部分平衡的性能，但是又保持了相對的平衡，它做了這樣一個操作，就是最長子樹的高度，只要不超過最短子樹的兩倍，就可以了，同時在紅黑樹中它引入了紅和黑兩個節點信息，有了這些信息它可以幫助我們做一個平衡，在AVL樹有旋轉保持平衡，而紅黑樹有了旋轉和變色兩種來保持平衡，紅黑樹是AVL樹的進階，它損失了一部分平衡的性能，但是維護了我們插入和刪除數據的高效，雖然它損失了一部分性能，但是它依然是一個平衡樹，既然是平衡樹，他最長子樹，不超過最短子樹的兩倍，那意味著如果最短子樹是 4 ，那么最長子樹就是8，這樣在們查找數據的時候，又不是一個二分查找了，效率又會變低

無論是二叉樹還是紅黑樹，都會因為樹的深度過深而造成IO次數變多，影響數據的讀取的效率，最重要的就是減少IO

IO是我們IT行業中的一個瓶頸，一個是磁盤IO一個是網絡IO，我們作為軟件開發，是沒有辦法去調整硬件方面的瓶頸，只能從從程序里面減少我們的IO量，我們有兩個方向，一個是減少IO的次數，一個是減少IO的量，從這兩個方面去解決，比如說原來我們讀取數據要讀10次，現在只要讀取一次，這樣的IO量就少了10倍，原來我們需要讀1MB的數據，現在只要讀1KB的數據，這也就是為什么我們在寫mysql查詢語句的時候不推薦使用select * from ，因為這樣的查詢會查詢到N多個字段，本來我只要兩個字段，但是給了我30個字段，這樣會導致IO量增加了，因此我們就會去考慮，關于索引的次數能不能減少，因此下面就引出了我們的——B樹

2.3 B樹

B樹的特點：

• 所有的鍵值分布在整顆樹中
• 搜索有可能在非葉子結點結束，在關鍵字全集內做一次查找，性能逼近二分查找
• 每個節點最多擁有m個子樹
• 根節點至少有2個子樹
• 分支節點至少擁有m/2顆子樹(除根節點和葉子節點外都是分支節點)
• 所有葉子節點都在同一層，每個節點最多可以有m-1個key，并且以升序排列

B樹結構說明：

示例圖說明：每個節點占用一個磁盤塊，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的地址，兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為列，關鍵字為16和34，p1指針指向的子樹的數據范圍小于16，P2指針指向的子樹的數據范圍為16-34，P3指針指向的子樹的數據范圍大于34 查找關鍵字(28)過程：

• 根據節點找到磁盤塊1，讀取內存【磁盤I/O操作第1次】
• 比較關鍵字28在區間(16,34)找到磁盤塊1的指針P2
• 根據P2指針找到磁盤塊3，讀入內存【磁盤I/O操作第2次】
• 比較關鍵字28在區間(25,31)，找到磁盤塊3的指針P2
• 根據P2指針找到磁盤塊8，讀取內存，【磁盤I/O操作第3次】
• 在磁盤塊8中的關鍵字列表找到關鍵字28

缺點：

• 每個節點都有key，同時也包含data，而每個頁存儲空間是有限的，如果data比較大的話會導致每個節點存儲的key數量變小
• 當存儲的數據量很大的時候會導致深度較大，增大查詢時磁盤IO次數，進而影響查詢性能

2.4 B+樹

B+Tree 是在BTree 的基礎之上做的一種優化，變化如下：

• B+Tree 每個節點可以包含更多的節點，這個做的 原因有兩個，第一個原因是為了降低樹的高度，第二個原因是將數據范圍變為多個區間，區間越多，數據檢索的越快
• 非葉子節點存儲key(1,2,3磁盤都是存儲的key)，葉子節點存儲key和數據
• 葉子節點兩兩指針相互連接(符合磁盤的預讀特性)順序查詢性能更高如果當前磁盤塊下沒有其他節點，就是 葉子節點，反之就是 非葉子節點

結構圖：

注意：在B+Tree上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有的葉子節點(即數據節點)之間是一種鏈式環結構，因此可以對B+Tree進行兩種查詢運算，一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始，進行隨機查找。

三、mysql的存儲引擎

3.1 mysql innoDB (葉子節點直接放置數據)

3.1 mysql innoDB (葉子節點直接放置數據)

存放的是對應的行記錄

1、InnoDB是通過B+Tree結構對主鍵創建索引，然后葉子節點中存儲記錄，如果沒有主鍵，那么會選擇唯一鍵，如果沒有唯一鍵，那么會生成一個6位的row_id來作為主鍵

2、如果創建索引的鍵是其他字段，那么在葉子節點中存儲的是該記錄的主鍵，然后在通過主鍵索引找到對應的記錄

在name上建立索引

在name列上存放的是ID，然后通過ID去找到對應的key和數據

3.1 mysql MyISAM

下面0X0022其實就是地址，顯示根據我們的ID，找到我們的地址，然后通過地址去找到對應的表對應的數據

四、索引的分類

mysql索引的五種類型：主鍵索引、唯一索引、普通索引和全文索引、組合索引。通過給字段添加索引可以提高數據的讀取速度，提高項目的并發能力和抗壓能力

• 主鍵索引：> 主鍵是一種唯一性索引，但它必須指定為PRIMARY KEY，每個表只能有一個主鍵
• 唯一索引 > 索引列的所有值都只能出現一次，即必須唯一，值可以為空
• 普通索引 > 基本的索引類型，值可以為空，沒有唯一性的限制
• 全文索引 > 全文索引的索引類型為FULLTEXT，全文索引可以在 varchar、char、text類型的列上創建
• 組合索引 > 多列值組成的一個索引，專門用于組合搜索

五、mysql的存儲引擎

小結

寫這篇文章的時候，小農的公司群消息不斷，因為項目中有問題需要我去解決，今天的mysql索引機制就到這里了.