Your both points (very valid) could perhaps be wrapped up as: Indexes have lower computational complexity for certain tasks (in particular range queries & sort

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.