以下是关于2级数组数据结构的详细描述，来源于"一种表示动态多重集的紧凑数据结构"

我们使用一个两级旋转数组来存储元素，并附加指针指向每个旋转数组的开始。旋转数组是有序数组的任意循环移位。在两级旋转数组中，元素存储在一个分为⌈√(2n)⌉块中的数组中，其中第i块是一个长度为i的旋转数组。第i块中的所有元素都小于或等于第i + 1块中的任何元素。我们显式地存储每个块的起始位置。要搜索元素e，我们首先进行二分搜索以找到两个相邻的块，其中e的第一个（最后一个）出现可以位于其中。然后我们在这些块中进行二分搜索以找到答案。因此，基于元素的搜索可以在O(lg n)的最坏情况下时间复杂度内得到支持。通过记录元素所在的块以及从块开始处的偏移量，可以实现在O(1)的最坏情况下时间复杂度内获得该元素的定位器。给定一个定位器，可以在O(1)的最坏情况下时间复杂度内轻松获得其前驱或后继的定位器。要插入元素e，我们首先找到e应插入的位置（使用上界）。我们通过从旋转数组中删除最后一个元素并将新元素与最后一个元素之间的所有元素向前移动一个位置来在该块中执行插入。然后我们必须按照以下方式更新插入块之后的每个块：从当前旋转数组中删除最后一个元素，并插入来自上一个旋转数组的最后一个元素，该元素现在成为旋转数组的新第一个元素。此外，我们还需要在O(1)的时间复杂度内更新每个块的起始位置。因此，可以在O(√n)的最坏情况下时间复杂度内得到支持。删除操作可以类似执行。