索引，是幫助MySQL高效獲取數據的一數據結構，也就是說，通過創建索引，我們可以提高查詢的效率。索引的本質是一種數據結構。下面讓我們慢慢的分析下MySQL的索引實現原理。

一、為什麼要用索引

假如我們一張表中有一百萬的條數據，執行select * from user where id='1'，在沒有創建索引的情況下，將會進行全表掃描。顯然是超級不可取的一種方式。因此我們需要對id進行建立索引，提高查詢效率。

二、索引分類

1、數據結構-Hash

哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。是的，若僅僅執行語句select * from user where id='1'，無疑用Hash查詢是超級快的，但是假如我需要查詢select * from user where id>'1'，那麼由於Hash是根據鍵值進行訪問的，此時是範圍查詢，就不方便了，將會類似於全表掃描。

<code>優點：查找可以直接根據key訪問缺點：不支持範圍查詢/<code>

2、數據結構-平衡二叉樹

平衡二叉查找樹，又稱 AVL樹。 它除了具備二叉查找樹的基本特徵之外，還具有一個非常重要的特點：它 的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值（平衡因子 ） 不超過1。 也就是說AVL樹每個節點的平衡因子只可能是-1、0和1（左子樹高度減去右子樹高度）。如下圖所示：

這裡假如查找0010，順序如下

1. 從硬盤讀取0004到內存中，比較0010>0004, 取右子樹；
2. 從硬盤讀取0008到內存中，比較0010>0008, 取右子樹；
   
3. 從硬盤讀取0009到內存中，比較0010>0009，取右子樹；
   
4. 從硬盤讀取0010到內存中，比較0010==0010，查詢成功；

由上可知，。進行了4次的IO操作。

1. 優點：查詢效率較高，
2. 缺點：雖然支持範圍查詢，但是迴旋查詢效率較低，插入操作需要進行旋轉。並且隨著樹的深度增加，IO查詢次數將會增大。

3、數據結構-B樹

維基百科對B樹的定義為“在計算機科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序並允許以O(log n)的時間複雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多於2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B樹為系統最優化大塊數據的讀和寫操作。B-tree算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在數據庫和文件系統。

這裡假如查找0010，順序如下

1. 從硬盤讀取0004到內存中，比較0010>0004, 取右子樹；
   
2. 從硬盤讀取0006和0008到內存中，比較0010>0008, 取右子樹；
3. 從硬盤讀取0009和0010到內存中，比較0010>0010, 查詢成功；

由上可知。只進行了三次IO操作。因為B樹節點元素比平衡二叉樹要多，所以B樹數據結構相比平衡二叉樹數據結構實現減少磁盤IO的操作。

1. 優點：B樹查詢效率比平衡二叉樹效率要高，因為B樹的節點中可以有多個元素，從而減少樹的高度，減少IO操作，從而提高查詢效率。
2. 缺點：範圍查詢效率還是比較低。

4、數據結構B+樹

通過繼承了B樹的特徵，B+樹相比B樹，新增葉子節點與非葉子節點關係，葉子節點中包含了key和value，非葉子節點中只是包含了key，不包含value。通過非葉子節點查詢葉子節點獲取對應的value，所有相鄰的葉子節點包含非葉子節點，使用鏈表進行結合，有一定順序排序，從而範圍查詢效率非常高。也就是說，上面的二叉樹和B-tree，都是每個節點不僅保存key，而且還保存了value(可能是地址，可能是內容)，但是B+tree非葉子節點只會保存key，只有葉子節點才會保存key和value。

由圖可以知道，雖然都是三層IO，但是葉子節點包含了非葉子節點，使用鏈表進行結合，有一定的順序排序，所以範圍查詢效率也是非常高的，不需要一個個做迴旋對比。

1. 優點：範圍查詢效率非常高；
   
2. 缺點：因為有冗餘的節點數據，所以比較耗內存；

5、小結

有上可知，最終還是會回到了時間和空間的問題，不可能二者兼得，減少了時間就必須多耗費空間，減少了空間的使用，就必須降低查詢效率。當然我們知道mysql索引的數據結構是樹，常用的存儲引擎innodb採用的是B+Tree。MyISAM和InnoDB對B-Tree索引的實現方式是不同的，我們下面來分析下。順便說一句：有一個很好用的網站可以讓我們直觀的操作數據結構：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html ，我上面的圖就是根據這個畫得。

三、MyISAM和InnoDB對B+樹索引的實現方式

我們先理解兩個概念：非聚簇索引和聚簇索引

非聚集索引。表數據存儲順序與索引順序無關。對於非聚集索引，葉結點包含索引字段值及指向數據頁數據行的邏輯指針，其行數量與數據錶行數據量一致。非聚簇索引的數據表和索引表是分開存儲的。

葉結點包含索引字段值及指向數據頁數據行的邏輯指針。

聚集索引。表數據按照索引的順序來存儲的，也就是說索引項的順序與表中記錄的物理順序一致。對於聚集索引，葉子結點即存儲了真實的數據行，不再有另外單獨的數據頁。 在一張表上最多隻能創建一個聚集索引，因為真實數據的物理順序只能有一種。

葉子結點即存儲了真實的數據行，不再有另外單獨的數據頁。

MyISAM存儲引擎採用的是非聚簇索引，葉子結點的key都存儲指向鍵值對應的數據的物理地址。InnoDB存儲引擎採用的是聚簇索引，聚簇索引的數據和主鍵索引存儲在一起。也就是對於B+樹來說，非聚集索引，葉子節點只會存儲指向數據頁數據行的邏輯指針。而聚集索引則存儲了真實的數據行，不再有另外單獨的數據頁。如下人圖：MyISAM非聚集索引

InnoDB聚集索引

通過上面兩個圖，我們應該很清楚的明白了MyISAM和InnoDB對B+樹索引的實現方式上的區別。再總結一下：MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在InnoDB中，表數據文件本身就是按B+樹組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引。

四、MyISAM和innoDB引擎對比

上面是描述了兩大引擎實現B+tree上的區別，這裡再比較一下這兩個引擎。

五、MySQL數據庫優化方案

Mysql的優化，大體可以分為三部分：

1、索引的優化

1.最左前綴索引的最左前綴和和B+Tree中的“最左前綴原理”有關，舉例來說就是where之後的條件如果設置了組合索引<col1>那麼以下3中情況可以使用索引：col1，<col1>，<col1>，其它的列，比如<col2>，<col1>，col2，col3等等都是不能使用索引的。也就是：/<col1>/<col2>/<col1>/<col1>/<col1>

<code>select * from table where col1="a";
select * from table where col1="a" and col2="b";
select * from table where col1="a" and col2="b" and col3="c";/<code>

上面三條語句是可以用到索引的。但是如下四條不遵從最左前綴的,導致索引失效：

<code>select * from table where col2="b";
select * from table where col3="c";
select * from table where col2="b" and col3="c";
select * from table where col1="a" and col3="c";/<code>

當然前提是<col1>為組合索引。/<col1>

2.不在索引列上做任何操作,否則會導致索引失效而轉向全表掃描

select * from table where left(col1,4)=’a’;

3.存儲引擎不能使用索引中範圍條件右邊的列,範圍之後全失效,將導致col1和col2被用到了，col3失效

select * from table where col1=’a’ and col2 >25 and col3=’c’;

4.儘量用覆蓋索引(覆蓋索引:查詢的列和所建立的索引的列個數相同,字段相同),減少select * 的使用

5.儘量不使用!=或<>,如果使用,則無法使用索引,會導致全表掃描

6.is null, is not null無法使用索引

7.帶索引的模糊查詢優化like查詢,%要在最右側(‘字符串%’),否則會進行全表掃描,那麼如何解決like查詢時’%字符串%’時索引不被使用的方法(可以使用覆蓋索引)

8.字符串類型不加單引號會導致索引失效,因為mysql會自己做類型轉換,相當於在索引列上進行了操作

9.少用or,用它會索引失效

2、sql慢查詢的優化

查詢優化神器 – explain命令,步驟如下：

1. 先運行看看是否真的很慢，注意設置SQL_NO_CACHE
2. where條件單表查，鎖定最小返回記錄表。這句話的意思是把查詢語句的where都應用到表中返回的記錄數最小的表開始查起，單表每個字段分別查詢，看哪個字段的區分度最高
   
3. explain查看執行計劃，是否與1預期一致（從鎖定記錄較少的表開始查詢）
   
4. order by limit 形式的sql語句讓排序的表優先查
   
5. 瞭解業務方使用場景
   
6. 加索引時參照建索引的幾大原則觀察結果，不符合預期繼續從0分析

3、表的優化

當MySQL單表記錄數過大時，增刪改查性能都會急劇下降，可以參考以下步驟來優化：單表優化除非單表數據未來會一直不斷上漲，否則不要一開始就考慮拆分，拆分會帶來邏輯、部署、運維的各種複雜度，一般以整型值為主的表在千萬級以下，字符串為主的表在五百萬以下是沒有太大問題的。而事實上很多時候MySQL單表的性能依然有不少優化空間，甚至能正常支撐千萬級以上的數據量：

1.字段

1. 儘量使用TINYINT、SMALLINT、MEDIUM_INT作為整數類型而非INT，如果非負則加上UNSIGNED
   
2. VARCHAR的長度只分配真正需要的空間
   
3. 使用枚舉或整數代替字符串類型
   
4. 儘量使用TIMESTAMP而非DATETIME，單表不要有太多字段，建議在20以內
   
5. 避免使用NULL字段，很難查詢優化且佔用額外索引空間用整型來存IP

2.索引

1. 索引並不是越多越好，要根據查詢有針對性的創建，考慮在WHERE和ORDER BY命令上涉及的列建立索引，可根據EXPLAIN來查看是否用了索引還是全表掃描
   
2. 應儘量避免在WHERE子句中對字段進行NULL值判斷，否則將導致引擎放棄使用索引而進行全表掃描
   
3. 值分佈很稀少的字段不適合建索引，例如"性別"這種只有兩三個值的字段
   
   
4. 字符字段只建前綴索引
   
5. 字符字段最好不要做主鍵
   
6. 不用外鍵，由程序保證約束
   
7. 儘量不用UNIQUE，由程序保證約束使用多列索引時主意順序和查詢條件保持一致，同時刪除不必要的單列索引

3.查詢SQL

1. 可通過開啟慢查詢日誌來找出較慢的SQL
   
2. 不做列運算：SELECT id WHERE age + 1 = 10，任何對列的操作都將導致表掃描，它包括數據庫教程函數、計算表達式等等，查詢時要儘可能將操作移至等號右邊
   
3. sql語句儘可能簡單：一條sql只能在一個cpu運算；大語句拆小語句，減少鎖時間；一條大sql可以堵死整個庫不用SELECT *OR改寫成IN：OR的效率是n級別，IN的效率是log(n)級別，in的個數建議控制在200以內
   
4. 不用函數和觸發器，在應用程序實現避免%xxx式查詢少用JOIN
   
   
5. 使用同類型進行比較，比如用'123'和'123'比，123和123比
   
6. 儘量避免在WHERE子句中使用!=或<>操作符，否則將引擎放棄使用索引而進行全表掃描
   
7. 對於連續數值，使用BETWEEN不用IN：SELECT id FROM t WHERE num BETWEEN 1 AND 5
   
8. 列表數據不要拿全表，要使用LIMIT來分頁，每頁數量也不要太大

4.引擎

<code>總體來講，MyISAM適合SELECT密集型的表，而InnoDB適合INSERT和UPDATE密集型的表。/<code>

當然還有一些參數配置的優化。

六、總結

我們從啥是索引，以及索引的類別和優缺點到MySQL兩種引擎實現B+tree不同方式對比，到最後大概說明了下MySQL的優化。基本上對MySQL的索引有了一個大概的認識，以後每一部分還是需要再深入研究瞭解的。話說又費了兩個鍾，以後還是要換方法，比如今天學習總結，明天再整理為博文，而不是邊學習邊整理，太費時間啦。

閱讀更多 Java全棧 的文章

關鍵字: 算法 數據結構 解析