今天我們來聊聊 DB 的 index。

What is Database index？

簡單來說，資料庫索引是一種可以加速資料查詢的資料結構，他是一種有序的結構。他就像書的目錄頁一樣，讓我們透過目錄可以快速找到我們要找的頁數，而不用翻遍整本書。在資料庫中，索引的作用就是指向資料表中特定資料的「指標」，幫助我們快速定位所需的 row 。

索引的原理

在講索引的原理之前，我們先了解一下資料庫是怎麼查詢資料的。

沒有索引的情況

• Full Table Scan:

  • 假設我們有一個 table ，並且我們想要查找特定條件下的紀錄。資料庫在查找的過程中，可能會遍歷整個表格來找到符合條件的資料，這個過程稱為全表掃描（Full Table Scan）。這樣的方式在資料量很小的時候你會覺得速度沒有差很多，但如果你的 table 是幾千萬筆的超大型 table，查詢時間可能會變得非常長。
  • 這種查找方式的時間複雜度為 O(n)，也就是與資料表的大小成正比。隨著資料表中紀錄的數量增加，查詢時間會變得越來越長。

• 無索引的缺點：

  • 效能差：當資料表變得非常龐大時，查詢時間可能會變得不可接受。
  • 資源消耗高：全表掃描會佔用大量的 CPU 和 I/O 資源，影響資料庫的整體效能。

非叢集索引

一般來說，我們自己設定的索引都會是一種非叢集索引(Non-clustered Indexes)，因為叢集索引只針對一個欄位，這個我們待會會講到，現在先介紹非叢集索引是如何運作的。

舉個例子最快理解，今天我們把 record_date 設成 index，我們要找 2024-09-26

• 從 root 節點開始，首先比較 2024-09-25 和 root 的值 2024-09-26，由於 26 > 25 ，我們進入右邊子節點 2024-09-28 。
• 接著比較 28 與 26 最後進到左子節點找到 2024-09-26。
• 這樣的搜尋方法有點類似 Binary search，時間複雜度由 Full Table Scan 的 O(N) -> O(logN)

                        [2024-09-25]
               /                                \
       [2024-09-22]                                 [2024-09-28]
    /             \                             /              \
[2024-09-20] [2024-09-23, 2024-09-24] [2024-09-26, 2024-09-27] [2024-09-29]

在 B-tree 索引中，每個子節點不僅僅儲存索引值（如 record_date），他還包含一個指向實際資料位置的 pointer。這些 pointer 指向資料表中實際儲存的 row。當查詢到索引時，就會透過 pointer 馬上找到對應的資料。

以下圖為例，Index 是有序的 friend 資料結構，並會指向 friends 的 table。

圖片來源

叢集索引

叢集索引(clustered Indexes)是每個表的唯一索引(unique index)，設有叢集索引的 table 中，table 的資料實際上是按照索引鍵的順序來儲存的，因此該索引幾乎都會是 table 的主鍵。

• 一張 table 只能有一個叢集索引，因為資料只能根據一個欄位來排序。
• 在大多數資料庫中，建立 table 的 Primary Key（主鍵)時，資料庫會自動幫它建立一個叢集索引。這是因為主鍵通常是唯一且用來查找資料的主要欄位，使用叢集索引可以有效加速查詢。

可以看到下圖跟上面的非叢集索引比起來，它就會完全參照它的順序。

圖片來源

索引的限制

雖然索引大幅提升了查詢效能，但也有一些限制需要考量：

• 儲存成本：因為還需要額外的空間來存放索引。所以也要針對該欄位的一些情況來考量，不是每個欄位建立索引都能帶來更好的改變。
• 維護成本：當資料表中的資料發生變化（插入、更新或刪除）時，資料庫也需要同步更新索引，這可能會影響寫入操作的效能。

適合索引的情況

• 欄位常常被拿來當 WHERE 的條件。
• 欄位的 Cardinality 較高，指的是這個欄位是不是很多不同的資料，這樣建立索引後，才能有效加快查詢的速度。
• 當 Cardinality 太低，如 Male/Female 的欄位，就只會浪費空間，而沒有正面的影響。
  • 欄位較少變更。
• 欄位的長度不要太長，欄位太長會導致索引的大小過大，反而降低效能。

Reference

• https://www.atlassian.com/data/sql/how-indexing-works