資料庫核心：索引，你知道多少？
- 2019 年 12 月 31 日
- 筆記
【這是一猿小講的第 80 篇原創分享】
今天聊點面試中經常聊的話題 —— 索引！雖然網上已經有很多類似的文章啦，但是我們開啟的方式卻不同。
01. 體驗很重要
首先打造一個世界上最簡單的迷你版資料庫，一起來圍觀體驗。
#!/bin/bash # 迷你版資料庫對外提供的函數 method=$1 # 向迷你版資料庫中存放的key key=$2 # 向迷你版資料庫中存儲的value value=$3 # key-value 數據存儲 function db_set() { echo "$key,$value" >> database } # 根據 key 查詢資料庫存儲的 value function db_get() { grep "^$key," database | sed -e "s/^$key,//" | tail -n 1 } case $method in (db_set) db_set ;; (db_get) db_get ;; (*) echo "Error method" ;; esac
這款迷你版的資料庫，實現了一個 key-value 的簡易數據存儲，主要由數據存儲（db_set）、查詢（db_get）兩個函數構成。
當我們調用 db_set key value，它將在資料庫中保存你所輸入的 key 和 value。
其中 key 和 value 幾乎可以是任何內容，例如，值可以是一個 JSON 文檔。然後，當我們調用 db_get key，它會查找與輸入 key 相關聯的最新值並返回。
例如，向迷你資料庫插入數據。
./minidb.sh db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' ./minidb.sh db_set 42 '{"name":"San Francisco","attractions":["Godlen Gate Bridge"]}'
然後，從迷你資料庫查詢指定的數據。
./minidb.sh db_get 42
./minidb.sh db_get 123456
迷你資料庫到這就算體驗完了，原理超級簡單，就是往 database 文件尾部追加數據就好了，其實許多資料庫內部實現都和 db_set 類似，它們都使用日誌文件，因為它只支援追加式的方式更新。
但是，大家有沒有想過？
如果日誌文件保存了大量的記錄，那麼資料庫的查詢（db_get）肯定會非常差。每次要查找一個 key 對應的值，就必須掃描整個資料庫文件來查找 key 出現的位置，這樣開銷會很大，有沒有高效的解決方案呢？
為了高效地查找資料庫中特定的 key 的值，那麼就需要引入新的數據結構 —— 索引！
02. 索引
哈希索引。
我們繼續以 key-value 數據的索引為基礎，假設數據存儲全部採用追加式的文件組成，像上面的迷你資料庫那樣，數據都追加到 database 文件中。那麼最簡單的索引策略，莫過於把每個 key 對應文件中的位元組偏移量（也就是在文件中的位置），保存到記憶體中的哈希表中（Hashtable 或 HashMap），這樣就可以快速找到每個值的位置。
每當向資料庫追加新的 key-value 時，也就需要更新記憶體中的 HashMap 來記錄剛剛寫入數據的偏移量；當查找某個值時，使用 HashMap 來找到文件中的存儲位置，然後讀取其內容。
上面的方式雖然很簡單，但是的確是一個可行的方法。靜下來思考，多數實現其實都是換湯不換藥，變化無非也就是通過計算 key 的 hash 值，然後映射對應的 value。
但是哈希索引使用起來，存在一定的問題（注意，這塊面試的時候經常會聊呦！）。
- 哈希表必須全部放入記憶體，如果有大量的 key 的情況下，表現就不會那麼好啦；
- 區間查詢效率不太好，例如要查詢 key0000 和 key9999 區間的所有鍵，只能採用逐個查找的方式查詢每一個鍵；
- 由於哈希索引數據沒有按照索引值順序存儲，所以無法用來進行排序。
- 。。。。。。
面對哈希索引的一些限制，在 LSM-Tree、B-Tree 等索引結構上得到了很大的解決，時間關係，今天就不深入展開啦。
03. 常見面試題
- B-Tree 與 哈希索引的比較？ 參見官方答案： https://dev.mysql.com/doc/refman/8.0/en/index-btree-hash.html
- 索引能提升查詢效率，是不是越多越好呢？ 索引是額外的數據結構，但是維護這個額外的數據結構肯定也會引入開銷，特別是在新數據寫入的時候。由於每次寫數據時，需要更新索引，所以索引也會降低寫的速度，設計系統的時候一定要進行權衡。
- 聊聊哈希表、二叉搜索樹、B-Tree、B+Tree 常見數據結構？學習演算法的好網址，建議收藏。 https://www.cs.usfca.edu/~galles/visualization/OpenHash.html https://www.cs.usfca.edu/~galles/visualization/BST.html https://www.cs.usfca.edu/~galles/visualization/BTree.html https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
文中有些觀點來自於近期看的一本書《數據密集型應用系統設計》，開卷有益，希望大家抽時間多讀書、多看報、少吃零食多睡覺。最後，希望通過本次簡短的分享，都有所啟發。
