一、什么是索引

1、索引初體驗(yàn)

user_innodb這張表里有4個(gè)字段，id，name，gender，phone。
當(dāng)這張表有500萬條數(shù)據(jù)，在沒有索引的name字段上執(zhí)行一條where查詢：

select * from user_innodb where name = '張三';

如果name字段上有索引呢？我們?cè)趎ame字段上面創(chuàng)建一個(gè)索引，再來執(zhí)行一下查詢：

-- name字段創(chuàng)建索引
ALTER TABLE user_innodb DROP INDEX idx_user_name;
ALTER TABLE user_innodb ADD INDEX idx_user_name (name);

我們?cè)賮韴?zhí)行一下select語句。
我們會(huì)發(fā)現(xiàn)，有索引的查詢和沒有索引的查詢相比，效率竟相差幾十倍。

索引到底是什么呢？為什么可以對(duì)我們的查詢產(chǎn)生這么大的影響？創(chuàng)建索引的時(shí)候做了什么事情？

2、索引圖解

維基百科上對(duì)數(shù)據(jù)庫索引的定義：

數(shù)據(jù)庫索引，是數(shù)據(jù)庫管理系統(tǒng)（DBMS）中一個(gè)排序的數(shù)據(jù)結(jié)構(gòu)，以協(xié)助快速查詢、更新數(shù)據(jù)庫表中數(shù)據(jù)。

數(shù)據(jù)是以文件的形式存放在磁盤上面的，每一行數(shù)據(jù)都有它的磁盤地址。如果沒有索引的花，我們要從500萬行數(shù)據(jù)里面檢索一條數(shù)據(jù)，只能依次遍歷這張表的全部數(shù)據(jù)，直到找到這條數(shù)據(jù)。

但是我們有了索引之后，只需要在索引里面去檢索這條數(shù)據(jù)就行了，因?yàn)樗且环N特殊的專門用來快速檢索的數(shù)據(jù)結(jié)構(gòu)，我們找到數(shù)據(jù)存放的磁盤地址以后，就可以拿到數(shù)據(jù)了。

索引就像是一本書的目錄一樣，目錄可能只有幾頁的內(nèi)容，根據(jù)拼音或者偏旁有序進(jìn)行排序的，我們可以通過目錄很快的定位到書中具體的內(nèi)容。同樣的，我們可以根據(jù)索引也可以很快的定位到這一條數(shù)據(jù)。

3、索引類型

從navicat中我們可以看到，索引包含索引名稱、索引字段、索引類型總共有三種、索引方法有兩種、注釋。

在InnoDB中，索引類型有三種：

• Normal 普通索引：也叫非唯一索引，是最普通的索引，沒有任何的限制。
• Full Text 全文索引：針對(duì)比較大的數(shù)據(jù)，比如我們存放的是消息內(nèi)容、一篇文章，有幾kb的數(shù)據(jù)的這種情況，如果要解決like查詢?cè)谌钠ヅ涞臅r(shí)候效率低的問題，可以創(chuàng)建全文索引。只有文本類型的字段才可以創(chuàng)建全文索引，比如char、varchar、text。
• Unique 唯一索引：唯一索引要求鍵值不能重復(fù)。另外需要注意的是，主鍵索引是一種特殊的唯一索引，它還多了一個(gè)限制條件，要求鍵值不能為空。主鍵索引用primay key創(chuàng)建。

注！SPATIAL 空間索引：空間索引是對(duì)空間數(shù)據(jù)類型的字段建立的索引，MYSQL中的空間數(shù)據(jù)類型有4種，分別是GEOMETRY、POINT、LINESTRING、POLYGON。MYSQL使用SPATIAL關(guān)鍵字進(jìn)行擴(kuò)展，使得能夠用于創(chuàng)建正規(guī)索引類型的語法創(chuàng)建空間索引。創(chuàng)建空間索引的列，必須將其聲明為NOT NULL，空間索引只能在存儲(chǔ)引擎為MYISAM的表中創(chuàng)建。

二、索引存儲(chǔ)模型推演

1、二分查找

算法-查找算法-線性表的查找（類C語言版）

二分查找的思想，也叫折半查找，每次都把候選數(shù)據(jù)縮小了一半。如果數(shù)據(jù)已經(jīng)排過序的話，這種方式效率比較高。

所以首先，我們可以考慮使用有序數(shù)組作為索引的數(shù)據(jù)結(jié)構(gòu)。有序數(shù)組的等值查詢和比較查詢效率非常高，但是更新數(shù)據(jù)的時(shí)候會(huì)出現(xiàn)一個(gè)問題，可能要挪動(dòng)大量的數(shù)據(jù)（改變index），所以只適合存儲(chǔ)靜態(tài)的數(shù)據(jù)。

為了支持頻繁的修改，比如插入數(shù)據(jù)，我們需要采用鏈表，但是鏈表的話，如果是單鏈表，它的查找效率還是不夠高。

所以，有沒有可以使用二分查找的鏈表呢？為了解決這個(gè)問題，BST（Binary Search Tree）也就是我們所說的二叉查找樹就誕生了。

2、二叉查找樹（BST Binary Search Tree）

算法-查找算法-樹表的查找（二叉排序樹、平衡二叉樹）（類C語言版）

二叉查找樹的 特點(diǎn)是什么？左子樹所有的節(jié)點(diǎn)都小于父節(jié)點(diǎn)，右子樹所有的節(jié)點(diǎn)都大于父節(jié)點(diǎn)。投影到平面以后，就是一個(gè)有序的線性表。

二叉查找樹既能夠?qū)崿F(xiàn)快速查找，又能夠?qū)崿F(xiàn)快速插入。

但是二叉查找樹有一個(gè)問題：就是它的查找耗時(shí)是和這棵樹的深度相關(guān)的，在最壞的情況下時(shí)間復(fù)雜度會(huì)退化成O(n)。

什么情況是最壞的情況呢？
還是剛才這一批數(shù)字，如果我們插入的數(shù)據(jù)剛好是有序的，它會(huì)變成鏈表（我們把這種樹叫做“斜樹”），這種情況下不能達(dá)到加快檢索速度的目的，和順序查找效率是沒有區(qū)別的。

造成它傾斜的原因是什么呢？
因?yàn)樽笥易訕渖疃炔钐?，這棵樹的左子樹根本沒有節(jié)點(diǎn)——也就是它不夠平衡。
所以，我們有沒有左右子樹深度相差不是那么大，更加平衡的樹呢？

這個(gè)就是平衡二叉樹，叫做Balanced binary search trees，或者AVL樹（AVL是發(fā)明這個(gè)數(shù)據(jù)結(jié)構(gòu)的兩位作者的名字簡(jiǎn)寫：G.M.Adelson-Velsky和E.M.Landis）。

3、平衡二叉樹（AVL Tree）（左旋、右旋）

算法-查找算法-樹表的查找（二叉排序樹、平衡二叉樹）（類C語言版）

AVL Trees（Balanced binary search trees） 平衡二叉樹的定義：左右子樹深度差絕對(duì)值不能超過1。

比如左子樹的深度是2，右子樹的深度只能是1、2、3，這個(gè)時(shí)候我們?cè)侔错樞虿迦霐?shù)據(jù)，不會(huì)變成一棵“斜樹”。

那它的平衡是怎么做到的呢？怎么保證左右子樹的深度差不能超過1呢？

（1）平衡二叉樹的調(diào)整

舉個(gè)例子，我們依次插入1、2、3，我們注意看，當(dāng)我們插入了1、2之后，如果按照二叉查找樹的定義，3肯定是要在2的右邊的，這個(gè)時(shí)候根節(jié)點(diǎn)1的右節(jié)點(diǎn)深度會(huì)變成2，但是左節(jié)點(diǎn)的深度是0，因?yàn)樗鼪]有子節(jié)點(diǎn)，所以就會(huì)違反平衡二叉樹的定義。

應(yīng)該怎么辦呢？因?yàn)樗怯夜?jié)點(diǎn)下面接一個(gè)右節(jié)點(diǎn)，屬于“右-右”型，所以這個(gè)時(shí)候我們要把2提上去，這個(gè)操作叫做左旋。

同樣的，如果我們插入7、6、5，這個(gè)時(shí)候就會(huì)變成左左型，就會(huì)發(fā)生右旋操作，把6提上去。

所以，為了保持平衡，AVL樹在插入和更新數(shù)據(jù)的時(shí)候執(zhí)行了一系列的計(jì)算和調(diào)整的操作。

平衡的問題我們解決了，那么平衡二叉樹作為索引怎么查詢數(shù)據(jù)？

（2）平衡二叉樹的索引

在平衡二叉樹中，一個(gè)節(jié)點(diǎn)，它的大小是一個(gè)固定的單位，作為索引應(yīng)該存儲(chǔ)建立索引的字段的值，叫做鍵值，比如id的值。還要存完整記錄在磁盤上的地址。由于AVL樹是二叉樹，所以還要額外地存儲(chǔ)左右子樹的指針。

如圖所示，
第一個(gè)是索引的鍵值。比如我們?cè)趇d上面創(chuàng)建了一個(gè)索引，我在用where id = 1的條件查詢的時(shí)候就會(huì)找到索引里面的id的這個(gè)鍵值。
第二個(gè)是數(shù)據(jù)的磁盤地址，因?yàn)樗饕淖饔镁褪侨ゲ檎覕?shù)據(jù)的存放的地址。
第三個(gè)，因?yàn)槭嵌鏄?，它必須還要有左子結(jié)點(diǎn)和右子節(jié)點(diǎn)的引用，這樣我們才能找到下一個(gè)結(jié)點(diǎn)。比如大于26的時(shí)候，走右邊，到下一個(gè)樹的節(jié)點(diǎn)，繼續(xù)判斷。

如果是這樣存儲(chǔ)數(shù)據(jù)的話，會(huì)有什么問題呢？

（3）AVL樹用于存儲(chǔ)索引數(shù)據(jù)

首先，索引的數(shù)據(jù)，是放在硬盤上的。查看數(shù)據(jù)和索引的大?。?/p>

select
concat(round(sum(data_length/1024/1024),2),'MB') AS data_len,
concat(round(sum(index_length/1024/1024),2),'MB') AS index_len
from information_schema.TABLES
where table_schema='ourea' and table_name='sys_member';

當(dāng)我們用樹的結(jié)構(gòu)來存儲(chǔ)索引的時(shí)候，訪問一個(gè)節(jié)點(diǎn)就要跟磁盤之間發(fā)生一次IO操作。InnoDB操作磁盤的最小的單位是一頁（或者叫一個(gè)磁盤塊），大小事16KB（16384字節(jié)）。

那么，一個(gè)樹的節(jié)點(diǎn)必須設(shè)計(jì)成16K大小，不然就會(huì)出現(xiàn)讀不完或者讀不夠的情況。如果我們一個(gè)字節(jié)只存一個(gè)鍵值+數(shù)據(jù)+引用，例如整形的字段，可能只用了十幾個(gè)或者幾十個(gè)字節(jié)，它遠(yuǎn)遠(yuǎn)達(dá)不到16K的容量。

想象一下，我們基于索引查找數(shù)據(jù)的時(shí)候，肯定是希望一次從磁盤加載很多的數(shù)據(jù)到內(nèi)存中進(jìn)行比較，這樣就可以盡快拿到完整的數(shù)據(jù)，如果一個(gè)節(jié)點(diǎn)只存1個(gè)這樣的單元，就需要讀更多的節(jié)點(diǎn)，發(fā)生 更多的IO操作。

如果是機(jī)械硬盤時(shí)代，每次從磁盤讀取數(shù)據(jù)需要10ms左右的尋址時(shí)間，交互次數(shù)越多，消耗的時(shí)間就越多。

比如上面的圖，一張表里面有6條數(shù)據(jù)，當(dāng)我們查詢id=66的時(shí)候，要查詢兩個(gè)子節(jié)點(diǎn)，需要跟磁盤交互3次，如果我們有幾百萬數(shù)據(jù)呢？這個(gè)時(shí)間更加難以估計(jì)。

怎么解決？一就是讓每個(gè)節(jié)點(diǎn)存儲(chǔ)更多的數(shù)據(jù)。二就是節(jié)點(diǎn)上的關(guān)鍵字?jǐn)?shù)量越多，我們的指針數(shù)也越多，也就意味著可以有更多的分叉（我們把它叫做“路數(shù)”）。

因?yàn)榉植嬖蕉啵瑯涞?code>深度就會(huì)減少（根節(jié)點(diǎn)是0）。

這樣，我們的數(shù)就從原來的高瘦的樣子，變成了矮胖的樣子。這時(shí)，我們的樹就不再是二叉了，而是多叉，或者叫做多路。

4、多路平衡查找樹（B Tree） （分裂、合并）

算法-B-樹、B樹、B+樹詳解

Balanced Tree就是我們說的多路平衡查找樹，叫做B Tree（B代表平衡）。

跟AVL（平衡二叉樹）一樣，B樹在枝節(jié)點(diǎn)和葉子結(jié)點(diǎn)存儲(chǔ)鍵值、數(shù)據(jù)地址、節(jié)點(diǎn)引用。

它有一個(gè)特點(diǎn)：分叉數(shù)（路數(shù)）永遠(yuǎn)比關(guān)鍵字?jǐn)?shù)多1。 比如我們畫的這棵樹，每個(gè)節(jié)點(diǎn)存儲(chǔ)兩個(gè)關(guān)鍵字，那么就會(huì)有三個(gè)指針指向三個(gè)子節(jié)點(diǎn)（當(dāng)然肯定不只存3個(gè)這么少）。

（1）查找實(shí)例

B Tree的查找規(guī)則是什么樣的呢？

比如我們要在這張表里面查找15，因?yàn)?5小于17走左邊；15大于12走右邊。在磁盤塊7里面就找到了15，只用了3次IO。

（2）B Tree保持平衡的秘訣

這確實(shí)比AVL（平衡二叉樹）效率更高，那B Tree是怎么實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)關(guān)鍵字，還能保持平衡的呢？跟AVL樹有什么區(qū)別？

比如Max Degree（路數(shù)）是3的時(shí)候，我們插入數(shù)據(jù)1、2、3，在插入3的時(shí)候，本來應(yīng)該在第一個(gè)磁盤塊，但是如果一個(gè)節(jié)點(diǎn)有三個(gè)關(guān)鍵字的時(shí)候，意味著有4個(gè)指針，子節(jié)點(diǎn)會(huì)變成4路，所以這個(gè)時(shí)候必須進(jìn)行分裂。把中間的數(shù)據(jù)2提上去，把1和3變成2的子節(jié)點(diǎn)。

如果刪除節(jié)點(diǎn)，會(huì)有相反的合并的操作。

注意這里是分裂和合并，跟AVL樹的左旋和右旋是不一樣的。

我們繼續(xù)插入4和5，B Tree又會(huì)出現(xiàn)分裂和合并的操作。

從這個(gè)里面我們也能看到，在更新索引的時(shí)候會(huì)有大量的索引的結(jié)構(gòu)的調(diào)整，所以解釋了為什么我們不要在頻繁更新的列上建索引，或者為什么不要更新主鍵。

節(jié)點(diǎn)和分裂和合并，其實(shí)就是InnoDB頁的分裂和合并。

如果索引鍵值有序，寫滿一頁接著開辟一個(gè)新的頁：

如果索引鍵值無序，存儲(chǔ)過程造成大量磁盤碎片，帶來頻繁的page分裂和合并：

5、B+樹（加強(qiáng)版多路平衡查找樹）

算法-B-樹、B樹、B+樹詳解

B Tree的效率已經(jīng)很高了，為什么MySQL還要對(duì)B Tree進(jìn)行改良，最終使用了B+Tree呢？

總體上來說，這個(gè)B樹的改良版本解決的問題比B Tree更全面。我們來看一下InnoDB里面的B+樹的存儲(chǔ)結(jié)構(gòu)：

MySQL中的B+Tree有幾個(gè)特點(diǎn)：
1、它的關(guān)鍵字的數(shù)量是跟路數(shù)相等的；

2、B+Tree的根節(jié)點(diǎn)和枝節(jié)點(diǎn)中都不會(huì)存儲(chǔ)數(shù)據(jù)，只有葉子結(jié)點(diǎn)才存儲(chǔ)數(shù)據(jù)。
搜索到關(guān)鍵字不會(huì)直接返回，會(huì)到最后一層的葉子節(jié)點(diǎn)。比如我們搜索id = 28，雖然在第一層直接命中了，但是全部的數(shù)據(jù)在葉子節(jié)點(diǎn)上面，所以我還要繼續(xù)往下搜索，一直到葉子節(jié)點(diǎn)。

3、B+Tree的每個(gè)葉子節(jié)點(diǎn)增加了一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，它的最后一個(gè)數(shù)據(jù)會(huì)指向下一個(gè)葉子節(jié)點(diǎn)的第一個(gè)數(shù)據(jù)，形成了一個(gè)有序鏈表的結(jié)構(gòu)。

（1）B+Tree搜索過程

1、比如我們要查找28，在根節(jié)點(diǎn)就找到了鍵值，但是因?yàn)樗皇侨~子結(jié)點(diǎn)，所以會(huì)繼續(xù)往下搜尋，28是[28,66)的左閉右開的區(qū)間的臨界值，所以會(huì)走中間的子節(jié)點(diǎn)，然后繼續(xù)搜索，它又是[28,34)的左閉右開區(qū)間的臨界值，所以會(huì)走左邊的子節(jié)點(diǎn)，最后在葉子節(jié)點(diǎn)上找到了需要的數(shù)據(jù)。

2、第二個(gè)，如果是范圍查詢，比如要查詢從22到60的數(shù)據(jù)，當(dāng)找到22之后，只需要順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有的數(shù)據(jù)節(jié)點(diǎn)，這樣就極大地提高了區(qū)間查詢效率（不需要返回上層父節(jié)點(diǎn)重復(fù)遍歷查找）。

（2）B+Tree帶來的優(yōu)勢(shì)

1、它是B Tree的變種，B Tree能解決的問題，它都能解決。B Tree解決的兩大問題，就是每個(gè)節(jié)點(diǎn)存儲(chǔ)更多的關(guān)鍵字、路數(shù)更多。
2、掃庫、掃表能力更強(qiáng)（如果我們要對(duì)表進(jìn)行全表掃描，只需要遍歷葉子節(jié)點(diǎn)就可以了，不需要遍歷整棵B+Tree拿到所有的數(shù)據(jù)）。
3、B+Tree的磁盤讀寫能力相對(duì)于B Tree來說更強(qiáng)（根節(jié)點(diǎn)和枝節(jié)點(diǎn)不保存數(shù)據(jù)，所以一個(gè)節(jié)點(diǎn)可以保存更多的關(guān)鍵字，一次磁盤加載的關(guān)鍵字更多）。
4、排序能力更強(qiáng)（因?yàn)槿~子節(jié)點(diǎn)上有下一個(gè)數(shù)據(jù)區(qū)的指針，數(shù)據(jù)形成了鏈表）。
5、效率更加穩(wěn)定（B+Tree永遠(yuǎn)是在葉子結(jié)點(diǎn)拿數(shù)據(jù)，所以IO次數(shù)是最穩(wěn)定的）。

舉個(gè)例子：假設(shè)一條記是16bytes，一個(gè)葉子結(jié)點(diǎn)（一頁）可以存儲(chǔ)10條記錄。非葉子結(jié)點(diǎn)可以存儲(chǔ)多少個(gè)指針？
假設(shè)索引字段+指針大小為16字節(jié)。非葉子結(jié)點(diǎn)（一頁）可以存儲(chǔ)1000個(gè)這樣的單元（鍵值+指針），代表有1000個(gè)指針。
樹深度為2的時(shí)候，有1000²個(gè)葉子節(jié)點(diǎn)，可以存儲(chǔ)的數(shù)據(jù)位1000W（千萬級(jí)別）。

在查找數(shù)據(jù)時(shí)，一次頁的查找代表一次IO，也就是說，一張千萬級(jí)別的表，查詢數(shù)據(jù)最多需要訪問3次磁盤。

樹的深度是怎么來的？根據(jù)你的鍵值類型和數(shù)據(jù)量計(jì)算出來的。字段值越大、數(shù)據(jù)量越大，深度越大。

所以在InnoDB中B+樹深度一般為1-3層，它就能滿足千萬級(jí)的數(shù)據(jù)存儲(chǔ)。

因?yàn)锽 Tree和B+Tree的特性，它們廣泛地用在文件系統(tǒng)和數(shù)據(jù)庫中，例如windows的HPFS文件系統(tǒng)，Oracle、MySQL、SQLServer數(shù)據(jù)庫。

6、為什么不用紅黑樹？

紅黑樹也是BST樹，但是不是嚴(yán)格平衡的，通過變色和旋轉(zhuǎn)來保持平衡。

必須滿足5個(gè)約束：
1、節(jié)點(diǎn)分為紅色或者黑色；2、根節(jié)點(diǎn)必須是黑色的；3、葉子節(jié)點(diǎn)都是黑色的NULL節(jié)點(diǎn)；4、紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色（不允許兩個(gè)相鄰的紅色節(jié)點(diǎn)）；5、從任意節(jié)點(diǎn)觸發(fā)，到其每個(gè)葉子節(jié)點(diǎn)的路徑中包含相同數(shù)量的黑色節(jié)點(diǎn)。

插入60、56、68、45、64、58、72、43、49

基于以上規(guī)則，可以推導(dǎo)出：從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑（紅黑相間的路徑）不大于最短路徑（全部是黑色節(jié)點(diǎn)）的2倍。

為什么不用紅黑樹？1、只有兩路；2、不夠平衡。

紅黑樹一般只放在內(nèi)存里面用。例如Java的TreeMap，它可以用來實(shí)現(xiàn)一致性哈希。

6、hash索引

算法-hash散列表查找詳解

在navicat工具中，創(chuàng)建索引，索引方式還有一種是HASH索引，以KV的形式檢索數(shù)據(jù)，也就是說，它會(huì)根據(jù)索引字段生成哈希碼和指針，指針指向數(shù)據(jù)。

（1）哈希索引的特點(diǎn)

1、它的事件復(fù)雜度是O(1)，查詢速度比較快。因?yàn)楣Ｋ饕锩娴臄?shù)據(jù)不是按順序存儲(chǔ)的，所以不能用于排序。
2、我們?cè)诓樵償?shù)據(jù)的時(shí)候要根據(jù)鍵值計(jì)算哈希碼，所以它只能支持等值查詢（= IN），不支持范圍查詢（> < >= <= between and）。
3、如果字段重復(fù)值很多的時(shí)候，會(huì)出現(xiàn)大量的哈希沖突（采用拉鏈法解決），效率會(huì)降低。

（2）注意

在InnoDB中，不能顯式地創(chuàng)建一個(gè)哈希索引（所謂的支持哈希索引指的是AHI，自適應(yīng)哈希，它是InnoDB自動(dòng)為buffer pool中的熱點(diǎn)頁創(chuàng)建的索引）。

memory存儲(chǔ)引擎可以使用Hash索引。

三、B+Tree的落地實(shí)現(xiàn)

1、認(rèn)識(shí)MySQL數(shù)據(jù)存儲(chǔ)文件

首先，MySQL的數(shù)據(jù)都是文件的形式存放在磁盤中的，我們可以找到這個(gè)數(shù)據(jù)目錄的地址。在MySQL中有這么一個(gè)參數(shù)，我們來看一下：

show variables like 'datadir';

每個(gè)數(shù)據(jù)庫有一個(gè)目錄，我們新建了一個(gè)叫做test的數(shù)據(jù)庫，那么這里就有一個(gè)test的文件夾。

數(shù)據(jù)庫里面的幾張表，進(jìn)入test目錄之后，發(fā)現(xiàn)這里面有一些跟我們創(chuàng)建的表名對(duì)應(yīng)的文件。

在這里我們能看到，每張InnoDB的表有兩個(gè)文件（.frm和.ibd），MyISAM的表有三個(gè)文件（.frm、.MYD、.MYI）。

有一個(gè)是相同的文件.frm。.frm是MySQL里面表結(jié)構(gòu)定義的文件，不管你建表的時(shí)候選用任何一個(gè)存儲(chǔ)引擎都會(huì)生成。

主要是其他兩個(gè)文件，實(shí)現(xiàn)了MySQL不同存儲(chǔ)引擎的索引。

2、MyISAM

在MyISAM里面，有另外兩個(gè)文件：

一個(gè)是.MYD文件，D代表Data，是MyISAM的數(shù)據(jù)文件，存放數(shù)據(jù)記錄，比如我們的user_myisam表的所有的表數(shù)據(jù)。

一個(gè)是.MYI文件，I代表Index，是MyISAM的索引文件，存放索引，比如我們?cè)趇d字段上面創(chuàng)建了一個(gè)主鍵索引，那么主鍵索引就是在這個(gè)索引文件里面。一個(gè)索引就會(huì)有一棵B+Tree，所有的B+Tree都在這個(gè)myi文件里面。

也就是說，在MyISAM里面，索引和數(shù)據(jù)是兩個(gè)獨(dú)立的文件。

（1）MyISAM索引機(jī)制

MyISAM的B+Tree里面，葉子節(jié)點(diǎn)存儲(chǔ)的事數(shù)據(jù)文件對(duì)應(yīng)的磁盤地址。所以從索引文件.MYI中找到鍵值后，會(huì)到數(shù)據(jù)文件.MYD中獲取相應(yīng)的數(shù)據(jù)記錄。

除了主鍵索引，在MyISAM中，其他索引也在這個(gè).MYI文件里面。

-- name字段創(chuàng)建索引
ALTER TABLE user_innodb DROP INDEX idx_user_name;
ALTER TABLE user_innodb ADD INDEX idx_user_name (name);

非主鍵索引跟主鍵索引存儲(chǔ)和檢索數(shù)據(jù)的方式是沒有任何區(qū)別的，一樣是在索引文件里面找到磁盤地址，然后到數(shù)據(jù)文件里面獲取數(shù)據(jù)。

3、InnoDB

與MyISAM不同，在InnoDB的某個(gè)索引的葉子節(jié)點(diǎn)上，它直接存儲(chǔ)了我們的數(shù)據(jù)。
所以，為什么說在InnoDB中索引即數(shù)據(jù)，數(shù)據(jù)即索引，就是這個(gè)原因。

但是會(huì)有一個(gè)問題，一張InnoDB的表可能有很多個(gè)索引，數(shù)據(jù)肯定是只有一份的，那數(shù)據(jù)在哪個(gè)索引的葉子節(jié)點(diǎn)上呢？

（1）聚集索引（聚簇索引）

InnoDB引入了聚集索引（聚簇索引）的概念。索引鍵值的邏輯順序跟表數(shù)據(jù)行的物理存儲(chǔ)順序是一致的。

InnoDB組織數(shù)據(jù)的方式就是（聚集）索引組織表（clustered index organize table）。如果說一張表創(chuàng)建了主鍵索引，那么這個(gè)主鍵索引就是聚集索引，決定數(shù)據(jù)行的物理存儲(chǔ)順序。

（比如字典的目錄是按拼音排序的，內(nèi)容也是按拼音排序的，按拼音排序的這種目錄就叫聚集索引）

那么問題來了，主鍵索引之外的索引，會(huì)不會(huì)也把完整記錄在葉子節(jié)點(diǎn)放一份呢？答案是并不會(huì)，因?yàn)檫@會(huì)帶來額外的存儲(chǔ)空間浪費(fèi)和計(jì)算消耗。

它們的葉子結(jié)點(diǎn)上沒有數(shù)據(jù)怎么檢索完整數(shù)據(jù)？比如我們?cè)趎ame字段上面建的普通索引。

（2）二級(jí)索引

InnoDB中，主鍵索引和輔助索引是有一個(gè)主次之分的。如果有主鍵索引，那么主鍵索引就是聚集索引。其他的索引統(tǒng)一叫做“二級(jí)索引”（secondary index）。

二級(jí)索引存儲(chǔ)的是二級(jí)索引的鍵值，例如在name上建立索引，節(jié)點(diǎn)上存的是name的值，qingshan tom等等（很明顯，它的鍵值邏輯順序跟物理行的順序不一致）。

而二級(jí)索引的葉子節(jié)點(diǎn)存的是這條記錄對(duì)應(yīng)的主鍵的值。比如qingshan id = 1，jack id = 4等等。

所以，二級(jí)索引檢索數(shù)據(jù)的流程是這樣的：
當(dāng)我們用name索引查詢一條記錄，它會(huì)在二級(jí)索引的葉子節(jié)點(diǎn)找到name=zhangsan，拿到主鍵，也就是id=1，然后再到主鍵索引的葉子節(jié)點(diǎn)拿到數(shù)據(jù)。

為什么不存地址而存鍵值呢？因?yàn)榈刂窌?huì)發(fā)生變化。

從這個(gè)角度來說，因?yàn)橹麈I索引比二級(jí)索引少掃描了一棵B+Tree（避免了回表），它的速度相對(duì)會(huì)快一些。

（3）一個(gè)表沒有主鍵

一張表沒有主鍵怎么辦？完整的記錄放在哪個(gè)索引的葉子節(jié)點(diǎn)？數(shù)據(jù)放在那里？
1、如果我們定義了主鍵（PRIMARY KEY），那么InnoDB會(huì)選擇主鍵作為聚集索引。
2、如果沒有顯式定義主鍵，則InnoDB會(huì)選擇第一個(gè)不包含有NULL值的唯一索引作為主鍵索引。
3、如果也沒有這樣的唯一索引，則InnoDB會(huì)選擇內(nèi)置6字節(jié)長(zhǎng)的ROWID作為隱藏的聚集索引，它會(huì)隨著記錄的寫入而主鍵遞增。文章來源地址http://www.zghlxwxcb.cn/news/detail-566480.html

select _rowid name from t;

到了這里，關(guān)于MySQL為什么要使用B+樹做索引？MySQL索引存儲(chǔ)模型推演，B+樹在MySQL的落地形式的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！