I'm not talking about a b-tree that won't fit in L2, I'm talking about a B-tree that won't even fit in main memory. In those cases, even with SSDs, the cost of pulling a page off disk dominates the in-memory cost of the binary search so the number of I/Os needed to find something becomes the dominant factor in performance. That leads to a focus on data density and cache replacement algorithms.
"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.
