h2database 是使用 Java 编写的开源数据库，兼容 ANSI-SQL89。

即实现了常规基于 BTree 的存储引擎，又支持日志结构存储引擎。功能非常丰富（死锁检测机制、事务特性、MVCC、运维工具等），数据库学习非常好的案例。

本文理论结合实践，通过 BTree 索引的设计和实现，更好的理解数据库索引相关的知识点以及优化原理。

BTree 实现类

h2database 默认使用的 MVStore 存储引擎，如果要使用 基于 BTree 的存储引擎，需要特别指定（如下示例代码 jdbcUrl）。

以下是常规存储引擎 (BTree 结构) 相关的关键类。

BTree 的数据结构可以从网上查到详细的描述和讲解，不做过多赘述。

需要特别说明的是：PageStore。我们数据查询和优化关键的缓存、磁盘读取、undo log 都是由 PageStore 完成。可以看到详细的文档和完整的实现。

BTree add index entry 调用链

提供索引数据新增的调用链。同样的，索引的删除和查询都会涉及到，方便 debug 参考。

  1. org.h2.command.dml.Insert#insertRows (Insert SQL 触发数据和索引新增)
  2. org.h2.mvstore.db.RegularTable#addRow (处理完的数据 Row, 执行新增)
  3. org.h2.index.PageBtreeIndex#add (逻辑层增加索引数据)
  4. org.h2.index.PageDataIndex#addTry (存储层增加索引数据)
  5. 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, 存储完整的数据。

聚集索引添加数据

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 也是这样的处理流程。

这其中涉及到三个问题：

  1. 如何查找 key 的位置，也就是 BTree 位置的计算？
  2. 如何计算 Row（实际数据）存储 Page 中的 offsets？
  3. Row 是怎样写入到磁盘中的，何时写入的？

索引数据存取实现

/**
 * 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 树恢复到一致的状态。

实践总结

其他知识点

参考

ddia/ch3.md B 树

作者：京东物流 杨攀

内容来源：京东云开发者社区


↙↙↙阅读原文可查看相关链接，并与作者交流