DynamoDB 中分区和排序键查询的渐近性能是否恒定为 O(1)？

Question

这个例子

如果我查询特定艺术家的特定歌曲，性能是 O(1)，还是取决于该艺术家在数据库中有多少条目？

链接的文档表明了稳定的性能：

如果您提供该项目的 Artist 和 SongTitle 值，则可以立即访问 Music 表中的任何项目。

然而，措辞含糊不清，没有给出任何支持。

这里，架构的描述方式表明性能不会恒定：

DynamoDB 使用分区键值作为内部哈希函数的输入。哈希函数的输出确定将存储项目的分区（DynamoDB 内部的物理存储）。具有相同分区键的所有项目都存储在一起，并按排序键值排序。

我预计这会导致 O(lg m) 性能，其中 m 是数据库中该特定分区键的条目数。为了在已排序的条目列表中搜索具有正确排序键的条目，需要这一非恒定时间 - 在本例中，是为了搜索正确的SongTitle.

Answer 1

如果你get通过它的完整主键来查找一个项目 - 它是不变的。

如果您查询 by Artist，这意味着您不提供完整的主键，那么获取指向第一项的指针是constant。