Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The implementation of that b-tree is actually pretty difficult (I've attempted in the past, but it depends on your skill of course) and the constant factor is much larger. (It's somewhat difficult to implement because when you remove a node, tricky things happen and you need to keep the sub-tree sizes consistent). Granted, whatever floats your boat!


I used this structure (although I knew it by totally different name) a lot in time constrained contests, the code is very short and easy to implement.

Also:

  idx -= (1 << ctz(idx));
I used to write this as:

  idx -= idx&-idx;


Sure B-trees are hard to write from the ground up but there are plenty of good implementations already the Internet that can be modified.

The extra functionality is a simple enough addition to any binary-tree-type data structure that I was annoyed that Boost/Qt didn't have it already included.


> Sure B-trees are hard to write from the ground up but there are plenty of good implementations already the Internet that can be modified.

Care to name some, also having a non-restrictive license? (That excludes GPL).


Try

http://www.touc.org/btree.html

This c++ template is fairly simple and I have tested it a reasonable amount.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: