@maruloop さんがTwitterで[[Cassandra]]のキー参照の最悪ケースの時間計算量について言及されていて、気になったので手元のCassandra Definitive Guideで調べた。 <iframe class="hatenablogcard" style="width:100%;height:155px;max-width:680px;" title="maru on Twitter: "Cassandraのvalueのgetって、最悪ケースの計算量っていくつになる？ 例えば、major compactionしてしまい、SSTableがひとつになって、かつbloomfilterで偽陽性が出たケースはそのノードのSSTable全走査になる？" / Twitter" src="https://hatenablog-parts.com/embed?url=https://twitter.com/maruloop/status/1274144971289812993" width="300" height="150" frameborder="0" scrolling="no"></iframe> 1. row cacheを調べる 2. memtablesと[[SStable]]sを調べる 3. [[Bloom filter]]を調べる 4. key cacheを調べる 5. ディスク上のSSTable indexesを調べる というような流れのRead Pathになっている。