B+ Trees and why I love them, part 1

Post by Flow » Sun, Aug 18, 2013, 8:00 AM UTC

gtrubetskoy wrote: post #14

Flow wrote: post #10

Earlier quoted context omitted.

I've read your first link and I don't get why you talk about "A relational database needs to store rows in order". AFAIK you have to add an "order by" clause to ensure ordering of any kind. Relational algebra is probably not dependent of ordering for the common operations. Of course, the actual implementation of a relational database might need ordering of keys to be reasonably efficient. Is that what you meant?

It needs to store rows in order to support indexes, so that a row could be found without having to scan the whole table, and that's exactly what B-Trees let you do, and also add or remove rows without having to rewrite the whole table, but only affected blocks.

Post by justin66 » Sun, Aug 18, 2013, 6:26 PM UTC

leif wrote: post #32

justin66 wrote: post #28

Earlier quoted context omitted.

> We also have a version of MongoDB in which we've replaced all the storage code with Fractal Trees, we call it TokuMX [5]. What's the deal with TokuKV? Is it a working drop-in replacement for BerkeleyDB and similar key-value stores?

It's not really a drop in replacement for BDB, it's more like a library whose API was inspired by BDB. You're welcome to use it directly, but it doesn't implement all of BDB, we have added a bunch of things (like db->update), and there may be some weird contractual things you need to get right that we haven't documented well. Contact us if you'd like to use it, we can help you.