1、什么是索引
索引是存儲(chǔ)引擎用于快速找到記錄的一種數(shù)據(jù)結(jié)構(gòu)。
2、索引有哪些數(shù)據(jù)結(jié)構(gòu)
- 順序查找結(jié)構(gòu)：這種查找效率很低，復(fù)雜度為o(n)。大數(shù)據(jù)量的時(shí)候查詢效率很低。
- 有序的數(shù)據(jù)排列：二分查找法又稱折半查找法。
通過一次比較，將查找區(qū)間縮小一半。而mysql中的數(shù)據(jù)并不是有序的序列。
- 二叉查找樹：左子樹的鍵值總是小于根的鍵值，右子樹的鍵值總是大于根的鍵值。通過中序遍歷得到的序列是有序序列，但如果二叉查找樹構(gòu)造的不好則跟順序查找沒什么區(qū)別
- 平衡二叉樹：如果需要二叉查找樹是平衡的，從而引出平衡二叉樹。平衡二叉樹首先得滿足二叉查找樹的定義，其次必須滿足任何結(jié)點(diǎn)的兩個(gè)子樹的高度的最大差為1。顯然上面的樹不是平衡二叉樹，平衡二叉樹示例如下：
平衡二叉查找樹的時(shí)間復(fù)雜度為o(logn)，查詢速度的確很快，但是維護(hù)一顆平衡二叉樹的代價(jià)也是非常大的。通常來說，需要一次或多次左旋和右旋來得到插入或更新后的平衡性。
- b樹：b樹和平衡二叉樹稍有不同的是b樹屬于多叉樹又名平衡多路查找樹：
- 根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)（每個(gè)節(jié)點(diǎn)有m-1個(gè)key， 且以升序排列） 其它節(jié)點(diǎn)至少有m/2個(gè)子節(jié)點(diǎn)
- 葉子結(jié)點(diǎn)都在同一層。
- b+樹
b+樹是b樹的變種，b+樹由b樹和索引順序訪問方法演化而來(在現(xiàn)實(shí)生活中幾乎沒有使用b樹的情況來)。
b+樹是為磁盤或其他直接存儲(chǔ)輔助設(shè)備設(shè)計(jì)的一種平衡查找樹。
在b+樹中所有記錄結(jié)點(diǎn)都是按鍵值的大小順序放在同一層的葉子結(jié)點(diǎn)上， 由各葉子節(jié)點(diǎn)指針進(jìn)行連接。
所有查詢都要查找到葉子節(jié)點(diǎn)，查詢性能穩(wěn)定。
所有葉子節(jié)點(diǎn)形成有序鏈表，便于范圍查詢。每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接（雙向鏈表）
3、innodb為什么使用b+樹做為索引
- 可以有效的利用系統(tǒng)對(duì)磁盤的塊讀取特性，在讀取相同磁盤塊的同時(shí)，盡可能多的加載索引數(shù)據(jù)，來提高索引命中效率，從而達(dá)到減少磁盤io的讀取次數(shù)（局部性原理與磁盤預(yù)讀）。
- b+樹的磁盤讀寫代價(jià)更低：b+樹的內(nèi)部節(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針（只有葉子節(jié)點(diǎn)存儲(chǔ)有），因此其內(nèi)部節(jié)點(diǎn)相對(duì)b樹更小，如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多，一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多，相對(duì)io讀寫次數(shù)就降低了。
- b+樹的查詢效率更穩(wěn)定。由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。
- b+樹支持范圍查詢，而b樹不支持
4、索引分類
從存儲(chǔ)結(jié)構(gòu)上分類：btree索引、hash索引、全文索引
從應(yīng)用上分類：主鍵索引、唯一索引、組合索引
從物理存儲(chǔ)角度：聚集索引和非聚集索引（輔助索引）
下面說說什么是聚集索引，什么是非聚集索引：
- 聚集索引
按照每張表的主鍵構(gòu)建一棵b+樹，同時(shí)葉子節(jié)點(diǎn)中存放的即為整張表的行記錄數(shù)據(jù)。也將聚集索引的葉子節(jié)點(diǎn)稱為數(shù)據(jù)頁，每個(gè)數(shù)據(jù)頁都通過一個(gè)雙向鏈表進(jìn)行鏈接。
聚集索引對(duì)于主鍵的排序查找和范圍查找的數(shù)據(jù)非常快。
- 輔助索引
除了存儲(chǔ)了索引列，還存儲(chǔ)了葉子節(jié)點(diǎn)的指針。
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://www.cnblogs.com/yuanfy008/p/15586155.html
