Joy of Think

从上个星期开始,我决定写个btree的实现.算法参考的是Introduce to algorithm中的Btree.

首先,决定从最简单的变体2-3树开始,然后决定只是使用定长的key和value:均采用int型.后面的经验证明这是一个正确的决定.

其次,由于btree是面向外存储的算法,我就定义了struct Page用来存放数据,Node用来存放内存中的Page信息.又实现了一个PagePool类型,和Handle类型,用来管理Page的生命期.实践证明,我作的还不够简单,其实不应该那么快的去考虑存储的问题,应该把Page和Node类型合一,先实现一个基本的2-3树,然后再逐步添加存储的逻辑.

然后就开始实现Btree树.首先是insert的算法.由于没有仔细研究Introduce to algorithm,先实现了一个要求splite回溯的算法,并且在Page中引入了一个parent域,在后面被证明是一个bug的来源.后来仔细看了书,才正确的实现了insert相关的算法.这是第一个大弯路.