BabuDB - Design Documentation

[Sai Nallapaneni]

Hey Folks,

I am working on a very similar key-value database which is embedded and non-relational. It internally uses B+ trees and has in-memory implementations using AVL Trees. But the problem I am trying to solve is range queries. For example, searching for ab* in an avl tree is extremely fast. You find the first instance of ab* in O(logN) and then its in-order traversal. But if I want to search for a *ab* key, then there is no easy solution except going through all the keys.

1. Does BabuDB solve this problem? If yes, how does range query work in babudb

2. Do you guys have any design doc or white paper on this product? 

Otherwise I will try to look at the code and try to figure out. 

thanks

Sai

[Felix Hupfeld]

2012/10/3 Sai Nallapaneni <sai.nal...@gmail.com>:

> Hey Folks,
>
> I am working on a very similar key-value database which is embedded and
> non-relational. It internally uses B+ trees and has in-memory
> implementations using AVL Trees. But the problem I am trying to solve is
> range queries. For example, searching for ab* in an avl tree is extremely
> fast. You find the first instance of ab* in O(logN) and then its in-order
> traversal. But if I want to search for a *ab* key, then there is no easy
> solution except going through all the keys.
>
> 1. Does BabuDB solve this problem? If yes, how does range query work in
> babudb

No. And I don't see a simple and cheap way of solving the *ab*
(substring?) problem with a normal search tree.

> 2. Do you guys have any design doc or white paper on this product?

Is http://www.xtreemfs.org/publications/babudb-snapi.pdf enough?