為什么要使用索引

索引是存儲(chǔ)引擎用于快速找到數(shù)據(jù)記錄的一種數(shù)據(jù)結(jié)構(gòu)，就好比一本教科書的目錄部分，通過(guò)目錄中找到對(duì)應(yīng)文章的頁(yè)碼，便可快速定位到需要的文章。

MySQL中也是一樣的道理，進(jìn)行數(shù)據(jù)查找時(shí)，首先查看查詢條件是否命中某條索引，符合則通過(guò)索引查找相關(guān)數(shù)據(jù)，如果不符合則需要全表掃描，即需要一條一條地查找記錄，直到找到與條件符合的記錄。

如上圖所示，數(shù)據(jù)庫(kù)沒(méi)有索引的情況下，數(shù)據(jù)分布在硬盤不同的位置上面，讀取數(shù)據(jù)時(shí)，擺臂需要前后擺動(dòng)查詢數(shù)據(jù)，這樣操作非常消耗時(shí)間。

如果數(shù)據(jù)順序擺放，那么也需要從1到6行按順序讀取，這樣就相當(dāng)于進(jìn)行了6次IO操作，依舊非常耗時(shí)。

如果我們不借助任何索引結(jié)構(gòu)幫助我們快速定位數(shù)據(jù)的話，我們查找 Col 2 = 89 這條記錄，就要逐行去查找、去比較。

從Col 2 = 34 開始，進(jìn)行比較，發(fā)現(xiàn)不是，繼續(xù)下一行。我們當(dāng)前的表只有不到10行數(shù)據(jù)，但如果表很大的話，有上千萬(wàn)條數(shù)據(jù)，就意味著要做很多很多次硬盤I/0才能找到。

現(xiàn)在要查找 Col 2 = 89 這條記錄。CPU必須先去磁盤查找這條記錄，找到之后加載到內(nèi)存，再對(duì)數(shù)據(jù)進(jìn)行處理。

這個(gè)過(guò)程最耗時(shí)間就是磁盤I/O（涉及到磁盤的旋轉(zhuǎn)時(shí)間（速度較快），磁頭的尋道時(shí)間(速度慢、費(fèi)時(shí))）

假如給數(shù)據(jù)使用 二叉樹 這樣的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，如下圖所示：

對(duì)字段 Col 2 添加了索引，就相當(dāng)于在硬盤上為 Col 2 維護(hù)了一個(gè)索引的數(shù)據(jù)結(jié)構(gòu)，即這個(gè) 二叉搜索樹。

二叉搜索樹的每個(gè)結(jié)點(diǎn)存儲(chǔ)的是 (K, V) 結(jié)構(gòu)，key 是 Col 2，value 是該 key 所在行的文件指針（地址）。

比如：該二叉搜索樹的根節(jié)點(diǎn)就是：(34, 0x07)。現(xiàn)在對(duì) Col 2 添加了索引，這時(shí)再去查找 Col 2 = 89 這條記錄的時(shí)候會(huì)先去查找該二叉搜索樹（二叉樹的遍歷查找）。

讀 34 到內(nèi)存，89 > 34; 繼續(xù)右側(cè)數(shù)據(jù)，讀 89 到內(nèi)存，89==89；找到數(shù)據(jù)返回。找到之后就根據(jù)當(dāng)前結(jié)點(diǎn)的 value 快速定位到要查找的記錄對(duì)應(yīng)的地址。

我們可以發(fā)現(xiàn)，只需要 查找兩次 就可以定位到記錄的地址，查詢速度就提高了。

這就是我們?yōu)槭裁匆ㄋ饕?strong>目的就是為了 減少磁盤I/O的次數(shù)，加快查詢速率。

索引及其優(yōu)缺點(diǎn)

索引概述

MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。

你可以簡(jiǎn)單理解為“排好序的快速查找數(shù)據(jù)結(jié)構(gòu)”，滿足特定查找算法。

這些數(shù)據(jù)結(jié)構(gòu)以某種方式指向數(shù)據(jù)， 這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn) 高級(jí)查找算法。

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

優(yōu)點(diǎn)

（1）類似大學(xué)圖書館建書目索引，提高數(shù)據(jù)檢索的效率，降低 數(shù)據(jù)庫(kù)的IO成本 ，這也是創(chuàng)建索引最主 要的原因。

（2）通過(guò)創(chuàng)建唯一索引，可以保證數(shù)據(jù)庫(kù)表中每一行 數(shù)據(jù)的唯一性 。

（3）在實(shí)現(xiàn)數(shù)據(jù)的參考完整性方面，可以 加速表和表之間的連接 。換句話說(shuō)，對(duì)于有依賴關(guān)系的子表和父表聯(lián)合查詢時(shí)， 可以提高查詢速度。

（4）在使用分組和排序子句進(jìn)行數(shù)據(jù)查詢時(shí)，可以顯著 減少查詢中分組和排序的時(shí)間 ，降低了CPU的消耗。

缺點(diǎn)

增加索引也有許多不利的方面，主要表現(xiàn)在如下幾個(gè)方面：

（1）創(chuàng)建索引和維護(hù)索引要 耗費(fèi)時(shí)間 ，并 且隨著數(shù)據(jù)量的增加，所耗費(fèi)的時(shí)間也會(huì)增加。

（2）索引需要占 磁盤空間 ，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個(gè)索引還要占一定的物理空間， 存儲(chǔ)在磁盤上 ，如果有大量的索引，索引文件就可能比數(shù)據(jù)文件更快達(dá)到最大文件尺寸。

（3）雖然索引大大提高了查詢速度，同時(shí)卻會(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)。

InnoDB中索引的推演

索引之前的查找

在一個(gè)頁(yè)中的查找

假設(shè)目前表中的記錄比較少，所有的記錄都可以被存放到一個(gè)頁(yè)中，在查找記錄的時(shí)候可以根據(jù)搜索條件的不同分為兩種情況：

以主鍵為搜索條件

• 可以在頁(yè)目錄中使用 二分法 快速定位到對(duì)應(yīng)的槽
• 然后再遍歷該槽對(duì)用分組中的記錄即可快速找到指定記錄

以其他列作為搜索條件

• 因?yàn)樵跀?shù)據(jù)頁(yè)中并沒(méi)有對(duì)非主鍵列簡(jiǎn)歷所謂的頁(yè)目錄，所以我們無(wú)法通過(guò)二分法快速定位相應(yīng)的槽。
• 這種情況下只能從 最小記錄開始依次遍歷到最大記錄（全表掃描）， 然后對(duì)比每條記錄是不是符合搜索條件。
• 很顯然，這種查找的效率是非常低的。

在很多頁(yè)中查找

在很多頁(yè)中查找記錄的活動(dòng)可以分為兩個(gè)步驟：

1. 定位到記錄所在的頁(yè)：即從整個(gè)雙向鏈表的頁(yè)，遍歷到最后的頁(yè)
2. 從所在的頁(yè)內(nèi)中查找相應(yīng)的記錄：找到對(duì)應(yīng)頁(yè)之后，再遍歷頁(yè)中的記錄。

在沒(méi)有索引的情況下，不論是根據(jù)主鍵列或者其他列的值進(jìn)行查找，由于我們并不能快速的定位到記錄所在的頁(yè)，所以只能從第一個(gè)頁(yè)沿著雙向鏈表 一直往下找，在每一個(gè)頁(yè)中根據(jù)我們上面的查找方式去查找指定的記錄。因?yàn)橐闅v所有的數(shù)據(jù)頁(yè)，所以這種方式顯然是超級(jí)耗時(shí)的。

設(shè)計(jì)索引

建立表

CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;

這個(gè)新建的 index_demo 表中有2個(gè)INT類型的列，1個(gè)CHAR(1)類型的列，而且我們規(guī)定了c1列為主鍵， 這個(gè)表使用 Compact 行格式來(lái)實(shí)際存儲(chǔ)記錄的。

這里我們簡(jiǎn)化了index_demo表的行格式示意圖：

我們只在示意圖里展示記錄的這幾個(gè)部分：

• record_type ：記錄頭信息的一項(xiàng)屬性，表示記錄的類型， 0 表示普通記錄、 2 表示最小記 錄、 3 表示最大記錄、 1 暫時(shí)還沒(méi)用過(guò)，下面講。
• next_record ：記錄頭信息的一項(xiàng)屬性，表示下一條地址相對(duì)于本條記錄的地址偏移量，我們用 箭頭來(lái)表明下一條記錄是誰(shuí)。
• 各個(gè)列的值 ：這里只記錄在 index_demo 表中的三個(gè)列，分別是 c1 、 c2 和 c3 。
• 其他信息 ：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

將記錄格式示意圖的其他信息項(xiàng)暫時(shí)去掉并把它豎起來(lái)的效果就是這樣：

把一些記錄放到頁(yè)里的示意圖就是：

簡(jiǎn)單的索引設(shè)計(jì)方案

我們?cè)诟鶕?jù)某個(gè)搜索條件查找一些記錄時(shí)為什么要遍歷所有的數(shù)據(jù)頁(yè)呢？因?yàn)楦鱾€(gè)頁(yè)中的記錄并沒(méi)有規(guī)律，我們并不知道我們的搜索條件匹配哪些頁(yè)中的記錄，所以不得不依次遍歷所有的數(shù)據(jù)頁(yè)。所以如果我們 想快速的定位到需要查找的記錄在哪些數(shù)據(jù)頁(yè) 中該咋辦？

我們可以為快速定位記錄所在的數(shù)據(jù)頁(yè)而建立一個(gè)目錄 ，建這個(gè)目錄必須完成下邊這些事：

• 下一個(gè)數(shù)據(jù)頁(yè)中用戶記錄的主鍵值必須大于上一個(gè)頁(yè)中用戶記錄的主鍵值。

假設(shè)：每個(gè)數(shù)據(jù)結(jié)構(gòu)最多能存放3條記錄（實(shí)際上一個(gè)數(shù)據(jù)頁(yè)非常大，可以存放下好多記錄）。

INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');

那么這些記錄以及按照主鍵值的大小串聯(lián)成一個(gè)單向鏈表了，如圖所示：

從圖中可以看出來(lái)， index_demo 表中的3條記錄都被插入到了編號(hào)為10的數(shù)據(jù)頁(yè)中了。

此時(shí)我們?cè)賮?lái)插入一條記錄

INSERT INTO index_demo VALUES(4, 4, 'a');

因?yàn)?頁(yè)10 最多只能放3條記錄，所以我們不得不再分配一個(gè)新頁(yè)：

此時(shí)新分配的 數(shù)據(jù)頁(yè)編號(hào)可能并不是連續(xù)的。它們只是通過(guò)維護(hù)者上一個(gè)頁(yè)和下一個(gè)頁(yè)的編號(hào)而建立了 鏈表 關(guān)系。另外，頁(yè)10中用戶記錄最大的主鍵值是5，而頁(yè)28中有一條記錄的主鍵值是4，因?yàn)?>4，所以這就不符合下一個(gè)數(shù)據(jù)頁(yè)中用戶記錄的主鍵值必須大于上一個(gè)頁(yè)中用戶記錄的主鍵值的要求，所以在插入主鍵值為4的記錄的時(shí)候需要伴隨著一次 記錄移動(dòng)，也就是把主鍵值為5的記錄移動(dòng)到頁(yè)28中，然后再把主鍵值為4的記錄插入到頁(yè)10中，這也就是維護(hù)索引的過(guò)程，這個(gè)過(guò)程的示意圖如下：

這個(gè)過(guò)程表明了在對(duì)頁(yè)中的記錄進(jìn)行增刪改查操作的過(guò)程中，我們必須通過(guò)一些諸如 記錄移動(dòng) 的操作來(lái)始終保證這個(gè)狀態(tài)一直成立：下一個(gè)數(shù)據(jù)頁(yè)中用戶記錄的主鍵值必須大于上一個(gè)頁(yè)中用戶記錄的主鍵值。這個(gè)過(guò)程稱為頁(yè)分裂。

給所有的頁(yè)建立一個(gè)目錄項(xiàng)。

由于數(shù)據(jù)頁(yè)的 編號(hào)可能是不連續(xù) 的，所以在向 index_demo 表中插入許多條記錄后，可能是這樣的效果，又要遍歷每個(gè)頁(yè)，但每個(gè)頁(yè)中的可以通過(guò)二分法來(lái)篩選，但也效率低下：

我們可以給每個(gè)頁(yè)做個(gè)目錄，每個(gè)頁(yè)對(duì)應(yīng)一個(gè)目錄項(xiàng)，每個(gè)目錄項(xiàng)包括下邊兩個(gè)部分：

1）頁(yè)的用戶記錄中最小的主鍵值，我們用 key 來(lái)表示。

2）頁(yè)號(hào)，我們用 page_on 表示。

以 頁(yè)28 為例，它對(duì)應(yīng) 目錄項(xiàng)2 ，這個(gè)目錄項(xiàng)中包含著該頁(yè)的頁(yè)號(hào) 28 以及該頁(yè)中用戶記錄的最小主 鍵值 5 。我們只需要把幾個(gè)目錄項(xiàng)在物理存儲(chǔ)器上連續(xù)存儲(chǔ)（比如：數(shù)組），就可以實(shí)現(xiàn)根據(jù)主鍵 值快速查找某條記錄的功能了。

比如：查找主鍵值為 20 的記錄，具體查找過(guò)程分兩步：

• 先從目錄項(xiàng)中根據(jù) 二分法 快速確定出主鍵值為 20 的記錄在 目錄項(xiàng)3 中（因?yàn)?12 < 20 < 209 ），它對(duì)應(yīng)的頁(yè)是 頁(yè)9 。
• 再根據(jù)前邊說(shuō)的在頁(yè)中查找記錄的方式去 頁(yè)9 中定位具體的記錄

InnoDB中的索引方案迭代1次：目錄項(xiàng)紀(jì)錄的頁(yè)

InnoDB怎么區(qū)分一條記錄是普通的 用戶記錄 還是 目錄項(xiàng)記錄 呢？使用記錄頭信息里的 record_type 屬性，它的各自取值代表的意思如下：

• 0：普通的用戶記錄
• 1：目錄項(xiàng)記錄
• 2：最小記錄
• 3：最大記錄

我們把前邊使用到的目錄項(xiàng)放到數(shù)據(jù)頁(yè)中的樣子就是這樣：

從圖中可以看出來(lái)，我們新分配了一個(gè)編號(hào)為30的頁(yè)來(lái)專門存儲(chǔ)目錄項(xiàng)記錄。這里再次強(qiáng)調(diào) 目錄項(xiàng)記錄 和普通的 用戶記錄 的不同點(diǎn)：

• 目錄項(xiàng)記錄 的 record_type 值是1，而 普通用戶記錄 的 record_type 值是0。
• 目錄項(xiàng)記錄只有 主鍵值和頁(yè)的編號(hào) 兩個(gè)列，而普通的用戶記錄的列是用戶自己定義的，可能包含 很多列 ，另外還有InnoDB自己添加的隱藏列。
• 了解：記錄頭信息里還有一個(gè)叫 min_rec_mask 的屬性，只有在存儲(chǔ) 目錄項(xiàng)記錄 的頁(yè)中的主鍵值最小的 目錄項(xiàng)記錄 的 min_rec_mask 值為 1 ，其他別的記錄的 min_rec_mask 值都是 0 。

相同點(diǎn)在于尋找記錄時(shí)，跟普通頁(yè)數(shù)據(jù)是一樣的，通過(guò)找到記錄對(duì)應(yīng)的頁(yè)目錄，再通過(guò)頁(yè)目錄找到對(duì)應(yīng)的頁(yè)，精準(zhǔn)查詢，減少了磁盤io的消耗。

迭代2次：多個(gè)目錄項(xiàng)紀(jì)錄的頁(yè)

從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之后需要兩個(gè)新的數(shù)據(jù)頁(yè)：

• 為存儲(chǔ)該用戶記錄而新生成了 頁(yè)31 。
• 因?yàn)樵却鎯?chǔ)目錄項(xiàng)記錄的 頁(yè)30的容量已滿 （我們前邊假設(shè)只能存儲(chǔ)4條目錄項(xiàng)記錄），所以不得 不需要一個(gè)新的 頁(yè)32 來(lái)存放 頁(yè)31 對(duì)應(yīng)的目錄項(xiàng)。

由于現(xiàn)在數(shù)據(jù)頁(yè)不止一個(gè)，也需要遍歷頁(yè)，才能找到對(duì)應(yīng)記錄的頁(yè)目錄。

迭代3次：目錄項(xiàng)記錄頁(yè)的目錄頁(yè)

如果我們表中的數(shù)據(jù)非常多則會(huì)產(chǎn)生很多存儲(chǔ)目錄項(xiàng)記錄的頁(yè)，那我們?cè)趺锤鶕?jù)主鍵值快速定位一個(gè)存儲(chǔ)目錄項(xiàng)記錄的頁(yè)呢？

那就為這些存儲(chǔ)目錄項(xiàng)記錄的頁(yè)再生成一個(gè)更高級(jí)的目錄，再套一層娃，就像是一個(gè)多級(jí)目錄一樣，大目錄里嵌套小目錄，小目錄里才是實(shí)際的數(shù)據(jù)，所以現(xiàn)在各個(gè)頁(yè)的示意圖就是這樣子：

如圖，我們生成了一個(gè)存儲(chǔ)更高級(jí)目錄項(xiàng)的 頁(yè)33 ，這個(gè)頁(yè)中的兩條記錄分別代表頁(yè)30和頁(yè)32，如果用 戶記錄的主鍵值在 [1, 320) 之間，則到頁(yè)30中查找更詳細(xì)的目錄項(xiàng)記錄，如果主鍵值 不小于320 的 話，就到頁(yè)32中查找更詳細(xì)的目錄項(xiàng)記錄。

我們可以用下邊這個(gè)圖來(lái)描述它：

B+Tree

一個(gè)B+樹的節(jié)點(diǎn)其實(shí)可以分成好多層，規(guī)定最下邊的那層，也就是存放我們用戶記錄的那層為第 0 層， 之后依次往上加。

之前我們做了一個(gè)非常極端的假設(shè)：存放用戶記錄的頁(yè) 最多存放3條記錄 ，存放目錄項(xiàng) 記錄的頁(yè) 最多存放4條記錄 。

其實(shí)真實(shí)環(huán)境中一個(gè)頁(yè)存放的記錄數(shù)量是非常大的，假設(shè)所有存放用戶記錄 的葉子節(jié)點(diǎn)代表的數(shù)據(jù)頁(yè)可以存放 100條用戶記錄 ，所有存放目錄項(xiàng)記錄的內(nèi)節(jié)點(diǎn)代表的數(shù)據(jù)頁(yè)可以存 放 1000條目錄項(xiàng)記錄 ，那么：

• 如果B+樹只有1層，也就是只有1個(gè)用于存放用戶記錄的節(jié)點(diǎn)，最多能存放 100 條記錄。
• 如果B+樹有2層，最多能存放 1000×100=10,0000 條記錄。
• 如果B+樹有3層，最多能存放 1000×1000×100=1,0000,0000 條記錄。
• 如果B+樹有4層，最多能存放 1000×1000×1000×100=1000,0000,0000 條記錄。相當(dāng)多的記錄！

你的表里能存放 100000000000 條記錄嗎？所以一般情況下，我們用到的 B+樹都不會(huì)超過(guò)4層 ，那我們通過(guò)主鍵值去查找某條記錄最多只需要做4個(gè)頁(yè)面內(nèi)的查找（查找3個(gè)目錄項(xiàng)頁(yè)和一個(gè)用戶記錄頁(yè)），又因?yàn)樵诿總€(gè)頁(yè)面內(nèi)有所謂的 Page Directory （頁(yè)目錄），所以在頁(yè)面內(nèi)也可以通過(guò) 二分法 實(shí)現(xiàn)快速定位記錄。

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

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

實(shí)際上B+樹的形成過(guò)程是這樣的：

• 每當(dāng)為某個(gè)表創(chuàng)建一個(gè)B+樹索引（聚簇索引不是人為創(chuàng)建的，默認(rèn)就有）的時(shí)候，都會(huì)為這個(gè)索引創(chuàng)建一個(gè)根節(jié)點(diǎn)頁(yè)。最開始表中沒(méi)有數(shù)據(jù)的時(shí)候，每個(gè)B+樹索引對(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+樹索引的根節(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è)索引。

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

我們知道B+樹索引的內(nèi)節(jié)點(diǎn)中目錄項(xiàng)記錄的內(nèi)容是 索引列 + 頁(yè)號(hào) 的搭配，但是這個(gè)搭配對(duì)于二級(jí)索引來(lái)說(shuō)有點(diǎn)不嚴(yán)謹(jǐn)。

還拿 index_demo 表為例，假設(shè)這個(gè)表中的數(shù)據(jù)是這樣的：

如果二級(jí)索引中目錄項(xiàng)記錄的內(nèi)容只是 索引列 + 頁(yè)號(hào) 的搭配的話，那么為 c2 列簡(jiǎn)歷索引后的B+樹應(yīng)該長(zhǎng)這樣：

如果我們想新插入一行記錄，其中 c1 、c2 、c3 的值分別是: 9、1、c, 那么在修改這個(gè)為 c2 列建立的二級(jí)索引對(duì)應(yīng)的 B+ 樹時(shí)便碰到了個(gè)大問(wèn)題：由于 頁(yè)3 中存儲(chǔ)的目錄項(xiàng)記錄是由 c2列 + 頁(yè)號(hào) 的值構(gòu)成的，頁(yè)3 中的兩條目錄項(xiàng)記錄對(duì)應(yīng)的 c2 列的值都是1，而我們 新插入的這條記錄 的 c2 列的值也是 1，那我們這條新插入的記錄到底應(yīng)該放在 頁(yè)4 中，還是應(yīng)該放在 頁(yè)5 中？答案：對(duì)不起，懵了

為了讓新插入記錄找到自己在那個(gè)頁(yè)面，我們需要保證在B+樹的同一層頁(yè)節(jié)點(diǎn)的目錄項(xiàng)記錄除頁(yè)號(hào)這個(gè)字段以外是唯一的。所以對(duì)于二級(jí)索引的內(nèi)節(jié)點(diǎn)的目錄項(xiàng)記錄的內(nèi)容實(shí)際上是由三個(gè)部分構(gòu)成的：

• 索引列的值
• 主鍵值
• 頁(yè)號(hào)

也就是我們把主鍵值也添加到二級(jí)索引內(nèi)節(jié)點(diǎn)中的目錄項(xiàng)記錄，這樣就能保住 B+ 樹每一層節(jié)點(diǎn)中各條目錄項(xiàng)記錄除頁(yè)號(hào)這個(gè)字段外是唯一的，所以我們?yōu)閏2建立二級(jí)索引后的示意圖實(shí)際上應(yīng)該是這樣子的：

這樣我們?cè)俨迦胗涗?code>(9, 1, 'c') 時(shí)，由于 頁(yè)3 中存儲(chǔ)的目錄項(xiàng)記錄是由 c2列 + 主鍵 + 頁(yè)號(hào) 的值構(gòu)成的，可以先把新紀(jì)錄的 c2 列的值和 頁(yè)3 中各目錄項(xiàng)記錄的 c2 列的值作比較，如果 c2 列的值相同的話，可以接著比較主鍵值，因?yàn)锽+樹同一層中不同目錄項(xiàng)記錄的 c2列 + 主鍵的值肯定是不一樣的，所以最后肯定能定位唯一的一條目錄項(xiàng)記錄，在本例中最后確定新紀(jì)錄應(yīng)該被插入到 頁(yè)5 中。

一個(gè)頁(yè)面最少存儲(chǔ) 2 條記錄

一個(gè)B+樹只需要很少的層級(jí)就可以輕松存儲(chǔ)數(shù)億條記錄，查詢速度相當(dāng)不錯(cuò)！這是因?yàn)锽+樹本質(zhì)上就是一個(gè)大的多層級(jí)目錄，每經(jīng)過(guò)一個(gè)目錄時(shí)都會(huì)過(guò)濾掉許多無(wú)效的子目錄，直到最后訪問(wèn)到存儲(chǔ)真實(shí)數(shù)據(jù)的目錄。

那如果一個(gè)大的目錄中只存放一個(gè)子目錄是個(gè)啥效果呢？那就是目錄層級(jí)非常非常多，而且最后的那個(gè)存放真實(shí)數(shù)據(jù)的目錄中只存放一條數(shù)據(jù)。所以 InnoDB 的一個(gè)數(shù)據(jù)頁(yè)至少可以存放兩條記錄。即得有兩條記錄才能形成樹的分支

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論