These data structures are good for main memory. I've implemented in-memory B-trees in C#, and they were 2x to 5x faster than .NET's built-in sorted maps. The bu

These data structures are good for main memory. I've implemented in-memory B-trees in C#, and they were 2x to 5x faster than .NET's built-in sorted maps. The built-in sorted maps also used 3x as much memory. Surprisingly, B-trees are better even for immutable collections, beating the built-in .NET immutable sorted map by 3x to 5x on updates. This is all with a straightforward implementation. Red-black trees and AVL trees should not be used any more in my opinion. They are much slower and in my opinion B-trees are easier to understand and implement. It is still customary for data structure courses to teach red-black trees and AVL trees, but they should teach B-trees instead.