數據庫索引對于程序開發人員都不陌生。開發系統時，都會使用各種各種的sql語句，最多的就是查詢語句，為了提高系統的響應速度或者從數據庫查詢數據更快，都會尋找查詢比較慢的SQL查詢，分析完原因之后，就會在數據表中加上索引。那什么是索引呢？
簡單說索引就像書的目錄一樣。一本1000頁的書，如果你想快速找到其中的某一個知識點，在不借助目錄的情況下，那我估計你可得找一會兒。同樣，對于數據庫的表而言，索引其實就是它的“目錄”。
索引的出現其實就是為了提高數據查詢的效率。
一：索引的常見模型
索引的出現是為了提高查詢效率，但是實現索引的方式卻有很多種，所以這里也就引入了索引模型的概念。可以用于提高讀寫效率的數據結構很多，這里我先給你介紹三種常見、也比較簡單的數據結構，它們分別是哈希表、有序數組和搜索樹。
哈希表、有序數組和搜索樹這三種模型的區別
哈希表是一種以鍵-值（key-value）存儲數據的結構，我們只要輸入待查找的值即key，就可以找到其對應的值即Value。哈希的思路很簡單，把值放在數組里，用一個哈希函數把key換算成一個確定的位置，然后把value放在數組的這個位置。
不可避免地，多個key值經過哈希函數的換算，會出現同一個值的情況。處理這種情況的一種方法是，拉出一個鏈表。
假設，你現在維護著一個身份證和姓名的表，需要根據身份證號查找對應的名字，這時對應的哈希索引的示意圖如下所示：
哈希表示意圖
圖中，User2和User4根據身份證號算出來的值都是N，但沒關系，后面還跟了一個鏈表。假設，這時候你要查ID_card_n2對應的名字是什么？
- 將ID_card_n2通過哈希函數算出N；
- 按順序遍歷，找到User2。
在看圖中4個ID_card_n的值并不是遞增的，為什么要這樣做呢？
好處：增加新的User時速度會很快，只需要往后追加。
缺點：因為不是有序的，所以哈希索引做區間查詢的速度是很慢的。
如果你要區間查詢，例如找身份證號在[ID_card_X,ID_card_Y]這個區間的所有用戶，就必須全部掃描一遍了。
所以，哈希表這種結構適用于只有等值查詢的場景，比如redis及其他一些NoSQL引擎。
而有序數組在等值查詢和范圍查詢場景中的性能就都非常優秀。還是上面這個根據身份證號查名字的例子，如果我們使用有序數組來實現的話，示意圖如下所示：
有序數組示意圖
我們假設身份證號沒有重復，這個數組就是按照身份證號遞增的順序保存的。這時候如果你要查ID_card_n2對應的名字，用二分法查找算法可以快速定位，這個時間復雜度是O(log(N))。
并且這個索引結構還支持范圍查詢。你要查身份證號在[ID_card_X, ID_card_Y]區間的User，可以先用二分法查找算法找到ID_card_X（如果不存在ID_card_X，就找到大于ID_card_X的第一個User），然后向右遍歷，直到查到第一個大于ID_card_Y的身份證號，退出循環。
如果僅僅看查詢效率，有序數組就是最好的數據結構了。但是在更新數據的時候就麻煩了，你往中間插入一個記錄就必須得挪動后面所有的記錄，成本太高。
所以，有序數組索引只適用于靜態存儲引擎，比如你要保存的是2018年某個城市的所有人口信息，這類不會再修改的數據。
二叉搜索樹也是最經典數據結構了，還是上面根據身份證號查名字的例子，如果我們用二叉搜索樹來實現的話，示意圖如下所示：
二叉搜索樹示意圖
二叉搜索樹的特點：每個節點的左兒子小于父節點，父節點又小于右兒子。這樣如果你要查ID_card_n2的話，按照圖中的搜索順序就是按照UserA -> UserC -> UserF -> User2這個路徑得到。這個時間復雜度是O(log(N))。
二叉樹搜索算法
當然為了維持O(log(N))的查詢復雜度，你就需要保持這棵樹是平衡二叉樹。為了做這個保證，更新的時間復雜度也是O(log(N))。
樹可以有二叉，也可以有多叉。多叉樹就是每個節點有多個兒子，兒子之間的大小保證從左到右遞增。二叉樹是搜索效率最高的，但是實際上大多數的數據庫存儲卻并不使用二叉樹。其原因是，索引不止存在內存中，還要寫到磁盤上。
你可以想象一下一棵100萬節點的平衡二叉樹，樹高20。一次查詢可能需要訪問20個數據塊。在機械硬盤時代，從磁盤隨機讀一個數據塊需要10 ms左右的尋址時間。也就是說，對于一個100萬行的表，如果使用二叉樹來存儲，單獨訪問一個行可能需要20個10 ms的時間，這個查詢可真夠慢的。
為了讓查詢過程盡量少的讀磁盤，就必須讓查詢過程訪問盡量少的數據塊。那么，我們就不應該使用二叉樹，而是要使用“N叉”樹。這里，“N叉”樹中的“N”取決于數據塊的大小。
以InnoDB的一個整數字段索引為例，這個N差不多是1200。這棵樹高是4的時候，就可以存1200的3次方個值，這已經17億了。考慮到樹根的數據塊總是在內存中的，一個10億行的表上一個整數字段的索引，查找一個值最多只需要訪問3次磁盤。其實，樹的第二層也有很大概率在內存中，那么平均訪問磁盤的次數就更少了。
N叉樹由于在讀寫上的性能優點，以及適配磁盤的訪問模式，已經被廣泛應用在數據庫引擎中了。
不管是哈希還是有序數組，或者N叉樹，它們都是不斷迭代、不斷優化的產物或者解決方案。數據庫技術發展到今天，跳表、LSM樹等數據結構也被用于引擎設計中，這里我就不再一一展開了。
你心里要有個概念，數據庫底層存儲的核心就是基于這些數據模型的。每碰到一個新數據庫，我們需要先關注它的數據模型，這樣才能從理論上分析出這個數據庫的適用場景。
截止到這里，我用了半篇文章的篇幅和你介紹了不同的數據結構，以及它們的適用場景，你可能會覺得有些枯燥。但是，我建議你還是要多花一些時間來理解這部分內容，畢竟這是數據庫處理數據的核心概念之一，在分析問題的時候會經常用到。當你理解了索引的模型后，就會發現在分析問題的時候會有一個更清晰的視角，體會到引擎設計的精妙之處。
MySQL中，索引是在存儲引擎層實現的，索引分為主鍵索引(key)、全文索引(FULLTEXT)、普通索引(NORMAL)、空間索引(SPATIAL)、唯一索引(UNIQUE)，具體詳解在下一篇介紹。
