有了Page结构,我们就可以将数据承载在一个个page大小的内存里面,同时还可以将page刷新到对应的文件里。有了node.item中的pageno,我们就可以较容易的进行文件和内存结构之间的互相映射了。
B+树在磁盘文件中的组织如下图所示:
B+树在内存中相对应的映射结构如下图所示:
文件page和内存page中的内容基本是一致的,除了一些内存page中特有的字段,例如dirty等。 每个索引一个B+树
在Freedom中,每个索引都是一颗B+树,对记录的插入和修改都要对所有的B+树进行操作。
B+Tree的测试笔者通过一系列测试case,例如随机变长记录对B+树进行插入并落盘,修复了其中若干个非常诡异的corner case。
B+Tree的todo笔者这里只是完成了最简单的B+树结构,没有给其添加并发修改的锁机制,也没有在B+树做操作的时候记录log来保证B+树在宕机等灾难性情况下的一致性,所以就算完成了这么多的工作量,距离一个高并发高可用的bptree还有非常大的距离。
Meta Datatable的元信息由create table所创建。创建之后会将元信息落盘,以便Freedom在重启的时候加载表信息。每张表的元信息只占用一页的空间,依旧复用page结构,主要保存的是聚簇索引和二级索引的信息。元信息对应的Item如下图所示:
如果想让mybatis可以自动生成关于Freedom的代码,还需实现一些特定的sql来展现Freedom的元信息。这个在笔者另一个项目rider中有这样的实现。原理如下图所示:
实现了上述4类SQL之后,mybatis-generator就可以通过jdbc从Freedom获取元信息进而自动生成代码了。 事务支持
由于当前Freedom并没有保证并发,所以对于事务的支持只做了最简单的WAL协议。通过记录redo/undolog从而实现原子性。
redo/undo log协议格式Freedom在每做一个修改操作时,都会生成一条日志,其中记录了修改前(undo)和修改后(redo)的行信息,undo用来回滚,redo用来宕机recover。结构如下图所示:
WAL协议很好理解,就是在事务commit前将当前事务中所产生的的所有log记录刷入磁盘。
Freedom自然也做了这个操作,使得可以在宕机后通过log恢复出所有的数据。
由于日志中记录了undo,所以对于一个事务的回滚直接通过日志进行undo即可。如下图所示:
Freedom如果在page全部刷盘之后关机,则可以由通过加载page的方式获取原来的数据。
但如果突然宕机,例如kill -9之后,则可以通过WAL协议中记录的redo/undo log来重新
恢复所有的数据。由于时间和精力所限,笔者并没有实现基于LSN的检查点机制。
以下是笔者实际运行Freedom的例子:
join查询
delete回滚
Freedom todo