MySQL索引基礎(chǔ)

介紹

????索引用于加快數(shù)據(jù)訪問的速度。把計(jì)算機(jī)的磁盤比作一本字典，索引就是字段的目錄，當(dāng)我們想快速查到某個(gè)詞語的時(shí)候只需要通過查詢目錄找到詞語所在的頁數(shù)，然后直接打開某頁就可以。MySQL最常用的索引是B+樹索引，為什么使用B+作為MySQL的索引，這是許多面試官必問的問題。

<!-- more -->

為什么B+樹

硬件相關(guān)知識

????計(jì)算機(jī)的磁盤是一個(gè)圓盤的接口，圓盤上有一個(gè)個(gè)的圓圈，數(shù)據(jù)就是記錄在這些圓圈的扇區(qū)上。如下圖所示

當(dāng)計(jì)算機(jī)系統(tǒng)讀取數(shù)據(jù)的時(shí)候要通過以下幾個(gè)步驟：
1、首先移動(dòng)臂根據(jù)柱面號使磁頭移動(dòng)到所需要的柱面上，這一過程被稱為尋道。所耗費(fèi)的時(shí)間叫尋道時(shí)間(ts)。
2、目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過程耗費(fèi)的時(shí)間叫旋轉(zhuǎn)時(shí)間。
????因此訪問磁盤的時(shí)間由三部分構(gòu)成： 尋道時(shí)間+旋轉(zhuǎn)時(shí)間+數(shù)據(jù)傳輸時(shí)間
第一部分尋道時(shí)間延遲最高，最大可達(dá)到100ms，旋轉(zhuǎn)時(shí)間取決于磁盤的轉(zhuǎn)速，轉(zhuǎn)速在7200轉(zhuǎn)/分鐘的磁盤平均旋轉(zhuǎn)時(shí)間在5ms左右。磁盤的讀取是以block(盤塊)為單位的，位于同一個(gè)盤塊的數(shù)據(jù)可以一次性讀取出來。在讀寫數(shù)據(jù)的時(shí)候盡量減少磁頭來回移動(dòng)的次數(shù)，避免過多的查找時(shí)間。如果每次從磁盤上讀取數(shù)據(jù)的時(shí)候都要經(jīng)歷上面的幾個(gè)過程那么效率上無疑是極低的。

為什么B+樹

????從上面可以看到，如果隨機(jī)訪問磁盤的速度是很慢的，因此需要設(shè)計(jì)一個(gè)合理的數(shù)據(jù)結(jié)構(gòu)來減少隨機(jī)訪問磁盤的次數(shù)。B樹就是這樣一種數(shù)據(jù)結(jié)構(gòu)。

B樹、B+樹介紹

B樹

????B樹是為存儲設(shè)備而設(shè)計(jì)的一種多叉平衡查找樹。它與紅黑樹類似，但是在降低IO操作方面B樹的表現(xiàn)要更好一些，B樹與紅黑樹最大的區(qū)別在于B樹可以有多個(gè)子節(jié)點(diǎn)，紅黑樹最多是有兩個(gè)子節(jié)點(diǎn)，這就決定了大多數(shù)情況下B樹的高度要比紅黑樹低很多，因此在查找的時(shí)候能夠降低IO次數(shù)。下圖是一棵B樹：

B 樹又叫平衡多路查找樹。一棵m階的B樹的特性如下：
????a.樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）；
????b.除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
????c.若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，整棵樹只有一個(gè)根節(jié)點(diǎn)）；
????d.所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息
????e.每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
????????a) Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序K(i-1)< Ki。
????????b) Pi為指向子樹根的接點(diǎn)，且指針P(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。
????????c) 關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1。
????B樹中的每個(gè)節(jié)點(diǎn)都盡可能存儲多的關(guān)鍵字信息和分支信息，但是不會超過磁盤塊的大小。這樣在有效降低了樹的高度，在查找的時(shí)候可以快速定位在指定的磁盤塊。假如要從上圖中找到79這個(gè)數(shù)字，首先從根節(jié)點(diǎn)開始掃描，79大于35所以選擇P3指針，指向磁盤塊4，在磁盤塊4中79在65和87之間，因此選擇P2指針，選擇磁盤塊10，這時(shí)候就可以從磁盤塊10中找到79。整個(gè)過程只需要3次IO，如果這棵樹被緩存在內(nèi)存中，那么只需要一次IO就可以讀到79這個(gè)數(shù)字。

B+樹

????B+樹是B的變種，一顆m階B+樹和m階B樹的異同點(diǎn)在于：
????1、有n棵子樹的節(jié)點(diǎn)中有n-1個(gè)關(guān)鍵字(與B樹n棵子樹有n-1個(gè)關(guān)鍵字，保持一致)
????2、所有的葉子節(jié)點(diǎn)中包含了全部的關(guān)鍵字的信息，以及指向含有這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小而自小而大順序鏈接(而B樹的葉子節(jié)點(diǎn)并沒有包含全部需要查找的信息)
????3、所有的非終端節(jié)點(diǎn)可以看成索引部分，節(jié)點(diǎn)中僅含有其子樹根節(jié)點(diǎn)中最大或者最小的關(guān)鍵字(而B樹的非終節(jié)點(diǎn)也要包含需要查找的有效信息)
????
由于B+樹的葉子節(jié)點(diǎn)是連接在一起的，因此相對于使用B樹作為索引，對于MySQL的范圍查詢更加優(yōu)化。同時(shí)由于葉子節(jié)點(diǎn)包含所有關(guān)鍵字信息，因此有的查詢語句就不需要回表，只需要查詢索引就可以查到需要的數(shù)據(jù)。

索引類型

B樹索引

????雖然是叫B樹索引，但是數(shù)據(jù)庫實(shí)際上使用的是B+樹來組織數(shù)據(jù)。B樹索引意味著所有值都是按照順序存儲的，并且每個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的距離是相同的。
假如有如下數(shù)據(jù)表：

CREATE TABLE `people` (
  `last_name` varchar(50) DEFAULT NULL,
  `first_name` varchar(50) DEFAULT NULL,
  `dob` date DEFAULT NULL,
  `gender` enum('m','f') DEFAULT NULL,
  KEY `last_name` (`last_name`,`first_name`,`dob`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

該表對last_name,first_name,dob三列建立了索引，索引的組織方式如下：

當(dāng)同時(shí)對多列進(jìn)行索引的時(shí)候，索引的順序是非常重要的，上面的索引首先是按照last_name進(jìn)行索引，在last_name相同的情況下在對first_name進(jìn)行排序，最后是dob字段。
????B樹索引適用于全鍵值、鍵值范圍和最左前綴查找:
全鍵值
????查找名字為Allen Kim，出生日期為1930-07-12的人，這樣的查找方式匹配了索引中的所有字段，依次掃描索引中的last_name、first_name和dob字段，找到對應(yīng)的數(shù)據(jù)。
鍵值范圍
????查找姓名在Allen和Barrymore之間的人，這種查找方式也會使用到索引。需要注意的是這里只能是索引中的第一列，也就是last_name的范圍查找。
前綴匹配
????查找last_name是以Al開頭的人，這種查詢會以此掃描索引中的節(jié)點(diǎn)，然后選出來對應(yīng)的復(fù)合條件的行。也是只能使用第一列的前綴查詢。如果是說想查first_name的前綴匹配，那么是無法使用到索引的，意味著要進(jìn)行全表掃描。
精確匹配某一列，范圍批量另外一列
????精確匹配的列必須是所以中的第一列，范圍匹配的列是第二列，這樣才能使用到上面的索引。

B樹索引的使用限制：
1、不是按照最左列開始查詢的，無法使用索引。
2、不能跳過索引的列進(jìn)行查詢。
3、如果使用到了范圍匹配，那么范圍匹配右邊的列都無法使用索引查詢。
###哈希索引
????哈希索引使用哈希表來實(shí)現(xiàn)，只有是精確匹配的時(shí)候才會生效。存儲引擎會對索引列計(jì)算出一個(gè)哈希值，然后保存一個(gè)哈希值到行數(shù)據(jù)的指針。哈希索引由于其特殊的組織方式，限制了其使用場景。哈希索引只適合值比較少的情況，例如枚舉類型。在以下幾種方式中是不適合使用哈希索引的：
1、哈希索引只包含哈希值和指針，不存儲字段值，因此使用哈希索引避免不了要進(jìn)行回表查詢。
2、哈希索引數(shù)據(jù)并不是按照值的順序進(jìn)行排序的，因此哈希索引無法用來排序
3、哈希索引不支持部分索引列匹配。比如說在(A,B)兩列上簡歷哈希索引，那么只有在同時(shí)使用A、B兩列查詢的時(shí)候才會使用哈希索引，只使用A列查詢無法使用哈希索引。
4、哈希索引只支持等值比較，不支持像between and這種范圍查詢。
5、使用哈希索引的時(shí)候應(yīng)該盡量避免哈希沖突。

后記

????數(shù)據(jù)庫的索引機(jī)制解決的問題是在訪問內(nèi)存數(shù)據(jù)與磁盤數(shù)據(jù)的速度差別很大的情況下，如何快速訪問數(shù)據(jù)的問題。只有了解了索引的原理才可以更好的設(shè)計(jì)表的索引字段以及寫出性能更優(yōu)的查詢語句。在我們寫SQL語句的時(shí)候頭腦中應(yīng)該大體上能規(guī)劃出查詢數(shù)據(jù)以及如何使用索引的過程。下一篇會介紹一下高性能索引的策略，帶你設(shè)計(jì)出更優(yōu)的索引。

歡迎關(guān)注我的微信公眾號：yunxi-talk，分享Java干貨，進(jìn)階Java程序員必備。