I was using it to store tiled maps. I ended up replacing it with a MapSchema -- it works pretty well for my needs so far.
For the general problem, maybe you could make this easier by getting rid of some more advanced functionality? Taking linear (or even superlinear?) time to look at one element of an array is a very odd thing to see. I think it's more important to fix this basic functionality than to have all these operations. It's your decision to make though.