Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

B+ Trees and why I love them, part 1

ayende.com

Post reply on HN
Print view View original

21–30 of 33 posts

Re: B+ Trees and why I love them, part 1

#21

Post by leif »

gtrubetskoy wrote: post #16
leif wrote: post #12

Earlier quoted context omitted.

Actually, you can beat B-trees pretty handily across the board in exactly the scenario you described (a, b, c). The log(N) performance of a B-tree is not just extremely hard to improve on (for searches), it's impossible to improve on. The lower bound for searching (in the DAM model) is log(N)/log(B), and B-trees meet that. But B-trees are also log(N)/log(B) for insertions, which is, it turns out, pretty damn slow. Th…

So why isn't everyone using this instead of InnoDB these days? Is it not production-ready yet?

It is production ready, and many people are using it, but as with any deep stack technology, growth is a slow process. From an engineering standpoint, I'd say the data structure wasn't fully mature (ready to replace nearly all uses of InnoDB) until probably the end of 2012. Most of this was issues with concurrency that we methodically picked apart from the 5.0 release through 6.6.

A few users still point out annoyances here and there (like the location of files on disk, how certain metadata is presented at the MySQL level, dealing with corner cases in the query optimizer) that don't have to do with the data structure, but with the integration as a MySQL concept, and though these complaints are rare, they will eventually need to be addressed, and it's hard to find the manpower to address them immediately.

Part of this problem is that it just takes a long time to sand down all the rough little edges of a product, even though the core data structure is mature. Another part is educating people, changing expectations (for example, teaching people that unique indexes do have a higher cost than non-unique indexes), and generating better documentation. It's a slow process but we're confident that it's progressing and will continue. Recall that InnoDB, while broadly accepted as superior to MyISAM for many years before, only became the actual default engine in MySQL 5.5.

Re: B+ Trees and why I love them, part 1

#22

Post by leif »

leif wrote: post #17
elbee wrote: post #15

Earlier quoted context omitted.

That looks extremely interesting! The idea of amortizing the cost of inserts is fascinating. Looking at the design you sketched a few questions come to mind: 1) Multi-threading: suppose I seek down the B-tree for key K. Most B-tree implementations use the latch on the node containing K as the final arbiter of concurrency. For example, if I'm looking at K and then I want the next row (perhaps because I'm using the new…

It is highly concurrent but you need some tricks beyond that simple description. Here's how we did it: http://www.tokutek.com/2013/01/concurrency-improvements-in-t... http://www.tokutek.com/2013/02/concurrency-improvements-in-t... Yes, unique checks are bad. They make it perform as badly as a B-tree for unique inserts. There are sometimes ways around that but at some level if you aren't reading in the leaf node, you'…

I now realize I didn't answer how we check uniqueness. We just do a query like any other normal point query, using a serializable transaction, and if we pass the check, then we do the insert with the same transaction (which took a row lock when we did the query because it was serializable, so nothing could have violated the uniqueness between the query and the insert).

Re: B+ Trees and why I love them, part 1

#23

Post by elbee »

leif wrote: post #17
elbee wrote: post #15

Earlier quoted context omitted.

That looks extremely interesting! The idea of amortizing the cost of inserts is fascinating. Looking at the design you sketched a few questions come to mind: 1) Multi-threading: suppose I seek down the B-tree for key K. Most B-tree implementations use the latch on the node containing K as the final arbiter of concurrency. For example, if I'm looking at K and then I want the next row (perhaps because I'm using the new…

It is highly concurrent but you need some tricks beyond that simple description. Here's how we did it: http://www.tokutek.com/2013/01/concurrency-improvements-in-t... http://www.tokutek.com/2013/02/concurrency-improvements-in-t... Yes, unique checks are bad. They make it perform as badly as a B-tree for unique inserts. There are sometimes ways around that but at some level if you aren't reading in the leaf node, you'…

So out of the main b-tree operations (Insert/Replace/Delete/Seek/Next/Prev) you make a convincing argument that Tokutek can be faster than b-trees for inserts, if you use non-unique indexes (which automatically disqualifies the primary index in most cases, and makes foreign keys hard).

That is good but not quite "beat B-trees pretty handily across the board" :-)

Re: B+ Trees and why I love them, part 1

#24

Post by leif »

elbee wrote: post #23
leif wrote: post #17

Earlier quoted context omitted.

It is highly concurrent but you need some tricks beyond that simple description. Here's how we did it: http://www.tokutek.com/2013/01/concurrency-improvements-in-t... http://www.tokutek.com/2013/02/concurrency-improvements-in-t... Yes, unique checks are bad. They make it perform as badly as a B-tree for unique inserts. There are sometimes ways around that but at some level if you aren't reading in the leaf node, you'…

So out of the main b-tree operations (Insert/Replace/Delete/Seek/Next/Prev) you make a convincing argument that Tokutek can be faster than b-trees for inserts , if you use non-unique indexes (which automatically disqualifies the primary index in most cases, and makes foreign keys hard). That is good but not quite "beat B-trees pretty handily across the board" :-)

Many primary keys in the wild are sequential, which makes the unique check hit cache and not require any I/O.

Let me be clear: in the worst case with a unique index, Fractal Tree indexes are the same speed as B-tree indexes. In most cases, they're far better. When you add in compression and agility, it really is "beat B-trees across the board."

Re: B+ Trees and why I love them, part 1

#25

Post by elbee »

leif wrote: post #24
elbee wrote: post #23

Earlier quoted context omitted.

So out of the main b-tree operations (Insert/Replace/Delete/Seek/Next/Prev) you make a convincing argument that Tokutek can be faster than b-trees for inserts , if you use non-unique indexes (which automatically disqualifies the primary index in most cases, and makes foreign keys hard). That is good but not quite "beat B-trees pretty handily across the board" :-)

Many primary keys in the wild are sequential, which makes the unique check hit cache and not require any I/O. Let me be clear: in the worst case with a unique index, Fractal Tree indexes are the same speed as B-tree indexes. In most cases, they're far better. When you add in compression and agility, it really is "beat B-trees across the board."

To be honest, I have no idea what "agility" is. Perhaps I am too cautious but I'll want to see a lot more data than some hand-picked benchmarks and a mystical "unique constraints aren't interesting" before I'm completely convinced.

[Random aside: I greatly dislike block (i.e. InnoDB-style) compression, which is what Tokutek seems to use. Decompressing the entire block just to retrieve one column of one row is crazily expensive, especially as the decompression cost goes up as the block size goes up. There is also the problem of deciding whether to store compressed blocks in the buffer cache (slow), decompressed blocks in the buffer cache (wastes ram) or to have a cache of uncompressed blocks (the InnoDB approach, which kind of combines both problems). I think that format-aware page or column compression (like Oracle, SQL Server or ESENT) is far more effective.]

I guess that this has gotten way off topic but I am glad there are people out there doing exciting new things in the B-tree space. I will keep a closer eye on Tokutek in the future.

Re: B+ Trees and why I love them, part 1

#26

Post by leif »

elbee wrote: post #25
leif wrote: post #24

Earlier quoted context omitted.

Many primary keys in the wild are sequential, which makes the unique check hit cache and not require any I/O. Let me be clear: in the worst case with a unique index, Fractal Tree indexes are the same speed as B-tree indexes. In most cases, they're far better. When you add in compression and agility, it really is "beat B-trees across the board."

To be honest, I have no idea what "agility" is. Perhaps I am too cautious but I'll want to see a lot more data than some hand-picked benchmarks and a mystical "unique constraints aren't interesting" before I'm completely convinced. [Random aside: I greatly dislike block (i.e. InnoDB-style) compression, which is what Tokutek seems to use. Decompressing the entire block just to retrieve one column of one row is crazily…

Agility refers to our online schema change abilities in mysql (hot column add/delete, hot indexing).

Our compression technique is naive, you're right (but we don't decompress the whole 4MB for one single point query, as you may be thinking, we're a bit more sophisticated). We have some more ideas in the pipeline if we need them (basically a bunch of tricks you can play when you know the schema), but the fact remains that what we have right now is extremely effective and there isn't much incentive yet to finish off our smarter prototypes.

Re: B+ Trees and why I love them, part 1

#27

Post by leif »

leif wrote: post #26
elbee wrote: post #25

Earlier quoted context omitted.

To be honest, I have no idea what "agility" is. Perhaps I am too cautious but I'll want to see a lot more data than some hand-picked benchmarks and a mystical "unique constraints aren't interesting" before I'm completely convinced. [Random aside: I greatly dislike block (i.e. InnoDB-style) compression, which is what Tokutek seems to use. Decompressing the entire block just to retrieve one column of one row is crazily…

Agility refers to our online schema change abilities in mysql (hot column add/delete, hot indexing). Our compression technique is naive, you're right (but we don't decompress the whole 4MB for one single point query, as you may be thinking, we're a bit more sophisticated). We have some more ideas in the pipeline if we need them (basically a bunch of tricks you can play when you know the schema), but the fact remains…

(Don't worry about off topic I love deep conversations like this. Come to our mailing list if you want to continue more though, we may be exhausting HN)

Re: B+ Trees and why I love them, part 1

#28

Post by justin66 »

leif wrote: post #12
elbee wrote: post #6

Earlier quoted context omitted.

The B-tree implementations used in a lot of databases have tweaks, but they are surprisingly similar to the textbook descriptions. In general, B-trees are actually a very useful data structure when: a) Your data is much larger than main memory (e.g. terabytes/petabytes of data and gigabytes of RAM). b) You want to support random insert/update/delete, seek, and next/previous key. c) There has to be a reasonable constr…

Actually, you can beat B-trees pretty handily across the board in exactly the scenario you described (a, b, c). The log(N) performance of a B-tree is not just extremely hard to improve on (for searches), it's impossible to improve on. The lower bound for searching (in the DAM model) is log(N)/log(B), and B-trees meet that. But B-trees are also log(N)/log(B) for insertions, which is, it turns out, pretty damn slow. Th…

> 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?

Re: B+ Trees and why I love them, part 1

#29

Post by nkurz »

leif wrote: post #27
leif wrote: post #26

Earlier quoted context omitted.

Agility refers to our online schema change abilities in mysql (hot column add/delete, hot indexing). Our compression technique is naive, you're right (but we don't decompress the whole 4MB for one single point query, as you may be thinking, we're a bit more sophisticated). We have some more ideas in the pipeline if we need them (basically a bunch of tricks you can play when you know the schema), but the fact remains…

(Don't worry about off topic I love deep conversations like this. Come to our mailing list if you want to continue more though, we may be exhausting HN)

Actually, this is the type of back-and-forth I (and I think others) would love to see more of. A dozen replies in, lots of good ideas, and no one is calling anyone else an idiot or a troll. Feel free to continue!

Re: B+ Trees and why I love them, part 1

#30

Post by nkurz »

koverstreet wrote: post #7
elbee wrote: post #6

Earlier quoted context omitted.

The B-tree implementations used in a lot of databases have tweaks, but they are surprisingly similar to the textbook descriptions. In general, B-trees are actually a very useful data structure when: a) Your data is much larger than main memory (e.g. terabytes/petabytes of data and gigabytes of RAM). b) You want to support random insert/update/delete, seek, and next/previous key. c) There has to be a reasonable constr…

There's two reasons a textbook b+ tree is never going to perform very well: * Binary searches suck The memory accesses of a binary search look pretty much like complete random access, so prefetching is useless. Once your b+ tree is big enough that most of it won't fit in L2, you've got a tight inner loop that's waiting on DRAM at every single iteration. This one is at least more or less solvable without changing the…

The memory accesses of a binary search look pretty much like complete random access

Why would this be? I would think that even in a naive implementation the fan-out is high enough that top levels of the B+ tree will always be in cache, so that you are only hitting RAM for the last level or two and the leaf. For in memory use, I thought the usual argument against binary search was (as 'elbee' mentions) the poor branch predictability, not the caching.

Post reply on HN