adityamukho · May 15, 2026 · May 15, 2026 · May 15, 2026 · May 15, 2026 · May 15, 2026
@@ -331,6 +331,27 @@ pub fn populate_with_dept(n: usize, dept_count: usize) -> Arc<Minigraf> {
     Arc::new(db)
 }
 
+/// In-memory DB with `n` entities, each with `:val` and `:name` attributes.
+/// Suitable for point-lookup and attribute-scan benchmarks.
+///
+/// Schema:
+///   `:e{i} :val {i}` for i in 0..n
+///   `:e{i} :name "entity{i}"` for i in 0..n
+pub fn populate_with_names(n: usize) -> Arc<Minigraf> {
+    let db = Minigraf::in_memory().unwrap();
+    for batch_start in (0..n).step_by(50) {
+        let batch_end = (batch_start + 50).min(n);
+        let mut cmd = String::from("(transact [");
+        for i in batch_start..batch_end {
+            cmd.push_str(&format!("[:e{i} :val {i}]", i = i));
+            cmd.push_str(&format!(r#"[:e{i} :name "entity{i}"]"#, i = i));
+        }
+        cmd.push_str("])");
+        db.execute(&cmd).unwrap();
+    }
+    Arc::new(db)
+}
+
 /// In-memory DB with `n` value facts, `dup_fraction`% of values are duplicates.
 /// Each entity has `:val` integer where `dup_fraction`% map to same values.
 ///

@@ -1465,6 +1465,44 @@ fn bench_retract(c: &mut Criterion) {
     }
 }
 
+// ── B+Tree selective lookup (Issue #208) ─────────────────────────────────────
+
+fn bench_btree_lookup(c: &mut Criterion) {
+    const SCALES: &[(&str, usize)] = &[("1k", 1_000), ("10k", 10_000), ("100k", 100_000)];
+
+    // entity_point: single known entity literal — should be O(1) with selective lookup.
+    {
+        let mut group = c.benchmark_group("btree_lookup/entity_point");
+        group.sample_size(10);
+        for &(label, n) in SCALES {
+            group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| {
+                let db = helpers::populate_with_names(n);
+                b.iter(|| {
+                    db.execute(r#"(query [:find ?n :where [:e0 :name ?n]])"#)
+                        .unwrap()
+                });
+            });
+        }
+        group.finish();
+    }
+
+    // attribute_scan: all entities via a single bound attribute.
+    {
+        let mut group = c.benchmark_group("btree_lookup/attribute_scan");
+        group.sample_size(10);
+        for &(label, n) in SCALES {
+            group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| {
+                let db = helpers::populate_with_names(n);
+                b.iter(|| {
+                    db.execute("(query [:find ?e ?n :where [?e :name ?n]])")
+                        .unwrap()
+                });
+            });
+        }
+        group.finish();
+    }
+}
+
 criterion_group!(
     benches,
     bench_insert,
@@ -1488,5 +1526,6 @@ criterion_group!(
     bench_concurrent_btree_scan,
     bench_prepared,
     bench_retract,
+    bench_btree_lookup,
 );
 criterion_main!(benches);