1. 概述

索引是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，相當(dāng)于書(shū)籍的目錄。如果表很大有上千萬(wàn)條數(shù)據(jù)，就意味著要做 很多次磁盤(pán)I/O才能找到需要的數(shù)據(jù)。建立索引后若根據(jù)索引（innodb存儲(chǔ)引擎使用的是B+樹(shù)結(jié)構(gòu)）查詢，相比按順序查找，將極大 減少磁盤(pán)I/0的次數(shù)，加快查找速度；降低 數(shù)據(jù)庫(kù)的IO成本，這也是創(chuàng)建索引最主要的原因

索引是在存儲(chǔ)引擎中實(shí)現(xiàn)的，因此每種存儲(chǔ)引擎的索引不一定完全相同，并且每種存儲(chǔ)引擎不一定支持所有索引類(lèi)型。同時(shí)，存儲(chǔ)引擎可以定義每個(gè)表的 最大索引數(shù)和 最大索引長(zhǎng)度。所有存儲(chǔ)引擎支持每個(gè)表至少16個(gè)索引，總索引長(zhǎng)度至少為256字節(jié)。

缺點(diǎn)：

1. 創(chuàng)建索引和維護(hù)索引要 耗費(fèi)時(shí)間，并且隨著數(shù)據(jù)量的增加，所耗費(fèi)的時(shí)間也會(huì)增加
2. 索引需要占 磁盤(pán)空間
3. 索引會(huì) 降低更新表的速度 。當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增刪改操作的時(shí)候，索引也要?jiǎng)討B(tài)地維護(hù)，這降低了數(shù)據(jù)的維護(hù)速度

因此，選擇使用索引時(shí)，需要綜合考慮索引的優(yōu)點(diǎn)和缺點(diǎn)。

索引可以提高查詢的速度，但是會(huì)影響插入記錄的速度。面臨頻繁增刪改情況下，最好的辦法是先刪除表中的索引，然后插入數(shù)據(jù)，插入完成后再創(chuàng)建索引。

2. 常見(jiàn)索引結(jié)構(gòu)

首先需要知道，MySQL數(shù)據(jù)庫(kù)從磁盤(pán)取數(shù)據(jù)到內(nèi)存中是以最小單位數(shù)據(jù)頁(yè)來(lái)取的，在前面章節(jié)架構(gòu)篇的緩沖池中有提到（默認(rèn)數(shù)據(jù)頁(yè)大小是16KB）。

2.1 聚簇索引

特點(diǎn)：

1. 使用記錄主鍵值的大小進(jìn)行記錄和頁(yè)的排序，這包括三個(gè)方面的含義

   • 頁(yè)內(nèi) 的記錄是按照主鍵的大小順序排成一個(gè) 單向鏈表
   • 各個(gè)存放 用戶記錄的頁(yè) 也是根據(jù)頁(yè)中用戶記錄的主鍵大小順序排成一個(gè) 雙向鏈表
   • 存放 目錄項(xiàng)記錄的頁(yè) 分為不同的層次，在同一層次中的頁(yè)也是根據(jù)頁(yè)中目錄項(xiàng)記錄的主鍵大小順序排成一個(gè) 雙向鏈表

2. B+樹(shù)的 葉子節(jié)點(diǎn) 存儲(chǔ)的是完整的用戶記錄

   所謂完整的用戶記錄，就是指這個(gè)記錄中存儲(chǔ)了所有列的值 (包括隱藏列)。

我們把具有這兩種特性的B+樹(shù)稱為 聚簇索引，所有完整的用戶記錄都存放在這個(gè) 聚簇索引 的葉子節(jié)點(diǎn)處。這種聚簇索引并不需要我們?cè)贛ySQL語(yǔ)句中顯式的使用INDEX 語(yǔ)句去創(chuàng)建，InnoDB 存儲(chǔ)引擎會(huì) 自動(dòng) 的為我們創(chuàng)建聚族索引（索引即數(shù)據(jù)）。

缺點(diǎn)：

• 插入速度嚴(yán)重依賴于插入順序，按照主鍵的順序插入是最快的方式，否則將會(huì)出現(xiàn)頁(yè)分裂，嚴(yán)重影響性能。因此，對(duì)于InnoDB表，一般會(huì)定義一個(gè)自增的ID列為主鍵
• 更新主鍵的代價(jià)很高，因?yàn)閷?huì)導(dǎo)致被更新的行移動(dòng)。因此，對(duì)于innoDB表，我們一般定義主鍵為不可更新
• 二級(jí)索引訪問(wèn)需要兩次索引查找 ，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)

限制：

• MySQL數(shù)據(jù)庫(kù)目前只有InnoDB數(shù)據(jù)引擎支持聚簇索引，而MylSAM并不支持聚簇索引
• 由于數(shù)據(jù)物理存儲(chǔ)排序方式只能有一種，所以每個(gè)MySQL的 表只能有一個(gè)聚簇索引。一般情況下就是該表的主鍵
• 如果沒(méi)有定義主鍵，lnnodb會(huì)選擇 非空的唯一索引 代替。如果沒(méi)有這樣的索引，lnnodb會(huì)隱式的定義一個(gè)主鍵來(lái)作為聚簇索引
• 為了充分利用聚簇索引的聚簇的特性，所以innodb表的主鍵列盡量 選用有序的順序id，而不建議用無(wú)序的id比如UUID、MD5、HASH、字符串列作為主鍵無(wú)法保證數(shù)據(jù)的順序增長(zhǎng)

2.2 二級(jí)索引(輔助索引、非聚簇索引)

上邊介紹的 聚簇索引 只能在搜索條件是 主鍵值 時(shí)才能發(fā)揮作用，因?yàn)锽+樹(shù)中的數(shù)據(jù)都是按照主鍵進(jìn)行排序的。那如果我們想以別的列作為搜索條件該怎么辦呢?肯定不能是從頭到尾沿著鏈表依次遍歷記錄一遍。
答案:我們可以 多建幾棵B+樹(shù)，不同的B+樹(shù)中的數(shù)據(jù)采用不同的排序規(guī)則。比方說(shuō)我們用 c2 列的大小作為數(shù)據(jù)頁(yè)、頁(yè)中記錄的排序規(guī)則，再建一棵B+樹(shù)，效果如下圖所示：

這個(gè)B+樹(shù)與上面聚簇索引有一個(gè)主要的不同點(diǎn)：

• B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)的并不是完整的用戶記錄，而是 c2列+主鍵這兩個(gè)列的值

二級(jí)索引查找流程：

當(dāng)根據(jù)二級(jí)索引查找時(shí)，先根據(jù)二級(jí)索引找到主鍵值，再用主鍵值去聚簇索引中通過(guò)主鍵值查找數(shù)據(jù)（這個(gè)過(guò)程便是回表）；如果索引中便包含了所要查找的數(shù)據(jù)列，如c2，則不需要進(jìn)行回表，可直接取出數(shù)據(jù)，此時(shí)便稱該索引為覆蓋索引

c2值相同時(shí)還會(huì)有別的處理，具體可等后面看3.2。

2.3 聯(lián)合索引

我們也可以同時(shí)以多個(gè)列的大小作為排序規(guī)則，也就是同時(shí)為多個(gè)列建立索引，比方說(shuō)我們想讓B+樹(shù)按照 c2和c3列 的大小進(jìn)行排序，這個(gè)包含兩層含義：

• 先把各個(gè)記錄和頁(yè)按照c2列進(jìn)行排序
• 在記錄的c2列相同的情況下，采用c3列進(jìn)行排序

為c2和c3列建立的索引的示意圖如下：

如圖所示，我們需要注意以下幾點(diǎn)：

• 每條 目錄項(xiàng)記錄 都由 c2、c3、頁(yè)號(hào) 這三個(gè)部分組成，各條記錄先按照c2列的值進(jìn)行排序，如果記錄的c2列相同，則按照c3列的值進(jìn)行排序
• B+樹(shù) 葉子節(jié)點(diǎn) 處的用戶記錄由 c2、c3和主鍵c1列 組成

以c2和c3列的大小為排序規(guī)則建立的B+樹(shù)稱為 聯(lián)合索引，本質(zhì)上也是一個(gè)二級(jí)索引。

3. InnoDB的B+樹(shù)索引的注意事項(xiàng)

3.1 根頁(yè)面位置萬(wàn)年不動(dòng)

B+樹(shù)的形成過(guò)程：

• 每當(dāng)為某個(gè)表創(chuàng)建一個(gè)B+樹(shù)索引(聚族索引不是人為創(chuàng)建的，默認(rèn)就有)的時(shí)候，都會(huì)為這個(gè)索引創(chuàng)建一個(gè) 根節(jié)點(diǎn) 頁(yè)面。最開(kāi)始表中沒(méi)有數(shù)據(jù)的時(shí)候，每個(gè)B+樹(shù)索引對(duì)應(yīng)的 根節(jié)點(diǎn) 中既沒(méi)有用戶記錄，也沒(méi)有目錄項(xiàng)記錄
• 隨后向表中插入用戶記錄時(shí)，先把用戶記錄存儲(chǔ)到這個(gè) 根節(jié)點(diǎn) 中
• 當(dāng)根節(jié)點(diǎn)中的可用 空間用完時(shí) 繼續(xù)插入記錄，此時(shí)會(huì)將根節(jié)點(diǎn)中的所有記錄復(fù)制到一個(gè)新分配的頁(yè)，比如 頁(yè)a 中，然后對(duì)這個(gè)新頁(yè)進(jìn)行 頁(yè)分裂 的操作，得到另一個(gè)新頁(yè)，比如 頁(yè)b 。這時(shí)新插入的記錄根據(jù)鍵值(也就是聚簇索引中的主鍵值，二級(jí)索引中對(duì)應(yīng)的索引列的值)的大小就會(huì)被分配到 頁(yè)a 或者 頁(yè)b 中，而 根節(jié)點(diǎn) 便升級(jí)為存儲(chǔ)目錄項(xiàng)記錄的頁(yè)

這個(gè)過(guò)程特別注意的是：一個(gè)B+樹(shù)索引的根節(jié)點(diǎn)自誕生之日起，便不會(huì)再移動(dòng)。這樣只要我們對(duì)某個(gè)表建立一個(gè)索引，那么它的根節(jié)點(diǎn)的頁(yè)號(hào)便會(huì)被記錄到某個(gè)地方，然后凡是 InnoDB 存儲(chǔ)引擎需要用到這個(gè)索引的時(shí)候，都會(huì)從那個(gè)固定的地方取出根節(jié)點(diǎn)的頁(yè)號(hào)，從而來(lái)訪問(wèn)這個(gè)索引

3.2 內(nèi)節(jié)點(diǎn)中目錄項(xiàng)記錄的唯一性

在上述二級(jí)索引中，如果第二層目錄項(xiàng)存在相同值，此時(shí)需要再插入一個(gè)相同值時(shí)，將無(wú)法得知將要插入的值應(yīng)該插入到哪個(gè)葉子節(jié)點(diǎn)頁(yè)面中去，故實(shí)際上二級(jí)索引為保持內(nèi)節(jié)點(diǎn)的唯一性，還會(huì)再目錄項(xiàng)中也加上主鍵值，這樣就可以在目錄項(xiàng)c2相同的情況下，再比較主鍵值即可得到葉子節(jié)點(diǎn)應(yīng)該插入到哪了，如下圖所示：

這種情況下，我們需要插入(9, 1, ‘x’)時(shí)就知道，我們需要插入到頁(yè)5中。

4. MyISAM中的索引方案

索引/存儲(chǔ)引擎	MyISAM	InnoDB	Memory
B+樹(shù)索引	支持	支持	支持

即使多個(gè)存儲(chǔ)引擎支持同一種類(lèi)型的索引，但是他們的實(shí)現(xiàn)原理也是不同的。Innodb和MyISAM默認(rèn)的索引是B+樹(shù)索引;而Memory默認(rèn)的索引是Hash索引。

MyISAM引擎使用 B+Tree 作為索引結(jié)構(gòu)，葉子節(jié)點(diǎn)的data域存放的是 數(shù)據(jù)記錄的地址。

MyISAM 的索引方案雖然也使用樹(shù)形結(jié)構(gòu)，但是卻 將索引和數(shù)據(jù)分開(kāi)存儲(chǔ)：

• 將表中的記錄 按照記錄的插入順序 單獨(dú)存儲(chǔ)在一個(gè)文件中，稱之為 數(shù)據(jù)文件。這個(gè)文件并不劃分為若干個(gè)數(shù)據(jù)頁(yè)，有多少記錄就往這個(gè)文件中塞多少記錄就成了。由于在插入數(shù)據(jù)的時(shí)候并 沒(méi)有刻意按照主鍵大小排序，所以我們并不能在這些數(shù)據(jù)上使用二分法進(jìn)行查找
• 使用MyISAM存儲(chǔ)引擎的表會(huì)把索引信息另外存儲(chǔ)到一個(gè)稱為 索引文件 的另一個(gè)文件中。MyISAM 會(huì)單獨(dú)為表的主鍵創(chuàng)建一個(gè)索引，只不過(guò)在索引的葉子節(jié)點(diǎn)中存儲(chǔ)的不是完整的用戶記錄，而是 主鍵值 + 數(shù)據(jù)記錄地址 的組合

這里設(shè)表一共有三列，假設(shè)我們以Col1為主鍵，上圖是一個(gè)MyISAM表的主索引 (Primary key) 示意?？梢钥闯鯩yISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。在MyISAM中，主鍵索引和二級(jí)索引(Secondary key) 在結(jié)構(gòu)上沒(méi)有任何區(qū)別，只是主鍵索引要求key是唯一的，而非主鍵索引的key可以重復(fù)，故MyISAM的主鍵及非主鍵索引均為二級(jí)索引。

因此，MylSAM中索引檢索的算法為: 首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。

5. InnoDB和MyISAM對(duì)比

MyISAM的索引方式都是“非聚簇”的，與InnoDB包含1個(gè)聚簇索引是不同的，兩種引擎中索引的區(qū)別：

• 在InnoDB存儲(chǔ)引擎中，我們只需要根據(jù)主鍵值對(duì) 聚簇索引 進(jìn)行一次查找就能找到對(duì)應(yīng)的記錄，而在 MyISAM 中卻需要進(jìn)行一次 回表 操作，意味著MyISAM中建立的索引相當(dāng)于全部都是 二級(jí)索引
• lnnoDB的數(shù)據(jù)文件本身就是索引文件，而MyISAM索引文件和數(shù)據(jù)文件是 分離的，索引文件僅保存數(shù)據(jù)記錄的地址
• lnnoDB的非聚簇索引data域存儲(chǔ)相應(yīng)記錄 主鍵的值，而MylSAM索引記錄的是地址。換句話說(shuō)，InnoDB的所有非聚簇索引都引用主鍵作為data域
• MyISAM的回表操作是十分 快速 的，因?yàn)槭悄弥刂菲屏恐苯拥轿募腥?shù)據(jù)的，反觀InnoDB是通過(guò)獲取主鍵之后再去聚簇索引里找記錄，雖然說(shuō)也不慢，但還是比不上直接用地址去訪問(wèn)
• lnnoDB要求表 必須有主鍵( MyISAM可以沒(méi)有)。如果沒(méi)有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以非空且唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵。如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類(lèi)型為長(zhǎng)整型

6. 小結(jié)

1. 不建議使用過(guò)長(zhǎng)的字段作為主鍵，因?yàn)樗卸?jí)索引都引用主鍵索引，過(guò)長(zhǎng)的主鍵索引會(huì)令二級(jí)索引變得過(guò)大
2. 用非單調(diào)的字段作為主鍵在innoDB中不是個(gè)好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一棵B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)，數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用 自增字段作為主鍵則是一個(gè)很好的選擇（分布式系統(tǒng)要考慮主鍵唯一性，有雪花算法等解決方案后續(xù)研究）
3. 聯(lián)合索引應(yīng)將數(shù)據(jù)重復(fù)少的放前面，使得通過(guò)索引能按索引左側(cè)字段盡快找到對(duì)應(yīng)數(shù)據(jù)
4. 聯(lián)合索引遵守最左匹配原則，即查找邏輯為先查找索引最左側(cè)字段，并逐個(gè)比對(duì)，而無(wú)法從索引右邊字段開(kāi)始

7. 補(bǔ)充：MySQL數(shù)據(jù)結(jié)構(gòu)的合理性

從MySQL的角度講，不得不考慮一個(gè)現(xiàn)實(shí)問(wèn)題就是磁盤(pán)IO。如果我們能讓索引的數(shù)據(jù)結(jié)構(gòu)盡量減少硬盤(pán)的 I/0 操作，所消耗的時(shí)間也就越小。可以說(shuō)，磁盤(pán)的 I/0 操作次數(shù) 對(duì)索引的使用效率至關(guān)重要

查找都是索引操作，一般來(lái)說(shuō)索引非常大，尤其是關(guān)系型數(shù)據(jù)庫(kù)，當(dāng)數(shù)據(jù)量比較大的時(shí)候，索引的大小有可能幾個(gè)G甚至更多，為了減少索引在內(nèi)存的占用，數(shù)據(jù)庫(kù)索引是存儲(chǔ)在外部磁盤(pán)上的。當(dāng)我們利用索引查詢的時(shí)候不可能把整個(gè)索引全部加載到內(nèi)存，只能 逐一加載，那么MySQL衡量查詢效率的標(biāo)準(zhǔn)就是磁盤(pán)IO次數(shù)

7.1 全表遍歷

需逐個(gè)加載數(shù)據(jù)頁(yè)，如果在最后一頁(yè)，需遍歷全表，將數(shù)據(jù)頁(yè)都加載進(jìn)內(nèi)存，要進(jìn)行大量I/O操作。

7.2 Hash結(jié)構(gòu)

哈希的查詢/插入/修改/刪除的平均時(shí)間復(fù)雜度都是O(1)，但索引結(jié)構(gòu)還是采取了樹(shù)型，具體原因有：

1. Hash 索引僅能滿足(=) (<>)和 IN 查詢。如果進(jìn)行 范圍查詢，哈希型的索引，時(shí)間復(fù)雜度會(huì)退化為O(n);而樹(shù)型的“有序”特性，依然能夠保持O(log2N)的高效率
2. Hash 索引還有一個(gè)缺陷，數(shù)據(jù)的存儲(chǔ)是 沒(méi)有順序的，在ORDER BY的情況下，使用 Hash 索引還需要對(duì)數(shù)據(jù)重新排序。
3. 對(duì)于聯(lián)合索引的情況，Hash 值是將聯(lián)合索引鍵合并后一起來(lái)計(jì)算的，無(wú)法對(duì)單獨(dú)的一個(gè)鍵或者幾個(gè)索引鍵進(jìn)行查詢
4. 對(duì)于等值查詢來(lái)說(shuō)，通常 Hash 索引的效率更高，不過(guò)也存在一種情況，就是 索引列的重復(fù)值如果很多，效率就會(huì)降低。這是因?yàn)橛龅?Hash 沖突時(shí)，需要遍歷桶中的行指針來(lái)進(jìn)行比較，找到查詢的關(guān)鍵字，非常耗時(shí)。所以，Hash 索引通常不會(huì)用到重復(fù)值多的列上，比如列為性別、年齡的情況等

另外，InnoDB 本身不支持 Hash 索引，但是提供 自適應(yīng) Hash 索引 (Adaptive Hash index) 。什么情況下才會(huì)使用自適應(yīng) Hash 索引呢?如果某個(gè)數(shù)據(jù)經(jīng)常被訪問(wèn)，當(dāng)滿足一定條件的時(shí)候，就會(huì)將這個(gè)數(shù)據(jù)頁(yè)的地址存放到Hash 表中。這樣下次查詢的時(shí)候，就可以直接找到這個(gè)頁(yè)面的所在位置。這樣讓 B+ 樹(shù)也具備了 Hash 索引的優(yōu)點(diǎn)。

自適應(yīng) Hash索引變量默認(rèn)是開(kāi)啟的：

show variables like '%adaptive_hash_index';

7.3 二叉搜索樹(shù)

如果利用樹(shù)形結(jié)構(gòu)作為索引結(jié)構(gòu)，那么磁盤(pán)的0次數(shù)和索引樹(shù)的高度是相關(guān)的。如果插入數(shù)據(jù)一直是逐漸變大，二叉搜索樹(shù)就會(huì)形成一根鏈條，查找數(shù)據(jù)的時(shí)間復(fù)雜度會(huì)退化為O(n)，為了提高查詢效率就需要盡量降低樹(shù)的高度，需要把原來(lái)“瘦高”的樹(shù)結(jié)構(gòu)變的矮胖，樹(shù)的每層的分叉越多越好

7.4 AVL樹(shù)

為解決二叉樹(shù)退化為鏈表的問(wèn)題，人們提出了平衡二叉搜索樹(shù)(Balanced Binary Tree)，又稱AVL樹(shù)（有別于AVL算法）。這樣搜索的時(shí)間復(fù)雜度就能穩(wěn)定在Log2N，但是當(dāng)數(shù)據(jù)量大時(shí)，樹(shù)的深度一樣會(huì)很高，而每訪問(wèn)一次節(jié)點(diǎn)就許可進(jìn)行一次磁盤(pán)I/O操作，需要消耗的時(shí)間一樣很多。

7.5 B-Tree

針對(duì)以上問(wèn)題，如果把二叉樹(shù)改為M叉樹(shù)(M>2)，M叉平衡樹(shù)的高度會(huì)遠(yuǎn)小于二叉樹(shù)的高度，所以可以讓樹(shù)更加“矮胖”。B樹(shù)的英文是Balance Tree，也就是多路平衡樹(shù)。簡(jiǎn)寫(xiě)為B-Tree（-表示兩個(gè)單詞相連，念橫杠而非B減樹(shù)），與B+樹(shù)典型區(qū)別是非葉子節(jié)點(diǎn)也會(huì)存儲(chǔ)數(shù)據(jù)。對(duì)于大量的索引數(shù)據(jù)來(lái)說(shuō)，采用B樹(shù)的結(jié)構(gòu)是非常合適的，因?yàn)闃?shù)的高度要遠(yuǎn)小于二叉樹(shù)的高度。

7.6 B+Tree

B+樹(shù)也是一種多路搜索樹(shù)，基于 B 樹(shù)做出了改進(jìn)，主流的 DBMS 都支持 B+ 樹(shù)的索引方式，比如 MySQL。相比于B-Tree，B+Tree適合文件索引系統(tǒng)。

B+Tree和B-Tree的根本差異就是B+樹(shù)的中間節(jié)點(diǎn)并不直接存儲(chǔ)數(shù)據(jù)，這樣的好處是？

• B+樹(shù)的查詢效率更穩(wěn)定，因?yàn)橹虚g節(jié)點(diǎn)無(wú)需存儲(chǔ)數(shù)據(jù)，要查到數(shù)據(jù)必須查到數(shù)據(jù)的葉子節(jié)點(diǎn)
• B+樹(shù)的查詢效率更高，因?yàn)橹虚g節(jié)點(diǎn)無(wú)需存儲(chǔ)數(shù)據(jù)，B+樹(shù)通常比B樹(shù) 更矮胖，查詢鎖需要的磁盤(pán)I/O也會(huì)更少，同樣的磁盤(pán)頁(yè)，B+樹(shù)可存儲(chǔ)更多的節(jié)點(diǎn)關(guān)鍵字
• B+樹(shù)查詢范圍的效率更高，B+樹(shù)葉子節(jié)點(diǎn)間有指針，數(shù)據(jù)又是遞增，范圍查找可通過(guò)指針連接查找，而B(niǎo)樹(shù)中要通過(guò)中序遍歷，效率要低很多

B樹(shù)和B+樹(shù)都可以作為索引的數(shù)據(jù)結(jié)構(gòu)，在MySQL中采用的是B+樹(shù)，但B樹(shù)和B+樹(shù)各有自己的應(yīng)用場(chǎng)景，不能完全說(shuō)B+樹(shù)比B樹(shù)好

注意：索引樹(shù)不會(huì)一次性加載（數(shù)據(jù)量大必然導(dǎo)致索引增大），而是逐一加載每一個(gè)磁盤(pán)頁(yè)，因?yàn)榇疟P(pán)頁(yè)對(duì)應(yīng)著索引樹(shù)的節(jié)點(diǎn)

7.7 R樹(shù)

R-Tree在MySQL很少使用，僅支持 geometry數(shù)據(jù)類(lèi)型，支持該類(lèi)型的存儲(chǔ)引擎只有myisam、bdb、innodb、ndb、archive幾種。舉個(gè)R樹(shù)在現(xiàn)實(shí)領(lǐng)域中能夠解決的例子: 查找20英里以內(nèi)所有的餐廳。如果沒(méi)有R樹(shù)你會(huì)怎么解決?一般情況下我們會(huì)把餐廳的坐標(biāo)(x,y)分為兩個(gè)字段存放在數(shù)據(jù)庫(kù)中，一個(gè)字段記錄經(jīng)度，另一個(gè)字段記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然后計(jì)算是否滿足要求。如果一個(gè)地區(qū)有100家餐廳的話，我們就要進(jìn)行100次位置計(jì)算操作了，如果應(yīng)用到谷歌、百度地圖這種超大數(shù)據(jù)庫(kù)中，這種方法便必定不可行了。R樹(shù)就很好的 解決了這種高維空間搜索問(wèn)題。它把B樹(shù)的思想很好的擴(kuò)展到了多維空間，采用了B樹(shù)分割空間的思想，并在添加、刪除操作時(shí)采用合并、分解結(jié)點(diǎn)的方法，保證樹(shù)的平衡性。因此，R樹(shù)就是一棵用來(lái)存儲(chǔ)高維數(shù)據(jù)的平衡樹(shù)。相對(duì)于B-Tree，R-Tree的優(yōu)勢(shì)在于范圍查找

8. 思考題

8.1 思考B+樹(shù)的存儲(chǔ)能力如何？為何說(shuō)一般查找記錄，最多只需1~3次磁盤(pán)IO？

InnoDB 存儲(chǔ)引擎中頁(yè)的大小為 16KB，一般表的主鍵類(lèi)型為INT(占用4個(gè)字節(jié)或BIGINT(占用8個(gè)字節(jié))，指針類(lèi)型也一般為4或8個(gè)字節(jié)，也就是說(shuō)一個(gè)頁(yè)(B+Tree 中的一個(gè)節(jié)點(diǎn))中大概存儲(chǔ)16KB/(8B+8B)=1K個(gè)鍵值 (因?yàn)槭枪乐?#xff0c;為方便計(jì)算，這里的K 取值為10^3。也就是說(shuō)一個(gè)深度為3的B+Tree 索引可以維護(hù)10^3 * 10^ 3 * 10^3 = 10 億條記錄。(這里假定一個(gè)數(shù)據(jù)頁(yè)也存儲(chǔ)10^3條行記錄數(shù)據(jù)了)

實(shí)際情況中每個(gè)節(jié)點(diǎn)可能不能填充滿，因此在數(shù)據(jù)庫(kù)中，B+Tree 的高度一般都在 2~4 層。MySQL的InnoDB 存儲(chǔ)引擎在設(shè)計(jì)時(shí)是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要 1~3次磁盤(pán)I/0 操作。

8.2 為什么說(shuō)B+樹(shù)比B-樹(shù)更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫(kù)索引?

1. B+樹(shù)的磁盤(pán)讀寫(xiě)代價(jià)更低，B+樹(shù)的內(nèi)部結(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹(shù)更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來(lái)說(shuō)IO讀寫(xiě)次數(shù)也就降低了
2. B+樹(shù)的查詢效率更加穩(wěn)定

9. 小結(jié)

使用索引可以幫助我們從海量的數(shù)據(jù)中快速定位想要查找的數(shù)據(jù)，不過(guò)索引也存在一些不足，比如占用存儲(chǔ)空間、降低數(shù)據(jù)庫(kù)寫(xiě)操作的性能等，如果有多個(gè)索引還會(huì)增加索引選擇的時(shí)間。當(dāng)我們使用索引時(shí)，需要平衡索引的利(提升查詢效率)和弊(維護(hù)索引所需的代價(jià))。

在實(shí)際工作中，我們還需要基于需求和數(shù)據(jù)本身的分布情況來(lái)確定是否使用索引，盡管 索引不是萬(wàn)能的，但 數(shù)據(jù)量大的時(shí)候不使用索引是不可想象的 ，畢竟索引的本質(zhì)，是幫助我們提升數(shù)據(jù)檢索的效率