今天給大家?guī)淼氖菙祿靸?yōu)化方面的知識.作為java開發(fā)工程師,跟數據庫打交道是不可避免的,扎實的數據庫優(yōu)化知識也是核心競爭力之一.談到數據庫優(yōu)化,我想大家肯定聽說過慢查詢,當然第一個想到的肯定是建索引,或者是建合適的索引,那么為什么建立索引就可以有效的解決查詢速度慢的問題呢?聯(lián)合索引的最左匹配原則它的底層機理又是怎樣的呢?索引越多性能就越優(yōu)異嗎?我相信,今天的索引底層數據結構和算法分析會給大家一個更加深入的認識.
MySQL支持諸多存儲引擎，而各種存儲引擎對索引的支持也各不相同.總的來說,MySQL數據庫支持多種索引類型，如BTree索引，哈希索引，全文索引等等。為了避免混亂和講述方便，本文將只關注于BTree索引，因為這是平常使用MySQL時主要打交道的索引，至于哈希索引和全文索引本文暫不討論。
索引（Index）,幫助數據庫高效獲取數據的一種數據結構.數據查詢作為數據庫最為核心的功能之一,相信數據庫工程師們必定會想方設法的研究數據結構和查詢算法來提高數據查詢性能.
數據結構那么多，mysql索引為什么要用B+Tree數據結構，而不是其他呢？當然,肯定是其它的數據不滿足數據庫的要求.

常見的用于查詢的數據結構

1. 二叉查找樹
2. 紅黑樹
3. hash
4. B-Tree
5. B+Tree

二叉查找樹

二叉樹.png

左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節(jié)點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針.
然而,當我們的索引鍵值數據是一個單調變化的數據時,我們就會發(fā)現(xiàn),進行查找最糟糕的情況將是O(n)復雜度.

紅黑樹

紅黑樹也是二叉查找樹的變種,在二叉查找樹的基礎上,增加了如下約束:

1.節(jié)點非紅即黑。
2.根節(jié)點是黑色。
3.所有NULL結點稱為葉子節(jié)點，且認為顏色為黑。
4.所有紅節(jié)點的子節(jié)點都為黑色。
5.從任一節(jié)點到其葉子節(jié)點的所有路徑上都包含相同數目的黑節(jié)點。

當鍵值數據為有序序列時,比如對Col1建立索引,得到的數據結構如下圖

紅黑樹.png

紅黑樹的深度h與數據量n的關系是

n>=2^h-1

當生產環(huán)境達到千萬級數據量時,此時紅黑樹的深度大約為23.這就意味著,最糟糕時,數據庫要進行23次磁盤IO,才能找到想要的數據.顯然我們是接受不了的.

B-Tree

B 樹是為了磁盤或其它存儲設備而設計的一種多叉平衡查找樹。相對于二叉，B樹每個內結點有多個分支，即多叉.順便提一下,B樹又可以寫成B-樹/B-Tree，并不是B“減”樹，橫杠僅為連接符，容易被誤導.
m 階B-Tree,是指該樹一個節(jié)點能擁有的最大子節(jié)點數為m.B-Tree中的每個節(jié)點根據實際情況可以包含大量的關鍵字信息和分支，如下圖所示為一個3階的B-Tree：

3階B-Tree.png

大家可以看出，B-Tree由于是多叉樹，同一層能保存更多的數據，因此它相比于紅黑樹，會顯得矮胖得多。對同樣數量的數據進行索引，最惡劣情況，所需要的磁盤IO也會更小一些。

B+Tree

B+Tree是在B-Tree基礎上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結構,InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結構。
從上一節(jié)中的B-Tree結構圖中可以看到每個節(jié)點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節(jié)點（即一個頁）能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上，而非葉子節(jié)點上只存儲key值信息，這樣可以大大加大每個節(jié)點存儲的key值數量，降低B+Tree的高度。

這里帶著大家估算一下一個B+Tree能對多大的數據量進行索引。在mysql數據庫中，每個節(jié)點（即一個頁）的大小為16KB（沒有設計的更大，也是出于性能的考慮，過大會導致一個節(jié)點io耗時過長)。鍵值和指針是成對出現(xiàn)的，在實際設計中，我們大多數情況會將主鍵定義為int型，這里以最大的BigInteger為例，8個字節(jié)。mysql數據庫，對指針會以6個字節(jié)存儲（不理解的可以私下微信交流）。也就是一堆鍵值和指針是14個字節(jié)。一個節(jié)點可以對16KB/14B=1170個數據進行檢索。那么建立一個深度為h的B+Tree樹，就可以對1170^(h-1)行數據進行索引了。一億萬的數據量，深度為多少呢？答案是4層。是不是很驚人，就是這么優(yōu)異。

B+Tree相對于B-Tree有幾點不同：

1. 非葉子節(jié)點只存儲鍵值信息。
2. 所有葉子節(jié)點之間都有一個鏈指針。 有助于實現(xiàn)范圍查找。
3. 數據記錄都存放在葉子節(jié)點中。

將上一節(jié)中的B-Tree優(yōu)化，由于B+Tree的非葉子節(jié)點只存儲鍵值信息，假設每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結構如下圖所示：

3階B+Tree.png

不同的存儲引擎，可能都是基于B+Tree數據結構，但細節(jié)上還是有差異的。這里以用的最多的MyISAM和Innodb為例，跟大家深入介紹下。

MyISAM存儲引擎下的索引

下圖是給出了一個Linux系統(tǒng)下mysql數據庫的文件系統(tǒng)。housemagagerAliyun數據庫下，test_myisam表采用的MyISAM存儲引擎，其它大部分表采用的是Innodb引擎。

mysql數據庫.png

mysql文件系統(tǒng).png

MyISAM index.png

Innodb存儲引擎下的索引

上文介紹myisam存儲引擎，有貼出innodb表的文件系統(tǒng)，我們可以發(fā)現(xiàn)，每個表只有一個ibd文件。由于博主采用的是共享表空間，表的元數據信息是統(tǒng)一放在了上級目錄的ibdata1文件中。但你們肯定會想到，那索引和數據呢？難道是放在一個文件里了？答案就在innodb的索引數據結構里了。
innodb的主鍵索引B+Tree，葉子節(jié)點存放著完整的數據記錄。

innodb primary index.png

這就是大家在看其它數據庫書籍時，介紹的所謂聚集索引概念。而MyISAM的那種，沒有保存完整數據記錄的，就是非聚集索引了。
而innodb的其它非主鍵索引，葉子節(jié)點存儲的數據其實是對應記錄行的主鍵值。也就是非主鍵索引進行搜索時，其實是需要2次索引的。

secondary index.png

1. 數據一致性
2. 節(jié)約空間

節(jié)約空間很容易理解，那數據一致性怎么理解呢？當你要插入一條新的數據記錄時，如果非主鍵索引也要儲存完整的數據，這就意味著，你要同時完成多份數據的修改，這就好比分布式事務一樣，要想保證多份數據的一致性，代價是非常高的。但是僅僅在主鍵索引上保存完整數據，你就可以很容易保證數據一致性了。

聯(lián)合索引

現(xiàn)有一張mysql職員信息表，定義如下，我們在departmentId,position,和entryDate三個字段上建立聯(lián)合索引，其索引結構如圖所示。

CREATE TABLE `staff_info` (
  `id` int(11) NOT NULL,
  `sex` char(1) NOT NULL,
  `departmentId` int(11) NOT NULL,
  `position` varchar(20) NOT NULL,
  `entryDate` date NOT NULL,
  `exitDate` date NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_union` (`departmentId`,`position`,`entryDate`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (1, 'M', 1002, 'Staff', '1996-08-03', '2002-06-03');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (2, 'M', 1001, 'Engineer', '1996-08-03', '2001-08-03');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (3, 'W', 1001, 'Staff', '2001-09-03', '2006-03-06');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (4, 'M', 1003, 'Staff', '1997-08-03', '2011-08-07');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (5, 'W', 1003, 'Staff', '2001-09-03', '2009-06-03');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (6, 'M', 1004, 'Staff', '1996-08-03', '2010-09-20');

聯(lián)合索引使用時，必須遵循最左匹配原則，即匹配條件必須有最左列，否則索引將失效。我們利用Explain執(zhí)行計劃對這一原則做一個演示。

1. 檢索條件同時包含聯(lián)合索引的全字段

mysql>EXPLAIN select  * from staff_info where departmentId = 1002 and position = 'Staff' and entryDate > '1990-01-01';

全匹配索引.png

key列顯示，該查詢使用了聯(lián)合索引idx_union，而key_len 69(departmentId(int 4)+position(varchar 3*20+2)+entryDate(date 3))則意味著3列全部用到。69

2. 檢索條件僅為最左第一列

EXPLAIN select  * from staff_info where departmentId = 1002;

union first.png

可以看到，該查詢使用了聯(lián)合索引，索引長度為4(departmentId(int 4))
3.檢索條件為聯(lián)合索引的第二列

EXPLAIN select  * from staff_info where position = 'Staff' 

union second.png

type =ALL，執(zhí)行計劃顯示，該查詢會進行全表掃描，聯(lián)合索引失效。
這時，你肯定會問，那為什么必須遵循最左匹配原則呢？我們可以從聯(lián)合索引的底層數據結構中找到答案。

聯(lián)合索引數據結構.png

我們可以清楚地看到，聯(lián)合索引的B+Tree每個非葉子節(jié)點，是根據最左列編排的，然后再依據其它列進行排序。如果我們的檢索條件不包含最左列，這就違背了B+Tree數據結構的設計理念，沒法進行高效搜索。