[Rails 效能優化] 資料庫索引 Database Indexing

如何優化資料庫查詢的速度

上篇講到 Rails 資料庫存取的 N+1 問題,並且如何使用 includes(與它的朋友們) 下有效率指令,在這裡:[Rails 效能優化] 資料庫關聯查詢。這一篇不講操作層面,從設計層面來看講如何讓指令有效率的執行。

資料庫索引(Database Index)

一般來說,當我們想要從資料庫找符合某特定條件的資料,資料庫的標準程序是一行一行檢查,並且問自己「這是符合條件的的資料嗎?」如果是,就把資料拿出來,如果不是,就繼續檢查直到結束。江湖術語是 Full Table Scan

可想而知,當資料量一大,資料庫要找到資料的時間就會越來越長。「有沒有方法能夠讓資料庫不用一行一行爬也可以找到想要的資料?」有的!就是索引(Index)。索引其實是一種資料結構(data structure),我們看不到,因為它通常存在我們使用的資料庫管理系統(DBSM, Database Management System)裡面。

索引到底是如何運作的?

大部分的 DBSM 都會預設把主鍵(Primary Key / ID)加上索引,現在假設有一個資料表(table)A,A 的 ID 欄位有被加上索引,則實際上在資料庫中,有另外一張表(我們叫它 A’)裡面儲存了 A 裡面的所有 ID,而 A’ 每一個資料(ID)都對應到 A 中的完整資料。

所以今天我們想要找 A 中一個 ID = 3 的資料,資料庫會用 Binary Search Algorithm(或是其他也很快的演算法,通常時間複雜度會是 O(log(N))在 A’ 中快速找到 ID = 3 這筆資料,然後再從這筆資料連到 A 中對應的資料。

實際情況下,A’ 這個擁有 A 的 ID 資料的儲存結構通常會以 Hash 或是 B-tree 實作。Hash 在搜尋不能重複的資料時,效率會比較好,因此適合用在主索引鍵(Primary Index)和唯一索引(Unique Index);B-tree 適合用在可以允許重複資料的一般索引(Non-Unique Index)。

非主要欄位 Non-Primary Column

端看使用者最常使用什麼欄位來獲取資料,我們可以自己定義主鍵以外的索引,比如說 first_name;或是使用複合式索引(composite indexes),比如說 first_name + last_name。

索引結構(Index Architecture)

索引可以分成叢集(Clustered)與非叢集(Non-Clustered)兩種類型。

叢集 Clustered

Clustering alters the data block into a certain distinct order to match the index, resulting in the row data being stored in order.

摘錄自維基百科

叢集索引(Clustered Index)直接修改原本的資料表順序,將資料按照要索引的欄位排,就是一個王牌的意思。如此可以讓資料搜尋非常有效率,尤其是依照順序(accessed sequentially)或是一個範圍連續資料的時候。想當然爾,一張資料表只會有一個叢集索引,通常就是主鍵欄位(primary key column)。

因為叢集索引會調整資料順序,所以它最大的特色就是實體的資料(physical data rows)跟索引表(index block/index table)中的順序會是一樣的。

非叢集 Non-Clustered

非叢集索引(Non-Clustered Index)是指不管資料在原本資料表中的排序,而在索引表中自己依照索引值建立排列。與叢集索引的差別是,叢集索引的排列順序就是實際上資料的排列順序,而非叢集索引的排列順序不會/無法影響到實際資料的排列順序。也因此,一個資料表中可以包含很多非叢集索引。

通常會使用非叢集索引的會是在 JOIN, WHERE 或是 ORDER BY 使用的非主鍵欄位(non-primary key columns)。

使用索引的限制

講完了好處,接下來要講講索引的限制了。首先,索引之所以可以增加資料庫的效率,是因為它額外創造了一張表來儲存索引的資料,也就是拿空間換取時間,這也是為什麼我們不能為每個欄位都加上索引的原因。再來,我們對資料庫做的任何更動都會連動到索引表(Index Table),如果這是一張更動很頻繁的表,那就會製造額外的負擔。

所以要如何在查詢速度與儲存空間/更新成本之間找到平衡,就是設計索引時需要好好思索的。

另外,就算加了索引,也不是萬能的。我們來看兩個狀況:

SELECT first_name FROM people WHERE last_name = ‘Shih’;

這個例子要尋找在people 中所有 last_name 是 ‘Shih’ 的 first_name資料,如果 last_name 欄位沒有被索引,那麼就會是一個 full table scan。如果有索引,那資料庫系統就會使用 B-tree 結構來尋找,大大增加搜尋效率,很好!

SELECT full_name FROM people WHERE full_name LIKE ‘%Shih’;

現在假設我們是要從 people中找到 full_name 的結尾是 ‘Shih’ 的full_name 資料, 這時候,就算full_name 有索引,還是會引發 full table scan,因為索引的預設搜尋方向是從左到右,當搜尋的字串開頭是外卡(wildcard),資料庫系統就沒有辦法使用 B-tree 了。

要解決這個困境可以增加一個 reverse(full_name) 的索引,然後改變 SQL 查詢:

SELECT full_name FROM people WHERE reverse(full_name) LIKE reverse(‘Shih’);

當然,我們就要自己衡量這樣值不值得了。

通常會加上索引的欄位

  • 主鍵 Primary Key(通常是預設)
  • 外部鍵 Foreign Key
  • 常被放在查詢子句中(ORDER, WHERE, GROUP)的欄位

在 Rails 的資料庫中加上索引的方法

其實只要在 migration 檔案中加上 add_index(table, columns, options)就好了。比如說今天我們要在 people 資料表中為 full_name 加上索引,那步驟如下:

  1. 新增 migration 檔案:終端機中執行 rails g migration AddFullNameIndexToPeople(名稱隨意)
  2. 目錄中找到這個新增的檔案,修改裡面的程式碼:
class MigrationName < ActiveRecord::Migration[5.2]
def change
a
dd_index(:people, :full_name)
end
end

3. 終端機中執行 rake db:migrate

輕輕鬆鬆。

更完整的用法請參考 API dock

好的,下一篇來講 transaction!

雖然已盡能力所及地確保資料的正確性,但我恐怕還是會有不對/不精確的觀念或用字,如果願意指正我的話我會非常感激!

參考資料

Date, Chris J. An Introduction to Database Systems C.J. Date. Pearson Addison-Wesley, 2004.

Database index - Wikipedia
en.wikipedia.org
Database — Indexing, Transactions & Stored Procedures (Part 9)
medium.com
add_index (ActiveRecord::ConnectionAdapters::SchemaStatements) - APIdock
apidock.com

MySQL 超新手入門(9)表格與索引

文章同步發表於 Medium


  • Find me at