在一个论坛上，我被告知数组已经是一个平衡的B树。它是如何获得的？也许是因为在 B 树中添加元素具有固定的复杂性？
我想纯粹从数据结构的角度来看，一个排序数组a可以被认为是只有一个节点的B树。即，大于a length阶的B树。在这种情况下，您的根节点将是数组a并且由于树中只有一个节点，因此该根节点将是叶节点（这意味着它保存数据而不仅仅是键）。
因为在深度为零处只有一个节点，这满足了在平衡的B树中所有叶节点必须位于相同深度的要求。
这将适用于顺序的定义，其中 m 阶的 B 树是每个节点最多有 m 个子节点的 B 树。这意味着节点最多可以包含 m-1 个键（如果是叶节点，则包含元素）。
我不知道 B 树，但众所周知，排序数组中嵌入了平衡二叉搜索树的结构。它在高德纳等地。
考虑数组的一部分，其范围low到high（high像往常一样指向一个末端）。树的根位于(low + high) / 2（我们称该索引为 mid ）。左子树从 low 延伸到 mid 。右侧子树从 mid + 1 延伸到 high 。零长度范围对应于叶子。
您可以轻松看到，这一定是一个搜索树：中间左侧的元素<=根元素，因为数组是排序的，根据定义，这些元素正是左侧子树中的元素。它在右侧的工作方式相同。
您还可以看到此隐式树必须平衡，因为左右子树的平均长度相同。
我之前在PHP中测试过这个问题。我将 18000 条日志记录插入临时表并进行查询，然后将这些日志记录添加到数组中（它是关联的）并再次执行相同的查询。前者平均耗时0.006秒，而后者平均耗时0.51秒。所以我认为关联数组至少在 PHP 中不是 b-treed。