---
tags: DDIA
---

# 索引

如何建立一個可供快速搜尋的資料庫。

[文本於此](https://evan361425.github.io/feedback/designing-data-intensive-applications/foundation-index/)

----


note:
上一次提到了在應用程式中，不同的商務邏輯會把資料轉換成不同的資料模型。

有關聯式資料庫適合簡單得多對多關係，文件式模型適合一對多關係，圖像式模型適合大量的多對多關係。

這次我們會討論資料庫如何透過索引快速從檔案中找到指定的資料，例如現在有一萬筆使用者資料，我想要快速找到使用者 123，不需要遍歷 10000 筆資料，可能找個三五次就找到了。

----

**沒有索引的狀況**

function set(key, value) {
  // echo "$1,$2" >> file
  file.append(key + ',' + value + '\n');
}

function get(key) {
  // grep "^$1," file | sed -e "s/^$1,//" | tail -n 1
  return file.read()
      .split('\n')
      .filter((line) => line.startsWith(key + ','))
      .pop()
      .substring(key.length + 1);
}

note:
可以看到這個資料庫在寫入時，擁有超高效能，甚至可以說不會再有比他更有效率（軟體面）的儲存方式了。 這種儲存方式稱為 log，附加（append）文字至檔案中。這種方式不會考慮之前有沒有儲存過該資料，而是直接新增至檔案尾處。所以並不會清除歷史紀錄。

> 這個方式並未考慮許多問題，例如：多工處理、清除歷史紀錄、容錯、資料毀損。

然而，當他讀取時，卻需要把所有文件都讀過一遍。當資料長兩倍時，可以預期他需要執行的時間也會提升至兩倍以上。為了解決這問題，索引出現了。

---

**索引的功能**


note:
可以看看圖片的例子理解索引的功能，和資料模型一樣，不同商務邏輯，需要使用不同的索引。

左邊如果是酪農，他可能會根據牛的功能透過柵欄去區分。今天這個農夫他想要抓一隻奶牛來擠奶，他就前往奶牛區去找就可以。反之如果他的農場是最右邊的那種方式，當他需要找奶牛的時候，就需要一隻一隻抓來確認。右邊這個區分方式聽起來像是我們一開始的例子，有新的牛進來了，我就打開閘門，丟進去，關閘門這樣就好。不需要把他引導到特定區域。

右邊的沒有索引，擁有最快速的寫入效能，但是讀取時就很麻煩。並不是沒有用途，而是要考慮商務邏輯。例如酪農今天要翻新農場，就在農場旁邊蓋一個小屋，先把牛趕到小屋裡面，這時候你不需要在這個臨時小屋設計精密的索引，你只是需要有個地方存他而已。這有點像是我們後面會提到的資料倉儲，我可能較為關心的是如何方便把資料匯進來？然後每次搜尋的時候，因為是統計資料，所以常常要查找所有資料並做統計。例如，農場裡的「牛的平均年齡」或者「最早進來的牛」。

中間的區分方式可能適合要養觀賞用的牛。

由上述例子可知，索引（Index）通常是在主要資料下**額外**建立的 metadata，並當有資料需要「寫入」時，更新這份 metadata。

工具的選擇常常都是在做權衡，索引在提升「讀取」效能的同時，便需要犧牲部分「寫入」效能。因此，資料庫通常不會預設讓所有資料成為索引，而是要根據開發人員根據每個應用程式的商務邏輯去設計。

----

- 日誌結構（log-structured）
- 散列（hash）
- 排序字串表（Sorted String Tables, SSTables）
- 頁導向（page-oriented）
- B 樹（B-Tree）

note:
我們介紹了索引的用途，和索引在資料庫中的定位，接下來我們來看看實作。
但在開始前，身為一個應用程式開發者，了解索引的底層設計有什麼好處？讓你在下搜尋語法的時候，清楚這語法下實際會運行的邏輯。除此之外，在調校資料庫的參數時，會知道他所代表的意義。

---

## 散列式索引

**Hash indexes**

<img src="https://i.imgur.com/pOxxy5n.png" height=400 />

note:
這是很常使用的方式，幾乎每個資料庫都會在一部份地方實作他。可以說是建立索引的重要基石。

這個範例是以 ID 為索引，我先在內存裡面存一張鍵值對照表，如果我要找 ID 是 456 的牛，我知道我要在檔案的 27 bytes 這個位置去找，不需要全部讀過一遍再找。

但是如果今天要找「種類」為「奶牛」的牛，就要建立第二組索引，後面會在次索引中談。

----

### 優劣勢

| 適合 | 反之會造成 |
| -------- | -------------- |
| 小量資料 | 內存不夠 |
| 大量I/O | |
| 隨機存取 | 範圍查詢低效率 |

note:
隨機存取代表不會有部分資料大量被存取，例如歷史訂單記錄，通常較新的會較常被存取。

----

**資料無限制的增長**


note:
為了避免單一資料過大，當超過一定大小（例如 8MB）就再新增一個檔案儲存資料。但是檔案的數量一樣會越長越多。

其中每個檔案我們稱為*資料段檔案*。

搜尋時，若在 segment 1 中的 hash index 找不到該 key，就往下一個 segment 找。

這時候就可以讓多個資料段檔案整併在一起。

----

### 壓縮整合


note:
這裡有兩個動作，一個是單一檔案的壓縮，第二個是兩個壓縮後的檔案做整合。

此行為是在背景執行，若執行到一半有讀寫的請求，會繼續使用舊的 segment，最後壓縮整合完畢後才使用新的 segment，並把舊的 segment 刪除。

----

### 其他細節

| 問題 | 解法 |
| ------------ | -------------------------- |
| 寫入時的編碼 | 二進位（binary） |
| 刪除資料 | 立碑（tombstone） |
| 資料庫重啟 | 快照（snapshot）滿的散列表 |
| 寫到一半中斷 | 核對和（checksum） |
| 同時寫入 | 附加（append）且不可變 |

note:
- 檔案格式，使用二進位的轉換，降低字串、數字等等多樣的變數格式轉換，例如表情符號。
- 如何刪除指定資料，需要在該 key-value 中的值位立碑（tombstone），在壓縮整併時，會自動捨棄該鍵值。
- 機器重啟時，重新獲得 hash index 需要全文讀取，非常耗時 會定時定量快照（snapshot）hash index 進檔案，避免機器重啟時的全文檢索。
- 寫入資料到一半時，機器壞掉 建立核對和（checksums），若核對和有錯，則不使用該值。
- 如何確保同步控制（Concurrency Control）時造成的錯誤，例如 A 資料寫到一半時，B 資料要開始寫入了，B 要如何等 A 寫完 僅開放一個寫入的線程（thread）。

----

### 日誌結構的好處

- 快速寫入
- 災難復原、併行處理簡單
- 定時合併降低資料破碎化（相較於頁導向偏向於更改舊有資料）

note:
一開始可能會覺得每次都重新寫新的資料而不是更改舊有資料很好記憶體，但是他優點很多。

第二點：不需考慮新舊資料並存，多個 append 後再合併。

log 有上述的優勢，就在此基礎之上建立了 SSTables

---

## 排序字串表

散列表會有內存不夠、範圍查詢效率低的缺點。如果每個檔案的鍵都是唯一且排序過的...

----


note:
排序過後，可以讓他

- 範圍查詢
- 稀疏式散列索引，避免內存不夠
- 鍵和鍵之間的資料區塊可以額外進行壓縮
- 整合可以非常快速且不需使用大量內存，後面在「如何整合」會提

----

### 如何排序


note:
就是先在內存中放一棵樹（可以是紅黑樹、AVL 樹），當樹達到一定大小的時候，存進資料系統中。

其策略如下：

- 每次資料進來，存進 in-memory 的樹狀結構（red-black tree 或 AVL tree），該樹狀結構可以保證新的資料會以排序過的方式存進結構中。
- 當樹狀結構越來越大，超過閥值（通常數個 MB），存進檔案（segment）裡。因為已經排序過，所以儲存的效率幾乎等於 I/O 的效率
- 當有讀取的請求時，先讀取 in-memory 再從最新的檔案依序讀取。
- 隨著時間進行，持續進行整合（merging）與壓縮（compaction）。
- 當機器壞掉時，in-memory 的資料就會遺失？ 每次新的寫入需求，都即時 append 到一個特殊檔案中，且不需排序，此檔案每次 in-memory 被清空時，都會跟著清空。此檔案的功能只用來當機器重啟時，重新放進 in-memory 的樹狀結構。

----

### 如何整合

<img src="https://i.imgur.com/QJL2UAm.png" height=500/>

note:
在做 merge 的過程，可以非常有效率且省空間。

----

### 其他細節

- 搜尋不存在的鍵很耗時
- 光暈過濾器（Bloom filter）
- 該以何種順序和時間點進行壓縮整合
- 新的和小的會被整合壓縮進舊的（sized-tiered）
- 低層級的會被整合壓縮進高層級的
- 等等
- 全文搜尋（Lucene）

note:
- Bloom filter 是一個特殊結構的檔案，會大略描述資料庫的狀態，並告訴你該鍵值是否存在
- 會記錄多個該值的簡易雜湊值（hash）
- 若下次存取該值時找不到雜湊值，就可以認定他不在這個資料庫中。
- 若全部的雜湊值皆存在，就代表有很高的可能性（根據雜湊演算法的數量和儲存該值的總量大小）確定該值存在於資料庫中
- 太過細節，不談（書中也沒提）。可以到文本去參閱，或參閱[此](https://docs.scylladb.com/architecture/compaction/compaction-strategies/)
- Elasticsearch 和 Solr 的底層演算法，唸法：loo-seen。
- 全文檢索比起 key-value 的檢索要更為複雜（後面有時間會提），但其邏輯類似：以 search words 作為 key，文章的 ID 作為 val

---

## B 樹

成熟且大量使用，since 1972。

頁導向（page-oriented）。

note:
上述提到的方法並不會去更新舊有資料，反之 B-Tree 則會去更新。 也就是他不需要做壓縮和整合的動作

----

### 如何搜尋


note:
每個區段代表一個節點，稱為頁。節點中會存在多個路徑指引（ref），其代表的是在範圍內的鍵值請去那裡找。

區塊分兩種

- 路徑區塊 - 用來導引至各個區塊，兩個 key 之間的資料即是存放這兩者之間的資料位置
- 資料區塊 - 用來儲存 key-value

例如上圖中，要找到使用者 251 就可以依序往下找。

每個頁是固定大小的（4KB），這做法是為了配合實際儲存進磁碟中電腦也是把他分段成固定大小的區段。

ref 數量代表分支因素（branching factor），以上圖為例即是 6，通常數量為數百。

----

### 容量

- 每頁大小：4KB
- 分支因素（branching factor）：500
- 層數：4

$500^4 * 4KB = 250 TB$

----

### 平衡


note:
當資料新增，樹就會這樣平衡，若資料更新變胖了，同樣適用。

因為B 樹是更新值而不像 append only 那種方式。也因為如此，相比於日誌結構的方式，寫入的效率會較低。

----

### 如何複寫

| | |
| ------------------------------------------------------------------------ | ----------------------------------------------------------------------- |
| <img src="https://i.imgur.com/X6isCfT.png" alt="機械式磁碟" height=200/> | <img src="https://i.imgur.com/31fNn8u.png" height=200 alt="固態硬碟" /> |
| 機械式磁碟 | 固態硬碟 |

note:
由於 B-Tree 會覆蓋先前儲存的值，這時就需要考慮到硬體是怎麼做覆寫的？

- 等待讀寫頭遇到正確位置，開始覆寫
- 韌體找到積體電路中頁的位置後會以固定單位大小寫入

多一種動作，多一層考慮，寫入效率會滴。

----

### 如何復原

預寫式日誌（Write-ahead logging, WAL）

note:
當更新資料時，可能會把 page 拆分兩個，或影響現有資料。做到一半時，機器壞了怎麼辦？

----

### 並行處理

閂鎖（Latches）避免找不到頁。

note:
當需要處理多工（concurrency control），一個線程在寫入時，樹狀結構可能是不穩定的（正在調整 B-Tree），需要利用 latches 演算法來鎖定該頁和母頁不被變更。

由此也可以看出 SSTable 和 B-Tree 在處理這問題的難易程度，SSTable 在壓縮整合的過程都是背景執行的，而不影響現有資料，最終執行完畢才會做更新。

要注意，Latches 不是 lock，lock 是用來避免破壞資料的一致性，latch 是底層的東西，避免線程之間的衝突。一般的資料庫操作是不能控制 Latches 的。

----

### 其他優化細節

- 快照
- 鍵的縮寫
- 有關係的頁放在附近
- 放入同層的頁的位置
- 碎形樹（fractal tree）

note:
- 災難復原時 WAF 之外，有些也利用快照的方式，建立副本，讓讀取時不必鎖定該樹。
- 不必使用完整的鍵，而是在確保獨立性的同時，取用縮寫即可。
- 讓相近的頁放在附近，但是當樹狀結構被更新，需要多做功去維持相近性。
- 增加同層附近頁的地址，加速搜尋
- 一些變形的 B 樹會整合日誌結構去做加速，碎形樹（fractal tree）

---

## 比較

資料庫效能和應用程式的類型有非常密切的關係。

- 排序字串表適合寫入，B 樹適合讀取。
- B 樹發展較成熟穩定，但是排序字串表正逐漸提升使用比例。

note:
接下來從各個面向看一下

----

### 寫入

寫入放大：B 樹 > 排序字串表
寫入效率：B 樹 < 排序字串表

寫入放大（write amplification）- 資料一生被重複寫入硬體的次數

note:
- B 樹次寫入進資料庫時時，都會寫入至少兩遍（WAL）。且每次更新頁的些微資料，都需要完整重新寫入（因為是改動舊資料）
- 排序字串表的寫入放大通常較低，但受壓縮和整合的演算法或使用者設定影響。
- 機械式硬碟（磁碟）在有順序性的寫入（append）會有較高的效能
- 固態硬碟因其是寫進晶片裡，適合緊密的資料寫入，故 append 較有效。（雖然韌體會盡量讓寫入保持緊密）

----

### 記憶體

B 樹 > 排序字串表（壓縮整合後）

note:
- B-Tree 通常需要較多記憶體，因為每個 page 都是固定大小，代表可能會有很多閒置空間
- SSTable 透過反覆壓縮整合，通常使用較少記憶體。但是若是過大的寫入量，可能會導致壓縮整合的速度來不及配合，進而無限量的增長記憶體，最終崩潰，需要替他準備監控系統。

----

### 系統耗損資源量

B 樹 < 排序字串表

note:
- SSTable 因其可能會需要反覆壓縮整合，儘管是背景執行，仍會吃掉機器的 CPU，導致速度降低
- B-Tree 其 latency 通常較穩定
- 除了 CPU，也要考慮資料的 I/O 能力。SSTable 需要壓縮整合，每次暫存的最新資料塊又需要足夠份量的資源來做寫入，導致和新資料的寫入互相競爭，拖慢速度。

----

### 處理競賽狀況

難度：B 樹 < 排序字串表

note:
- B-Tree 中，每個 key 只會有一個 value，可透過鎖定特定 page 來保持資料的一致性。
- SSTable 同一個 key 可能存在多個資料，在處理一致性時會需要較費工的演算法

---

## 次索引

不一定要唯一（unique），例如性別。

note:
上述都是想像索引為 primary index。

很多情況我們會需要增加除了主要 index 外的 index（_secondary indexes_），而這類的 index 不一定需要 unique，例如使用者的性別。

這種情況有兩種方式可以解決可重複性的 index。

1. 每個 secondary index 用 key-value 儲存，其中的 value 代表多個 _primary index_。例如，年齡 20 的 value 有 `[user-1, user-10]`
2. 用 _primary index_ 去整合 _secondary-key_。例如，手機為 09123 的 key-value 為 `1_09123-*user data*`

----

**怎麼存資料？**

- 堆積檔（heap file）
- 群聚式索引（clustered index）

note:
除此之外，避免同步的困難，都不會把完整資料放在多個 index 的 tree 中，而是存進

----

### 堆積檔

索引

使用者1 -> 堆積檔1-0
使用者10 -> 堆積檔1-30
年齡 20 -> 堆積檔1

堆積檔（heap file）

# ID,Name,Year
1,John,20
10,Marry,20

note:
所謂的 _heap file_ 就是存放多個同 _secondary index_ 的資料的檔案。

這方法使用起來很單純，因為當檔案有多個資料。例如上述中的 `[user-1, user-10]`，就直接以下列的方式做儲存

# ID,Name,Year
1,John,20
10,Marry,20

而 _primary index_ 的樹狀結構也是儲存 _heap file_ 的位置資訊。例如 user-10 的 value 可能就是 file1-30（第 30 個 byte 開始算起）。但是當資料更新時，就需要

1. 把所有 index 的資料庫都更新檔案位置。
2. 或在舊的 _heap file_ 中存放新的 _heap file_ 的位置，這樣搜尋時間會越來越長

----

### 群聚式索引

使用者1 -> John,20
使用者10 -> Marry,20
年齡 20 -> [使用者1, 使用者10]

覆蓋索引（covering index）

使用者1 -> John,20
使用者10 -> Marry,20
年齡 20 -> [使用者1:John, 使用者10:Marry]

note:
_clustered index_ 類似於 _primary index_，其意義代表存放資料的 index。當透過 _secondary indexes_ 找到特定資料的 _clustered index_ 時，再利用其找到資料。

以 MySQL 的 InnoDB 來說，每個 _primary index_ 就是 _clustered index_。

但是這種方式會需要：

- 額外的儲存空間（多開一個 Index Tree 去存）。
- 額外的搜尋時間

有些實作，會在 _secondary index_ 的地方存些資料（稱其為 _covering index_），有些實作只把資料存在 _clustered index_。

_cover_ 代表的意思就是，雖僅儲存部分的複寫資料，他卻可以 _cover_ 一些搜尋結果。
但是 covering index 也需要花一些功去維持資料的一致性。

---

## 其他

除了上述外，還有哪些有趣議題？

----

### 多欄位索引

- 串連索引（concatenated index），`姓` + `名`
- 二維同時檢索，HyperDex
- [R-Tree](https://www.gushiciku.cn/pl/gbAh/zh-tw)，點變成面

note:
上述有提到每次 query 只會參考一個 index。但是多個 index 去做篩選會大大加速搜尋的速度，該怎麼辦？

例如：我要搜尋經緯度在 `51.5151` `122.122122` 的商店。若是使用單一把緯度作 index，則可能搜尋到所有經度在 `-180~180` 範圍內的資訊，搞得有 index 跟沒 index 一樣。

簡單的方式是使用 _concatenated index_，也就是把兩個 index 整合再一起。例如，需要搜尋姓和名一樣的使用者，搜尋姓和名的 _concatenated index_：`王` `小明`，但是當搜尋條件改成`小明` `王`？

比起 _concatenated index_，更常使用的方式是重新設計一個儲存 index 的樹狀結構：[R-Tree](https://www.gushiciku.cn/pl/gbAh/zh-tw)。

其他可能需要多維度的 index 場景有：

- 電商需要搜尋長、寬、高的商品
- 新功能上線後的年輕註冊者

----

### 模糊索引

搜尋文字，但是考慮：

拼錯、文法轉換、同義詞、搭配詞

note:
有時要搜尋的 Index 是文字，而這串文字又是人類語言，這時在做搜尋時就可能需要考慮：

- 拼錯。
- 文法轉換。如：過去式、現在式。
- 同義詞。
- 該詞彙長搭配的詞。如：減肥、運動。

如同 SSTable 會利用稀疏的鍵（sparse keys）去減少 Index 的儲存量，Lucene(loo-seen) 的全文檢索資料庫也會把字詞的部分字元作為稀疏的鍵（類似 [_trie_](https://zh.wikipedia.org/wiki/Trie) 樹狀結構），加速模糊搜尋（fuzzy search）。

以樹狀結構作為點。

其他類型的 fuzzy index 的演算法可能為文章分類、機器學習等。

----

### 完全內存

有錢當大爺。

- 不在乎當電源切斷，是否需要維持資料：[Memcached](https://memcached.org)
- 需要維持資料：[VoltDB](https://github.com/VoltDB/voltdb)、[MemSQL](https://en.wikipedia.org/wiki/SingleStore)、[Oracle TimesTen](https://en.wikipedia.org/wiki/TimesTen)、[Redis](https://github.com/redis/redis)、[Couchbase](https://github.com/couchbase)

note:
把資料存進檔案（filesystem）和把資料都存進內存記憶體（RAM）比，有兩個好處

- 當電源切斷，記憶體的資料就沒了
- 便宜

但是 filesystem 是一個大儲藏室，你需要為其設計很多東西，包括定時定量的打掃、分層分區等等。

為了解決 filesystem 在讀寫的效率平衡，發展了很多機制：Index、File 大小和數量等等。

近來 RAM 越來越便宜，且若資料庫並不需要儲存大型資料，這時便發展出內存資料庫（in-memory database），其種類大致分兩種：

- 不在乎當電源切斷，是否需要維持資料：[Memcached](https://memcached.org)
- 需要維持資料：[VoltDB](https://github.com/VoltDB/voltdb)、[MemSQL](https://en.wikipedia.org/wiki/SingleStore)、[Oracle TimesTen](https://en.wikipedia.org/wiki/TimesTen)、[Redis](https://github.com/redis/redis)、[Couchbase](https://github.com/couchbase)
- 透過特殊硬體（不斷電系統）
- 寫 Log，這方法除維持資料，也擁有提供備份、方便分析等好處。
- 定時快照。
- 透過其他機器複製資料（replicate）

內存資料庫不僅僅因為讀取時不接觸 filesystem，其儲存的檔案格式已經經過解析（parse），降低了解析所需消耗的效能。這同時也讓內存資料庫允許更多種類的儲存，例如佇列（queue）或叢集（set）。

除此之外，近來也有需多研究，讓內存資料庫不再受限於內存記憶體的大小，當大小超出其負荷時，資料庫會把最久沒存取的資料放進 filesystem 中，類似 OS 在操作大型資料時的做法，然而卻更為精準，而非一次僅能控制一組記憶體區塊。

---

## 總結

資料怎麼存、取？

- 日誌結構、頁導向
- 次索引（secondary index）
- 多欄位索引、模糊索引、完全內存

note:
這篇只是第三章的一半而已，由此可知書中雖然是輕描淡寫地說明概念，但其實背後有很多可以深入研究的點。

日誌結構適合寫入，頁導向透過樹狀結構可以快速搜尋，但是會改舊的資料，所以寫入時會有些困難。

我們也提到當有不止一個索引，例如搜尋人的 ID 外，也要搜尋人的性別，可以使用次欄位。

其他還有
- 搜尋地理位置等多維度的多欄位。
- 並非完全匹配的模糊索引。
- 直接使用內存來儲存資料。

----

散列表（Hash table）

- 基礎，適合大量隨機地存取小筆資料。
- Riak 的 [Bitcask](https://github.com/basho/bitcask)

note:
散列表適合大量隨機地存取小筆資料，例如統計瀏覽頁面的數量。但是當資料量過大時，會造成內存不夠而且也不能有效的範圍存取。

----

排序字串表（Sorted String Tables, SSTables）。

- 範圍存取、稀疏鍵、高效壓縮整合。
- [Google LevelDB](https://github.com/google/leveldb)
- [Facebook RocksDB](https://github.com/facebook/rocksdb) - based on LevelDB
- [Apache Cassandra](https://github.com/apache/cassandra)(類似) - based on Big Table paper
- [Apache HBase](https://github.com/apache/cassandra)(類似) - based on Big Table paper
- [Lucene](https://github.com/apache/lucene)（被 [Elasticsearch](https://github.com/elastic/elasticsearch) 和 [Solr](https://github.com/apache/lucene-solr) 使用） - _term dictionaries_

note:
以散列表為基礎，發展出了排序字串表。可以有效得做範圍存取且透過稀疏鍵（sparse key）可以避免使用過多內存。然後再做壓縮整合時可以非常有效率。

----

頁導向（page-oriented）

**B 樹**

- 更新原址資料（update-in-place）
- 資料切塊成固定大小的頁（page）
- 大部分的資料庫都實作這類方式

note:
不管是 B+ 樹、B* 樹等等的變形

----

### 預告