I am the author of Are there well-solved and simple storage patterns for Solidity?.
Doubling is indeed possible if the payloads themselves are quite compact. It's relative, because there is a fixed-cost overhead associated with index maintenance. It's less expensive than a linked-list or other sorting scheme, but more expensive than no reorganization.
Regarding your array that grows indefinitely. You'll find that your append cost is consistent at any scale. SSTORE costs 20,000 to write a word to a new key and 5,000 to overwrite an existing key. This may seem counter-intuitive, but it's true. Avoid anything that resembles
for(i=start; i<finish ... because you may be introducing a gas cost that will increase with scale.
You'll find it is not practical for a contract to enumerate the list, e.g.
function getNextRecord(... if it must wade through many zeroed out (soft deleted) rows to find it, but contracts can access the table just fine if they know what row they want. The key is O(1), not O(n). The cost to retrieve a record with a known index is the same at any scale. Forget what you know about searching through indexes. The cost is the same.
You'll also find that software clients can read one row at a time. Basically, reads are "free".
Last, but important, software clients can employ any caching strategy they like which means the off-chain database can be cleaned of "deleted" records, while what remains can be verified on the chain by anything that wants to. Have a look over here for more on this: https://blog.b9lab.com/the-joy-of-minimalism-in-smart-contract-design-2303010c8b09
Hope it helps.