# Database 的 Index 是什麼？

Index 索引，它的用途就如同一些書籍的最後幾頁，標示了書中所提到的「詞彙」對應的頁數。下圖為 Thinking in Java 2/e 繁體中文版的索引頁：

<img src="https://i.imgur.com/XDHll8k.png" width="400"/>

而 Database 的 Index 也是相似的功能，只是它會針對 Key 或是獨立建立的 Index 來當成索引。以上圖為例，若是我想要尋找 `abstract` 相關的概念，我可以在圖上的這些頁數中找到：

<img src="https://i.imgur.com/2dKmlJQ.png" width="400"/>

試想一種情況，若是沒有 `index` 該如何找到它們呢？簡單暴力的方法

> 每一頁都去翻開來看，並且記錄下它們的頁數。
>

## 資料庫如何查找資料？

先不論特定廠牌或 engine 的實作，資料庫查找資料的原則就是：

- 如果「條件允許」且「有 index」，優先使用 index 取得資料
- 如果沒有能使用 index 的情況，那就每一筆都查看看

這裡要注意，使用 index 的情境是：

- 你想查的資料有對應的 index
- 你下的 QUERY 子句，符合使用 index 的條件

相反的情況，就是無法使用 index 的情境。這情境有個專有名詞 `full table scan`，也就是前面提到的，書沒有替讀者準備索引頁，所以讀者若想要知道哪些字詞的位置，只好每一頁翻開來看。

## 用程式碼來舉個例子

想像一下你有一個 `table` 裡面有 3 筆資料，每一筆資料有 2 個欄位，分別是 id 與 name。如果，我想找是不是 `name` 有 cat 的資料，它可以寫成這個樣子：

table = [dict(id=1, name="cat"), dict(id=2, name="dog"), dict(id=3, name="bird")]

def find_by_name(name: str):
    result = []
    for x in table:
        if x['name'] == name:
            result.append(x)
    return result

if __name__ == '__main__':
    print(find_by_name("cat"))
    print(find_by_name("what?"))

由於，我們對於這個 table 沒有建立索引，所以它只好做 `full table scan` 囉！若是分析它的時間複雜度，那就是 `O(n)`。輸出的結果為：

[{'id': 1, 'name': 'cat'}]
[]

現在開始想像，你的 `table` 其實不是只有 3 筆資料，而是百萬筆的時候，那麼 `O(n)` 就會因為 n 變大而讓查詢變久了。想要讓它變快，就是得靠建立 index。那麼 Database 有提供 `建立 index` 的功能，常見的 index 為 b-tree 與 hash。我們示範概念的話，用 hash 來實作會容易些，畢竟 b-tree 寫起來挺麻煩的。

我們簡單用個 dictionary 來存 index，而它的 `key` 就是 `name` 欄位的值，它的 `value` 用個 list 來存放，因為有機會同一個 key 有多筆資料：

index_on_name = dict()

def build_index_on_name():
    for x in table:
        if x['name'] not in index_on_name:
            index_on_name[x['name']] = []
        index_on_name[x['name']].append(x)

我們可以簡單把它印出來感受一下：

build_index_on_name()
print(index_on_name)

輸出結果為：

{'cat': [{'id': 1, 'name': 'cat'}], 'dog': [{'id': 2, 'name': 'dog'}], 'bird': [{'id': 3, 'name': 'bird'}]}

接著，我們可以來實作 `使用 index` 的查詢了，用它的查詢結果會是與 full table scan 一致的，但查詢的效率轉成了 `O(1)`：

def find_by_name_with_index(name: str):
    return index_on_name.get(name, [])

## Rebuild Index 與 Incremental build Index

我們重新看一下 `build_index_on_name` 的實作：

index_on_name = dict()

def build_index_on_name():
    for x in table:
        if x['name'] not in index_on_name:
            index_on_name[x['name']] = []
        index_on_name[x['name']].append(x)

你會想要問，它明明也是 `O(n)` 為什麼能加速呢？首先，這是建立一個 `全新的` Index 的流程，建好一次後，後續可以用上 index 的查詢就是 `O(1)` 囉！那麼不是全新的建立 Index 的流程，會是怎麼樣呢？我們來改寫一下程式：

table = []
index_on_name = dict()

def find_by_name(name: str):
    result = []
    for x in table:
        if x['name'] == name:
            result.append(x)
    return result

def find_by_name_with_index(name: str):
    return index_on_name.get(name, [])

def add_data(data: dict):
    table.append(data)

    # update index
    name = data['name']
    if name not in index_on_name:
        index_on_name[name] = []
    index_on_name[name].append(data)

if __name__ == '__main__':
    add_data(dict(id=1, name="cat"))
    add_data(dict(id=2, name="dog"))
    add_data(dict(id=3, name="bird"))

    print(find_by_name("cat"))
    print(find_by_name("what?"))

    print(find_by_name_with_index("cat"))
    print(find_by_name_with_index("what?"))

在這程式中，你會發現多出了 `add_data`，可以理解就是平時我們針 table 做 `insert` 的動作，而在增加資料的同時，它會去 `update index`。除非，我們想要重建，或第一次針對某些條件建立 index，才會呼叫到 `build_index_on_name` 函式了。

這裡有個得提醒的要點是，index 包含在 `insert` 的流程中，它會影響寫入的效率，所以「適量」的 index 才是好的，示意的程式如下。當你建立太多的 index 時，你新增資料不可避免地比原先慢：

def add_data(data: dict):
    table.append(data)

    # update index 1
    # update index 2
    # update index 3
    # update index 4
    # update index 5
    # update index ...

同理，不是只有 `insert` 會需要更新 index，`update` 與 `delete` 也都有更新 index 的流程。

## Index 的適用條件

在最開始有提到，要在查詢用上 index 得條件適當才行，以目前的例子來說都是針對 `name` 這個欄位建立的 index，如果欄位擴充了，還多了電話：

def find_by_name_with_index(name: str):
    return index_on_name.get(name, [])

由於，我們並沒有事先建好 `name` 與 `phone` 的組合，那麼資料庫會使用最原始的 full table scan：

def find_by_name_and_phone_with_index(name: str, phone: str):
    return index_on_???????.get(name, [])

而 Index 的適用條件，要先過 `WHERE` 子句這一關，也就是：

WHERE name="cat" AND phone="9527"

當你的 QUERY 吃不到 index 時，通常可以靠資料庫的分析工具得到印證：

> MySQL 與 Postgres 都有的 EXPLAIN 查詢
>

對應的解決有 2 個選擇：

- 建新的 index，但記得考慮 `資料異動` 時對效能的影響
- 利用既有的 index 查出資料，再縮小範圍

舉例來說，目前這句因為有針對 `name` 的 index 而能快速找到結果，而且是 `O(1)`：

SELECT * FROM table WHERE name="cat"

那麼，只要先利用現用 index 的查詢 `O(1)` 快速縮小範圍，讓後續過濾資料 `O(n)` 的 n 變小就行了 (示範概念，我沒有驗過 SQL 能不能動)：

SELECT * FROM (SELECT * FROM table WHERE name="cat") a WHERE a.phone="9527"

PS. 要提醒這裡的 `O(1)` 只是舉例，如果是 [B-tree](https://en.wikipedia.org/wiki/B-tree) 那會是 `O(log n)`，要看選用的 index 類型而定，常理來說都比 full table scan 有效率。

## 相關練習

1. 真的使用 Database 去建立資料
2. 將 Python 的部分，改寫成自己喜歡的語言
2. 理解常用資料庫對`full table scan` 的描述，與 `沒有吃到 index` 的常見寫法