2026-09-01
late.rs
use std::collections::BTreeSet;
fn main() {
// index on (user, time)
let index = BTreeSet::from([(1, 30), (1, 70), (2, 10), (2, 50), (3, 20)]);
let late: Vec<_> = index.range((0, 40)..).collect();
println!("{late:?}");
}
index は、どの利用者がいつ操作したかの記録を (user, time) の組で持つ BTreeSet です。このコードは、利用者を問わず、時刻が40以上の記録だけを取り出して表示するつもりのものです。入力はありません。いまの出力は [(1, 30), (1, 70), (2, 10), (2, 50), (3, 20)] で、本来の出力は [(1, 70), (2, 50)] です。
Answer
Wrong
let late: Vec<_> = index.range((0, 40)..).collect();
range((0, 40)..) は、(0, 40) 以上の要素をすべて返します。タプルの大小は辞書式順序(lexicographic order)で、1つ目の要素を先に比べ、等しいときだけ2つ目を比べます。user が1以上の要素は time がいくつでも (0, 40) より大きいので、40が効くのは user が0の要素だけです。user が0の記録は無いため、5件すべてが返ります。
Right
let late: Vec<_> = index.iter().filter(|&&(_, time)| time >= 40).collect();
(user, time) の順の並びでは、時刻が40以上の記録は利用者ごとの区間に散らばり、一続きになりません。この並びのままでは全件をたどって time を1つずつ確かめるしかなく、filter はそれをそのまま書いたものです。時刻だけで探すことが多いなら、(time, user) の順に並べた別の BTreeSet を持てば、range((40, 0)..) で一続きの区間として取り出せます1。
- データベースの複合インデックスも同じで、
(user, time)のインデックスはWHERE time >= 40だけの問い合わせでは範囲を絞れません。先頭の列から順に条件が付いているときだけ範囲を絞れるという性質は、leftmost prefix(左端からの接頭辞)の規則と呼ばれます。