從千萬級資料查詢來聊一聊索引結構和資料庫原理

在日常工作中我們不可避免地會遇到慢SQL問題，比如筆者在之前的公司時會定期收到DBA彪哥發來的Oracle AWR報告，并特别提示我某條sql近階段執行明顯很慢，可能要優化一下等。對于這樣的問題通常大家的第一反應就是看看sql是不是寫的不合理啊諸如：“避免使用in和not in，否則可能會導緻全表掃描”“ 避免在where子句中對字段進行函數操作”等等，還有一種常見的反應就是這個表有沒有加索引？絕大部分情況下，加了個索引基本上就搞定了。

既然題目是《從千萬級資料查詢來聊一聊索引結構和資料庫原理》，首先就來構造一個千萬級的表直覺感受下。我們建立了一張user表，然後插入了1000萬條資料，查詢一下：

用了近30秒的時間，這還是單表查詢，關聯查詢明顯會更讓人無法忍受。接下來，我們隻是對id增加一個索引，再來驗證一把：

從30s到0.02s，提升了足足1500倍。為什麼加了索引之後，速度嗖地一下子就上去了呢？我們從【索引資料結構】、【Mysql原理】兩個方面入手。

一、索引資料結構

我們先來看下 MySQL官方對索引的定義：

索引（Index）是幫助MySQL高效擷取資料的資料結構。

這裡面有2個關鍵詞：高效查找、資料結構。對于資料庫來說，查詢是我們最主要的使用功能，查詢速度肯定是越快越好。最基本的查找是順序查找，更高效的查找我們很自然會想到二叉樹、紅黑樹、Hash表、BTree等等。

1.1 二叉樹

這個大家很熟悉了，他有一個很重要的特點： 左邊節點的鍵值小于根的鍵值，右邊節點的鍵值大于根的鍵值。比如圖1，它确實能明顯提高我們的搜尋性能。但如果用來作為資料庫的索引，明顯存在很大的缺陷，但對于圖2這種遞增的id，存儲後索引近似于變成了單邊的連結清單，肯定是不合适的。

1.2 紅黑樹

也稱之為平衡二叉樹。在JDK1.8後，HashMap對底層的連結清單也優化成了紅黑樹（後續文章我們可以講講Hashmap1.8之後的調整）。平衡二叉樹的結構使樹的結構較好，明顯提高查找運算的速度。但是缺陷也同樣很明顯，插入和删除運算變得複雜化，進而降低了他們的運算速度。對大資料量的支撐很不好，當資料量很大時，樹的高度太高，如果查找的資料是葉子節點，依然會超級慢。

1.3 BTree

B-Tree是為磁盤等外儲存設備設計的一種平衡查找樹。系統從磁盤讀取資料到記憶體時是以磁盤塊（block）為基本機關的，位于同一個磁盤塊中的資料會被一次性讀取到記憶體中。在Mysql存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小機關。Mysql存儲引擎中預設每個頁的大小為16KB，檢視方式：

mysql> show variables like 'innodb_page_size';           

我們也可以将它修改為4K、8K、16K。系統一個磁盤塊的存儲空間往往沒有16K，是以Mysql每次申請磁盤空間時都會将若幹位址連續磁盤塊來達到頁的大小16KB。Mysql在把磁盤資料讀入到磁盤時會以頁為基本機關，在查詢資料時如果一個頁中的每條資料都能有助于定位資料記錄的位置，這将會減少磁盤I/O次數，提高查詢效率。

如上圖所示，一棵B樹包含有鍵值、存儲子節點的指針資訊、及除主鍵外的資料。相對于普通的樹BTree将橫向節點的容量變大，進而存儲更多的索引。

1.4 B+Tree

在B-Tree的基礎上大牛們又研究出了許多變種，其中最常見的是B+Tree，MySQL就普遍使用B+Tree實作其索引結構。

與B-Tree相比，B+Tree做了以下一些改進：

1、非葉子節點，隻存儲鍵值資訊，這樣極大增加了存放索引的資料量。

2、 所有葉子節點之間都有一個鍊指針。對于區間查詢時，不需要再從根節點開始，可直接定位到資料。

3、 資料記錄都存放在葉子節點中。根據二叉樹的特點，這個是順序通路指針，提升了區間通路的性能。

通過這樣的設計，一張千萬級的表最多隻需要3次磁盤互動就可以找出資料。

二、Mysql部分原理說明

這一部分我們選舉幾個日常面試過程中或者使用過程中比較常見的問題通過問答的形式來進行講解。

2.1、資料庫引擎MyISAM和InnoDB有什麼差別

• MyISAM：

  在Mysql8之前，預設引擎是MyISAM，其目标是快速讀取。

特點：

1、讀取非常快，如果頻繁插入和更新的話，因為涉及到資料全表鎖，效率并不高

2、儲存了資料庫行數，執行count時，不需要掃描全表；

3、不支援資料庫事務；

4、不支援行級鎖和外鍵；

5、不支援故障恢複。

6、支援全文檢索FullText，壓縮索引。

建議使用場景：

1、做很多count計算的，（如果count計算後面有where還是會全表掃描）

2、插入和更新較少，查詢比較頻繁的

• InnoDB：

  在Mysql8裡，預設存儲引擎改成了InnoDB。

特點

1、支援事務處理、ACID事務特性

2、實作了SQL标準的四種隔離級别

3、支援行級鎖和外鍵限制

4、可以利用事務日志進行資料恢複

5、不支援FullText類型的索引，沒有儲存資料庫行數，計算count(*)需要全局掃描

6、支援自動增加列屬性auto_increment

7、最後也是非常重要的一點：InnerDB是為了處理大量資料時的最大性能設計，其CPU效率可能是其他基于磁盤的關系型資料庫所不能匹敵的。

建議使用場景

1、可靠性高或者必須要求事務處理

2、表更新和查詢相當的頻繁，并且表鎖定的機會比較大的情況下，指定InnerDB存儲引擎。

2.2 表和資料等在Mysql中是如何存儲的

我們建立一個資料庫mds_demo，裡面有兩張表：order_info,user

我們找到mysql存放資料的data目錄，存在一個mds_demo的檔案夾，同時我們也找到了order_info和user的檔案。

為什麼兩張表産生了不同的檔案呢？原因很簡單，因為建立這兩張表時使用了不同的引擎

• MyISAM引擎在建立表的時候，會建立三個檔案

  .MYD檔案：存放表裡的資料

.MYI檔案：存放索引資料

.sdi檔案：Serialized Dictionary Information的縮寫。在Mysql5裡沒有sdi檔案，但會有一個FRM檔案，使用者存放表結構資訊。在MySQL8.0中重新設計了資料字典，改為sdi。

MyISAM的索引和資料是分開的，并且索引是有壓縮的，是以存儲檔案就會小很多，MyISAM應對錯誤碼導緻的資料恢複的速度很快。

• InnerDB引擎在建立表的時候，隻有1個檔案.ibd，即存放了索引又存放了檔案，參見B+Tree。是以它也被稱之為聚集索引，即葉子節點包含完整的索引和資料，對應的MyISAM為非聚集索引。

  補充說明一下：存儲引擎是針對表的，而不是針對資料庫，同一個庫的不同的表可以使用不同的引擎。

2.3 為什麼InnoDB必須要有主鍵，并且推薦使用整型的自增主鍵？

通過上面的講解這個問題其實已經很清楚了，為了滿足MySQL的索引資料結構B+樹的特性，必須要有索引作為主鍵，可以有效提高查詢效率。有的童鞋可能會說我建立表的時候可以沒有主鍵啊，這個其實和Oracle的rownum一樣，如果不指定主鍵，InnoDB會從插入的資料中找出不重複的一列作為主鍵索引，如果沒找到不重複的一列，InnoDB會在背景增加一列rowId做為主鍵索引。是以不如我們自己建立一個主鍵。

将索引的資料類型是設定為整型，一來占有的磁盤空間或記憶體空間更少，另一方面整型相對于字元串比較更快速，而字元串需要先轉換為ASCII碼然後再一個個進行比較的。

參見B+樹的圖它本質上是多路多叉樹，如果主鍵索引不是自增的，那麼後續插入的索引就會引起B+樹的其他節點的分裂和重新平衡，影響資料插入的效率，如果是自增主鍵，隻用在尾節點做增加就可以。

最後特别強調一點：不管目前是否有性能要求或者資料量多大，千萬不要使用UUID作為索引。

2.4 為什麼Mysql存儲引擎中預設每個頁的大小為16KB？

假設我們一行資料大小為1K，那麼一頁就能存16條資料，包含指針+資料+索引。假設一行資料大小為1K，那麼一頁（1個葉子節點）就能存16條資料；對于非葉子節點，假設ID為bigint類型那麼長度為8B，指針大小在Innodb源碼中為6B，一共就是14B，那麼一頁裡就可以存儲16K/14=1170個(主鍵+指針)，這樣一顆高度為3的B+樹能存儲的資料為：1170117016=2千萬級别。是以我們前面1000萬的資料隻有0.02s。

2.5 HASH算法的使用場景

Hash算法是一種雜湊演算法，就是計算出某個字段的hash，然後存放在對應的位址中，查找資料時隻需要1次定位而不像BTree那樣從根節點找到葉子節點經過多次IO操作，是以查詢效率非常地高。但同樣也有很多的弊端，講一下最重要的兩條。

1、很明顯hash隻支援=、IN等查詢，而不支援範圍查詢

2、 Hash 索引在任何時候都不能避免表掃描。

是以使用時務必注意。

圖檔：

本文中的部分圖檔來源于網絡，版本歸原作者所有。

參考：

https://www.cnblogs.com/vianzhang/p/7922426.html https://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html http://blog.codinglabs.org/articles/theory-of-mysql-index.html https://tech.meituan.com/2014/06/30/mysql-index.html https://www.ucloud.cn/yun/110762.html https://www.cs.usfca.edu/~galles/visualization/BST.html

向圖檔作者及内容參考的作者表示感謝！

感謝各位大佬關注公衆号“碼大叔”，也可以關注我的個人微信号“qiaojs”，我們一起交流學習！

微信公衆号：碼大叔 十年戎“碼”，老“叔”開花