我們常說的“數(shù)據(jù)庫”，比如“MySQL”、“Oracle”等，其實(shí)嚴(yán)格來說是DBMS(Database Management System)，數(shù)據(jù)庫只是一個(gè)存儲數(shù)據(jù)著數(shù)據(jù)的倉庫，而DBMS做的事是讓我們能夠操作數(shù)據(jù)庫，比如解析SQL、DML等，都是DBMS在支持著。
在DBMS之下，又有著存儲引擎，為DBMS提供數(shù)據(jù)增刪改查的支持，不同的存儲引擎提供不同的特性，負(fù)責(zé)組織數(shù)據(jù)的就是存儲引擎。

一、數(shù)據(jù)的組織方式

1. 單條記錄的結(jié)構(gòu)

每一個(gè)字段都需要定義一個(gè)數(shù)據(jù)類型(DataType)，數(shù)據(jù)類型在數(shù)據(jù)組織時(shí)的意義是確定數(shù)據(jù)長度，存儲介質(zhì)將會為其分配合適長度的空間。
每個(gè)字段被按照順序組織起來，并且在開頭存儲著這一行的某些頭信息(MetaData)，例如記錄總長度、時(shí)間戳等，這就組成了一條在硬盤上被存儲的完整記錄：

定長記錄行的表示

如果是變長記錄，比如某一個(gè)字段是varchar(256)，則會在頭信息后緊接著存儲這一列的指針，指向這個(gè)字段的值存儲地址（一般是在記錄的末尾）：

變長記錄行的表示

2. 多條記錄如何被組織

行是一條具有完整意義的記錄，被按照一定的規(guī)則，依次存儲在文件中。
記錄在文件中有以下幾種主要的組織方法：

1. 堆文件

記錄與記錄之間沒有順序關(guān)系，每條記錄可以存放在文件中的任何地方，只要想被存儲的地址有足夠空間。

2. 順序文件

也就是遵循某個(gè)搜索碼(Search key)的順序，依次存儲每一條記錄。搜索碼是一系列搜索條件的組合，可以是一個(gè)鍵，也可以是多個(gè)鍵組合。如下圖，按照第二列，也就是姓名的順序去決定記錄的存儲順序：

順序文件

開辟溢出塊

3. 聚簇文件

前面提到的順序文件是不同的表存儲在不同的文件中，但是某些具體應(yīng)用場景下，可能常常涉及多表查詢，比如有一個(gè)名為Singers的表保存著歌手信息，又有一個(gè)名為Albums的表保存著每個(gè)歌手發(fā)布的專輯信息，如果你正在開發(fā)一個(gè)音樂播放器，那么涉及的場景一般都是需要找出某個(gè)歌手發(fā)布的所有專輯展示給客戶，如果不同的表保存在不同的文件中，那么需要進(jìn)行連接(Join) ，復(fù)雜度比較高，但是如果將每個(gè)歌手的專輯信息都在物理上存儲在歌手信息之后，也就是兩張表混合存放在同一個(gè)文件中:

聚簇文件

采用聚簇文件則不需要進(jìn)行Join操作，找到Singer后，直接順序讀取后面的頁，就能拿到指定歌手的所有專輯，提高了查詢效率。

4. 散列文件

散列文件完全沒有順序，每條記錄應(yīng)該存放的位置，是根據(jù)搜索碼的Hash值決定的，因此插入刪除都不涉及記錄移動(dòng)，且由于搜索碼的Hash值直接決定了存儲位置，所以查找符合特定搜索碼的記錄非?？?，但是不支持范圍查找與順序讀取。

3. 記錄的讀取

DBMS維護(hù)著自己的緩存空間，使用一些緩存置換算法盡量確保那些經(jīng)常被使用的數(shù)據(jù)在緩存中，以避免磁盤的讀取。與DBMS一樣，磁盤一般也有著自己的緩沖區(qū)以保存經(jīng)常被讀取的數(shù)據(jù)，減少響應(yīng)時(shí)間。因此，如果要讀取一條記錄，根據(jù)優(yōu)先順序，路徑為DBMS緩存區(qū) => 磁盤緩存區(qū) => 磁盤。

1. 從DBMS緩存區(qū)讀取

這是成本最低的方式，因?yàn)镈BMS緩存區(qū)就在內(nèi)存，可以直接被CPU使用，不涉及磁盤IO，可以考慮IO時(shí)間為0。

2. 從磁盤緩存區(qū)讀取

如果磁盤緩存區(qū)有需要的記錄，則只需要直接讀出，傳輸時(shí)間考慮為1ms。

3. 從磁盤讀取

由于SSD比較貴，常用的還是機(jī)械硬盤，對于機(jī)械硬盤，要讀取指定地址的數(shù)據(jù)，是需要經(jīng)過尋道的，機(jī)械臂需要先移動(dòng)到指定位置，因此無論讀取多少數(shù)據(jù)，準(zhǔn)備工作都會耗費(fèi)一段時(shí)間。
整個(gè)IO流程包括：排隊(duì)等待 => 尋道 => 半圈旋轉(zhuǎn) => 傳輸

隨機(jī)讀取

一次隨機(jī)讀取中，有90%的時(shí)間都花費(fèi)在排隊(duì)和準(zhǔn)備工作，真正的傳輸時(shí)間只有1ms，隨機(jī)讀取10頁，就需要10*10=100ms，但如果是順序讀，對于傳輸速度為40MB/s的硬盤，讀取一個(gè)4kb的頁僅需要0.1ms，即使順序讀取100頁，也只需要1頁隨機(jī)讀99頁順序讀，也就是10ms+9.9ms=19.9ms，速度差距幾十倍，這也是為何我們想要盡量保證需要讀取的數(shù)據(jù)都在物理上排列在一起，因?yàn)檫@樣就可以順序讀取多個(gè)頁，而不需要進(jìn)行多次隨機(jī)讀取。

磁盤及CPU時(shí)間的基礎(chǔ)假設(shè)

因此對于數(shù)據(jù)讀取速度的優(yōu)化，主要就是需要降低IO時(shí)間，而降低IO時(shí)間的關(guān)鍵，就在于減少隨機(jī)讀次數(shù)以及讀取更少的數(shù)據(jù)。
合適的索引將會很大程度上地幫助我們實(shí)現(xiàn)這個(gè)目標(biāo)。

二、索引

考慮一種情況：我們有一張存儲著100萬個(gè)注冊用戶的Users表，我們要搜索用戶名為AfterShip的用戶，如果這張表是使用順序文件存儲，并且存儲順序是根據(jù)account_id列，而不是根據(jù)username列，在沒有索引時(shí)，查找的方式應(yīng)該是從第一條記錄起依次讀入記錄，并對比每一條記錄的username是否為AfterShip，直到找到為止。最好的情況是第一條記錄即符合要求，最壞的情況是最后一條記錄才符合要求，在最壞的情況下，需要讀取100萬條記錄，假設(shè)每條記錄1kb，需要讀取976MB的數(shù)據(jù)！即使以200MB/s的傳輸速度，僅僅是IO時(shí)間就需要5s讀取記錄，并且還需要大量的時(shí)間給CPU處理100萬條的記錄。
如果是以account_id作為搜索條件，最快的方式是從文件的最中間位置讀出最中間記錄，對比account_id的大小，再判斷往前還是往后讀，也就是使用2分搜索，最壞的情況下需要進(jìn)行l(wèi)ogN次，也就是20次左右的隨機(jī)讀，耗時(shí)200ms。
因此，當(dāng)我們的搜索碼被順序地組織起來，我們就能更少地讀取數(shù)據(jù)，以更快的方式查詢到符合要求的記錄，但是，文件只能以一種搜索碼組織起來，不能既以account_id為順序，又以username為順序，因此，我們需要一種冗余的數(shù)據(jù)——索引，來以我們想要的順序組織某個(gè)搜索碼，加速我們的查詢。

1. 什么是索引

索引是一種被以合適的數(shù)據(jù)結(jié)構(gòu)組織起來方便搜索的冗余數(shù)據(jù)，也存儲在文件中。
比如對于Users表，我們?yōu)?code>username建立索引，那么DBMS會將username的值復(fù)制一份，并排序，保存在一個(gè)文件中：

索引

2. 索引的分類

索引可以從多個(gè)維度分類，每個(gè)維度的分類互不沖突。

• 聚簇索引(Clustered Index) 與 非聚簇索引(Nonclustered Index / Secondary Index)
  前面講到順序文件是將記錄根據(jù)某個(gè)搜索碼的值排列的，我們在這個(gè)搜索碼上建立的索引就是聚簇索引，聚簇索引代表著記錄的物理存儲順序是被這個(gè)索引的排列順序決定的。在MySQL中，主鍵(Primary Key)就是聚簇索引，因?yàn)槊織l記錄的物理順序是與主鍵順序相同的。聚簇索引不一定是主鍵，可以是任何搜索碼，但一般的DBMS都將主鍵作為聚簇索引。
  不以索引順序組織表文件順序的索引，就是非聚簇索引，也稱為輔助索引(Secondary Index)，比如上面講到的以username建立的索引。
• 稠密索引 與 稀疏索引
  根據(jù)是否是為每個(gè)搜索碼都建立對應(yīng)的索引，分為稠密索引與稀疏索引。
  稠密索引為每一個(gè)搜索碼都建立一條索引記錄，如果此稠密索引是聚簇索引，那么只需要保存符合此搜索碼的第一條記錄的指針即可，因?yàn)樗蟹洗怂阉鞔a的記錄一定都在物理順序上緊隨其后，如果此稠密索引是非聚簇索引，那么每個(gè)索引項(xiàng)中都必須保存著符合此搜索碼的所有記錄的指針，在下圖中，我們?yōu)榈诙?，也就是地名，建立稠密索引?br>
  稠密索引為每一個(gè)搜索碼都建立一條索引記錄
  
  如果我們將記錄分為多個(gè)組，僅為每個(gè)組的第一條記錄建立索引，也就是索引到組而不是索引到記錄，那么就稱為稀疏索引。如何將記錄分組？其中一種方式是以頁為單位，為每一頁的記錄建立一條索引：
  
  稀疏索引僅為每組的第一條記錄建立索引

查找速度：
對于稠密索引，由于為每一個(gè)搜索碼都建立的相應(yīng)的索引項(xiàng)，因此空間占用比較大，但是查找速度較快，因?yàn)榭梢詮乃饕募兄苯诱业綄?yīng)記錄的位置，而使用稀疏索引需要先找到記錄所在的頁，再讀出整個(gè)頁，從頁中找到具體的記錄。
維護(hù)成本：
稠密索引為每個(gè)搜索碼都建立對應(yīng)的索引項(xiàng)，且索引項(xiàng)中還保存著符合此搜索碼的所有記錄的指針，也就是關(guān)聯(lián)到了表中的每一條記錄，因此當(dāng)任何一條記錄被刪除、插入，都需要修改甚至移動(dòng)、重組索引文件，維護(hù)成本較高。
而稀疏索引僅僅為分組建立索引項(xiàng)，當(dāng)組中有記錄刪除時(shí)不一定會馬上修改索引，有記錄插入到現(xiàn)有的組時(shí)，只要不占用新的頁或者影響到組的第一條記錄，那么也不會建立新的索引，索引更新相對不那么頻繁，維護(hù)成本較小。

• 有序索引 與 散列索引
  前面講到的索引都是根據(jù)特定搜索碼排序的，都叫做有序索引，索引項(xiàng)的位置是根據(jù)其搜索碼在整個(gè)搜索碼集合中的相對位置決定的，要查找某條記錄，通過對比搜索碼大小的方式找到相應(yīng)索引項(xiàng)，然后通過指針從表中讀取記錄。
  而散列索引使用特定散列算法算出搜索碼的Hash值，根據(jù)Hash值直接確定這條搜索碼的索引項(xiàng)的地址，而不是通過比較搜索碼大小的方式，對于指定搜索碼，查找速度非?？欤荒芟裼行蛩饕粯又С址秶檎?。在增刪記錄時(shí)，也不需要造成索引的移動(dòng)、重組，因此維護(hù)成本比有序索引更低。

3. 多級索引

繼續(xù)考慮那張存有100萬條用戶數(shù)據(jù)的Users表，我們?yōu)?code>username建立了有序稠密索引，并且我們假設(shè)username是具備唯一性的，也就是對于100萬個(gè)用戶，就有100萬個(gè)不同的username，稠密索引將會有100萬條索引項(xiàng)，如果一個(gè)4kb的頁能保存100條索引項(xiàng)，那么就需要1萬頁來保存整個(gè)索引文件。如果我們要查詢username為AfterShip的用戶，使用二分法就需要進(jìn)行l(wèi)ogN次的查詢，也就是14次隨機(jī)讀找到其索引項(xiàng)，再通過一次隨機(jī)讀讀出記錄，一共150ms，一秒內(nèi)只能進(jìn)行6次查詢。如果我們能減少其隨機(jī)讀次數(shù)，那么每少一次隨機(jī)讀，就會少10ms的耗時(shí)，減少隨機(jī)讀有以下兩個(gè)思路：

1. 將索引緩存在內(nèi)存中，避免磁盤讀取
2. 優(yōu)化路徑，以更少的隨機(jī)讀查找到對應(yīng)索引項(xiàng)

如果我們基于100萬條稠密索引再去建立稀疏索引，也就是對1萬個(gè)頁建立索引，那么對于一頁能保存100條索引項(xiàng)的情況下，我們將會有更上一級的，僅占用100頁的稀疏索引，整個(gè)索引文件為400kb，足夠小到能夠放入內(nèi)存，因此可以保存在DBMS緩存區(qū)，先通過稀疏索引找到稠密索引所在的頁地址，再進(jìn)行一次隨機(jī)讀，讀出整個(gè)頁，找到搜索碼對應(yīng)的具體索引項(xiàng)，然后再進(jìn)行第二次隨機(jī)讀，讀出表中記錄，一共只有1次內(nèi)存讀+2次隨機(jī)讀，20ms。僅僅多建立一層稀疏索引，也即是使用二級索引結(jié)構(gòu)，就有7倍的效率提升。在現(xiàn)實(shí)場景中，往往會多次進(jìn)行這種索引結(jié)構(gòu)的建立，也就是多級索引結(jié)構(gòu)。

二級索引結(jié)構(gòu)

4. 代表性索引結(jié)構(gòu)

（1）B+樹索引

B+樹是一種多級索引的實(shí)現(xiàn)，采用平衡樹結(jié)構(gòu)，有非頁節(jié)點(diǎn)、葉節(jié)點(diǎn)兩種節(jié)點(diǎn)組成，每種節(jié)點(diǎn)存放的數(shù)據(jù)有細(xì)微差別：

• 非葉節(jié)點(diǎn)（根節(jié)點(diǎn)也是非葉節(jié)點(diǎn)）：
  節(jié)點(diǎn)最多包含著n-1個(gè)搜索碼值K1…Kn-1，并包含著n個(gè)指針P1…Pn，也就是兩邊是指針，中間是搜索碼值，Pn指針指向小于其Kn搜索碼的下一級索引節(jié)點(diǎn)，Pn+1指向大于等于Kn搜索碼的下一級索引節(jié)點(diǎn)。
  

  根節(jié)點(diǎn)
  
  舉個(gè)栗子：
  
  非葉節(jié)點(diǎn)

• 葉節(jié)點(diǎn)
  葉節(jié)點(diǎn)的P1…Pn-1的指針都指向記錄地址（如果是稠密索引）或者頁地址（如果是稀疏索引），葉節(jié)點(diǎn)的最后一個(gè)指針Pn與非葉節(jié)點(diǎn)不同，它指向的是下一個(gè)同級葉節(jié)點(diǎn)，構(gòu)成橫向有序的索引結(jié)構(gòu)。
  

  葉節(jié)點(diǎn)

一個(gè)完整的三級B+樹如下所示：

三級B+樹

B+樹的葉節(jié)點(diǎn)中的搜索碼值是可以重復(fù)的，當(dāng)這個(gè)B+樹索引是非聚簇稠密索引且搜索碼對應(yīng)的記錄不唯一時(shí)，就需要將一個(gè)搜索碼重復(fù)放置在葉節(jié)點(diǎn)中，指向不同的記錄：

搜索碼重復(fù)

• B+樹維護(hù)成本
  考慮一個(gè)稠密B+樹索引，在刪除記錄時(shí)，由于B+樹要求每個(gè)葉節(jié)點(diǎn)都必須處于半滿狀態(tài)，當(dāng)被刪除索引項(xiàng)所處的節(jié)點(diǎn)不滿足半滿時(shí)，需要向兄弟節(jié)點(diǎn)借搜索碼值，并且在需要時(shí)調(diào)整父節(jié)點(diǎn)，是一個(gè)局部重組B+樹的過程。
  在插入記錄時(shí)，可能出現(xiàn)某個(gè)索引節(jié)點(diǎn)已經(jīng)沒有多余空間存儲，此時(shí)則需要分裂葉節(jié)點(diǎn)，并且上層非葉節(jié)點(diǎn)也可能需要分裂，依次往上遞歸，也是一次重組的過程。

• B+樹的優(yōu)點(diǎn)
  從上面能夠看出，在某些情況下，刪除和插入記錄時(shí)，B+樹的維護(hù)成本比較高，但是為何依舊是最常用的索引結(jié)構(gòu)之一呢，因?yàn)槲覀兺鶗衙總€(gè)節(jié)點(diǎn)的空間設(shè)置得足夠大，一般是一整頁，如果一個(gè)索引項(xiàng)占用100bytes，則對于4kb的頁能夠存儲40個(gè)索引項(xiàng)，即使是100萬條記錄的表，B+樹也只需要log(40)1000000=3層，查詢路徑非常短，因此B+樹實(shí)際上是一種效率非常高的索引結(jié)構(gòu)。

（2）B樹索引

這是一種與B+樹類似的平衡樹索引，區(qū)別在于，B+樹只有葉節(jié)點(diǎn)保存著指向記錄的指針，非葉節(jié)點(diǎn)僅僅是索引著索引的索引，而B樹整棵樹的所有節(jié)點(diǎn)都保存著指向其對應(yīng)記錄的指針，整棵樹才是一個(gè)完整的索引：

B樹索引

（3）散列索引

前面講到的索引結(jié)構(gòu)都需要通過對比搜索碼的大小去查找索引項(xiàng)的位置，復(fù)雜度是對數(shù)級別的，而散列索引將存儲空間分為多個(gè)組，稱為桶(Bucket)，直接通過散列函數(shù)計(jì)算搜索碼的Hash值，通過Hash值確定此搜索碼的索引項(xiàng)在哪個(gè)桶中，讀取桶中的索引項(xiàng)，就可以找到對應(yīng)索引項(xiàng)，復(fù)雜度為O(1)，因此散列索引對于查詢指定搜索碼的效率非常高。
根據(jù)桶的數(shù)量是否固定，散列索引分為靜態(tài)散列與動(dòng)態(tài)散列兩種：

散列索引分類

• 靜態(tài)散列
  靜態(tài)散列非常簡單，桶的個(gè)數(shù)早已確定，比如對于Users表，已確定共有100個(gè)桶，那么對于每條記錄應(yīng)該放置在哪個(gè)桶，即計(jì)算Hash(搜索碼) mod 100，就能確定應(yīng)該放置到哪個(gè)桶。
  我們并不知道每張表最終會有多少記錄，因此預(yù)先分配的桶的容量可能隨著記錄的增加而不夠用，比如預(yù)先分配的桶容量可能是一頁4kb，每個(gè)索引項(xiàng)100bytes只能存儲40個(gè)索引項(xiàng)，當(dāng)有第41條索引項(xiàng)插入時(shí)，就需要開辟溢出桶：
  
  溢出桶
  
  溢出桶是使用鏈表實(shí)現(xiàn)的，主桶保存著下一個(gè)溢出桶的指針，每個(gè)溢出桶依次鏈接。
  于是，靜態(tài)散列有一個(gè)非常明顯的缺陷：當(dāng)數(shù)據(jù)量變得很大時(shí)，可能會大量開辟溢出桶，造成每次查找索引項(xiàng)，可能要進(jìn)行多次隨機(jī)讀，鏈表越長，隨機(jī)讀次數(shù)越多，效率下降。
• 動(dòng)態(tài)散列
  動(dòng)態(tài)散列可以使得桶的個(gè)數(shù)隨著記錄的增加而動(dòng)態(tài)增加，這里介紹比較基礎(chǔ)的可擴(kuò)展散列(Extendable Hashing)：
  首先，我們選擇一個(gè)具有均勻和隨機(jī)特性的散列函數(shù)H，此散列函數(shù)的結(jié)果是N位二進(jìn)制數(shù)，比如N=32，則每個(gè)Hash值為32位的二進(jìn)制數(shù)。
  此記錄的索引項(xiàng)應(yīng)該存儲在哪個(gè)桶中，取二進(jìn)制數(shù)的前 i 位，i 的起始值為1，我們會保存著這個(gè) i 值，我們來看一條記錄是如何放入桶中：
  1. 使用散列函數(shù)H計(jì)算搜索碼X的Hash值，假設(shè)H(X) = 0001…（省略后面的28位，省略號表示在我們的討論中不重要，下同）
  2. 查看 i 值，此時(shí) i = 1，則表示此記錄的索引項(xiàng)應(yīng)該存在 0001…的第1位，也就是0號桶中

  3. 我們維護(hù)著一個(gè)桶地址列表，保存著每個(gè)號碼的桶的指針，在列表中找到0號桶的指針，訪問0號桶，將其放進(jìn)去。下圖中，我們?yōu)槊總€(gè)桶中保存著一個(gè)值K，表示這個(gè)桶是以前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四個(gè)桶，將之前已經(jīng)滿了的1號桶，其中10開頭的記錄放入10號桶，11開頭的記錄放入11號桶，且這兩個(gè)新桶的K值設(shè)置為2，之前的0號桶不動(dòng)，并且00和01都同時(shí)指向0號舊桶，不改變：
  
  僅分裂已經(jīng)滿了的桶
  
  因此可以發(fā)現(xiàn)，我們僅僅分裂已經(jīng)滿了的桶，其他桶不會動(dòng)，并且不同的桶號，可能指向的是同一個(gè)地址，暫時(shí)共用一個(gè)未滿的桶。
  在記錄被刪除時(shí)，如果桶已經(jīng)空了，則會合并桶。
  這就是神奇的動(dòng)態(tài)散列算法。

5. 多碼索引

目前為止我們討論的都是搜索碼為一個(gè)字段的情況，其實(shí)搜索碼可以是多個(gè)字段的組合，比如index(username,age,city)，索引項(xiàng)中按照索引定義次序依次存儲著三個(gè)字段的值，比如(AfterShip,25,ShenZhen)，索引項(xiàng)之間的排序先根據(jù)第一列索引排序，第一列相同的情況下再根據(jù)第二列排序，以此類推。

6. 覆蓋索引（Covering Index）

覆蓋索引不是一種索引分類，而是一種對索引的使用方式。
繼續(xù)考慮上面那張保存著100萬用戶的Users表，我們要查找username為AfterShip的用戶的email，如果我們僅僅為username建立索引，那么我們需要先通過索引查找到username為AfterShip的賬號的記錄指針，再回表讀取此記錄email列的值。但如果我們的索引是為(username,email)建立的復(fù)合索引，那么我們在索引項(xiàng)中就能直接獲取到email值，而不需要回表讀取，減少一次隨機(jī)IO操作。
因此，適當(dāng)?shù)乩酶采w索引，可以減少IO，加快查詢。

參考資料

• 清華大學(xué) 公開課 《操作系統(tǒng)》
• 哈爾濱工業(yè)大學(xué) 公開課《數(shù)據(jù)庫系統(tǒng)》（下）
• 北京工業(yè)大學(xué) 公開課 《高級數(shù)據(jù)庫系統(tǒng)》
• 《數(shù)據(jù)庫系統(tǒng)概念》
• 《數(shù)據(jù)庫索引設(shè)計(jì)與優(yōu)化》