Joy of Think

等到实现基本的2-3数之后,首先就可以将一些部分采用template模板化.
首先是Key和Value的类型.由于Key和Value的类型会被用于多个地方,所以基本上会定义一组类型,例如:
Key::InT 用于作为函数的只读参数
Key::OutT 用于函数的输出参数
Key::InOutT 用于函数的输入输出参数
Key::T 基本类型声明
Key和Value类型可以被实现为变长类型的一个Handle类型,这样可以无缝的支持变长类型.(如果是变长类型,动态空间如何管理就是一个问题???)
另外要将Key类型的比较操作转化为函数,这样就可以很方便的实现升序和降序.(可以采用模板偏特化的技术 )

Link: http://www.tianya.cn/techforum/content/176/539134.shtml

Link: http://www.sys-con.com/

A general IT tech website

从上个星期开始,我决定写个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相关的算法.这是第一个大弯路.

Link: http://discussion.dreamhost.com/showflat.pl?Cat=&Board=3rdparty&Number=97047

A method to hack dotProject to show correct timezone.