On: Why databases use ordered indexes but programming uses hash tables

[dexen]

Your both points (very valid) could perhaps be wrapped up as:

Indexes have lower computational complexity for certain tasks (in particular range queries & sort), but higher constants than typical hashing.

Thus indexes make more sense with two-tiered memory; to cache in RAM metadata about data kept in block storage.

How that could be put to good use with the L1 cache being much faster than RAM is anyone's guess[1].

--

[1] without guessing, we already know a small interpreter that fits in L1 can be blazing fast.

[loeg → dexen]

Rust's default (edit: ordered) map structure is a memory Btree, fwiw.

[microtonal → loeg]

What do you mean by this? There is no default map type. The standard library has types such as BTreeMap and HashMap, that pretty much are what it says on the tin.

[loeg → microtonal]

Ordered map.