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:
- 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.
- 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.