B+ Tree

[v.denis]

Hi, guys.

I've published my B+ Tree library project.
It is for Delphi but I post it here because Pascal community here is quite big.

https://code.google.com/p/delphi-bpus-tree/

It's key-value storage.
Both keys and values are array of bytes.
There is no limit for value length, but key length has a limit.
It's good for search. It does binary search for key.
There are cursors to iterate keys.
Adding/modifying records can produce some dead bytes on the storage (they are not indexed). You can clean it (remove the garbage) after all entries added.

It's kind of NOSQL, there are just key --> values. Though you can serialize (yourself) any kind of data.

Keys are in lexicographical order.

And it's single-threaded and not thread-safe (no locks).

[Leledumbo]

Doesn't seem to be compilable straightforward, the dependencies to new Delphi unit naming convention is a problem. Dependencies to Delphi's generics unit is another challenge though there's somewhat compatible implementation proposed.

[marcov]

I've always liked B+Trees as a concept. Yes, there are some downsides as Leledumbo mentions, but even a pessimist like me believes they can be overcome.

I happen to be playing a lot with datastructures lately, since I need to rework a part with a lot of indexes soon.  I'll see if I can benchmark it a bit in the weekend.

I tried to set up a generic container type, but Delphi generics suck for value types, it seems this solution is not really generic in that regard, but needs typecast to tbytes?

Another problem is that the unit name "gmap" conflicts with an unit in the FPC tree.

[Leledumbo]

but even a pessimist like me believes they can be overcome.

Certainly, that's why I said it as a porting challenge
Anyway, as B+tree is the foundation of many RDBMS storage engine, I think someone will start creating his own RDBMS when this library gets ported.