如何成為建數據庫索引的高手？

文/ 西壁

原文標題為：《 你所了解的索引知識》

今天來聊聊數據庫里的索引，你知道的，網上這樣的文章一抓一大把的， 基本都是從索引的原理說起，講到索引的分類， 物理組織和存儲形式，如何找到對應的記錄，如何構建復雜的索引等等 ，如果我再寫一篇這樣的就沒意思了，而且這些未必真的是大家（尤其是開發同學）關心的。所以我今天打算以一個不同的角度來講下索引，而且針對B+tree索引，希望大家看了會有所幫助。

對于一個SQL，開發同學最關心的啥？ 我覺得并不是這個SQL在數據庫里面是如何執行的，而是這條SQL是否能盡快的返回結果，前面我們在講連接池的時候提到過，在SQL的生命周期里，每一個環節都有足夠的優化空間，但是我們有沒有想過，SQL優化的本質是啥？終極目標又是啥？其實優化本質上就是減少SQL對資源的消耗和依賴，正如數據庫優化的終極大招是Do nothing in database一樣，SQL優化的終極目的也是Consume no resource。

資源有兩個特性：首先資源是有限的，大家都搶著用就會有瓶頸的，所以SQL的瓶頸可能是由資源緊張產生的。其次資源是有代價的，并且代價各異，比如內存的時延100ns， SSD100us，SAS盤10ms，網絡更高，那么訪問CPU l1/l2/l3 cache的代價就比訪問內存的要低，訪問內存資源的代價要比訪問硬盤資源的代價低，所以SQL的瓶頸也可能是訪問了代價比較高的資源導致的。現代計算機體系下，機器上粗粒度的資源就那么幾種，無非就是CPU，內存，硬盤，和網絡。那么我們來看下SQL需要消耗哪些資源：比較、排序、SQL解析、函數或邏輯運算需要用到CPU；緩存數據訪問，臨時數據存放需要用到內存；冷數據讀取，大數據量的排序和關聯，數據寫入落盤，需要訪問硬盤；SQL請求交互，結果集返回需要網絡資源。那么我們在數據庫里面對SQL的優化思路，自然是減少SQL的解析，減少復雜的運算，減少數據處理的規模，減少對物理IO的依賴，減少服務器和客戶端的網絡交互， 那么如果解釋清楚了索引如何能夠幫助做到這幾點，這篇文章的目的就達到了。

不過先不忙著解釋這些，先讓大家成為建索引的高手再說，哈哈，你沒看錯，成為索引高手就這么簡單，三招速成，再多我也不會了，練完三招后上面這個問題也自然解釋清楚了，好， 讓我們拿下面的查詢SQL來開始練招吧。

SELECT CNO, FNAME

FROM CUST

WHERE LNAME = :LNAME AND CITY = :CITY

ORDER BY FNAME

第一招就是構建一星索引，根據where后面等值的條件，或者范圍的條件來構建索引，即index(LNAME,CITY) 。教科書上一般都說索引是為了能以最快的速度定位到想要的數據，即用空間來換時間，這當然沒錯，但是你有沒有想過，快速定位了你想要的數據后，也就過濾掉了不必要的數據，所以一星索引的核心就是利用索引來盡可能的過濾不必要的數據，減少數據處理的規模，對于RDBMS來說是極為關鍵的，比如說CUST表有1000000行，CITY的過濾度是10%，LNAME的過濾度是0.1%，那么如果沒有索引，你不得不把表里所有的一百萬行數據都讀出來，做處理，但是如果有了這個一星索引，需要處理的數據被極大的縮小了，只需要根據索引找到符合條件的索引葉子節點的范圍，讀取0.1%*10%*1000000=100rows就可以了，哪怕我們樂觀的假定產生的都是邏輯IO， 而不是物理IO，單次的差別就已經很明顯了，更別說是執行頻率很高的時候了，我們線上很多爛SQL對DB造成了影響，一看機器邏輯讀都好幾百萬了，基本上就可以定位是SQL索引缺失，或者不合理造成的。當理解了這個時候，你就一定不會產生一個誤區，在硬件越好越好，時延越來越低的今天，是不是索引還有存在的必要。

第二招就是構建二星索引， 針對上面的case, 我們構建索引如下index（LNAME,CITY,FNAME）,基本的想法就是利用索引的有序性，把消除ordby或者group by等需要排序的操作，因為大家都知道排序是非常消耗CPU資源的，大量的排序操作會把user cpu搞得很高，即使CPU吃得消，如果數據量比較大，需要排序的數據放不下內存的sort buffer，只能悲劇的和外存換進換出，性能下降的就不是一點兩點了，這時候利用索引避免排序的優勢就明顯的體現出來了。

想必第三招你沒學就已經會了，沒錯，第三招就是構建三星索引，即index（LNAME,CITY,FNAME,CNO)， 跟之前的二星索引的差別在于， 在索引中額外添加了要查詢的列CNO，這就是所謂的索引覆蓋，即在索引的葉子節點就能夠讀到查詢SQL所需要的所有信息，而不需要回原表去查詢了，在目前內存如此充足的情況下，很多時候，除了root節點和branch結構，甚至整個索引都是可以被放入內存的，這樣能大概率的避免，至少是減少物理IO。

也許你會說，這招式都是最理想的狀態，現實的SQL千變萬化，有各種奇葩的條件，有很多動態的SQL，有多表關聯的SQL，肯定不能拿上面說的三腳貓的招數硬往上套， 沒錯，實際情況下確實要考慮這樣那樣的因素，我們也沒辦法構建所有的索引都是三星的，我們只能根據實際情況， 構建最佳的索引，而非理想的索引，但是萬變不離其宗，理解了這三招的原理，就能夠見招拆招了，無招勝有招了。比如各種奇葩的條件，那我們選擇那些過濾性最好的， 比如動態的SQL，我們就抓住主干的那些SQL，比如兩表關聯（MySQL）， 因為那就nest loop一種，那就用小表驅動大表，在關聯字段各自盡可能的構建最優索引。 

我們前面也提到了，索引其實是一種權衡，是一種拿空間來換時間的藝術，所以極左或者極右都是不恰當的，創建過多的索引所帶來的空間損耗 ，和對DML所產生的負擔，在某些極端場景下，都不能被忽視， 對于DML性能損耗的優化，除了只創建必要的索引外，有些NOSQL實現了二級索引，但是索引是采用異步方式維護，不在一個事務里，這是通過犧牲強一致性來提高性能， 但是RDBMS還做不到，另外在innodb上，我們會推薦使用業務無關的自增字段來作為主鍵，提高順序插入性能的同時，還能避免過多的索引分裂。對于空間成本上的優化，同樣可以有些技巧，還是拿Innodb舉例，我們推薦使用數字型主鍵，而不推薦使用大字段作為主鍵的重要原因在于，大字段主鍵會極大的增大二級索引所占用的空間，因為二級索引葉子節點包含指向的主鍵，另外在Oracle上，我們會定期rebuild index來節省索引所占用的空間。

同時B+tree索引，作為一種面向磁盤&SSD的數據結構，相對來說，查詢和寫入性能也是相對比較平衡的，讀寫的時間復雜度都在O(log2n)，寫入上因為采用的是update-in-place的方式 ，每次寫入的時候需要先通過隨機查找來找到要寫入的位置，性能會不是那么好，當然你也可以選擇類似lsm_tree這樣的實現（包括OB自己實現的Btree），通過犧牲一定程度的讀性能，來提高寫的性能。未來會不會出現一種能更完美的數據結構，能夠同時更高效的支持讀取和寫入，是一件比較值得期待的事情。

說了這么多， 總結一下，我認為那么在不考慮業務層面優化的前提假設下，索引是最有效的藥方，其他的優化方式與之相比都只能是看成偏方了，而且B-tree作為普遍采用的數據結構，基本上是通用于多種關系型數據庫的，記得我從Oracle轉MySQL的時候，索引的運用基本上能平滑過渡，所以希望大家都能了解到這些索引知識， 對平時的工作中寫出更好更合理的SQL會很有幫助。