If you don't need insert/remove in middle, only at the end, there are more optimal data structures for Lists like RAOTS[1].
Btrees are O(log n) random access, O(log n) cons and use O(log n) excess space.
Unrolled linked lists are still O(n) random access because we ignore the constant factor of block size. They also use O(n) excess space for pointers, but have O(1) cons.
RAOTS are O(1) random access, O(1) amortized cons [O(√n) worse case], and use O(√n) excess space.
RAOTS is basically a tree of depth 1. The root is an "index block" of pointers to data blocks which grow in size proportional to the square root of the data length (similar to Hashed Array Trees, but doesn't require restructuring on each power of 2). The index block has length ~√n.
The square root is an approximation - the structure grows in "superblocks" where each superblock has `~√n` blocks of size `~√n` The pattern is: [1x1, 1x2, 2x2, 2x4, 4x4, 4x8, 8x8, 8x16, 16x16, 16x32, ...] Even indexed superblocks double the data block size, odd indexed superblocks double the number of blocks per superblock. It doesn't use an actual `sqrt()` call uses but some bit tricks via `clz`.
A simpler trick, which has no single name but have been known as "segmented lists", is where the index block points to blocks increasing in size geometrically, essentially like a dynamic array but where we don't need to `realloc`. The index block is length 1+log₂n and each index i points to a block of length 2⁽ⁱ⁻¹⁾. These have O(1) random access, O(1) amortized cons [O(n) worst case] and waste O(n) space [with constant factor of 1/2]. The random access is very efficient as it's only two dereferences and a few bit tricks:
index_block[bit_width(idx)][idx - bit_floor(idx)]
This is more cache friendly than the other approaches.
There's also Bagwell's VList[2] which is like a mashup of the "segmented list" and an unrolled list - the blocks grow geometrically in size, but still contain the pointer the the next block rather than them being in a separate index block.
If you don't need insert/remove in middle, only at the end, there are more optimal data structures for Lists like RAOTS[1].
Btrees are O(log n) random access, O(log n) cons and use O(log n) excess space.
Unrolled linked lists are still O(n) random access because we ignore the constant factor of block size. They also use O(n) excess space for pointers, but have O(1) cons.
RAOTS are O(1) random access, O(1) amortized cons [O(√n) worse case], and use O(√n) excess space.
RAOTS is basically a tree of depth 1. The root is an "index block" of pointers to data blocks which grow in size proportional to the square root of the data length (similar to Hashed Array Trees, but doesn't require restructuring on each power of 2). The index block has length ~√n.
The square root is an approximation - the structure grows in "superblocks" where each superblock has `~√n` blocks of size `~√n` The pattern is: [1x1, 1x2, 2x2, 2x4, 4x4, 4x8, 8x8, 8x16, 16x16, 16x32, ...] Even indexed superblocks double the data block size, odd indexed superblocks double the number of blocks per superblock. It doesn't use an actual `sqrt()` call uses but some bit tricks via `clz`.
A simpler trick, which has no single name but have been known as "segmented lists", is where the index block points to blocks increasing in size geometrically, essentially like a dynamic array but where we don't need to `realloc`. The index block is length 1+log₂n and each index i points to a block of length 2⁽ⁱ⁻¹⁾. These have O(1) random access, O(1) amortized cons [O(n) worst case] and waste O(n) space [with constant factor of 1/2]. The random access is very efficient as it's only two dereferences and a few bit tricks:
This is more cache friendly than the other approaches.
There's also Bagwell's VList[2] which is like a mashup of the "segmented list" and an unrolled list - the blocks grow geometrically in size, but still contain the pointer the the next block rather than them being in a separate index block.
[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
[2]:https://dl.acm.org/doi/10.5555/1756972.1756975
B+ tree if you want unrolling, B-tree if you just want the faster random access.