Pilih grid spasial

Pertanyaan

Grid spasial mana yang cocok untuk beban kerja ini, dan apa yang terjadi saat dua titik berdekatan jatuh di dua sel berbeda?

Setelah baca ini, kamu bisa menjelaskan bahwa kesamaan prefix bukan kedekatan, membandingkan bentuk sel segi empat dan heksagon, dan memilih geohash, H3, atau S2 dengan alasan yang bisa diuji.

Prasyarat dan contoh

Kamu sudah paham pencarian lewat sel dan perluasan ke tetangga (M14.02), serta partition key (M07).

Sistem lama kamu menyimpan driver dengan kunci geohash 6 karakter. Tim produk minta fitur baru: "tampilkan permintaan per area, supaya driver tahu zona mana yang lagi ramai". Kamu menjumlahkan per sel dan hasilnya kotak-kotak persegi panjang yang aneh: di satu sisi kota penuh, sisi sebelahnya yang cuma 20 m jauhnya kosong. Itu efek batas sel, bukan data yang salah.

Mekanisme

1. Geohash: mudah, tapi batasnya kasar. Geohash menyisipkan bit bujur dan lintang (kurva Z-order), lalu menulisnya sebagai base32. Dua sifatnya perlu dipegang:

• Sel dengan prefix sama berada dalam sel induk yang sama. Itu berguna untuk pencarian prefix dan untuk memperbesar atau memperkecil sel.
• Sebaliknya tidak berlaku. Titik berdekatan bisa punya prefix hampir beda total (contoh qqgux dan qquh8 pada lintang -6,2: 22 m terpisah, hanya dua karakter sama). Kalau kamu mengurutkan hasil dengan "prefix terpanjang yang sama", kamu akan salah memilih tetangga.

Sel geohash adalah persegi panjang yang menyempit ke arah kutub, jadi delapan tetangganya nggak berjarak sama: tetangga diagonal lebih jauh dari tetangga sisi.

2. H3: heksagon dengan jarak tetangga seragam. H3 (dari Uber) membagi bumi menjadi heksagon pada 16 resolusi. Keunggulannya, enam tetangga selalu berjarak sama dari pusat, sehingga "cincin k" (gridDisk) membentuk lingkaran yang lebih mendekati radius daripada kotak 3 × 3. Ini nyaman untuk agregasi, heatmap, dan harga dinamis per zona.

| Resolusi H3 | Luas sel rata-rata | Panjang sisi | | ----------- | ------------------ | ------------ | | 7 | sekitar 5,16 km² | sekitar 1,22 km | | 8 | sekitar 0,74 km² | sekitar 461 m | | 9 | sekitar 0,105 km² | sekitar 174 m |

Catatannya: H3 punya 12 sel pentagon, dan hubungan induk-anak nggak sepenuhnya mengandung (heksagon anak tidak persis berada di dalam induknya, karena heksagon tak bisa disubdivisi rapi).

3. S2: hierarki persegi pada kubus. S2 (dari Google) memproyeksikan bumi ke enam sisi kubus dan membagi tiap sisi secara rekursif. ID sel berupa bilangan 64-bit dengan urutan kurva Hilbert, yang menjaga lokasi berdekatan lebih sering berdekatan di urutan ID daripada Z-order. Sel level 30 berukuran sekitar satu sentimeter. Kekuatan S2: pengandungan hierarkis yang tepat (anak selalu di dalam induk) dan RegionCoverer, yang menutup poligon atau lingkaran dengan campuran sel berbeda level. Ini cocok untuk geofence dan query area bentuk bebas.

4. Cara memilih.

| Kebutuhan | Pilihan wajar | | ----------------------------------------------- | ----------------- | | Kunci prefix di key-value store, sederhana | Geohash | | Agregasi per zona, heatmap, tetangga seragam | H3 | | Poligon besar, hierarki tepat, ID numerik | S2 | | Data kecil, jarang berubah, query bentuk bebas | Indeks spasial DB |

5. Batas sel adalah masalah semua grid. Pergantian sel itu seperti batas partisi pada M07: sistem tidak melihat apa pun di seberangnya. Perbedaannya hanya tempat artefak muncul. Geohash membuat persegi panjang yang memiringkan hasil pada lintang tinggi, H3 membuat tepi bergerigi, S2 membuat tepi yang mengikuti kubus. Semuanya mengharuskan tetangga atau cincin diperiksa.

Saat rancangan ini gagal

• Menganggap prefix sama berarti dekat. Kamu menyortir dengan ORDER BY geohash dan menganggap baris berurutan itu bertetangga. Di batas Z-order, baris berurutan bisa terpisah ratusan kilometer.
• Resolusi tetap untuk semua kepadatan. Sel yang pas di Sudirman terlalu kecil di Gunung Kidul. Solusinya resolusi adaptif (S2 covering, atau H3 dengan resolusi berbeda per wilayah) atau memadatkan sel kosong.
• Memakai sel sebagai "zona bisnis". Batas sel adalah artefak teknis, bukan batas wilayah layanan. Driver yang bergeser 10 m melintasi batas sel dan harga zona melompat.
• Mencampur sistem grid. Menyimpan geohash di satu tabel dan H3 di tabel lain, lalu menggabungkannya di aplikasi. Kamu butuh titik lat/lon sumber untuk menerjemahkan di antaranya.
• Pentagon dan sudut kubus. Perilaku tepi H3 dan S2 yang jarang tapi ada: simpan tes untuk lokasi dekat sudut, bukan hanya Jakarta.

Contoh tandingan: untuk harga dinamis per zona, H3 resolusi 8 (0,74 km²) membuat tiap zona mempunyai enam tetangga seragam dan perhitungan rata-rata tetangga sederhana. Dengan geohash, kamu menulis pengecualian untuk tetangga diagonal.

Latihan

Aplikasi pesan antar punya dua kebutuhan: (a) cari driver dalam radius 1 km saat pelanggan memesan, dan (b) tampilkan peta panas permintaan per area 0,7 km² untuk operator. Tim hanya mau satu sistem grid.

Pilih satu dan sebutkan satu konsekuensi yang harus diterima.

Lihat pembahasan+

Dua jawaban sama-sama bisa dipertanggungjawabkan.

H3 resolusi 8 (0,74 km²): enam tetangga seragam membuat cincin-1 dan cincin-2 menutup radius 1 km dengan baik dan peta panas per sel apa adanya. Konsekuensi: kamu perlu library H3 di semua klien dan layanan yang menghitung sel, dan sel resolusi 8 untuk pencarian terlalu besar di area padat, jadi pencarian kandidat tetap butuh filter jarak yang tepat.

Geohash panjang 6 (0,74 km² di khatulistiwa): cocok sebagai kunci key-value dan cukup untuk pencarian. Konsekuensi: peta panas berbentuk persegi panjang dengan tetangga diagonal berjarak berbeda, sehingga warna di batas lebih ramai daripada kenyataan dan operator bisa salah menafsirkan.

Kesimpulan yang diterima: bila peta panas penting untuk operator, pilih H3. Bila dua kebutuhan hanya ada di satu layanan kecil, geohash lebih murah dioperasikan. Alasan yang buruk adalah "karena Uber pakai H3".

Terkait

• Sebelumnya: M14.02 Temukan kandidat terdekat.
• Lanjut ke M14.04 Tangani entitas yang bergerak.
• M07 (partisi dan penempatan data) menjelaskan kenapa batas sel mirip batas partisi.
• Lab L14 dan rancangan D17 belum tersedia.

Catatan

• Asumsi: angka luas dan panjang sisi H3 adalah rata-rata dokumentasi H3, nilai asli bervariasi per sel.
• Yang nggak dibahas: hierarki S2 berlevel penuh, proyeksi H3 lanjut, dan indeks DB spesifik vendor.
• Rujukan: dokumentasi H3 (h3geo.org) dan S2 Geometry (s2geometry.io). Nilai harus dicek ulang terhadap versi yang kamu pakai.
• Terakhir ditinjau: 26 Oktober 2026.