What's the name of this array data structure?

This data structure is closely related to the hashed array tree (HAT) data structure. A hashed array tree is structured like what you've described above - you have a top-level array of size √n, where each entry is a pointer to an array with √n elements. This makes insertions and lookups reasonably fast and has only O(√n) memory overhead compared with the O(n) memory overhead of a traditional dynamic array.

Your structure differs from the HAT in a few ways. For starters, your structure does not appear to have a way to grow the structure if you need more space, whereas the HAT is designed to be growable. Additionally, your structure allows for random insertions, whereas the HAT is designed for sequential insertions. That said, there's no fundamental reason that the HAT has to behave this way, so you can think of your data structure as a slight modification on the HAT. In fact, you might want to look at how the HAT grows in order to make your data structure support growth.

Hope this helps!

Well, I would call that a square matrix with row vectors. If not fully populated, it's a sparse square matrix with row vectors.^1.

There are two optimizations at work here. The first is the sparse memory allocation, and the second is the strength reduction of the row subscript calculation. This optimization is probably not quite so important with superscaler CPU's executing instructions out-of-order, and in an age where compilers routinely do global flow optimizations.

But it does allow row indexing via a pointer dereference rather than a multiply by the row size.

---

^{1. However, in numerical analysis, a sparse matrix is one that's mostly zeroes, and so a sparse data structure formally has the same definition. In this case, it's more of a partial data structure, but there just aren't, to my knowledge, accepted terms for these things.}