h2database 是使用Java 編寫的開源資料庫，相容ANSI-SQL89。
即實現了常規基於 BTree 的儲存引擎，又支援紀錄檔結構儲存引擎。功能非常豐富（死鎖檢測機制、事務特性、MVCC、運維工具等），資料庫學習非常好的案例。
本文理論結合實踐，通過BTree 索引的設計和實現，更好的理解資料庫索引相關的知識點以及優化原理。
h2database 預設使用的 MVStore 儲存引擎，如果要使用 基於 BTree 的儲存引擎，需要特別指定（如下範例程式碼 jdbcUrl）。
以下是常規儲存引擎(BTree 結構) 相關的關鍵類。
BTree 的資料結構可以從網上查到詳細的描述和講解，不做過多贅述。
需要特別說明的是：PageStore。我們資料查詢和優化關鍵的快取、磁碟讀取、undo log都是由 PageStore 完成。可以看到詳細的檔案和完整的實現。
提供索引資料新增的呼叫鏈。同樣的，索引的刪除和查詢都會涉及到，方便 debug 參考。
// 範例程式碼
// CREATE TABLE city (id INT(10) NOT NULL AUTO_INCREMENT, code VARCHAR(40) NOT NULL, name VARCHAR(40) NOT NULL);
public static void main(String[] args) throws SQLException {
// 注意：MV_STORE=false，MVStore is used as default storage
Connection conn = DriverManager.getConnection("jdbc:h2:~/test;MV_STORE=false", "sa", "");
Statement statement = conn.createStatement();
// CREATE INDEX IDX_NAME ON city(code); 新增資料觸發 BTree 索引新增
// -- SQL 範例化為：IDX_NAME:16:org.h2.index.PageBtreeIndex
statement.executeUpdate("INSERT INTO city(code,name) values('cch','長春')");
statement.close();
conn.close();
}
結合上述的範例程式碼，從索引新增的流程實現來了解BTree 索引的特性以及使用的注意事項。從底層實現分析索引的執行，對 SQL 索引使用和優化有進一步認識。
public void addRow(Session session, Row row) {
// MVCC 控制機制，記錄和比對當前事務的 id
lastModificationId = database.getNextModificationDataId();
if (database.isMultiVersion()) {
row.setSessionId(session.getId());
}
int i = 0;
try {
// 根據設計規範，indexes 肯定會有一個聚集索引（h2 稱之為scan index）。①
for (int size = indexes.size(); i < size; i++) {
Index index = indexes.get(i);
index.add(session, row);
checkRowCount(session, index, 1);
}
// 記錄當前 table 的資料行數，事務回滾後會相應遞減。
rowCount++;
} catch (Throwable e) {
try {
while (--i >= 0) {
Index index = indexes.get(i);
// 對應的，如果發生任何異常，會移除對應的索引資料。
index.remove(session, row);
}
}
throw de;
}
}
① 同Mysql InnoDB 資料儲存一樣， RegularTable 必有，且只有一個聚集索引。以主鍵(或者隱含自增id)為key, 儲存完整的資料。
public void add(Session session, Row row) {
// 索引key 生成 ②
if (mainIndexColumn != -1) {
// 如果主鍵非 long, 使用 org.h2.value.Value#convertTo 嘗試把主鍵轉為 long
row.setKey(row.getValue(mainIndexColumn).getLong());
} else {
if (row.getKey() == 0) {
row.setKey((int) ++lastKey);
retry = true;
}
}
// 新增行資料到聚集索引 ③
while (true) {
try {
addTry(session, row);
break;
} catch (DbException e) {
if (!retry) {
throw getNewDuplicateKeyException();
}
}
}
}
② 對於有主鍵的情況，會獲取當前 row 主鍵的值，轉為long value。對於沒有指定主鍵的情況，從當前聚集索引屬性 lastKey 自增得到唯一 key。
只有指定主鍵的情況，才會校驗資料重複（也就是索引key 重複，自增 lastKey 是不會有重複值的問題）。
③ 聚集索引 PageDataIndex 按照BTree 結構查詢對應的key 位置，按照主鍵/key 的順序，將 Row 儲存到page 中。非聚集索引 PageBtreeIndex 也是這樣的處理流程。
這其中涉及到三個問題：
/**
* Find an entry. 二分查詢 compare 所在的位置。這個位置儲存 compare 的offset。
* org.h2.index.PageBtree#find(org.h2.result.SearchRow, boolean, boolean, boolean)
* @param compare 查詢的row, 對應上述範例 compare.value = 'cch'
* @return the index of the found row
*/
int find(SearchRow compare, boolean bigger, boolean add, boolean compareKeys) {
// 目前 page 持有的資料量 ④
int l = 0, r = entryCount;
int comp = 1;
while (l < r) {
int i = (l + r) >>> 1;
// 根據 offsets[i]，讀取對應的 row 資料 ⑤
SearchRow row = getRow(i);
// 比大小 ⑥
comp = index.compareRows(row, compare);
if (comp == 0) {
// 唯一索引校驗 ⑦
if (add && index.indexType.isUnique()) {
if (!index.containsNullAndAllowMultipleNull(compare)) {
throw index.getDuplicateKeyException(compare.toString());
}
}
}
if (comp > 0 || (!bigger && comp == 0)) {
r = i;
} else {
l = i + 1;
}
}
return l;
}
④ 每個塊（page）entryCount ，兩個方法初始化。根據塊分配和範例建立初始化，或者 PageStore 讀取塊檔案，從Page Data 解析得到。
⑤ 反序列化過程，從page 檔案位元組碼（4k的位元組陣列），根據協定讀取資料並範例化為 row 物件。參考： org.h2.index.PageBtreeIndex#readRow(org.h2.store.Data, int, boolean, boolean) 。
⑥ 全型別支援大小比對，具體的規則參考：org.h2.index.BaseIndex#compareRows
⑦ 如果資料中存在重複的鍵值，則不能建立唯一索引、UNIQUE 約束或 PRIMARY KEY 約束。h2database 相容多種資料庫模式，MySQL NULL 非唯一，MSSQLServer NULL 唯一，僅允許出現一次。
private int addRow(SearchRow row, boolean tryOnly) {
// 計算資料所佔位元組的長度
int rowLength = index.getRowSize(data, row, onlyPosition);
// 塊大小，預設 4k
int pageSize = index.getPageStore().getPageSize();
// 塊檔案可用的 offset 獲取
int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
if (last - rowLength < start + OFFSET_LENGTH) {
// 校驗和嘗試分配計算，這其中就涉及到分割頁面生長 B 樹的過程 ⑧
}
// undo log 讓B樹更可靠 ⑨
index.getPageStore().logUndo(this, data);
if (!optimizeUpdate) {
readAllRows();
}
int x = find(row, false, true, true);
// 新索引資料的offset 插入到 offsets 陣列中。使用 System.arraycopy(x + 1) 來挪動資料。
offsets = insert(offsets, entryCount, x, offset);
// 重新計算 offsets，寫磁碟就按照 offsets 來寫入資料。
add(offsets, x + 1, entryCount + 1, -rowLength);
// 追加實際資料 row
rows = insert(rows, entryCount, x, row);
entryCount++;
// 標識 page.setChanged(true);
index.getPageStore().update(this);
return -1;
}
⑧如果你想新增一個新的鍵，你需要找到其範圍能包含新鍵的頁面，並將其新增到該頁面。如果頁面中沒有足夠的可用空間容納新鍵，則將其分成兩個半滿頁面，並更新父頁面以反映新的鍵範圍分割區
⑨為了使資料庫能處理異常崩潰的場景，B 樹實現通常會帶有一個額外的硬碟資料結構：預寫式紀錄檔（WAL，即 write-ahead log，也稱為 重做紀錄檔，即 redo log）。這是一個僅追加的檔案，每個 B 樹的修改在其能被應用到樹本身的頁面之前都必須先寫入到該檔案。當資料庫在崩潰後恢復時，這個紀錄檔將被用來使 B 樹恢復到一致的狀態。
查詢優化實質上就是存取資料量的優化，磁碟IO 的優化。
如果資料全部快取到記憶體中，實際上就是計算量的優化，CPU 使用的優化。
索引是有序的，實際上就是指塊檔案內的 offsets 是以陣列形式體現的。 特殊的是，在h2database 中，offsets陣列元素也是有序的（例如：[4090, 4084, 4078, 4072, 4066, 4060, 4054, 4048, 4042]），應該是方便磁碟順序讀，防止磁碟碎片化。
理論上，聚集索引掃描 IO 比 BTree 索引要多，因為同樣的塊檔案內，BTree 索引 儲存的資料量更大，所佔的塊檔案更少。如果一個table 列足夠少，聚集索引掃描效率更高。
建表需要謹慎，每個列的欄位長度儘可能的短，來節省頁面空間。
合理使用覆蓋索引查詢，避免回表查詢。 如述範例，select id from city where code = 'cch' ，掃描一次 BTree 索引即可得到結果。如果 select name from city where code = 'cch', 需要掃描一次 BTree 索引得到索引key (主鍵)，再遍歷掃描聚集索引，根據 key 得到結果。
合理的使用快取，讓磁碟IO 的影響降到最低。 比如合理設定快取大小，冷熱資料區分查詢等。
作者：京東物流 楊攀
內容來源：京東雲開發者社群