adewes/blitzdb — pull request #12 by jxieeducation (2014-04-23 17:58:46+00:00)
Title: proof of concept for BTree index

This is an extremely simple proof of concept for https://github.com/adewes/blitzdb/issues/9

This allows the backend to adopt a BTree model using the BTrees pip library (sudo pip install BTrees, did not add to the requirements.txt yet).
While attempting to add the BTree, I found a few problems with using a BTree.
1. querying the whole set: if user tries to store a tuple, it's easy to add both elements to the hash. however, with trees, it's much more complicated.
2. search: if an object's built in compare function is wrong / raises an error, the BTree can't do anything about it, because it needs to compare the elements.
It's easy to make a BTree of the hashes of the elements, however, that pretty much defeats the purpose of using a BTree in the first place.

While writing the simple add / remove functions, I assumed that caching is not needed for BTrees, because it offers little adv. as the tree goes down.
I also believe a BTree will also be clunky when elements get large, because it runs in O(n), while the hashmap runs in O(1).

Please let me know what you think?