我們常說的“數(shù)據(jù)庫”，比如“MySQL”、“Oracle”等，其實嚴(yán)格來說是DBMS(Database Management System)，數(shù)據(jù)庫只是一個存儲數(shù)據(jù)著數(shù)據(jù)的倉庫，而DBMS做的事是讓我們能夠操作數(shù)據(jù)庫，比如解析SQL、DML等，都是DBMS在支持著。
在DBMS之下，又有著存儲引擎，為DBMS提供數(shù)據(jù)增刪改查的支持，不同的存儲引擎提供不同的特性，負(fù)責(zé)組織數(shù)據(jù)的就是存儲引擎。
一、數(shù)據(jù)的組織方式
1. 單條記錄的結(jié)構(gòu)
每一個字段都需要定義一個數(shù)據(jù)類型(DataType)，數(shù)據(jù)類型在數(shù)據(jù)組織時的意義是確定數(shù)據(jù)長度，存儲介質(zhì)將會為其分配合適長度的空間。
每個字段被按照順序組織起來，并且在開頭存儲著這一行的某些頭信息(MetaData)，例如記錄總長度、時間戳等，這就組成了一條在硬盤上被存儲的完整記錄：
如果是變長記錄，比如某一個字段是varchar(256)，則會在頭信息后緊接著存儲這一列的指針，指向這個字段的值存儲地址（一般是在記錄的末尾）：
由于每次從磁盤中讀取數(shù)據(jù)的單位是頁(Page)，為了保證讀取速度，一般數(shù)據(jù)庫都會要求一條記錄的長度不超過一頁（頁的長度不固定，可以被設(shè)置，一般是4kb），保證一次讀取就能讀到一條完整記錄，而不需要跨頁讀取，因此對于某些存儲著大數(shù)據(jù)的字段，比如圖片、視頻，他們往往被獨立存儲到其他文件，而不與記錄中的其他小字段存儲在一起。
2. 多條記錄如何被組織
行是一條具有完整意義的記錄，被按照一定的規(guī)則，依次存儲在文件中。
記錄在文件中有以下幾種主要的組織方法：
1. 堆文件
記錄與記錄之間沒有順序關(guān)系，每條記錄可以存放在文件中的任何地方，只要想被存儲的地址有足夠空間。
2. 順序文件
也就是遵循某個搜索碼(Search key)的順序，依次存儲每一條記錄。搜索碼是一系列搜索條件的組合，可以是一個鍵，也可以是多個鍵組合。如下圖，按照第二列，也就是姓名的順序去決定記錄的存儲順序：
這種方式非常利于順序讀取，因為連續(xù)的記錄都保存在連續(xù)的頁中，可一次性讀出多個頁獲得批量的記錄，而無需多次尋址多次讀取。
但是這種方式不利于記錄的刪除和插入，因為刪除記錄時需要將后面的記錄依次前移，插入記錄時需要將后面的記錄依次后移，如果受影響的記錄多，效率將會很低。
為了解決每次插入刪除數(shù)據(jù)都需要移動后面的記錄的問題，現(xiàn)實中可能采取了指針，也就是每一條記錄中保存著指向下一條記錄的指針，當(dāng)有記錄被刪除時，僅僅修改指針，避免記錄的移動；當(dāng)有記錄插入時，先檢查在合適的位置是否有空閑空間，如果沒有，采用開辟溢出塊的方式，不直接插入至合適位置，而是在其他空間存儲這條記錄，然后修改上一條記錄的指針指向這條新插入的記錄，去避免大量記錄的移動：
但是如果大量的記錄都存儲在溢出塊中，順序文件本身所帶來的好處就大打折扣，因為很多記錄已經(jīng)不再在物理上按順序存儲，那么順序獲取記錄時，就可能需要多次尋址多次讀取，而不能通過一次性讀取連續(xù)的頁來獲取連續(xù)的記錄。此時，文件就需要被重組，會將所有記錄重新組織成完全物理鄰接的文件。
3. 聚簇文件
前面提到的順序文件是不同的表存儲在不同的文件中，但是某些具體應(yīng)用場景下，可能常常涉及多表查詢，比如有一個名為Singers的表保存著歌手信息，又有一個名為Albums的表保存著每個歌手發(fā)布的專輯信息，如果你正在開發(fā)一個音樂播放器，那么涉及的場景一般都是需要找出某個歌手發(fā)布的所有專輯展示給客戶，如果不同的表保存在不同的文件中，那么需要進(jìn)行連接(Join) ，復(fù)雜度比較高，但是如果將每個歌手的專輯信息都在物理上存儲在歌手信息之后，也就是兩張表混合存放在同一個文件中:
采用聚簇文件則不需要進(jìn)行Join操作，找到Singer后，直接順序讀取后面的頁，就能拿到指定歌手的所有專輯，提高了查詢效率。
4. 散列文件
散列文件完全沒有順序，每條記錄應(yīng)該存放的位置，是根據(jù)搜索碼的Hash值決定的，因此插入刪除都不涉及記錄移動，且由于搜索碼的Hash值直接決定了存儲位置，所以查找符合特定搜索碼的記錄非?？?，但是不支持范圍查找與順序讀取。
3. 記錄的讀取
DBMS維護(hù)著自己的緩存空間，使用一些緩存置換算法盡量確保那些經(jīng)常被使用的數(shù)據(jù)在緩存中，以避免磁盤的讀取。與DBMS一樣，磁盤一般也有著自己的緩沖區(qū)以保存經(jīng)常被讀取的數(shù)據(jù)，減少響應(yīng)時間。因此，如果要讀取一條記錄，根據(jù)優(yōu)先順序，路徑為DBMS緩存區(qū) => 磁盤緩存區(qū) => 磁盤。
1. 從DBMS緩存區(qū)讀取
這是成本最低的方式，因為DBMS緩存區(qū)就在內(nèi)存，可以直接被CPU使用，不涉及磁盤IO，可以考慮IO時間為0。
2. 從磁盤緩存區(qū)讀取
如果磁盤緩存區(qū)有需要的記錄，則只需要直接讀出，傳輸時間考慮為1ms。
3. 從磁盤讀取
由于SSD比較貴，常用的還是機(jī)械硬盤，對于機(jī)械硬盤，要讀取指定地址的數(shù)據(jù)，是需要經(jīng)過尋道的，機(jī)械臂需要先移動到指定位置，因此無論讀取多少數(shù)據(jù)，準(zhǔn)備工作都會耗費(fèi)一段時間。
整個IO流程包括：排隊等待 => 尋道 => 半圈旋轉(zhuǎn) => 傳輸
一次隨機(jī)讀取中，有90%的時間都花費(fèi)在排隊和準(zhǔn)備工作，真正的傳輸時間只有1ms，隨機(jī)讀取10頁，就需要10*10=100ms，但如果是順序讀，對于傳輸速度為40MB/s的硬盤，讀取一個4kb的頁僅需要0.1ms，即使順序讀取100頁，也只需要1頁隨機(jī)讀99頁順序讀，也就是10ms+9.9ms=19.9ms，速度差距幾十倍，這也是為何我們想要盡量保證需要讀取的數(shù)據(jù)都在物理上排列在一起，因為這樣就可以順序讀取多個頁，而不需要進(jìn)行多次隨機(jī)讀取。
因此對于數(shù)據(jù)讀取速度的優(yōu)化，主要就是需要降低IO時間，而降低IO時間的關(guān)鍵，就在于減少隨機(jī)讀次數(shù)以及讀取更少的數(shù)據(jù)。
合適的索引將會很大程度上地幫助我們實現(xiàn)這個目標(biāo)。
二、索引
考慮一種情況：我們有一張存儲著100萬個注冊用戶的Users表，我們要搜索用戶名為AfterShip的用戶，如果這張表是使用順序文件存儲，并且存儲順序是根據(jù)account_id列，而不是根據(jù)username列，在沒有索引時，查找的方式應(yīng)該是從第一條記錄起依次讀入記錄，并對比每一條記錄的username是否為AfterShip，直到找到為止。最好的情況是第一條記錄即符合要求，最壞的情況是最后一條記錄才符合要求，在最壞的情況下，需要讀取100萬條記錄，假設(shè)每條記錄1kb，需要讀取976MB的數(shù)據(jù)！即使以200MB/s的傳輸速度，僅僅是IO時間就需要5s讀取記錄，并且還需要大量的時間給CPU處理100萬條的記錄。
如果是以account_id作為搜索條件，最快的方式是從文件的最中間位置讀出最中間記錄，對比account_id的大小，再判斷往前還是往后讀，也就是使用2分搜索，最壞的情況下需要進(jìn)行l(wèi)ogN次，也就是20次左右的隨機(jī)讀，耗時200ms。
因此，當(dāng)我們的搜索碼被順序地組織起來，我們就能更少地讀取數(shù)據(jù)，以更快的方式查詢到符合要求的記錄，但是，文件只能以一種搜索碼組織起來，不能既以account_id為順序，又以username為順序，因此，我們需要一種冗余的數(shù)據(jù)——索引，來以我們想要的順序組織某個搜索碼，加速我們的查詢。
1. 什么是索引
索引是一種被以合適的數(shù)據(jù)結(jié)構(gòu)組織起來方便搜索的冗余數(shù)據(jù)，也存儲在文件中。
比如對于Users表，我們?yōu)?code>username建立索引，那么DBMS會將username的值復(fù)制一份，并排序，保存在一個文件中：
每條索引保存著指向原始記錄的指針，同時保存著這條索引字段的值。
如果索引也是一個順序文件，那么我們根據(jù)上面的例子，要查找
username為AfterShip的記錄，就可以使用二分搜索，或者哪怕是順序掃描整個索引也比之前進(jìn)行全表掃描快得多，因為一個username的長度如果是50bytes，那么掃描整個索引也只需要讀取不到50MB的索引文件，體積只是全表掃描的二十分之一。由此可見，索引可以有效地加快查詢速度。剛剛講到的是順序索引，在索引的具體實現(xiàn)中還有多種更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法，索引有多種實現(xiàn)方式，每種實現(xiàn)方式都各有優(yōu)缺點，適應(yīng)不同的應(yīng)用環(huán)境。
2. 索引的分類
索引可以從多個維度分類，每個維度的分類互不沖突。
-
聚簇索引(Clustered Index) 與 非聚簇索引(Nonclustered Index / Secondary Index)
前面講到順序文件是將記錄根據(jù)某個搜索碼的值排列的，我們在這個搜索碼上建立的索引就是聚簇索引，聚簇索引代表著記錄的物理存儲順序是被這個索引的排列順序決定的。在MySQL中，主鍵(Primary Key)就是聚簇索引，因為每條記錄的物理順序是與主鍵順序相同的。聚簇索引不一定是主鍵，可以是任何搜索碼，但一般的DBMS都將主鍵作為聚簇索引。
不以索引順序組織表文件順序的索引，就是非聚簇索引，也稱為輔助索引(Secondary Index)，比如上面講到的以username建立的索引。 -
稠密索引 與 稀疏索引
根據(jù)是否是為每個搜索碼都建立對應(yīng)的索引，分為稠密索引與稀疏索引。
稠密索引為每一個搜索碼都建立一條索引記錄，如果此稠密索引是聚簇索引，那么只需要保存符合此搜索碼的第一條記錄的指針即可，因為所有符合此搜索碼的記錄一定都在物理順序上緊隨其后，如果此稠密索引是非聚簇索引，那么每個索引項中都必須保存著符合此搜索碼的所有記錄的指針，在下圖中，我們?yōu)榈诙?，也就是地名，建立稠密索引?br>稠密索引為每一個搜索碼都建立一條索引記錄
如果我們將記錄分為多個組，僅為每個組的第一條記錄建立索引，也就是索引到組而不是索引到記錄，那么就稱為稀疏索引。如何將記錄分組？其中一種方式是以頁為單位，為每一頁的記錄建立一條索引：
稀疏索引僅為每組的第一條記錄建立索引
查找速度：
對于稠密索引，由于為每一個搜索碼都建立的相應(yīng)的索引項，因此空間占用比較大，但是查找速度較快，因為可以從索引文件中直接找到對應(yīng)記錄的位置，而使用稀疏索引需要先找到記錄所在的頁，再讀出整個頁，從頁中找到具體的記錄。
維護(hù)成本：
稠密索引為每個搜索碼都建立對應(yīng)的索引項，且索引項中還保存著符合此搜索碼的所有記錄的指針，也就是關(guān)聯(lián)到了表中的每一條記錄，因此當(dāng)任何一條記錄被刪除、插入，都需要修改甚至移動、重組索引文件，維護(hù)成本較高。
而稀疏索引僅僅為分組建立索引項，當(dāng)組中有記錄刪除時不一定會馬上修改索引，有記錄插入到現(xiàn)有的組時，只要不占用新的頁或者影響到組的第一條記錄，那么也不會建立新的索引，索引更新相對不那么頻繁，維護(hù)成本較小。
-
有序索引 與 散列索引
前面講到的索引都是根據(jù)特定搜索碼排序的，都叫做有序索引，索引項的位置是根據(jù)其搜索碼在整個搜索碼集合中的相對位置決定的，要查找某條記錄，通過對比搜索碼大小的方式找到相應(yīng)索引項，然后通過指針從表中讀取記錄。
而散列索引使用特定散列算法算出搜索碼的Hash值，根據(jù)Hash值直接確定這條搜索碼的索引項的地址，而不是通過比較搜索碼大小的方式，對于指定搜索碼，查找速度非?？?，但不能像有序索引一樣支持范圍查找。在增刪記錄時，也不需要造成索引的移動、重組，因此維護(hù)成本比有序索引更低。
3. 多級索引
繼續(xù)考慮那張存有100萬條用戶數(shù)據(jù)的Users表，我們?yōu)?code>username建立了有序稠密索引，并且我們假設(shè)username是具備唯一性的，也就是對于100萬個用戶，就有100萬個不同的username，稠密索引將會有100萬條索引項，如果一個4kb的頁能保存100條索引項，那么就需要1萬頁來保存整個索引文件。如果我們要查詢username為AfterShip的用戶，使用二分法就需要進(jìn)行l(wèi)ogN次的查詢，也就是14次隨機(jī)讀找到其索引項，再通過一次隨機(jī)讀讀出記錄，一共150ms，一秒內(nèi)只能進(jìn)行6次查詢。如果我們能減少其隨機(jī)讀次數(shù)，那么每少一次隨機(jī)讀，就會少10ms的耗時，減少隨機(jī)讀有以下兩個思路：
- 將索引緩存在內(nèi)存中，避免磁盤讀取
- 優(yōu)化路徑，以更少的隨機(jī)讀查找到對應(yīng)索引項
如果我們基于100萬條稠密索引再去建立稀疏索引，也就是對1萬個頁建立索引，那么對于一頁能保存100條索引項的情況下，我們將會有更上一級的，僅占用100頁的稀疏索引，整個索引文件為400kb，足夠小到能夠放入內(nèi)存，因此可以保存在DBMS緩存區(qū)，先通過稀疏索引找到稠密索引所在的頁地址，再進(jìn)行一次隨機(jī)讀，讀出整個頁，找到搜索碼對應(yīng)的具體索引項，然后再進(jìn)行第二次隨機(jī)讀，讀出表中記錄，一共只有1次內(nèi)存讀+2次隨機(jī)讀，20ms。僅僅多建立一層稀疏索引，也即是使用二級索引結(jié)構(gòu)，就有7倍的效率提升。在現(xiàn)實場景中，往往會多次進(jìn)行這種索引結(jié)構(gòu)的建立，也就是多級索引結(jié)構(gòu)。
4. 代表性索引結(jié)構(gòu)
（1）B+樹索引
B+樹是一種多級索引的實現(xiàn)，采用平衡樹結(jié)構(gòu)，有非頁節(jié)點、葉節(jié)點兩種節(jié)點組成，每種節(jié)點存放的數(shù)據(jù)有細(xì)微差別：
-
非葉節(jié)點（根節(jié)點也是非葉節(jié)點）：
節(jié)點最多包含著n-1個搜索碼值K1…Kn-1，并包含著n個指針P1…Pn，也就是兩邊是指針，中間是搜索碼值，Pn指針指向小于其Kn搜索碼的下一級索引節(jié)點，Pn+1指向大于等于Kn搜索碼的下一級索引節(jié)點。
根節(jié)點
舉個栗子：
非葉節(jié)點 -
葉節(jié)點
葉節(jié)點的P1…Pn-1的指針都指向記錄地址（如果是稠密索引）或者頁地址（如果是稀疏索引），葉節(jié)點的最后一個指針Pn與非葉節(jié)點不同，它指向的是下一個同級葉節(jié)點，構(gòu)成橫向有序的索引結(jié)構(gòu)。
葉節(jié)點
一個完整的三級B+樹如下所示：
B+樹的葉節(jié)點中的搜索碼值是可以重復(fù)的，當(dāng)這個B+樹索引是非聚簇稠密索引且搜索碼對應(yīng)的記錄不唯一時，就需要將一個搜索碼重復(fù)放置在葉節(jié)點中，指向不同的記錄：
B+樹維護(hù)成本
考慮一個稠密B+樹索引，在刪除記錄時，由于B+樹要求每個葉節(jié)點都必須處于半滿狀態(tài)，當(dāng)被刪除索引項所處的節(jié)點不滿足半滿時，需要向兄弟節(jié)點借搜索碼值，并且在需要時調(diào)整父節(jié)點，是一個局部重組B+樹的過程。
在插入記錄時，可能出現(xiàn)某個索引節(jié)點已經(jīng)沒有多余空間存儲，此時則需要分裂葉節(jié)點，并且上層非葉節(jié)點也可能需要分裂，依次往上遞歸，也是一次重組的過程。B+樹的優(yōu)點
從上面能夠看出，在某些情況下，刪除和插入記錄時，B+樹的維護(hù)成本比較高，但是為何依舊是最常用的索引結(jié)構(gòu)之一呢，因為我們往往會把每個節(jié)點的空間設(shè)置得足夠大，一般是一整頁，如果一個索引項占用100bytes，則對于4kb的頁能夠存儲40個索引項，即使是100萬條記錄的表，B+樹也只需要log(40)1000000=3層，查詢路徑非常短，因此B+樹實際上是一種效率非常高的索引結(jié)構(gòu)。
（2）B樹索引
這是一種與B+樹類似的平衡樹索引，區(qū)別在于，B+樹只有葉節(jié)點保存著指向記錄的指針，非葉節(jié)點僅僅是索引著索引的索引，而B樹整棵樹的所有節(jié)點都保存著指向其對應(yīng)記錄的指針，整棵樹才是一個完整的索引：
B樹不常被應(yīng)用，因為在B樹種范圍查詢的效率非常低，B+樹中所有葉節(jié)點被鏈接起來成為有序鏈表，可以方便地遍歷所需范圍的數(shù)據(jù)，而B樹則需要更加復(fù)雜的算法去遍歷多個層次的節(jié)點才能獲取到一定范圍內(nèi)的數(shù)據(jù)。
（3）散列索引
前面講到的索引結(jié)構(gòu)都需要通過對比搜索碼的大小去查找索引項的位置，復(fù)雜度是對數(shù)級別的，而散列索引將存儲空間分為多個組，稱為桶(Bucket)，直接通過散列函數(shù)計算搜索碼的Hash值，通過Hash值確定此搜索碼的索引項在哪個桶中，讀取桶中的索引項，就可以找到對應(yīng)索引項，復(fù)雜度為O(1)，因此散列索引對于查詢指定搜索碼的效率非常高。
根據(jù)桶的數(shù)量是否固定，散列索引分為靜態(tài)散列與動態(tài)散列兩種：
-
靜態(tài)散列
靜態(tài)散列非常簡單，桶的個數(shù)早已確定，比如對于Users表，已確定共有100個桶，那么對于每條記錄應(yīng)該放置在哪個桶，即計算Hash(搜索碼) mod 100，就能確定應(yīng)該放置到哪個桶。
我們并不知道每張表最終會有多少記錄，因此預(yù)先分配的桶的容量可能隨著記錄的增加而不夠用，比如預(yù)先分配的桶容量可能是一頁4kb，每個索引項100bytes只能存儲40個索引項，當(dāng)有第41條索引項插入時，就需要開辟溢出桶：
溢出桶
溢出桶是使用鏈表實現(xiàn)的，主桶保存著下一個溢出桶的指針，每個溢出桶依次鏈接。
于是，靜態(tài)散列有一個非常明顯的缺陷：當(dāng)數(shù)據(jù)量變得很大時，可能會大量開辟溢出桶，造成每次查找索引項，可能要進(jìn)行多次隨機(jī)讀，鏈表越長，隨機(jī)讀次數(shù)越多，效率下降。 -
動態(tài)散列
動態(tài)散列可以使得桶的個數(shù)隨著記錄的增加而動態(tài)增加，這里介紹比較基礎(chǔ)的可擴(kuò)展散列(Extendable Hashing)：
首先，我們選擇一個具有均勻和隨機(jī)特性的散列函數(shù)H，此散列函數(shù)的結(jié)果是N位二進(jìn)制數(shù)，比如N=32，則每個Hash值為32位的二進(jìn)制數(shù)。
此記錄的索引項應(yīng)該存儲在哪個桶中，取二進(jìn)制數(shù)的前 i 位，i 的起始值為1，我們會保存著這個 i 值，我們來看一條記錄是如何放入桶中：- 使用散列函數(shù)H計算搜索碼X的Hash值，假設(shè)H(X) = 0001…（省略后面的28位，省略號表示在我們的討論中不重要，下同）
- 查看 i 值，此時 i = 1，則表示此記錄的索引項應(yīng)該存在 0001…的第1位，也就是0號桶中
-
我們維護(hù)著一個桶地址列表，保存著每個號碼的桶的指針，在列表中找到0號桶的指針，訪問0號桶，將其放進(jìn)去。下圖中，我們?yōu)槊總€桶中保存著一個值K，表示這個桶是以前K位作為標(biāo)識的。
桶地址列表與桶
-
桶分裂
在上圖中，1號桶已經(jīng)滿了，如果新增一條Hash值為1010…的記錄，根據(jù)i的值，我們需要將它放進(jìn)1號桶，但是檢查發(fā)現(xiàn)1號桶已經(jīng)滿了，于是需要進(jìn)行桶的分裂，先更新桶地址列表，使得i值增加1，使用前2位作為桶號，列表中變成00、01、10、11四個桶，將之前已經(jīng)滿了的1號桶，其中10開頭的記錄放入10號桶，11開頭的記錄放入11號桶，且這兩個新桶的K值設(shè)置為2，之前的0號桶不動，并且00和01都同時指向0號舊桶，不改變：
僅分裂已經(jīng)滿了的桶
因此可以發(fā)現(xiàn)，我們僅僅分裂已經(jīng)滿了的桶，其他桶不會動，并且不同的桶號，可能指向的是同一個地址，暫時共用一個未滿的桶。
在記錄被刪除時，如果桶已經(jīng)空了，則會合并桶。
這就是神奇的動態(tài)散列算法。
5. 多碼索引
目前為止我們討論的都是搜索碼為一個字段的情況，其實搜索碼可以是多個字段的組合，比如index(username,age,city)，索引項中按照索引定義次序依次存儲著三個字段的值，比如(AfterShip,25,ShenZhen)，索引項之間的排序先根據(jù)第一列索引排序，第一列相同的情況下再根據(jù)第二列排序，以此類推。
6. 覆蓋索引（Covering Index）
覆蓋索引不是一種索引分類，而是一種對索引的使用方式。
繼續(xù)考慮上面那張保存著100萬用戶的Users表，我們要查找username為AfterShip的用戶的email，如果我們僅僅為username建立索引，那么我們需要先通過索引查找到username為AfterShip的賬號的記錄指針，再回表讀取此記錄email列的值。但如果我們的索引是為(username,email)建立的復(fù)合索引，那么我們在索引項中就能直接獲取到email值，而不需要回表讀取，減少一次隨機(jī)IO操作。
因此，適當(dāng)?shù)乩酶采w索引，可以減少IO，加快查詢。
