Mysql簡(jiǎn)易索引

一、沒(méi)有索引的時(shí)候如何查找

先忽略掉索引這個(gè)概念，如果現(xiàn)在直接要查某條記錄，要如何查找呢？

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

如果表中的記錄很少，一個(gè)頁(yè)就夠放，那么這時(shí)候有 2 種情況：

• 用主鍵為搜索條件：這時(shí)就是之前文章提過(guò)的方式，頁(yè)面目錄中用二分法快速定位到槽，然后遍歷該槽對(duì)應(yīng)分組的記錄，最終找到指定記錄。
• 用其他非主鍵的列為搜索條件：因?yàn)閿?shù)據(jù)頁(yè)中沒(méi)有為非主鍵列建立頁(yè)目錄，無(wú)法通過(guò)二分法快速定位槽，只能從 Infimum 記錄開(kāi)始一次遍歷單鏈表的每條記錄，效率低下。

在很多頁(yè)中查找

當(dāng)表中的記錄非常多，就會(huì)用到很多的數(shù)據(jù)頁(yè)來(lái)存儲(chǔ)，這時(shí)候需要 2 個(gè)步驟：

• 定位到記錄所在頁(yè)。
• 重復(fù)上述在一個(gè)頁(yè)中查找的過(guò)程。

總得來(lái)說(shuō)，當(dāng)沒(méi)有索引，我們無(wú)法快速定位到記錄所在頁(yè)，只能從第一頁(yè)沿著雙向鏈表(頁(yè)有前一頁(yè)和后一頁(yè))一直找下去，然后在每一頁(yè)中重復(fù)上述的過(guò)程查詢(xún)指定的記錄，需要遍歷所有記錄，這種方式非常耗時(shí)。

二、一個(gè)簡(jiǎn)易索引

既然是因?yàn)轫?yè)數(shù)太多導(dǎo)致定位記錄太慢，那如何解決呢？不妨參考一下“頁(yè)目錄”。

頁(yè)目錄就是為了根據(jù)主鍵快速定位一條記錄在頁(yè)中的位置而設(shè)置的。那么我們也可以想辦法為快速定位記錄所在的頁(yè)，搞一個(gè)“別的目錄”。

但是這個(gè)“別的目錄”要想完成還得干好 2 件事。

1. 下一頁(yè)用戶(hù)記錄的主鍵值必須大于上一頁(yè)的

假設(shè)，每個(gè)數(shù)據(jù)頁(yè)最多可以放 3 條記錄(實(shí)際上可以放很多)，那么現(xiàn)在向表里插入 3 條記錄，每條記錄有3個(gè)列 c1、c2、c3。為了看著方便，存儲(chǔ)行格式也簡(jiǎn)化下，只留關(guān)鍵屬性。注意中間3條是用戶(hù)記錄，首尾的2條是虛擬記錄 Infimum 和 Supremum。

此時(shí)，繼續(xù)插入 1 條記錄。按照假設(shè)的情況，現(xiàn)在需要多分配一個(gè)新的頁(yè)，所以 2 個(gè)頁(yè)之間就變成了這樣。

注意紅色字體顯示的2條記錄，本來(lái)主鍵 4 的記錄是新插入的，按理應(yīng)該放在新的頁(yè)。但是，為了滿(mǎn)足下一頁(yè)用戶(hù)記錄的主鍵值必須大于上一頁(yè)的用戶(hù)記錄主鍵值，做了諸如記錄移動(dòng)的操作，這個(gè)過(guò)程也可以稱(chēng)為“頁(yè)分裂”。

另外，為什么新頁(yè)是頁(yè) 28，而不是 11？因?yàn)轫?yè)在磁盤(pán)上可能并不挨著，它們只是通過(guò)維護(hù)上一頁(yè)和下一頁(yè)的編號(hào)而建立了鏈表關(guān)系。

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

現(xiàn)在繼續(xù)向表里增加數(shù)據(jù)，最終多個(gè)頁(yè)的關(guān)系是這樣：

因?yàn)檫@些頁(yè)在磁盤(pán)上可能不挨著，所有想要快速?gòu)倪@么多頁(yè)中根據(jù)主鍵快速定位某記錄，就要給它們編制一個(gè)目錄。

每個(gè)頁(yè)對(duì)應(yīng)一個(gè)目錄項(xiàng)，每個(gè)目錄項(xiàng)包括：

• 頁(yè)的用戶(hù)記錄中最小的主鍵值，用 key 來(lái)表示
• 頁(yè)號(hào)，用 page_no 表示

所以，給它們編好目錄之后就是這樣的關(guān)系：

那么，現(xiàn)在我想查找主鍵值為 20 的記錄，具體就分兩步走：

先從目錄項(xiàng)中根據(jù)二分法快速確定出主鍵值為 20 的記錄所在目錄項(xiàng) 3 中，且對(duì)應(yīng)的頁(yè)為 9。知道是在頁(yè) 9，重復(fù)之前的方式，找到最終目標(biāo)記錄。

到此，一個(gè)簡(jiǎn)易的方案完成。而完成的這個(gè)簡(jiǎn)易目錄，它有個(gè)別名，叫做索引。

三、簡(jiǎn)易索引暴露出的問(wèn)題

上述的簡(jiǎn)易索引是原書(shū)作者為了循序漸進(jìn)的幫助讀者理解而設(shè)置的內(nèi)容，這并不是innodb的索引方案。

那么針對(duì)上述的建議索引，看下有哪些問(wèn)題。

問(wèn)題一：

InnoDB 使用頁(yè)作為管理存儲(chǔ)空間的基本單位，也就是最多只能保存16kb的連續(xù)存儲(chǔ)。

當(dāng)表中記錄越來(lái)越多，此時(shí)就需要非常大的連續(xù)存儲(chǔ)空間才可以把所有的目錄項(xiàng)都裝下，這對(duì)大數(shù)據(jù)量的表來(lái)說(shuō)不現(xiàn)實(shí)。

問(wèn)題二：

我們經(jīng)常還要對(duì)記錄執(zhí)行增刪改操作，會(huì)牽一發(fā)而動(dòng)全身。

比如，上圖中我如果把頁(yè) 28 中的記錄都刪除，那么頁(yè) 28 就沒(méi)必要存在，進(jìn)而目錄項(xiàng) 2 也沒(méi)必要存在。這時(shí)候就需要把目錄項(xiàng) 2 后的目錄項(xiàng)都向前移動(dòng)一下。

就算不移動(dòng)，把目錄項(xiàng) 2 作為冗余放在目錄項(xiàng)列表中，仍然會(huì)浪費(fèi)很多的存儲(chǔ)空間。

所以，InnoDB 的作者發(fā)現(xiàn)了一種靈活管理所有目錄項(xiàng)的方式，詳見(jiàn)下一篇。

本文參考書(shū)籍：《mysql是怎樣運(yùn)行的》

以上就是Mysql簡(jiǎn)易索引方案講解的詳細(xì)內(nèi)容，更多關(guān)于Mysql簡(jiǎn)易索引的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論