h2database 是使用Java 編寫的開源資料庫，相容ANSI-SQL89。

即實作了正常基于 BTree 的存儲引擎，又支援日志結構存儲引擎。功能非常豐富（死鎖檢測機制、事務特性、MVCC、運維工具等），資料庫學習非常好的案例。

本文理論結合實踐，通過BTree 索引的設計和實作，更好的了解資料庫索引相關的知識點以及優化原理。

BTree 實作類

h2database 預設使用的 MVStore 存儲引擎，如果要使用基于 BTree 的存儲引擎，需要特别指定（如下示例代碼 jdbcUrl）。

以下是正常存儲引擎(BTree 結構) 相關的關鍵類。

org.h2.table.RegularTable
org.h2.index.PageBtreeIndex （SQL Index 本體實作）
org.h2.store.PageStore （存儲層，對接邏輯層和檔案系統）

BTree 的資料結構可以從網上查到詳細的描述和講解，不做過多贅述。

需要特别說明的是：PageStore。我們資料查詢和優化關鍵的緩存、磁盤讀取、undo log都是由 PageStore 完成。可以看到詳細的文檔和完整的實作。

BTree add index entry 調用鍊

提供索引資料新增的調用鍊。同樣的，索引的删除和查詢都會涉及到，友善 debug 參考。

org.h2.command.dml.Insert#insertRows (Insert SQL 觸發資料和索引新增)
org.h2.mvstore.db.RegularTable#addRow (處理完的資料Row, 執行新增)
org.h2.index.PageBtreeIndex#add (邏輯層增加索引資料)
org.h2.index.PageDataIndex#addTry (存儲層增加索引資料)
org.h2.index.PageDataLeaf#addRowTry (存儲層新增實作)

// 示例代碼
// 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();
}

Code Insight

結合上述的示例代碼，從索引新增的流程實作來了解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, 存儲完整的資料。

聚集索引添加資料

索引中的 key 是查詢要搜尋的内容，而其值可以是以下兩種情況之一：它可以是實際的行（文檔，頂點），也可以是對存儲在别處的行的引用。在後一種情況下，行被存儲的地方被稱為堆檔案（heap file），并且存儲的資料沒有特定的順序（根據索引相關的）。
從索引到堆檔案的額外跳躍對讀取來說性能損失太大，是以可能希望将被索引的行直接存儲在索引中。這被稱為聚集索引（clustered index）。
基于主鍵掃描即可唯一确定、并且擷取到資料，聚集索引性能比非主鍵索引少一次掃描

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 也是這樣的處理流程。

這其中涉及到三個問題：

如何查找 key 的位置，也就是 BTree 位置的計算？
如何計算 Row （實際資料）存儲 Page 中的 offsets？
Row 是怎樣寫入到磁盤中的，何時寫入的？

索引資料存取實作

B 樹将資料庫分解成固定大小的塊（block）或分頁（page），傳統上大小為 4KB（有時會更大），并且一次隻能讀取或寫入一個頁面。
每個頁面都可以使用位址或位置來辨別，這允許一個頁面引用另一個頁面 —— 類似于指針，但在硬碟而不是在記憶體中。（對應h2 database PageBtreeLeaf 和 PageBtreeNode）
不同于 PageDataIndex ，PageBtreeIndex 按照 column.value 順序來存儲。添加的過程就是比對查找 column.value，确定在塊（block）中offsets 的下标 x。剩下就是計算資料的offset 并存入下标 x 中。

/**
 * 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 的影響降到最低。比如合理配置緩存大小，冷熱資料區分查詢等。

其他知識點

分支因子為 500 的 4KB 頁面的四層樹可以存儲多達 256TB 的資料）。（在 B 樹的一個頁面中對子頁面的引用的數量稱為分支因子（branching factor）。

參考

ddia/ch3.md B樹

作者：京東物流楊攀

内容來源：京東雲開發者社群

h2database BTree 設計實作與查詢優化思考

BTree 實作類

BTree add index entry 調用鍊

Code Insight

表添加資料

聚集索引添加資料

索引資料存取實作

實踐總結

其他知識點

參考

繼續閱讀

Spring+Hibernate配置hbm.xml檔案在jar檔案中。

python操作配置檔案

查詢Oracle表空間資訊

黑猴子的家：emp.txt

Google App Engine錯誤解決方案之Class com.xxx.xxx does not seem to have been enhanced. You may want to rerun the enhancer and check for

IntelliJ IDEA 2020.1.2 設定多個project共享database插件

【MySQL資料庫】資料庫的基本查詢 DQL資料庫的基本查詢 DQL

利用ado壓縮資料庫(vc源代碼)HOWTO: Compacting Microsoft Access Database Through OLE DB

關系資料庫設計理論函數依賴(FD)函數依賴的規則BC範式

HPM Note1,Book Organization

Partitioning Concepts

MySQL安裝時常見問題和解決方案【詳解】

Doris資料更新及删除1.資料更新

使用JDeveloper Remote debug PLSQL程式

單字母域名

testlink 切換資料庫