本系列所說的Mysql性能調(diào)優(yōu)，主要是針對開發(fā)者在實際環(huán)境中的sql調(diào)優(yōu)，代碼層面上的優(yōu)化。不涉及到mysql底層代碼的調(diào)優(yōu)。
我們知道，一個mysql數(shù)據(jù)表，數(shù)據(jù)量小的時候，可能簡單的查詢耗時不會太久，性能也可以接受。但當(dāng)數(shù)據(jù)量大的時候，查詢速度會很緩慢。這時候我們會用到索引去優(yōu)化查詢。在我們的開發(fā)過程中，合理的索引對表操作的效率提升可能是指數(shù)級的。那我們在優(yōu)化我們項目中的sql語句時，首要的就是基于索引原理進行優(yōu)化。而要想有效率的，有針對性地進行mysql調(diào)優(yōu)。必然要先了解其內(nèi)部的一些知識，所以我們在這系列的第一篇要先聊一聊mysql索引的底層數(shù)據(jù)結(jié)構(gòu)和算法。
一.什么是索引
可能我們之前聽過，說索引就類似于字典的目錄，或者類似書籍的目錄，當(dāng)你像查什么字可以根據(jù)拼音，偏旁部首等去定位到需要查看的頁數(shù)，去獲取相關(guān)的內(nèi)容。這種說法不能說有錯，但對于我們開發(fā)人員，這中層次的理解顯然是遠遠不夠的。至少你不可能就通過這個理解去做什么優(yōu)化。因為這個沒有說明白索引到底怎么回事兒。
先借用mysql官網(wǎng)的一句話來說：
?索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
可能這個解釋還是比較籠統(tǒng)，那接下來就讓我們詳細的研究一下索引到底是什么。
索引的數(shù)據(jù)結(jié)構(gòu)
- 二叉樹
- 紅黑樹
- B-Tree
- B+Tree
這里我羅列出來了上述的幾種常見數(shù)據(jù)結(jié)構(gòu)，大家應(yīng)該都很熟悉了，我們再稍微的聊一下。比如說我們有如下的一個數(shù)據(jù)表：
這個表包含兩列，一共7條數(shù)據(jù)?，F(xiàn)在比如說我這里有一條sql語句
select * from test where col2 = 89
在不創(chuàng)建索引的情況，它應(yīng)該就是走的所謂的“全表”。說白了就是從第一條逐次比對。第一個col2=34不對就下一個col2=77，一直到第6條，發(fā)現(xiàn)col2=89，那滿足條件了將這條記錄取出來，然后再繼續(xù)查找。我們知道，數(shù)據(jù)庫表中的數(shù)據(jù)是存儲在磁盤當(dāng)中的，而且這個存儲位置也并非是絕對連續(xù)的（可能有連續(xù)的情況）。而當(dāng)我們?nèi)ゴ疟P中去讀取一條數(shù)據(jù)，就是說做一次I/O讀取交互的時候，這個效率是不高的。那當(dāng)我們數(shù)據(jù)量大的時候，還使用這種全表掃描，每一條數(shù)據(jù)都要進行一次讀取，這個效率是我們絕對接受不了的。那怎么避免這種情況呢？
最簡單的，我們可以想辦法減少查找次數(shù)。就是說，比如這里要的col=89這條數(shù)據(jù)，我們想辦法不要去全表去掃描，不要逐行的去讀取數(shù)據(jù)然后比對，以減少和磁盤做I/O讀取操作的次數(shù)，從而提高我們的效率。那怎么做呢？這時候我們的索引就來了。我們可以給col2這列建一個索引，以達到我們想要的目的。
首先我們來看一下二叉樹，如上圖右側(cè)部分，我們以二叉樹的方式，建立col2這一列的索引。二叉樹我們都知道的，右側(cè)大于父節(jié)點，左側(cè)小于父節(jié)點。上圖中，我們二叉樹根節(jié)點為表中第一條數(shù)據(jù)的col2值，為34。這個二叉樹每個節(jié)點的結(jié)構(gòu)就是key-value的。key就可以存的col2的每條的對應(yīng)值，value可以是這條記錄的存儲地址。比如上圖，34對應(yīng)的數(shù)據(jù)地址就是0x07這樣。當(dāng)建立好這個索引后，再看我們最初的sql語句，這時候，你發(fā)現(xiàn)它走索引后，第一個掃描根節(jié)點即34那里，發(fā)現(xiàn)我們要找的89大于這個節(jié)點，那ok，直接向右查詢，發(fā)現(xiàn)是89，直接取出這個值。就我上面這個例子，你發(fā)現(xiàn)不建立索引的時候，至少是要掃描6次才能找到col2=89這條數(shù)據(jù)，而走了二叉樹結(jié)構(gòu)的索引后，2次就找到了。這里效率可以說提升了很多。之前至少要和磁盤進行6次I/O讀取，而現(xiàn)在只需要2次。這就是索引，詳細到現(xiàn)在我們對索引的理解應(yīng)該是要比“書籍目錄”深刻一點兒了。但我們都知道，MySQL使用的并不是二叉樹作為索引的數(shù)據(jù)結(jié)構(gòu)。至于為什么，讓我們想一下這樣一個問題。
現(xiàn)在呢，我們更改一下我們的查詢sql語句，改為用col1這一列來查找，如下：
select * from test where col1 = 6
現(xiàn)在要查詢的還是col2=89的這條數(shù)據(jù)，但我們用col1=6來查找。這時候，基于上次的經(jīng)驗，我們要給col1創(chuàng)建一個索引，好的，一個二叉樹索引創(chuàng)建完了。這個索引是什么樣的的呢。大概是下面這樣的：
因為二叉樹的右側(cè)永遠大于父節(jié)點嘛，那當(dāng)?shù)谝粋€數(shù)據(jù)也就是根節(jié)點的col1=1時，數(shù)據(jù)結(jié)構(gòu)會如上圖，這時候，想一下我們的語句，當(dāng)走索引的時候，你發(fā)現(xiàn)，完了！又是需要查詢6次才能獲取到我們想要的數(shù)據(jù)。那這種情況如果數(shù)據(jù)量大的話，效率肯定也很低下，這可能也就是MySQL沒有使用二叉樹作為索引數(shù)據(jù)結(jié)構(gòu)的原因。那我們怎么能優(yōu)化一下呢？
這里我們可以使用紅黑樹進行優(yōu)化，紅黑樹詳細很多人都聽說過，為了更直觀了解它和單純的二叉樹的區(qū)別，我們可以看一下下面這個動圖，這個展示了基于我們col1這個例子建立紅黑樹是什么樣的：
你會發(fā)現(xiàn)，這個紅黑樹會根據(jù)數(shù)值的不同去平衡數(shù)據(jù)節(jié)點，其實紅黑樹就是一種特例的二叉樹，它還是屬于二叉樹的，只不過加了平衡算法，但它又不能完全的稱之為“平衡二叉樹”，因為它的左右可以是高度不同的，平衡二叉樹是另一種叫做AVL樹的數(shù)據(jù)結(jié)構(gòu)，感興趣可以自己去查一下，這里就不多說了。說會我們的例子，當(dāng)我們將原來的二叉樹換成紅黑樹后，會發(fā)現(xiàn)現(xiàn)在查詢到我們想要的數(shù)據(jù)只需要三次查詢，較之前的純粹二叉樹結(jié)構(gòu)有了一些性能上的提升。盡管如此，我們也都知道MySQL用的也不是紅黑樹。因為這樣的平衡二叉樹，或者說紅黑樹，仍然有一些問題。比如說，我上邊的例子是因為只有七條數(shù)據(jù)，數(shù)據(jù)量很少，我們可以接受。但當(dāng)數(shù)據(jù)量達到百萬級別，千萬級別的時候。我們平常的生產(chǎn)環(huán)境這個數(shù)據(jù)量很容易達到的。這個時候，紅黑樹的性能就沒有那么高了，說白了就是它有一個“樹高”的問題，當(dāng)數(shù)據(jù)量很大的時候，當(dāng)我們查找的數(shù)據(jù)在葉節(jié)點上時候，可能要查詢很多次，幾十次，因為雖然紅黑樹做了平衡，但隨著數(shù)據(jù)量的增加，它的“樹高”也在不停的增長。當(dāng)我們查一條數(shù)據(jù)的時候要和磁盤交互幾十次的時候，那這個性能就明顯不夠了。紅黑樹也就無法滿足我們的需求了。好的，那我們繼續(xù)優(yōu)化，針對這種“樹高”的問題，我們怎么處理呢？
其實通過上面的二叉樹和紅黑樹，我們應(yīng)該已經(jīng)感覺到了，就是我們和磁盤的交互次數(shù)，或者說我們查詢數(shù)據(jù)的次數(shù)，和“樹”的高度是緊密相關(guān)的。那如果我們能讓上邊的紅黑樹或者說二叉樹的樹高，不管是存幾百萬還是幾千萬數(shù)據(jù)的時候都能保證樹高在3、4層的話，這個我們和磁盤交互的次數(shù)，感覺我們還是可以接受的。性能就會相對較高一些。那怎么做呢？
我們想想一下，既然想減少樹的縱向高度，那是不是可以在橫向上想想辦法。我們知道，這個樹的每個節(jié)點，或者說索引的的節(jié)點也是存在磁盤上的。比如說上面紅黑樹的根節(jié)點“1”這個值，可能占用了磁盤的一個存儲空間。那我們能不能在生成樹的時候，直接讓每個節(jié)點的存儲空間擴大一些。就比如，在第一層，我現(xiàn)在可以存多個索引值。7個值的話，我們看紅黑樹是有三層，如果可以將每一層的每個節(jié)點多存儲幾個元素，比如說我這里設(shè)置成每個節(jié)點最多4個。整個存儲過程就如下：
這種優(yōu)化后，發(fā)現(xiàn)7條數(shù)據(jù)只需要存兩層，如果我將每層設(shè)置做多可存值大于7，那就只需要一層。相對紅黑樹，性能應(yīng)該就是又有一些提升了。而這種數(shù)據(jù)結(jié)構(gòu)，就是B-Tree。為了更形象一點兒，我們再看一下下圖：
上圖為大致的B-Tree數(shù)據(jù)結(jié)構(gòu)，其中15、56、77等可以理解為索引字段的值，而data則為對應(yīng)那條記錄的數(shù)據(jù)，或者說存儲地址。我們觀察B-Tree結(jié)構(gòu)，發(fā)現(xiàn)它有如下幾個主要特點：
- 葉節(jié)點具有相同的深度，就是說不會像紅黑樹一樣分支的深度不一致。
- 所有的索引元素不重復(fù)的
- 節(jié)點中的數(shù)據(jù)索引從左至右遞增排序
雖然B-Tree一定程度上解決了“樹高”的問題，但我們知道MySQL用的是叫做B+樹的數(shù)據(jù)結(jié)構(gòu)，那接下來我們就看看它和B樹的區(qū)別，再研究一下MySQL為什么要使用B+樹。首先就我們的例子，生成一個B+Tree，看一下什么樣子的:
好像粗略看去，和B-Tree很相似。沒錯，本來B+Tree就是B-Tree的變種，這里我們注意上面動圖中，葉節(jié)點中間的那個指示箭頭。這個東西代表葉節(jié)點是有存相鄰節(jié)點的相關(guān)信息的，就是節(jié)點的中可能有一小塊存儲空間放的是相鄰節(jié)點的存儲地址，這樣的話，方面直接快速查到相鄰節(jié)點和排序等。我們再看下面的圖片：
看這張圖片，和B-Tree很明顯的結(jié)構(gòu)，你會發(fā)現(xiàn)除了最下層的葉節(jié)點中含有data信息，上面的每一層，包括根節(jié)點，都沒有存儲數(shù)據(jù)，只是存了索引值。那我們可以知道，最后的葉節(jié)點中是包含所有索引值和data的。說白了，就是最下一層葉節(jié)點中包含上面所有層的索引值，而且是從左到右逐次遞增的，并且節(jié)點之間存有相鄰節(jié)點的信息。這時候其實上部分的節(jié)點存的就是“冗余索引”。那Mysql為什么要在B-Tree上做這種變更呢？
二.Mysql的索引
我們都知道，數(shù)據(jù)表包括索引都是存儲在磁盤上的，比如MySQL如果你不更改安裝配置的話，一般到它的安裝目錄下就能找到每個表對應(yīng)的數(shù)據(jù)文件。
那是不是有這樣一個問題，就像上面的B+Tree，雖然在每個節(jié)點中存儲了多個索引值，減少了樹高，但我查找的時候不是還要和磁盤交互么，不是還要去一條一條比對么？那這個磁盤I/O不是還是很慢么？沒錯，如果是直接去磁盤進行讀取操作的話，那是這樣的。但MySQL是這么做的：首先我們從根節(jié)點來說起，就是剛開始查詢的時候，它會把整個根節(jié)點讀入到RAM中，說白了就是將磁盤中的節(jié)點信息，讀到內(nèi)存中，然后在內(nèi)存中做查詢。其中會用到一些算法，比如““折半法”,也就是二分查找等。當(dāng)在內(nèi)存中做這種查找的時候，效率是十分快速的。甚至和磁盤讀取來比較的話，這個時間消耗甚至是可以忽略不記的。我們舉個例子，比如說我們上面的那個B+Tree圖片，一共3層，當(dāng)我查找索引值為20這一記錄的時候，它的查找過程大概是這樣的：首先根節(jié)點從磁盤中讀到內(nèi)存中，然后運用二分法快速的查到20這個值所在的下一層存儲位置，然后再將對應(yīng)的節(jié)點整個讀取到緩存中，再進行查找，最終查到我們要的值所在位置，然后讀取出來。那其實我們主要耗時的地方還是和磁盤交互的過程，在這里就相當(dāng)于把節(jié)點數(shù)據(jù)讀取到內(nèi)存中這個操作。一共就是有3次的I/O讀取。這個效率就很高了。我們的例子數(shù)據(jù)比較少，可能沒有直觀的感受，那我們計算一下。
首先我要說的是當(dāng)你用MySQL時，運行如下語句：
SHOW GLOBAL STATUS like 'Innodb_page_size';
你會得到一個值，默認應(yīng)該是16K，這個值是什么呢？它代表的就是每個節(jié)點的存儲空間大小。就是文件頁，或者說磁盤頁。這個東西用根節(jié)點來說，就是這個節(jié)點的空間是16K。我們想一下，就假設(shè)一行數(shù)據(jù)1K大?。ㄒ话惚砀褚粭l數(shù)據(jù)達不到），那在最下一層的葉節(jié)點中，每個節(jié)點可以存16條數(shù)據(jù)。好的，那上層我們假設(shè)我們建立主鍵索引的字段為ID列，算大一點bigInt類型，bigInt在MySQL中大小為8B，指針在Innodb源碼中大小是6B，一共為14B。那么一頁就是16K/14B = 1170（主鍵加指針）。如果我們這個B+Tree有3層，那數(shù)據(jù)總量就是1170117016 = 21902400?，F(xiàn)在是不是很直觀了，千萬級別的數(shù)據(jù)，使用Innodb類型的表格，使用索引只有3層，這時候想一下千萬級別我們走索引查詢的話，只需要進行3次I/O讀取操作！這就是為什么MySQL可以千萬級別查詢做到毫秒級別。
說到這里，那我們再想一下為什么B-Tree不行。想一下，B-Tree是每個索引后都跟著數(shù)據(jù)的，那以根節(jié)點來說，如果同樣是16k的大小，B+Tree可以存1170條，而B-Tree只能16條。當(dāng)數(shù)據(jù)量大的時候，樹又會很高了。還一個問題是，可能會想那我們把文件頁大小分配大一點不就好了，但有個問題，如果這個值大了，B-Tree雖然每個節(jié)點中的索引量可以存儲的更多了，但是由于文件頁很大，這時候如果像B+Tree一樣將其讀取到內(nèi)存中操作，顯然就不合適了。將及其耗費資源。如果不讀取到內(nèi)存，那處理速度依然很慢。這就是為什么Mysql要將B-Tree變種從而得到B+Tree。
好了，本篇就先聊到這里吧，還有很多點沒有說到，下一篇再結(jié)合Mysql展開詳細說一下，然后再說一些優(yōu)化方法，這篇文章是要我們對B+Tree有個深入了解。因為后邊索引優(yōu)化，都是基于這個結(jié)構(gòu)的。腦袋中有這個結(jié)構(gòu)，會省力很多。文章來源：http://www.zghlxwxcb.cn/news/detail-699654.html
下篇會聊一下mysql的存儲引擎，主要是Innodb。文章來源地址http://www.zghlxwxcb.cn/news/detail-699654.html
到了這里，關(guān)于Mysql性能調(diào)優(yōu)——1.深入理解Mysql索引數(shù)據(jù)結(jié)構(gòu)和算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
