Cassandra中聚类键的范围查询原理及时间复杂度是怎样的？

根据官方文档说明：聚类列负责实现分区内的数据排序，当表存在多个聚类列时，数据将按嵌套排序规则存储。

本次解答基于以下示例时序表：

CREATE TABLE alerts_by_year(
  year int,
  ts timestamp,
  alert text,
  PRIMARY KEY ((year), ts)
);

对应讨论的时间范围查询语句如下：

SELECT * FROM alerts_by_year
  WHERE year=2022
  AND ts >'2022-06-24 03:11:00'
  AND ts <'2022-06-24 04:11:00'

1. 范围查询的算法复杂度 #

• 该查询既不是纯常数时间，也不会达到全分区遍历的O(n)复杂度。
• 查询第一阶段为分区定位：通过分区键year的哈希值直接定位到2022年对应的分区存储位置，这一步复杂度为O(1)常数时间。
• 查询第二阶段为分区内范围查找：由于分区内数据按ts严格有序，通过跳表/二分结构定位时间范围上下边界的复杂度为O(log N)，其中N为该分区下存储的总条目数；定位完成后顺序读取范围内的K条匹配数据，这部分复杂度为O(K)，K为查询实际返回的结果条目数。
• 整体复杂度仅和分区总条目数的对数值、实际返回结果集大小线性相关，当查询范围远小于分区总数据量时，查询效率极高。

2. 复杂度与存储类型（memtable/sstable）的相关性 #

• 算法复杂度量级和数据存储在memtable还是sstable无关。两类存储结构都严格保证分区内数据按聚类键有序排列，定位范围边界的算法逻辑一致，都是对数级定位边界+顺序读取匹配结果，不会出现某类存储需要全量遍历的情况。
• 两者仅存在IO成本的差异：memtable是驻留内存的有序跳表结构，读取无磁盘IO延迟；sstable是磁盘上的不可变有序文件，内置布隆过滤器、分区索引、聚类键稀疏索引辅助定位，读取时可能产生磁盘IO开销，但不会改变算法复杂度的量级。

3. 聚类键范围查询的实现逻辑 #

• 不需要遍历所有ts聚类键即可定位目标范围，核心是基于有序存储结构的直接裁剪和定位，具体流程如下：
  • 分区裁剪：根据分区键year=2022计算哈希值，直接定位到该分区在memtable、所有相关sstable中的存储入口，直接过滤掉所有不属于2022年的分区数据。
  • 边界定位：在单个分区的有序数据集中，memtable通过跳表结构直接查找时间范围的起止位置；sstable先通过聚类键稀疏索引匹配到范围所在的数据块，再在块内通过二分查找定位精确的起止点，全程不会扫描范围外的聚类键。
  • 结果读取：从起始位置开始顺序向后读取条目，直到触碰结束边界立即停止，仅返回符合时间范围要求的数据。

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