The most comprehensive list of structures and problems and their known lower and upper complexity bounds that I've ever found was in:
http://www.amazon.com/Handbook-Discrete-Computational-Mathematics-Applications/dp/1584883014
Basically each chapter is a compilation of the asymptotic results within each sub-discipline of computational geometry. It doesn't directly cover the more conventional data structures, however.