Mysql簡易索引

一、沒有索引的時候如何查找

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

在一個頁中查找

如果表中的記錄很少，一個頁就夠放，那么這時候有 2 種情況：

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

在很多頁中查找

當(dāng)表中的記錄非常多，就會用到很多的數(shù)據(jù)頁來存儲，這時候需要 2 個步驟：

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

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

二、一個簡易索引

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

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

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

1. 下一頁用戶記錄的主鍵值必須大于上一頁的

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

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

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

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

2. 給所有的頁建立一個目錄項

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

因為這些頁在磁盤上可能不挨著，所有想要快速從這么多頁中根據(jù)主鍵快速定位某記錄，就要給它們編制一個目錄。

每個頁對應(yīng)一個目錄項，每個目錄項包括：

• 頁的用戶記錄中最小的主鍵值，用 key 來表示
• 頁號，用 page_no 表示

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

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

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

到此，一個簡易的方案完成。而完成的這個簡易目錄，它有個別名，叫做索引。

三、簡易索引暴露出的問題

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

那么針對上述的建議索引，看下有哪些問題。

問題一：

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

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

問題二：

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

比如，上圖中我如果把頁 28 中的記錄都刪除，那么頁 28 就沒必要存在，進而目錄項 2 也沒必要存在。這時候就需要把目錄項 2 后的目錄項都向前移動一下。

就算不移動，把目錄項 2 作為冗余放在目錄項列表中，仍然會浪費很多的存儲空間。

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

本文參考書籍：《mysql是怎樣運行的》

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

最新評論