The proposal on that page is of a tree which does require random access updates, it just positions entries in the order they happened to be added instead of sorting by their hash. Once you start updating it to indicate spent status all the exact same issues of TXO size and cache coherence on updates show up again, but now you're using a more complex bespoke data structure instead of a basic fundamental one.