1、什么是索引

索引是存儲引擎用于快速找到記錄的一種數據結構。

2、索引有哪些數據結構

• 順序查找結構：這種查找效率很低，復雜度為o(n)。大數據量的時候查詢效率很低。
• 有序的數據排列：二分查找法又稱折半查找法。

通過一次比較，將查找區間縮小一半。而mysql中的數據并不是有序的序列。

• 二叉查找樹：左子樹的鍵值總是小于根的鍵值，右子樹的鍵值總是大于根的鍵值。通過中序遍歷得到的序列是有序序列，但如果二叉查找樹構造的不好則跟順序查找沒什么區別

• 平衡二叉樹：如果需要二叉查找樹是平衡的，從而引出平衡二叉樹。平衡二叉樹首先得滿足二叉查找樹的定義，其次必須滿足任何結點的兩個子樹的高度的最大差為1。顯然上面的樹不是平衡二叉樹，平衡二叉樹示例如下：

平衡二叉查找樹的時間復雜度為o(logn)，查詢速度的確很快，但是維護一顆平衡二叉樹的代價也是非常大的。通常來說，需要一次或多次左旋和右旋來得到插入或更新后的平衡性。

• b樹：b樹和平衡二叉樹稍有不同的是b樹屬于多叉樹又名平衡多路查找樹：

1. 根節點至少有兩個子節點（每個節點有m-1個key， 且以升序排列） 其它節點至少有m/2個子節點
2. 葉子結點都在同一層。

• b+樹

b+樹是b樹的變種，b+樹由b樹和索引順序訪問方法演化而來(在現實生活中幾乎沒有使用b樹的情況來)。
b+樹是為磁盤或其他直接存儲輔助設備設計的一種平衡查找樹。
在b+樹中所有記錄結點都是按鍵值的大小順序放在同一層的葉子結點上， 由各葉子節點指針進行連接。
所有查詢都要查找到葉子節點，查詢性能穩定。
所有葉子節點形成有序鏈表，便于范圍查詢。每個葉子結點都存有相鄰葉子結點的指針，葉子結點本身依關鍵字的大小自小而大順序鏈接（雙向鏈表）

3、innodb為什么使用b+樹做為索引

1. 可以有效的利用系統對磁盤的塊讀取特性，在讀取相同磁盤塊的同時，盡可能多的加載索引數據，來提高索引命中效率，從而達到減少磁盤io的讀取次數（局部性原理與磁盤預讀）。
2. b+樹的磁盤讀寫代價更低：b+樹的內部節點并沒有指向關鍵字具體信息的指針（只有葉子節點存儲有），因此其內部節點相對b樹更小，如果把所有同一內部節點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多，一次性讀入內存的需要查找的關鍵字也就越多，相對io讀寫次數就降低了。
3. b+樹的查詢效率更穩定。由于非終結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。
4. b+樹支持范圍查詢，而b樹不支持

4、索引分類

從存儲結構上分類：btree索引、hash索引、全文索引

從應用上分類：主鍵索引、唯一索引、組合索引

從物理存儲角度：聚集索引和非聚集索引（輔助索引）

下面說說什么是聚集索引，什么是非聚集索引：

• 聚集索引

按照每張表的主鍵構建一棵b+樹，同時葉子節點中存放的即為整張表的行記錄數據。也將聚集索引的葉子節點稱為數據頁，每個數據頁都通過一個雙向鏈表進行鏈接。

聚集索引對于主鍵的排序查找和范圍查找的數據非常快。

• 輔助索引

除了存儲了索引列，還存儲了葉子節點的指針。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。

原文鏈接：https://www.cnblogs.com/yuanfy008/p/15586155.html