In something like an append-only log or DAG, you'd still have to index where in that log to skip to (or you'd be scanning for it every time), which is still computational complex, and not nearly as scalable as a mutable index. So yes, while you are correct, it either way is still better to use the mutable approach.