【Mysql】一個簡易的索引方案

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

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

在一個頁中查找

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

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

在很多頁中查找

當表中的記錄非常多，就會用到很多的數據頁來存儲，這時候需要 2 個步驟：

定位到記錄所在頁。
重複上述在一個頁中查找的過程。

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

二、一個簡易索引

既然是因為頁數太多導致定位記錄太慢，那如何解決呢？不妨參考一下「頁目錄」。

頁目錄就是為了根據主鍵快速定位一條記錄在頁中的位置而設置的。那麼我們也可以想辦法為快速定位記錄所在的頁，搞一個「別的目錄」。

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

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

假設，每個數據頁最多可以放 3 條記錄（實際上可以放很多），那麼現在向表裡插入 3 條記錄，每條記錄有3個列 c1、c2、c3。為了看着方便，存儲行格式也簡化下，只留關鍵屬性。注意中間3條是用戶記錄，首尾的2條是虛擬記錄 Infimum 和 Supremum。

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

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

另外，為什麼新頁是頁 28，而不是 11？因為頁在磁盤上可能並不挨着，它們只是通過維護上一頁和下一頁的編號而建立了鏈表關係。

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

現在繼續向表裡增加數據，最終多個頁的關係是這樣：

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

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

所以，給它們編好目錄之後就是這樣的關係：

那麼，現在我想查找主鍵值為 20 的記錄，具體就分兩步走：

先從目錄項中根據二分法快速確定出主鍵值為 20 的記錄所在目錄項 3 中，且對應的頁為 9。
知道是在頁 9，重複之前的方式，找到最終目標記錄。

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

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

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

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

問題一：

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

當表中記錄越來越多，此時就需要非常大的連續存儲空間才可以把所有的目錄項都裝下，這對大數據量的表來說不現實。

問題二：

我們經常還要對記錄執行增刪改操作，會牽一髮而動全身。

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

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

所以，InnoDB 的作者發現了一種靈活管理所有目錄項的方式，詳見下一篇。

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

Tags: 把蘋果咬哭的不規律日常數據庫