B+ Trees and why I love them, part 1

B+ Trees and why I love them, part 1
ayende.com

Specially, sofistications on AVL and Red-Black trees

* 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 rest of the design, but then if you also want to solve the other main issue it gets harder.

* With small btree nodes, the overhead of looking up and locking btree nodes (even assuming they're all cached in memory) kills you.

Trouble is if you make your btree nodes big enough to fix that overhead, they're now so big that rewriting them when you insert a single key is just ridiculous.

So where you end up is to get anywhere near the highest possible performance you're forced into log structured btree nodes. Which actually has its advantages for solving the first problem, but now what you've got is really a hybrid b+ tree/compacting data structure.

Source: bcache author.

"Binary searches suck"

That is a valid point. Cache misses when doing the search inside of the b-tree can be painful. I know that there is some research into structuring the b-tree nodes to be more cache-friendly (David Lomet mentions this in his "Evolution of Effective B-Tree" paper: http://research.microsoft.com/pubs/77583/p64-lomet.pdf) but haven't actually seen any in production.

Part of the problem here is that page density is so critical that people are often wary of having a less-efficient, but more cache-friendly data representaton. It is normally better to have 10% more records in main memory than being able to search the nodes a touch faster. Various forms of key prefix compression are an example of this tradeoff.

Another consideration is the actual cost of doing the key comparison. I'm most familiar with relational database systems and they all support multi-column keys (e.g string+integer+boolean+date), which normally lead to an expensive, branch-laden comparison function because the comparison has to be type-aware and support various collation options. The cost of doing that branching means the CPU cache misses are a smaller overall part of the overall search cost. One exception to that is ESENT, which uses memcmp-able normalized keys, but doing that creates its own set of problems (Unicode is a pain, lack of denormalization means storing data twice, etc.).

"Rewriting them when you insert a single key is just ridiculous."

I don't think anyone does this. Most implementations have settled on a system that stores the keys in the node in an ad-hoc fashion and have an array of 'pointers' to the keys which starts at the end of the page and grows towards the front (except for Postgres, which appears to do it the other way around). Inserting a new key means moving the pointers, but not the actual keys. Some systems try to avoid doing even that -- for example the InnoDB engine in MySQL links together the keys and the page directory only points to every 4th-8th key. I believe that this is an attempt to balance the speed of the binary search against the cost of update/delete.

In addition, with write-ahead-logging the node isn't flushed when updated, instead the log records describing the update are flushed and the page is lazily flushed in the background by a checkpointing process, hopefully after several other updates have been made to the same node.

Microsoft SQL Server, Microsoft ESENT, MySQL's InnoDB and Postgres' b-tree index all use minor variations on the basic textbook b-tree for their data storage.

Source: Many years working on the ESENT database engine, a brief stint in Microsoft SQL Server, some hacking done on the MySQL InnoDB engine.