Count the reads, both ways

import java.util.*;

/**
 * Warm-up: count the work, both ways.
 *
 * This is a model of an index, not a database. The only property being
 * modelled is the one that matters — the keys are kept in sorted order — and
 * every claim about lookups, ranges and ORDER BY follows from it.
 *
 * A real B+tree stores keys in pages with a fanout in the hundreds, so its
 * depth is three or four rather than twenty. That makes these numbers
 * pessimistic for a real index, and the argument identical.
 */
public class Starter {

    static int rows = 1_000_000;

    static int customerOf(int row) {
        return (int) ((row * 7919L) % 250_000);
    }

    /** The index: (key, row) packed into a long, sorted by key. */
    static long[] buildIndex(int n) {
        long[] entries = new long[n];
        for (int row = 0; row < n; row++) {
            entries[row] = ((long) customerOf(row) << 32) | row;
        }
        Arrays.sort(entries);
        return entries;
    }

    public static void main(String[] args) {
        long[] index = buildIndex(rows);
        int target = 12_345;

        // ── the scan ──
        int examined = 0, scanMatches = 0;
        for (int row = 0; row < rows; row++) {
            examined++;
            if (customerOf(row) == target) scanMatches++;
        }
        System.out.println("scan  : examined " + examined + ", matched " + scanMatches);

        // TODO 1: write the index lookup. Binary search `index` for the first
        // entry whose key is >= target, counting comparisons as you go, then
        // walk forward while the key still equals target.
        //
        //     int lo = 0, hi = rows, comparisons = 0;
        //     while (lo < hi) { ... }
        //
        // Predict the comparison count before you run it. The rule is
        // ceil(log2(rows)).

        // TODO 2: change `rows` to 2_000_000 and run again. One number
        // doubles and the other goes up by one. Say which, and why that is
        // the whole argument for indexes.

        // TODO 3: use the SAME index, unchanged, for a range —
        // customer_id BETWEEN 100000 AND 100004. Find the start, then read
        // forward. Note that you did not need a different index.

        // TODO 4: check whether the range results came out sorted without
        // sorting them. Then say what that means for ORDER BY customer_id.

        // TODO 5: a hash index would answer TODO 1 in one step and could not
        // answer TODO 3 at all. Explain why in one sentence — the answer is
        // about what a hash does to neighbouring values.

        // TODO 6: the index above holds only (customer_id, row). Say what
        // would have to change for a query selecting `total` to be answered
        // without touching the table at all, and what that is called.
    }
}