> while I don't see an easy way to avoid big locks with COLA

Do not modify arrays in-place, create new arrays instead. This way you can have multiple readers as the data pretty much read-only, no write locks and, again, cache-oblivious merging (fast).

Extension of COLA called Fractal Indexes (on-disk storage) are commercialized by Tokutek: https://en.wikipedia.org/wiki/Fractal_tree_index