企业网站建设步骤,重庆网络网站推广,如何通过psd做网站,网站排名快速提升h2database 是使用Java 编写的开源数据库#xff0c;兼容ANSI-SQL89。 即实现了常规基于 BTree 的存储引擎#xff0c;又支持日志结构存储引擎。功能非常丰富#xff08;死锁检测机制、事务特性、MVCC、运维工具等#xff09;#xff0c;数据库学习非常好的案例。 本文理论… 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_STOREfalseMVStore is used as default storageConnection conn DriverManager.getConnection(jdbc:h2:~/test;MV_STOREfalse, sa, );Statement statement conn.createStatement();// CREATE INDEX IDX_NAME ON city(code); 添加数据触发 BTree 索引新增// -- SQL 实例化为IDX_NAME:16:org.h2.index.PageBtreeIndexstatement.executeUpdate(INSERT INTO city(code,name) values(cch,长春));statement.close();conn.close();
}Code Insight 结合上述的示例代码从索引新增的流程实现来了解BTree 索引的特性以及使用的注意事项。从底层实现分析索引的运行对 SQL 索引使用和优化有进一步认识。 表添加数据 public void addRow(Session session, Row row) {// MVCC 控制机制记录和比对当前事务的 idlastModificationId 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 尝试把主键转为 longrow.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;
}④ 每个块pageentryCount 两个方法初始化。根据块分配和实例创建初始化或者 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);// 块大小默认 4kint 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);// 追加实际数据 rowrows 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树
