Namaran

Code daily. Without assist.

2026-09-01

scan.rs

use std::collections::BTreeSet;

fn main() {
    // index on (shop, price)
    let index = BTreeSet::from([(1, 5), (1, 9), (2, 1), (2, 5), (3, 2), (3, 5), (4, 5)]);
    let scanned: Vec<_> = index.range((1, 5)..=(3, 5)).collect();
    let hits = scanned.iter().filter(|row| row.1 == 5).count();
    println!("{} {}", scanned.len(), hits);
}

これは何を出力するでしょうか?

Answer

6 3 です。

BTreeSet はタプルを辞書式順序(lexicographic order)で並べます。1つ目の要素で比べ、等しいときだけ2つ目の要素で比べる順序です。range((1, 5)..=(3, 5)) が返すのは、この順序で (1, 5) 以上 (3, 5) 以下の要素で、2つ目が5の要素だけを集めたものではありません。

並び順は (1, 5), (1, 9), (2, 1), (2, 5), (3, 2), (3, 5), (4, 5) で、範囲に入るのは先頭から (3, 5) までの6個です。shop が2の要素は、price がいくつでも (1, 5) より大きく (3, 5) より小さいので、すべて入ります。price の5が効くのは範囲の両端だけで、6個のうち price が5なのは (1, 5)、(2, 5)、(3, 5) の3個です。

データベースで (shop, price) の順に作った複合インデックス(composite index)に「shop が1から3、price が5」と問い合わせると、同じことが起きます。先頭の列が範囲の条件だと、2番目の列の条件は読む範囲を狭められず、読んだ行を1つずつ捨てることにしか使えません。列の順を (price, shop) にすれば price が5の行は連続して並ぶので、読むのは条件に合う3行だけで済みます。