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 参考。
  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, 存储残缺的数据。

汇集索引增加数据

  • 索引中的 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 也是这样的解决流程。

这其中波及到三个问题：

  1. 如何查找 key 的地位，也就是 BTree 地位的计算？
  2. 如何计算 Row （理论数据）存储 Page 中的 offsets？
  3. 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树

作者：京东物流 杨攀

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