Hi! There is my pre alpha implementation of sparse array based on adaptive radix tree: https://github.com/Iakh/d-art-containers
It is based on this article http://www-db.in.tum.de/~leis/papers/ART.pdf And here is general information about radix tree: https://en.wikipedia.org/wiki/Radix_tree Radix tree uses node with "Radix" children. For this iplementation Radix == 256(byte capacity). Each byte of a key for the container corresponds one level of the tree (tree haight is equal to size of the key). Also radix tree doesn't store keys of the data explicitly. A key can be restored on the path to the leaf. ART uses several optimizations few of wich currently implemented: - Adaptive node size: there are Node4, Node16, Node48, Node256 with different strategies to store elements (implemented Node4 and Node256) - Collapsing nodes. Nodes with one child does not explixitly created. Only their keys stored. (implemented) - SIMD optimisations for fast access in nodes other then Node256. (not implemented) Also implemented sort of range over each element. Is the container needed in Phobos?
