Friday, December 27, 2013

Working toward a more generic implementation

The purpose of this project is to help me understand effective patterns in Go. It's been a very fun journey. After I completed the first B-tree implementation I looked around for existing implementations that I could compare it to. I found these two:

cznic's is an in-memory implementation that appears to be a part of an SQL project in Go. A very nice piece of work. cznic's approach to polymorphism is to search/replace in the file to create a specialization --Just like C++ used to do-- which isn't very satisfying to me. He/she seems to have done extensive benchmarking on the code. 

santucco's implementation is an on-disk implementation, which really got me thinking. The B-tree is meant to be an on-disk index with its nodes sized to match disk blocks. What would it take to make a tree that was suitably generic so that client code could choose an in-memory or on-disk implementation? 

After a lot of thought and several trial implementations I came up with these design parameters:
  1. Generic code should implement as much of the algorithm as possible. Type-specific code should not be hard to write and you should not have to re-validate the algorithm for each specific type.
  2. Allocation and disposal of node memory must be done in client code. This gives client code the flexibility to use any type of backing storage. 
Over the next month (that I have off!!) I'll compare all three implementations more completely. The latest commit can be found on GitHub.