Fast Ordered Collections for Swift Using In-Memory B-Trees

Quote the readme: "B-trees were originally invented in the 1970s as a data structure for slow external storage devices. As such, they are strongly optimized for locality of reference: they prefer to keep data in long contiguous buffers and they keep pointer derefencing to a minimum. (Dereferencing a pointer in a B-tree usually meant reading another block of data from the spinning hard drive, which is a glacially slow device compared to the main memory.)"

Sounds like it could be pretty cache friendly. Besides, a B-tree can be used to implement a hash/dict/map.

B-trees don't beat hash tables at their own game, but hash tables don't beat B-trees at theirs either. Both are general-use data structures that have their particular niches. The trick is to always select the correct tool for the job.

You might be thinking about red-black trees. The size overhead of B-trees is the same or better than that of hash tables. As for cache friendliness, B-trees were explicitly designed to work great on two-level storage; the advantage is clearly theirs.