数据结构是计算机科学的基石。在现实中,数据结构支撑了大大小小的计算设备的运作;在教学中,数据结构也是计算机科学入门的基本课程。在当前时代,海量的数据为数据结构提出了更高的需求。我们既想要数据结构算法有着更短的运行时间,也希望数据结构能占用更少的空间。本文从两个侧面研究数据结构。对于较为简单的低维数据结构问题,我们考虑简洁数据结构,即以接近信息论极限的空间来解决该问题。对于较为困难的高维数据结构问题,我们研究如何通过并行计算来以较少的计算资源加速它的运算;我们也尝试为高维数据结构证明时间复杂度下界,来说明其不存在高效的数据结构算法,以逼近“维数灾难”的证明。本文正文分为两个部分。第一部分以低维数据结构问题的简洁数据结构为主题。首先我们为基本的范围最值查询问题证明了复杂度下界。我们为该问题证明了首个复杂度下界,并且该下界证明了当前最前沿算法在常数时间复杂度下的最优性。我们通过彻底重构前人的复杂度下界证明技术,使得我们不再只能证明平均情况的复杂度下界,而是能够证明更高的最坏情况的复杂度下界。然后我们考虑了动态的近似集合成员查询(布隆过滤器)问题。我们考虑了一个具有很强现实意义、有趣但又很少被理论界考虑的设定:动态的数据结构可以使用动态的空间占用,但是其空间占用仅依赖于当前数据集的大小,而不是预先估计的最大大小。一方面,这样的设定可以节约大量的运行空间;另一方面,这样的设定也是实践中“可扩展性”在数据结构上的具体体现。在这样的设定中,我们为动态的近似集合成员查询构造了目前为止在所有意义上的最优的数据结构算法:在空间上,它是唯一一个在n?logu这样的自然情况下能解决该问题的简洁数据结构;在时间上,它的所有更新和查询操作都可以在最坏情况的常数时间内完成。我们的数据结构算法为Pagh、Segev和Wieder(FOCS2013)提出的开放性问题给出了一个肯定的回答。最后我们考虑了另一个根本性的数据结构问题,字典问题。我们构思了一种全新的思路来处理经典的字典数据结构中会导致空间浪费的“溢出”问题。通过这样的全新策略,在常见的u=polyn的情况下,我们的额外空间开销从≈O(n(logn)~(2/3))个比特降低到了O(nlog...logn)个比特,同时也保证了所有的更新操作和查询操作都可以在最坏情况的常数时间内完成。我们的数据结构算法为Arbitman、Naor和Segev(FOCS2010)提出的开放性问题给出了一个肯定的回答。第二部分以高维数据结构问题中的最近邻搜索为主题。围绕最近邻搜索,我们重点研究并行的随机化近似最近邻搜索,并在多项式空间中为该问题证明了并行度与内存访问量之间的渐近最优的置换。具体来说,我们分别给出了高效的数据结构算法和证明了复杂度下界。我们的数据结构上界采用了经典的线性维数约简方法再加上多路搜索。我们的复杂度下界证明将数据结构算法构造为一个通信协议,然后采用回合消去的方法证明了通信复杂度下界。然后我们考虑使用当前最前沿的数据结构下界证明技术来为λ-近邻问题证明复杂度下界。我们首先构造了一种刻画了单元采样技术的通信协议,说明通过这样的协议我们可以更简单地应用单元采样技术。接着我们通过一个通信协议的反例说明当前最前沿的单元采样技术在λ-近邻问题上难以成功。最后我们考虑了一种抽象了所有基于哈希的数据结构算法的计算模型,并在该模型中通过更简单直接地应用布尔函数分析的方法简化了前人的对于λ-近邻搜索问题的复杂度下界证明。