[skitter]

> BSTs however are not good for disk based storage.

The listed reasons also apply to in-memory storage – searching a btree node is faster than doing the equivalent amount of pointer traversals for a binary tree. Of course this comes at the cost of increased implementation complexity, but unless you're using C, you're probably not implementing your own tree-based map.

You can then use different variants such as packing more entries into interior nodes by only storing values in the leafs (assuming you're making a map and not just a set, that is). If you then link neighboring nodes, you basically have a skip list.

[eatonphil]

For further reading on this, see for example:

[0] https://abseil.io/blog/20190812-btree

[1] https://opensource.googleblog.com/2013/01/c-containers-that-...