前言
數(shù)據(jù)庫的索引在日常工作中經(jīng)常會接觸到，重要性我們都很清楚。但是關(guān)于索引的實現(xiàn)，不同存儲引擎下索引的實現(xiàn)原理又是怎樣的，使我們今天需要去深入的。
什么是索引
一句話說，索引的出現(xiàn)是為了提高數(shù)據(jù)庫的查詢效率，就像書的目錄一樣 一本幾百頁的數(shù)，如果我們想要快速的找到某篇文章，在不借助目錄的情況下，那一定需要費不少力氣。索引就像數(shù)據(jù)庫表的目錄一樣。
索引的常見模型
索引的出現(xiàn)是為了提高查詢效率，但是實現(xiàn)索引的方式有很多種，所以這里也就引入的索引模型的概念?？梢杂糜谔岣咦x寫效率的數(shù)據(jù)結(jié)構(gòu)有很多，這里簡單的介紹3幾種常見也比較簡單的，分別是哈希表、有序數(shù)組、搜索樹。
下面主要從使用的角度，分析一下這三種模型的區(qū)別。
哈希索引模型
哈希表是一種鍵值（KV）存儲的數(shù)據(jù)結(jié)構(gòu)，我們只要輸入待查詢的值key，即可以找到對應的值即value。哈希的思路很簡單，即把值放進數(shù)組里，用一個哈希函數(shù)把key換算成一個確定的位置，然后把value放在數(shù)組的這個位置。不可避免的多個key值經(jīng)過hash函數(shù)的換算會出現(xiàn)同一個值得情況。處理這種情況的辦法就是 拉出一個鏈表。
假設(shè)，我們現(xiàn)在維護了一張身份證和姓名的數(shù)據(jù)表，需要根據(jù)身份證號查詢姓名，這是對應的hash索引的示意圖如下：
圖中，id_number2、id_number4計算出來的值都是N，但是沒關(guān)系，后面還跟了一個鏈表。假設(shè)這時我們要查詢id_number2對應的名字是什么,首先通過id_number2通過hash函數(shù)算出N，然后拿到鏈表，便利獲取user2.
需要注意的是，圖中id_number的4個值不是連續(xù)的，這樣做的好處是插入新的user時非?？?，只需要往后面追加。但缺點是，因為不是有序的，hash索引在做區(qū)間查詢的時候效率很低。
我們可以想象一下，假設(shè)我們需要查詢[id_numberX, id_numberY]這個區(qū)間的所有用戶姓名，那就必須要全部掃描一遍。
所以，Hash索引更適合做等值得這種檢索，比如Memcached及其他一些NoSQL庫的引擎。
有序數(shù)據(jù)索引模型
而有序數(shù)組在等值查詢和范圍查詢下的性能都非常優(yōu)秀，還是上面這個根據(jù)id_numer查詢姓名的事例，如果使用有序數(shù)組作為索引結(jié)構(gòu)的話，示意圖如下：
這里我們假設(shè)身份證號碼沒有重復，那么它就是按照身份證號碼依次遞增保存的。這時候如果我們需要查詢id_number2對應的姓名，按照二分法很快就可以查找到。時間復雜度T（n）= O（log（n））
同時很顯然這數(shù)據(jù)結(jié)構(gòu)支持范圍檢索，如果我們要查詢[id_numberX, id_numberY]這個區(qū)間內(nèi)的姓名，首先通過二分法快速查找到id_numberX的身份證，如果id_numberX不存在，那就先找到第一個大于id_numberX的身份證，然后向右遍歷，直到找到大于id_numberY的身份證，結(jié)束循環(huán)。
如果僅看效率，那有序數(shù)組是最好的數(shù)據(jù)結(jié)構(gòu)了，比如我們要保存2018年某城市人口或經(jīng)濟等數(shù)據(jù)，像這種不需要再修改的數(shù)據(jù)是再合適不過的。因為有序數(shù)組的插入性能非常的差，因為向有序數(shù)組的中間插入一個User，那需要將其后面的所有數(shù)據(jù)都向后移動一個位置。
二叉搜索數(shù)索引模型
還是上面的例子，我們用二叉搜索數(shù)實現(xiàn)的示意圖如下：
二叉搜索數(shù)的特點：每個節(jié)點的左兒子小于父節(jié)點，而父節(jié)點又小于右兒子。這樣如果我們要查詢User2的話，就需要按照這個順序：
這個時間復雜度T（n） = O（log（n））
N叉數(shù)索引模型
樹可以二叉，也可以有多叉（N叉數(shù)），N叉數(shù)多個兒子的大小從左到右依次遞增，二叉樹是搜索效率最高的，但是實際上大部分的數(shù)據(jù)庫都不使用二叉樹，因為索引不僅存在內(nèi)存中，還需要寫入磁盤。
我們可以想象一下一顆100萬節(jié)點的二叉樹，樹高20。依次查詢可能訪問20 個數(shù)據(jù)塊。在機械硬盤時代，從磁盤隨機讀取一個數(shù)據(jù)塊需要20ms左右的尋址時間。也就是說一個100萬行的數(shù)據(jù)，使用二叉樹索引模型的話，查詢一行，需要的時間大概在20 * 20ms的時間，那是不能忍受的。
為了讓一個查詢盡量少的讀取磁盤，就需要盡量讓查詢過程讓問盡量少的數(shù)據(jù)塊，那么我們就不應該使用二叉樹，應該使用“N叉”數(shù)，這里的N取決與數(shù)據(jù)塊的大小。
以InnoDB的整數(shù)字段索引為例，如果這個N為1200，樹高為4的時候，就可以存1200的3次方個值，這已經(jīng)17億了?？紤]到樹根的數(shù)據(jù)塊總在內(nèi)存中的，所以一個一個10行數(shù)據(jù)的表上整形字段的索引，在查詢一個值得時候最多只需要訪問3次磁盤。其實，樹的第二層也有很大概率在內(nèi)存中，所以訪問磁盤的次數(shù)就更少了。
N叉數(shù)由于在讀寫上的性能優(yōu)先，以及適配磁盤的訪問模式，已經(jīng)被廣泛的應用在數(shù)據(jù)庫引擎中。
不管是是hash表、有序數(shù)據(jù)還是N叉數(shù)，他們都是不斷迭代的、不斷優(yōu)化的產(chǎn)物，或者解決方案。數(shù)據(jù)庫技術(shù)發(fā)展到今天跳表、LSM樹等也被用于數(shù)據(jù)庫引擎中，這里就不一一展開了（其實這里我也展開不了，也沒具體了解過，感興趣的話可以了解下【尷尬】）。
我們心里要有個概念，數(shù)據(jù)庫底層存儲的核心就是基于這些數(shù)據(jù)模型的。每碰到一個數(shù)據(jù)庫我們需要先關(guān)注它的數(shù)據(jù)模型，這樣才能從理論上分析出這個數(shù)據(jù)庫適用于什么樣的場景。
上面我主要記錄的是關(guān)于常用的幾種索引數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)及適用場景。下面我們來具體看下在MySQL中，是怎么應用的。首先MySQL中，索引是在存儲引擎層實現(xiàn)的，所以并沒有統(tǒng)一的標準，即不同存儲引擎的索引工作方式都是不一樣的。而即使多個存儲引擎支持同一個索引模型，那其底層的具體實現(xiàn)可能也是有差別的。
由于InnoDB是使用最為廣泛的且是MySQL現(xiàn)在的默認存儲引擎，所以接下來我們就以InnoDB為例，來分析下其索引模型是如何工作的。
InnoDB的索引模型
在InnoDB中，表都是根據(jù)主鍵順序以索引的形式存放的，這種存放方式的表被稱為索引組織表。在這之前我們都知道 InnoDB的索引結(jié)構(gòu)是采用B+數(shù)結(jié)構(gòu)存儲的，所以數(shù)據(jù)也都是存儲在B+數(shù)中的，但是可能對其細節(jié)不是很了解，下面我們來一塊分析下。
首先，我們要知道每一個索引在InnoDB里面都分別對應一棵B+數(shù)。
假設(shè)，我們有一個主鍵ID的表，其中有一個字段K，在K字段上也有一個其他索引（非主鍵索引）。
我的建表語句是這樣的：
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
表中R1~R5的（ID，k）值分別是這樣的：（100， 1）、（200，2）、（300，3）、（500， 5）和（600， 6）。ID索引樹與k索引樹對應的示意圖分別是這樣子的：
從圖中不難看出，根據(jù)葉子節(jié)點的內(nèi)容，數(shù)據(jù)看索引可以分為主鍵索引和非主鍵索引。
主鍵索引的葉子節(jié)點存放的是整行數(shù)據(jù)（圖中的Rx），在InnoDB中，主鍵索引也被稱為聚簇索引。
非主鍵索引的葉子節(jié)點對應的是主鍵的值，在InnoDB中非主鍵索引也被稱為二級索引。
根據(jù)上的索引說明，我們來看一個問題：基于主鍵索引和普通索引的查詢有什么區(qū)別？
- 如果查詢語句是select * from T where ID = 500,即主鍵查詢方式，只需要查詢ID這棵B+樹。
- 如果查詢語句是select * from T where k = 5, 即非主鍵索引查詢，則需要先搜索k索引樹，獲取到主鍵ID的值 = 500，再到ID索引樹查詢一次，這個回到ID索引樹查詢的過程稱為 回表
也就是說基于普通索引/二級索引的查詢需要多掃描一棵索引樹。所以我們應用中盡量使用主鍵索引。
索引維護
B+樹為了維護索引有序性，在插入新值得時候必須做必要的維護。以上面圖為例，如果我們需要插入新行的ID值為700，則只需要在R5的行后面查詢新行即可。但是如果需要插入的新行ID=400，那就相對比較麻煩了，需要邏輯上移動后面行的位置，為新行騰出空位。
而更糟糕的是，如果R5的數(shù)據(jù)頁已經(jīng)滿了，則根據(jù)B+樹的算法，需要申請一個新的數(shù)據(jù)頁，然后挪動部分數(shù)據(jù)過去，這個過程叫做頁分裂。這種情況下，性能自然會受到影響。
除了性能外頁分裂還將影響數(shù)據(jù)頁的利用率，原本在一個頁的數(shù)據(jù)，現(xiàn)在拆分到兩個數(shù)據(jù)頁，整體空間利用率下降大約50%。
有頁分裂自然也就有頁合并。當相鄰兩頁由于刪除了數(shù)據(jù)，利用率很低之后，會將數(shù)據(jù)頁合并。
基于上面的索引維護過程說明，我們來看一個案例：
我們會在一些建表規(guī)范里看到過一個數(shù)據(jù)表一定要有一個自增主鍵，事無絕對，我們來看下什么情況下建議一定要有？什么情況下不應該有？
主鍵自增是指在自增列上定義的主鍵， 在建表語句中一般是這么定義的：
mysql> ID int(11) NOT NULL AUTO_INCREMENT PRIMARY KEY
在插入數(shù)據(jù)的時候，可以不指定ID的具體值，系統(tǒng)會獲取當前ID最大值加1（默認情況下是+1，除非我們在建表的時候指定了自增間隔N, 那么則是+N）作為下一條記錄的ID。
也就是說，主鍵自增的插入方式正好符合我們前面提到的遞增插入場景。每次插入一條新記錄都是追加插入，不需要挪動任何節(jié)點，也不涉及葉子節(jié)點的分裂，所以寫數(shù)據(jù)的成本很低。
但是有些場景下我們需要將業(yè)務字段作為主鍵，比如：報告編號、不重復的身份證號等字段，這樣我們往往沒法保證有序插入（自增插入），所以寫數(shù)據(jù)的成本是相對高很多。
除了性能的考量，我們還可以從占用空間的角度來分析。比如我們有一個字符串類型的身份證號，那么我們是使用它來做主鍵還是自增ID呢？
由于每個二級索引的葉子節(jié)點上都是主鍵的值，所以如果使用身份證，那每個二級索引的葉子節(jié)點都將存一個占用20個字節(jié)的字符串。而如果使用整形作為主鍵，則占用4個字節(jié)；使用長整型，占用8個字節(jié)。
顯然主鍵值越小，二級索引的葉子節(jié)點就越小，普通索引占用的空間也就越小
有沒有什么場合使用業(yè)務字段作為主鍵的呢？還是有的，比如某些業(yè)務場景的索引要求是這樣的：
1.只有一個索引
2.該索引必須是唯一索引
可能你已經(jīng)看出來了，這是一個經(jīng)典的KV場景。由于沒有其他索引，也就不用考慮其他索引葉子節(jié)點的大小問題了。
這個時候我們就需要考慮上面提到的“盡量使用主鍵查詢”原則，直接將這個業(yè)務字段設(shè)置為主鍵，避免回表引入的性能損耗。
最左前綴原則
關(guān)于索引還有一個非常非常重要的索引生效原則：最左前綴原則
剛開始接觸索引的時候，我們會發(fā)現(xiàn)很多業(yè)務字段都會作為等值、范圍、模糊等檢索條件，那我們常常會由于這樣沒每個字段都創(chuàng)建一個索引是不是很麻煩，索引占用的空間應該非常大吧，是的！我們說過每個索引都會對應一個B+樹。
比如我需要根據(jù)身份證查詢用戶的家庭地址，需要這不是一個頻繁的查詢需要，但是數(shù)據(jù)量很大的情況下我們總不能讓它走全表吧。那應該怎么做的？
這里，我們先說結(jié)論：B+樹這種結(jié)構(gòu)可以利用索引的最左前綴來定位數(shù)據(jù)
為了更直觀的說明這個問題，我畫了下面這張圖，我們利用（name，age）這個聯(lián)合索引（也有叫復合索引的）來解釋：
可以看到索引項是按照索引定義里面的順序出現(xiàn)的 , 即（name, age）-> ("曹操"， 30)
當我們的邏輯需要時查詢一個姓名為“曹操”的人，可以快速定位到ID4，然后向后遍歷所有需要得到的結(jié)果。
如果我們要查姓名第一個字為“曹”的人，會使用模糊匹配， “ where name like '曹%' ”， 這時候我們也可以利用到這個索引，查詢到第一個ID4。
可以看出不只是索引的全部定義，只要滿足索引的最左前綴，就能利用索引實現(xiàn)快速檢索。這個最左前綴可以是聯(lián)合索引的前N個字段，也可以是字符串索引的前N個字符。
基于上面的最左前綴原則，我們來看下：在建立索引的時候，如何安排索引內(nèi)的字段順序
其實就是將最高頻檢索條件對應的字段放到最左邊即可。
補充：如果有一個聯(lián)合索引（a，b），同時又存在a,b各自的索引（a）和（b），那這種情況下如果只有一個基于b的查詢條件，這種是不能利用到（a, b）索引的。這種情況我們需要同時維護一個（a,b）（b）兩個索引就可以了。
索引下推
這個是MySQL 5.6引入的，上面的最左前綴原則可以用于在索引中定位問題。但是那些不滿足最左前綴的怎辦呢？
我們還是以上面的（name，age）這個聯(lián)合索引為例。如果現(xiàn)在有一個需求檢索出用戶表中姓名第一個字為“曹”，并且年齡為45歲的所有男人。SQL我們會這樣寫
SQL> select * from T where name like '曹%' and age = 45 and ismale=1；
你已經(jīng)知道了前綴索引規(guī)則，所以這個語句在搜索索引樹的時候，只能用“曹”找到第一個滿足條件的ID4。當然，這還不錯了，總比全表掃描好。然后判斷其他條件是否滿足。
在MySQL 5.6之前，只能從ID4開始一個個的進行回表，在主鍵B+樹中找到記錄，在判斷其他字段值。
而在MySQL 5.6之后，MySQL可以在（name， age）所以上直接判斷age是否等于45.滿足條件的在進行回表，減少了回表的次數(shù)。這個引入的新的邏輯叫索引下推
總結(jié)
MySQL的索引模型，已經(jīng)后面提到的最左前綴等是非常非常重要的，搞懂這些，對我們的數(shù)據(jù)查詢性能會有很大的幫助。但是關(guān)于索引的內(nèi)容絕不止我今天記錄的這一點點，還有很多的東西需要我們?nèi)ヌ剿鳌?/p>
個人博客網(wǎng)站：RelaxHeart網(wǎng) - TEC博客
