DynamoDB复合键查询的执行逻辑与时间复杂度疑问

1. "Fish"记录的查询流程 #

当查询分区键为"Fish"的记录时，DynamoDB的处理逻辑如下：

• 首先通过"Fish"的哈希值计算，定位到其所属的物理分区（即使该分区包含"Lizard"这类其他分区键的记录，也不会干扰定位过程）。
• 每个物理分区内部，同一分区键的所有记录会被组织成按排序键（Name）有序的独立集合——不同分区键的记录在物理分区内相互隔离，不会混在一起排序。
• 针对该有序集合，DynamoDB直接执行查询操作：如果是精确匹配排序键，会用二分查找快速定位对应位置；如果是范围查询，会先找到范围起始点，再顺序读取范围内的记录。

2. 排序键重复场景的处理 #

当"Fish"分区键下存在多条排序键（Name）相同的记录时：

• 二分查找会先定位到该排序键对应的起始位置，然后连续读取所有同排序键的记录（这些记录在有序集合里是连续存储的）。
• 此时时间复杂度分为两部分：定位起始点的O(log k)（k为"Fish"分区键下的总记录数），加上读取m条重复记录的O(m)（m为重复记录的数量）。

3. 复合键查询的时间复杂度结论 #

不能认为复合键查询的时间复杂度始终为O(log n)（n为物理分区大小），核心原因和细节如下：

• 物理分区的总大小n包含了其他分区键的记录，而查询只会针对目标分区键下的有序集合（大小为k）操作，与n无关。
• 不同查询类型的复杂度存在差异：
  • 精确匹配分区键+精确匹配排序键：O(log k)
  • 精确匹配分区键+排序键范围查询：O(log k + m)（m为范围内的记录数）
  • 精确匹配分区键+排序键相等查询（含重复记录）：O(log k + m)（m为重复记录数）

内容的提问来源于stack exchange，提问作者Max