Mysql簡易索引方案分析

Mysql簡易索引

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

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

在一個頁面中找出

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

• 用主鍵為搜尋條件：這時就是先前文章提過的方式，頁面目錄中用二分法快速定位到槽，然後遍歷該槽對應分組的記錄，最終找到指定記錄。

• 用其他非主鍵的列為搜尋條件：因為資料頁中沒有為非主鍵列建立頁目錄，無法透過二分法快速定位槽，只能從Infimum 記錄開始一次遍歷單鍊錶的每筆記錄，效率低。

在很多頁中查找

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

• 定位到記錄所在頁面。

• 重複上述在一個頁面中尋找的過程。

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

二、一個簡易索引

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

頁目錄就是為了根據主鍵快速定位一筆記錄在頁中的位置而設定的。因此，我們可以探討一種方法，即建立一個「其他目錄」來快速定位記錄所在的頁面。

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

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

假設，每個資料頁最多可以放3 筆記錄(實際上可以放很多)，那麼現在向表裡插入3 筆記錄，每筆記錄有3個列c1、c2、c3。為了看著方便，儲存行格式也簡化下，只留關鍵屬性。虛擬記錄Infimum和Supremum分別位於使用者記錄的首尾，中間有3筆使用者記錄。

此時，繼續插入 1 筆記錄。在假設的情況下，需要至少分配一個新頁面，因此這兩個頁面將被重新分配並重新排列。

請注意紅色字體顯示的兩筆記錄，其中包含了一個新插入的主鍵為 4 的記錄，應該被放在新頁上。但是，為了滿足下一頁使用者記錄的主鍵值必須大於上一頁的使用者記錄主鍵值，做了諸如記錄移動的操作，這個過程也可以稱為「頁分裂」。

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

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

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

為了從多個不相鄰的頁面快速定位某個記錄，需要為它們編制一個目錄，因為這些頁面在磁碟上可能不是連續的。

每個頁對應一個目錄項，每個目錄項包含：

頁的使用者記錄的使用者記錄中最小的主鍵值，用key 來表示

頁號，用page_no 表示

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

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

利用二分法從目錄項中快速確定主鍵值為20 的記錄在目錄項3，且它所在的頁碼為9。知道是在頁 9，重複之前的方式，找到最終目標記​​錄。

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

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

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

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

###問題一：######InnoDB 使用頁面作為管理儲存空間的基本單位，也就是最多只能保存16kb的連續儲存。 ######當表中記錄越來越多，此時就需要非常大的連續儲存空間才可以把所有的目錄項目都裝下，這對大數據量的表來說不切實際。 ###

問題二：

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

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

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

以上是Mysql簡易索引方案分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！