索引
MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數據的數據結構。
我們知道，數據庫查詢是數據庫的最主要功能之一。我們都希望查詢數據的速度能儘可能的快，因此數據庫系統的設計者會從查詢算法的角度進行優化。最基本的查詢算法當然是順序查找（linear search），這種複雜度為O(n)的算法在數據量很大時顯然是糟糕的，好在計算機科學的發展提供了很多更優秀的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會發現，每種查找算法都只能應用於特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用於二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構（例如，理論上不可能同時將兩列都按順序進行組織），所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。
看一個例子：
圖1.png
圖1展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也並不是一定物理相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的複雜度內獲取到相應數據。
雖然這是一個貨真價實的索引，但是實際的數據庫系統幾乎沒有使用二叉查找樹或其進化品種紅黑樹（red-black tree）實現的，原因會在下文介紹。
B-Tree和B+Tree
目前大部分數據庫系統及文件系統都採用B-Tree或其變種B+Tree作為索引結構，在本文的下一節會結合存儲器原理及計算機存取原理討論為什麼B-Tree和B+Tree在被如此廣泛用於索引，這一節先單純從數據結構角度描述它們。
B-Tree
是一種多路搜索樹（並不是二叉的）：
1.定義任意非葉子結點最多隻有M個兒子；且M>2；
2.根結點的兒子數為[2, M]；
3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小於K[1]的
子樹，P[M]指向關鍵字大於K[M-1]的子樹，其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹；
8.所有葉子結點位於同一層；
9.每個k對應一個data。
如：（M=3）相當於一個2–3樹，2–3樹是一個這樣的一棵樹， 它的每個節點要麼有2個孩子和1個數據元素，要麼有3個孩子和2個數據元素，葉子節點沒有孩子，並且有1個或2個數據元素。
B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為空，或已經是葉子結點；B-Tree上查找算法的偽代碼如下：
BTree_Search(node, key) { if(node == null) return null; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i+1]->node); } data = BTree_Search(root, my_key);
- B-樹的特性：
- 1.關鍵字集合分佈在整顆樹中；
- 2.任何一個關鍵字出現且只出現在一個結點中；
- 3.搜索有可能在非葉子結點結束；
- 4.其搜索性能等價於在關鍵字全集內做一次二分查找；
- 5.自動層次控制；
- B-樹的自控制:
- B樹中每一個內部節點會包含一定數量的鍵值。通常，鍵值的數量被選定在d和2d之間。在實際中，鍵值佔用了節點中大部分的空間。因數2將保證節點可以被拆分或組合。如果一個內部節點有2d個鍵值，那麼添加一個鍵值給此節點的過程，將會拆分2d鍵值為2個d鍵值的節點，並把此鍵值添加給父節點。每一個拆分的節點需要最小數目的鍵值。相似地，如果一個內部節點和他的鄰居兩者都有d個鍵值，那麼將通過它與鄰居的合併來刪除一個鍵值。刪除此鍵值將導致此節點擁有d-1個鍵值;與鄰居的合併則加上d個鍵值，再加上從鄰居節點的父節點移來的一個鍵值。結果為完全填充的2d個鍵值。
- B-樹的構造過程：
- 下面是往B樹中依次插入
- 6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
- btreebuild.gif
B+Tree
B-Tree有許多變種，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實現其索引結構。
- 與B-Tree相比，B+Tree有以下不同點：
- 1.非葉子結點的子樹指針與關鍵字個數相同；
- 2.非葉子結點的子樹指針P[i]，指向關鍵字值屬於[K[i], K[i+1])的子樹（B-樹是開區間）；
- 3.為所有葉子結點增加一個鏈指針；
- 4.所有關鍵字都在葉子結點出現；
- 5.內節點不存儲data，只存儲key
- 如：（M=3）
- Paste_Image.png
B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價於在關鍵字全集做一次二分查找；
- B+的特性：
- 1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；
- 2.不可能在非葉子結點命中；
- 3.非葉子結點相當於是葉子結點的索引（稀疏索引），葉子結點相當於是存儲（關鍵字）數據的數據層；
- 4.更適合文件索引系統；
- B+樹的構造過程：
- 下面是往B+樹中依次插入
- 6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
- Bplustreebuild.gif
索引的物理存儲
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對於內存存取，I/O存取的消耗要高几個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進複雜度。換句話說，索引的結構組織要儘量減少查找過程中磁盤I/O的存取次數。
B-tree
Paste_Image.png
假如每個盤塊可以正好存放一個B樹的結點（正好存放2個文件名）。那麼一個BTNODE結點就代表一個盤塊，而子樹指針就是存放另外一個盤塊的地址。
- 下面，咱們來模擬下查找文件29的過程：
- 1.根據根結點指針找到文件目錄的根磁盤塊1，將其中的信息導入內存。【磁盤IO操作 1次】
- 2.此時內存中有兩個文件名17、35和三個存儲其他磁盤頁面地址的數據。根據算法我們發現：17<29<35，因此我們找到指針p2。
- 3.根據p2指針，我們定位到磁盤塊3，並將其中的信息導入內存。【磁盤IO操作 2次】
- 4.此時內存中有兩個文件名26，30和三個存儲其他磁盤頁面地址的數據。根據算法我們發現：26<29<30，因此我們找到指針p2。
- 5.根據p2指針，我們定位到磁盤塊8，並將其中的信息導入內存。【磁盤IO操作 3次】
- 6.此時內存中有兩個文件名28，29。根據算法我們查找到文件名29，並定位了該文件內存的磁盤地址。
- 分析上面的過程，發現需要3次磁盤IO操作和3次內存查找操作。關於內存中的文件名查找，由於是一個有序表結構，可以利用折半查找提高效率。至於IO操作是影響整個B樹查找效率的決定因素。
當然，如果我們使用平衡二叉樹的磁盤存儲結構來進行查找，磁盤4次，最多5次，而且文件越多，B樹比平衡二叉樹所用的磁盤IO操作次數將越少，效率也越高。
B+tree
Paste_Image.png
- B+tree的優點：
- B+-tree的磁盤讀寫代價更低
- ****B+-tree****的內部結點並沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
- 舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而****B+
- ****樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候，B 樹就比****B+ ****樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。
- B+-tree的查詢效率更加穩定
- 由於非終結點並不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。
mysql的兩種存儲引擎的索引存儲機制
MyISAM索引實現
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是數據記錄的地址。下圖是MyISAM索引的原理圖：
Paste_Image.png
這裡設表一共有三列，假設我們以Col1為主鍵，則上圖是一個MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件僅僅保存數據記錄的地址。在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何區別，只是主索引要求key是唯一的，而輔助索引的key可以重複。如果我們在Col2上建立一個輔助索引，則此索引的結構如下圖所示：
Paste_Image.png
同樣也是一顆B+Tree，data域保存數據記錄的地址。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為地址，讀取相應數據記錄。
MyISAM的索引方式也叫做“非聚集”的。
InnoDB索引實現
雖然InnoDB也使用B+Tree作為索引結構，但具體實現方式卻與MyISAM截然不同。
第一個重大區別是InnoDB的數據文件本身就是索引文件。從上文知道，MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引。
Paste_Image.png
上圖是InnoDB主索引（同時也是數據文件）的示意圖，可以看到葉節點包含了完整的數據記錄。這種索引叫做聚集索引。因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形。
第二個與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域。例如，定義在Col3上的一個輔助索引：
Paste_Image.png
這裡以英文字符的ASCII碼作為比較準則。聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
瞭解不同存儲引擎的索引實現方式對於正確使用和優化索引都非常有幫助，例如知道了InnoDB的索引實現後，就很容易明白為什麼不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB數據文件本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時數據文件為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。
鏈接：https://juejin.im/post/5cb7247df265da03af27ccf9
閱讀更多 Java高級互聯網架構 的文章
