Laporan bulanan harus tampil terurut, papan klasemen harus menampilkan juara di atas, dan pencarian “semua produk dengan harga Rp50.000 sampai Rp100.000” harus bisa memotong rentang. HashMap gagal di ketiga kebutuhan itu — bukan karena kualitasnya buruk, melainkan karena desainnya memang tidak menyimpan urutan: posisi key ditentukan hash acak. Rust menyediakan BTreeMap<K, V> untuk dunia yang butuh keterurutan: peta berbasis B-tree yang menjaga key tersusun rapi dari awal hingga akhir. API-nya nyaris identik dengan HashMap — insert, get, remove, len semuanya hadir — sehingga fokus chapter ini adalah apa yang berbeda: keterurutan yang terjamin, method khusus seperti first_key_value dan range, serta mesin B-tree yang membuat semuanya mungkin.

BTreeMap Menjaga Urutan Key #

Kita masukkan nama siswa dengan urutan yang sengaja diacak — Citra dulu, baru Andi, baru Budi — lalu telusuri isinya:

rust 
use std::collections::BTreeMap;

fn main() {
    let mut exam_scores = BTreeMap::new();
    exam_scores.insert("Citra", 88);
    exam_scores.insert("Andi", 75);
    exam_scores.insert("Budi", 92);

    println!("Daftar nilai (terurut berdasarkan nama):");
    for (student, score) in &exam_scores {
        println!("{}: {}", student, score);
    }

    println!("Jumlah siswa: {}", exam_scores.len());
}

Output yang Dihasilkan:

text 
Daftar nilai (terurut berdasarkan nama):
Andi: 75
Budi: 92
Citra: 88
Jumlah siswa: 3

Output tersebut stabil di setiap eksekusi — perhatikan bahwa ini bukan pola “kumpulkan lalu sort” seperti chapter HashMap: loop for (student, score) in &exam_scores langsung menelusuri isi map, dan hasilnya tetap terurut abjad Andi-Budi-Citra meskipun urutan penyisipan adalah Citra-Andi-Budi. Mari kita bedah barisnya:

  1. Baris 4 (let mut exam_scores = BTreeMap::new();): peta kosong bertipe BTreeMap<&str, i32> — tipe key &str dan value i32 disimpulkan dari pasangan pertama.
  2. Baris 5-7 (exam_scores.insert(...)): tiga pasangan masuk dengan urutan acak. Struktur internal B-tree menempatkan setiap key pada posisi yang benar secara keterurutan pada saat penyisipan — tidak ada proses sortir belakangan.
  3. Baris 10-12 (for (student, score) in &exam_scores): iterasi BTreeMap selalu berjalan dari key terkecil ke key terbesar, hasil dari in-order traversal pada pohon yang tersusun.
  4. Baris 14 (exam_scores.len()): sama seperti koleksi lain, len menghitung jumlah pasangan — yaitu 3.

Ketentuan kuncinya satu: tipe key harus mendukung perbandingan urutan penuh — angka, String, dan &str memenuhinya secara bawaan. Key &str diurutkan secara leksikografis (urutan kamus), dan key angka diurutkan dari terkecil ke terbesar.

Mekanisme B-Tree di Balik Layar #

B-tree adalah pohon seimbang dengan ciri khas: setiap node memuat banyak key sekaligus dalam keadaan terurut, bukan satu key per node seperti pohon biner biasa. Contoh bentuk dengan enam key:

Aturan yang membuat diagram di atas menjadi pohon pencarian: semua key di anak kiri selalu lebih kecil daripada key pertama induknya, semua key di anak tengah berada di antara kedua key induk, dan semua key di anak kanan lebih besar daripada key kedua induk. Penelusuran in-order — kunjungi anak kiri, key pertama, anak tengah, key kedua, anak kanan — menghasilkan deretan key yang terurut penuh: 60, 75, 80, 95, 105, 120. Node yang memuat banyak key membuat pohon tetap dangkal meski datanya besar, dan kedalaman yang kecil berarti pencarian satu key hanya butuh sedikit lompatan node — tepatnya berbentuk logaritmik terhadap jumlah key.

Perbandingannya dengan HashMap menjadi jelas dari sini. Hash mencari posisi lewat perhitungan aritmetika dalam satu langkah besar; B-tree mencari posisi dengan menelusuri node-node yang terurut lewat perbandingan. Konsekuensi trade-off-nya: HashMap menang dalam kecepatan murni untuk lookup tunggal, BTreeMap menang dengan keterurutan, pencarian rentang, serta kemampuan menemukan key minimum dan maksimum. Satu bonus yang sering dilupakan: B-tree tidak perlu menghitung hash sama sekali, sehingga tipe key yang mahal di-hash tetap nyaman dipakai.

Elemen Pertama dan Terakhir #

Karena key tersimpan terurut, posisi terkecil dan terbesar dapat diambil langsung tanpa menelusuri seluruh isi — method first_key_value dan last_key_value mengembalikan Option berisi tuple reference (&K, &V):

rust 
use std::collections::BTreeMap;

fn main() {
    let mut exam_scores = BTreeMap::new();
    exam_scores.insert("Citra", 88);
    exam_scores.insert("Andi", 75);
    exam_scores.insert("Budi", 92);

    if let Some((student, score)) = exam_scores.first_key_value() {
        println!("Siswa pertama (abjad): {} - {}", student, score);
    }

    if let Some((student, score)) = exam_scores.last_key_value() {
        println!("Siswa terakhir (abjad): {} - {}", student, score);
    }
}

Output yang Dihasilkan:

text 
Siswa pertama (abjad): Andi - 75
Siswa terakhir (abjad): Citra - 88

Mari kita telaah pola pemakaiannya:

  1. Baris 9-11 (if let Some((student, score)) = ...first_key_value()): method mengembalikan Option<(&K, &V)> — None saat peta kosong, karena peta kosong tidak punya elemen pertama. Pattern Some((student, score)) mendestrukturisasi tuple reference sekaligus: student menerima &&str, score menerima &i32.
  2. Baris 13-15 (last_key_value()): mekanisme yang sama untuk ujung sebaliknya. Kedua method membaca posisi paling kiri dan paling kanan dari struktur pohon — operasi yang oleh HashMap harus disimulasikan dengan menelusuri seluruh isi.

Menelusuri Rentang dengan range #

Fitur yang benar-benar tidak dimiliki HashMap: mengambil hanya potongan keterurutan. Method range menerima batas bawah dan batas atas bergaya Range — sama seperti range pada loop for — lalu menghasilkan penelusuran hanya atas key-key di dalam rentang tersebut:

rust 
use std::collections::BTreeMap;

fn main() {
    let mut grade_counts = BTreeMap::new();
    grade_counts.insert(60, 2);
    grade_counts.insert(75, 4);
    grade_counts.insert(80, 3);
    grade_counts.insert(95, 1);

    println!("Nilai ujian di rentang 70-85:");
    for (score, count) in grade_counts.range(70..=85) {
        println!("Nilai {}: {} siswa", score, count);
    }

    println!("Semua nilai (terurut):");
    for (score, count) in &grade_counts {
        println!("Nilai {}: {} siswa", score, count);
    }
}

Output yang Dihasilkan:

text 
Nilai ujian di rentang 70-85:
Nilai 75: 4 siswa
Nilai 80: 3 siswa
Semua nilai (terurut):
Nilai 60: 2 siswa
Nilai 75: 4 siswa
Nilai 80: 3 siswa
Nilai 95: 1 siswa

Mari kita bedah bagian intinya:

  1. Baris 11 (grade_counts.range(70..=85)): rentang inklusif 70..=85 menjaring key 75 dan 80 — key 60 terlalu kecil, key 95 terlalu besar, dan keduanya tidak pernah disentuh oleh penelusuran. Pohon terurus membuat operasi ini sebanding dengan jarak node, bukan dengan jumlah seluruh key.
  2. Baris 16-18 (for (score, count) in &grade_counts): iterasi penuh tetap tersedia dan tetap terurut — pembanding yang menegaskan bahwa range memang potongan dari keterurutan yang sama.

Kombinasi first_key_value, last_key_value, dan range adalah alat baku untuk laporan bersyarat: siswa dengan nilai tertinggi, produk termurah, atau transaksi di bulan tertentu — semuanya terjawab tanpa memuat seluruh isi peta ke memori sementara.

HashMap atau BTreeMap #

Keputusan pemilihan bisa dirangkum dalam empat pertanyaan:

  • Apakah program hanya mencari value berdasarkan key, tanpa peduli urutan? HashMap — tercepat untuk pola akses tersebut.
  • Apakah isi harus tampil terurut, atau key minimum/maksimum dibutuhkan? BTreeMap.
  • Apakah pencarian rentang muncul dalam daftar kebutuhan? BTreeMap — range tidak ada padanannya di HashMap.
  • Apakah key berupa tipe yang mahal di-hash (misalnya string panjang) atau urutannya sulit ditentukan? BTreeMap hanya butuh perbandingan.

Ringkasan #

BTreeMap menyimpan pasangan key-value dengan key yang selalu terurut: iterasi berjalan dari key terkecil ke terbesar dengan hasil yang stabil antar eksekusi, first_key_value dan last_key_value mengambil ujung keterurutan dalam Option, dan range memotong potongan keterurutan tanpa menelusuri sisanya. Mesin di baliknya adalah B-tree — node berisi banyak key terurut dengan penelusuran in-order dan pencarian logaritmik, tanpa perhitungan hash sama sekali. Kita kini memegang empat koleksi standar dengan karakter lengkap, dan tugas terakhir section ini adalah melatih refleks memilihnya: chapter penutup, Memilih Koleksi.