The discovery of materials is increasingly guided by quantum-mechanical crystal-structure prediction, but the structural complexity in bulk and nanoscale materials remains a bottleneck. Here we demonstrate how data-driven approaches can vastly accelerate the search for complex structures, combining a machine-learning (ML) model for the potential-energy surface with efficient, fragment-based searching. We use the characteristic building units observed in Hittorf's and fibrous phosphorus to seed stochastic ("random") structure searches over hundreds of thousands of runs. Our study identifies a family of hierarchically structured allotropes based on a P8 cage as principal building unit, including one-dimensional (1D) single and double helix structures, nanowires, and two-dimensional (2D) phosphorene allotropes with square-lattice and kagome topologies. These findings yield new insight into the intriguingly diverse structural chemistry of phosphorus, and they provide an example for how ML methods may, in the long run, be expected to accelerate the discovery of hierarchical nanostructures.