Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Bagaimana aplikasi menemukan driver atau tempat terdekat? Geohash vs quadtree dengan TypeScript, PostGIS ST_DWithin, Redis GEOSEARCH, dan hitungan write rate.
Matthews Wong
Software Engineer
Ringkasan Utama
Untuk menemukan driver atau tempat terdekat, indeks setiap posisi dengan kunci spasial, bukan memindai seluruh tabel. Geohash mengubah koordinat menjadi string yang bisa dicocokkan prefix-nya, tetapi delapan sel tetangga juga harus dicari; quadtree menyesuaikan kepadatan di memori. Pilihan pragmatisnya adalah PostGIS dengan GiST index dan ST_DWithin, atau Redis GEOSEARCH untuk posisi live.
Layar aplikasi ride-hailing menampilkan sepuluh mobil dalam radius dua kilometer, dan query versi pertamanya selalu sama: hitung jarak dari penumpang ke setiap baris lalu urutkan. Cukup untuk seratus driver uji coba, tetapi langsung menjadi query paling lambat begitu armada sungguhan masuk.
Ini desain contoh, bukan cerita pengalaman. Saya belum pernah menjalankan sistem dispatch, jadi setiap angka di bawah diturunkan dari asumsi yang disebutkan dengan hitungan yang ditunjukkan, dan perilaku tiap tool berasal dari dokumentasinya. Stack-nya yang biasa saya pakai di satu VPS, Postgres dan Redis di balik service Node, dan kode TypeScript-nya bisa dijalankan apa adanya.
Karena jarak dihitung dari titik query, tidak ada index biasa yang bisa menjawabnya. Btree pada lat dan lng hanya bisa mempersempit satu sumbu, tidak bisa mengekspresikan lingkaran, sehingga planner membaca semuanya, menghitung haversine per baris, lalu mengurutkan. Query di bawah benar, dan justru versi yang harus dihindari.
-- Wrong: correct, and a full table scan on every request. No index can help,
-- because the distance is computed per row from the query point.
SELECT driver_id,
6371 * 2 * asin(sqrt(
power(sin(radians(lat - -6.2088) / 2), 2) +
cos(radians(-6.2088)) * cos(radians(lat)) *
power(sin(radians(lng - 106.8456) / 2), 2)
)) AS km
FROM driver_positions
ORDER BY km
LIMIT 10;Biayanya adalah hasil kali dua angka yang tidak Anda kendalikan, ukuran armada dan laju pencarian. Dengan input asumsi di bawah, rencana naif melakukan 20 juta perhitungan jarak per detik. Membatasi kerja ke sembilan sel geohash memangkasnya menjadi sekitar 149 ribu, karena sel adalah filter kasar yang membuang sebagian besar kota sebelum trigonometri dijalankan.
Assumed inputs (a design exercise, not a measurement):
online drivers = 100,000
nearby searches = 200 per second
Naive plan: every search computes a distance for every driver
100,000 x 200 = 20,000,000 distance computations per second
Bounded plan: only drivers in 9 geohash cells (precision 6, around Jakarta)
one cell = 0.611 km x 1.216 km = 0.743 km2
nine cells = 9 x 0.743 = 6.69 km2
city area (assumed) = 30 km x 30 km = 900 km2
share of the city = 6.69 / 900 = 0.74%
candidates (if drivers are spread evenly) = 100,000 x 0.0074 = about 743
work per second = 743 x 200 = 148,600 distance computations
(135x fewer; real drivers cluster, so test your own density)Itulah inti semua teknik di artikel ini: ganti kedekatan dua dimensi dengan kunci satu dimensi yang bisa di-seek oleh index, lalu saring sedikit kandidat yang tersisa dengan jarak sebenarnya.
Geohash berulang kali membagi dua dunia. Setiap bit menyatakan titik berada di separuh mana dari rentang longitude, lalu separuh mana dari rentang latitude, dan setiap lima bit menjadi satu karakter alfabet base32 0123456789bcdefghjkmnpqrstuvwxyz yang melewatkan a, i, l, dan o. Encoder di bawah mengikuti definisi itu dan menghasilkan dua contoh acuan di halaman Wikipedia, ezs42 untuk 42.605, -5.603 dan u4pruydqqvj untuk 57.64911, 10.40744.
const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"; // no a, i, l, o
export interface Bounds { latMin: number; latMax: number; lngMin: number; lngMax: number }
// Bits alternate longitude, latitude, longitude ... starting with longitude.
export function encode(lat: number, lng: number, precision = 7): string {
let latLo = -90, latHi = 90, lngLo = -180, lngHi = 180;
let hash = "", bits = 0, ch = 0, evenBit = true;
while (hash.length < precision) {
if (evenBit) {
const mid = (lngLo + lngHi) / 2;
if (lng >= mid) { ch = (ch << 1) | 1; lngLo = mid; } else { ch <<= 1; lngHi = mid; }
} else {
const mid = (latLo + latHi) / 2;
if (lat >= mid) { ch = (ch << 1) | 1; latLo = mid; } else { ch <<= 1; latHi = mid; }
}
evenBit = !evenBit;
if (++bits === 5) { hash += BASE32[ch]; bits = 0; ch = 0; }
}
return hash;
}
export function bounds(hash: string): Bounds {
let latLo = -90, latHi = 90, lngLo = -180, lngHi = 180, evenBit = true;
for (const c of hash) {
const idx = BASE32.indexOf(c);
if (idx === -1) throw new RangeError("invalid geohash character: " + c);
for (let mask = 16; mask > 0; mask >>= 1) {
const bit = (idx & mask) !== 0;
if (evenBit) { const mid = (lngLo + lngHi) / 2; if (bit) lngLo = mid; else lngHi = mid; }
else { const mid = (latLo + latHi) / 2; if (bit) latLo = mid; else latHi = mid; }
evenBit = !evenBit;
}
}
return { latMin: latLo, latMax: latHi, lngMin: lngLo, lngMax: lngHi };
}
// The 8 surrounding cells: step one cell height/width from the centre and re-encode.
// Longitude wraps at 180; latitude is clamped, so polar cells have fewer neighbours.
export function neighbours(hash: string): string[] {
const b = bounds(hash);
const h = b.latMax - b.latMin, w = b.lngMax - b.lngMin;
const lat = (b.latMin + b.latMax) / 2, lng = (b.lngMin + b.lngMax) / 2;
const out = new Set<string>();
for (const dLat of [-1, 0, 1]) {
for (const dLng of [-1, 0, 1]) {
if (dLat === 0 && dLng === 0) continue;
const nLat = lat + dLat * h;
if (nLat < -90 || nLat > 90) continue;
const nLng = ((((lng + dLng * w + 180) % 360) + 360) % 360) - 180;
out.add(encode(nLat, nLng, hash.length));
}
}
return [...out];
}
// Cells to scan for "within radiusM of here": the centre cell plus its 8 neighbours,
// valid only while radiusM is no larger than one cell edge. Then filter by true distance.
export function searchCells(lat: number, lng: number, precision: number): string[] {
const centre = encode(lat, lng, precision);
return [centre, ...neighbours(centre)];
}Precision hanyalah panjang string, dan setiap karakter tambahan memperkecil sel. Ukuran di bawah diturunkan dari jumlah bit, bukan dikutip: 360 dan 180 derajat dibagi dua pangkat jumlah bit, dikali sekitar 111,32 km per derajat. Hasilnya sesuai dengan kolom error di Wikipedia, yang mencantumkan setengah lebar, misalnya 0,61 km pada panjang 6.
Each base32 character carries 5 bits. Bits alternate longitude, latitude, longitude...
so odd lengths give longitude one extra bit.
precision lat bits lng bits cell height cell width at the equator
4 10 10 19.6 km 39.1 km
5 12 13 4.89 km 4.89 km
6 15 15 611 m 1.22 km
7 17 18 153 m 153 m
8 20 20 19 m 38 m
Derivation for precision 6:
height = 180 deg / 2^15 = 0.00549 deg x 111.32 km per deg = 0.611 km
width = 360 deg / 2^15 = 0.01099 deg x 111.32 km per deg = 1.223 km
width shrinks with cos(latitude): at Jakarta (-6.2 deg) 1.223 x 0.9942 = 1.216 kmDua sifat penting. Sel berbentuk persegi panjang, lebih lebar daripada tinggi pada panjang genap, dan menyempit ke arah kutub karena satu derajat longitude mengecil mengikuti cosinus latitude. Lalu prefix yang sama berarti sel induk yang sama, dan itulah yang membuat btree biasa atau query prefix LIKE bisa berfungsi sebagai spatial index.
Prefix yang sama membuktikan dua titik dekat, tetapi titik yang dekat belum tentu berprefix sama. Wikipedia mencatat bahwa titik di dua sisi ekuator, meridian Greenwich, atau meridian 180 bisa punya prefix yang sedikit atau sama sekali tidak sama. Dua titik di bawah berjarak sekitar 14 meter, tetapi karakter pertamanya sudah berbeda.
import { encode, neighbours } from "./geohash";
// Two drivers about 14 m apart (0.0002 deg of longitude at 51.5 N), either side of the
// Greenwich meridian. Same street corner, no shared prefix at all:
encode(51.5, -0.0001, 6); // "gcpuzz"
encode(51.5, 0.0001, 6); // "u10hbp"
// A prefix match only finds points in the SAME cell. The fix is to ask for the cell
// the passenger is in plus its 8 neighbours:
neighbours("qqguxm"); // ["qqguxh","qqguxk","qqguxs","qqguxj","qqguxt","qqguxn","qqguxq","qqguxw"]Perbaikan standarnya adalah mencari sel penumpang sendiri ditambah delapan sel tetangganya, lalu membuang yang di luar radius sebenarnya. Ini hanya benar jika radius tidak lebih besar dari sisi sel yang lebih pendek, karena setiap hasil pasti berada di sel tengah atau sel yang bersebelahan. Jadi pilih precision terpanjang yang sisi terpendeknya masih menutupi radius: 2 km butuh precision 5 dengan 4,89 km, sedangkan 500 m cukup dengan precision 6 yang 611 m.
-- Geohash in a plain btree column: 9 equality probes, then an exact distance filter.
-- Precondition: the radius is no larger than the smaller cell edge, or 9 cells miss points.
CREATE INDEX driver_positions_gh6_idx ON driver_positions (geohash6);
SELECT driver_id
FROM driver_positions
WHERE geohash6 = ANY ($1) -- the centre cell plus its 8 neighbours
AND haversine_km(lat, lng, $2, $3) <= 0.5; -- the cell is a coarse filter, not the answerPencarian tetangga di encoder sengaja dibuat sederhana: geser satu tinggi atau lebar sel dari titik tengah lalu encode ulang, dengan longitude yang wrap dan latitude yang di-clamp. Library produksi memakai lookup table demi kecepatan, tetapi versi ini mudah diverifikasi terhadap bounds hasil decode.
Simpan geohash sebagai kolom teks pendek pada satu precision tetap dan beri index btree biasa. Sembilan probe equality lebih baik daripada prefix scan, dan kolomnya tetap berguna jika Anda pindah database.
Quadtree membagi ruang menjadi empat kuadran, tetapi hanya di tempat yang padat. Menurut Wikipedia, setiap sel punya kapasitas maksimum dan terbelah saat kapasitas tercapai, sehingga pusat kota yang padat mendapat sel dalam yang kecil, sementara laut kosong tetap satu leaf besar. Geohash memotong grid yang sama di mana-mana, grid quadtree mengikuti data. Sketsa di bawah memakai kapasitas 4, angka dalam pseudocode Wikipedia, dan memangkas seluruh subtree yang kotaknya tidak menyentuh query.
interface Point { id: string; lat: number; lng: number }
interface Box { latMin: number; latMax: number; lngMin: number; lngMax: number }
const CAPACITY = 4; // a leaf splits into 4 children when the 5th point arrives
const overlaps = (a: Box, b: Box) =>
a.latMin <= b.latMax && a.latMax >= b.latMin && a.lngMin <= b.lngMax && a.lngMax >= b.lngMin;
const contains = (b: Box, p: Point) =>
p.lat >= b.latMin && p.lat <= b.latMax && p.lng >= b.lngMin && p.lng <= b.lngMax;
export class QuadTree {
private points: Point[] = [];
private children: QuadTree[] | null = null;
private box: Box;
private depth: number;
constructor(box: Box, depth = 0) {
this.box = box;
this.depth = depth;
}
insert(p: Point): boolean {
if (!contains(this.box, p)) return false;
if (!this.children) {
// depth cap: many points on one spot would otherwise split forever
if (this.points.length < CAPACITY || this.depth >= 20) { this.points.push(p); return true; }
this.split();
}
return this.children!.some((c) => c.insert(p));
}
query(range: Box, found: Point[] = []): Point[] {
if (!overlaps(this.box, range)) return found; // prune a whole subtree
for (const p of this.points) if (contains(range, p)) found.push(p);
this.children?.forEach((c) => c.query(range, found));
return found;
}
private split(): void {
const { latMin, latMax, lngMin, lngMax } = this.box;
const latMid = (latMin + latMax) / 2, lngMid = (lngMin + lngMax) / 2;
this.children = [
{ latMin, latMax: latMid, lngMin, lngMax: lngMid },
{ latMin, latMax: latMid, lngMin: lngMid, lngMax },
{ latMin: latMid, latMax, lngMin, lngMax: lngMid },
{ latMin: latMid, latMax, lngMin: lngMid, lngMax },
].map((b) => new QuadTree(b, this.depth + 1));
const old = this.points;
this.points = [];
for (const p of old) this.children.some((c) => c.insert(p));
}
}Konsekuensinya, quadtree adalah struktur data yang Anda simpan di memori, bukan kunci yang bisa disimpan di kolom database. Tidak ada masalah boundary karena query menelusuri setiap kotak yang tumpang tindih, tetapi memindahkan titik berarti delete dan insert, dan tree perlu diseimbangkan saat kepadatan bergeser. Cocok untuk satu proses yang memegang posisi live, seperti game server atau worker dispatch, kurang cocok untuk web tier yang stateless.
Untuk kebanyakan produk, ya. PostGIS memberi tipe geography yang diukur dalam meter, GiST index, dan ST_DWithin, yang menurut dokumentasi menyertakan perbandingan bounding box yang memakai index yang tersedia. Anda menulis satu predikat SQL, bukan memelihara sel, tetangga, dan precision sendiri, dan datanya tetap berdampingan dengan model relasional lain, yang biasanya bentuk backend ERP atau POS.
CREATE EXTENSION IF NOT EXISTS postgis;
CREATE TABLE driver_positions (
driver_id bigint PRIMARY KEY,
location geography(Point, 4326) NOT NULL, -- 4326 = WGS 84 longitude/latitude
updated_at timestamptz NOT NULL DEFAULT now()
);
CREATE INDEX driver_positions_location_gix
ON driver_positions USING GIST (location);
-- Drivers within 2 km of a passenger in central Jakarta, seen in the last 30 seconds.
-- ST_DWithin takes metres for geography and uses the GiST index; note longitude FIRST.
SELECT d.driver_id,
ST_Distance(d.location, p.pt) AS metres
FROM driver_positions d,
(SELECT ST_SetSRID(ST_MakePoint(106.8456, -6.2088), 4326)::geography AS pt) p
WHERE ST_DWithin(d.location, p.pt, 2000)
AND d.updated_at > now() - interval '30 seconds'
ORDER BY metres
LIMIT 10;
-- Wrong: ST_Distance(d.location, p.pt) < 2000 in the WHERE clause cannot use the index.Dua detail penyebab sebagian besar masalah. Koordinat longitude dulu, jadi ST_MakePoint(106.8456, -6.2088) adalah Jakarta, dan menukarnya menaruh Anda di Samudra Selatan. Lalu radius harus dilempar ke ST_DWithin sebagai filter, bukan dihitung di klausa WHERE, kalau tidak index terlewati. Untuk geography, jarak dalam meter dan secara default diukur pada spheroid; dokumentasi menyebut use_spheroid false mengukur pada bola demi evaluasi yang lebih cepat.
Jangan memakai kolom geohash di Postgres kecuali ada alasan yang tidak bisa dipenuhi PostGIS. Idenya sama dengan lebih banyak kode yang harus Anda pelihara, dan query sembilan sel di atas adalah bagian yang sering salah secara halus.
ST_Distance(a, b) kurang dari 2000 di klausa WHERE benar tetapi tidak memakai index. Taruh radius di dalam ST_DWithin, dan pakai ST_Distance hanya di SELECT dan ORDER BY untuk sedikit baris yang lolos.
Pakai Redis saat datanya panas, cukup kecil untuk RAM, dan terus ditulis ulang, seperti posisi terakhir tiap driver online. GEOADD menyimpan member di sorted set, dan GEOSEARCH, tersedia sejak Redis 6.2.0, mengqueri dari koordinat atau member yang ada berdasarkan radius atau box, dengan urutan ASC, COUNT, dan WITHDIST. Ia menggantikan perintah GEORADIUS yang sudah deprecated.
# Longitude first, then latitude. The member is whatever you want back.
GEOADD drivers 106.8456 -6.2088 driver:42
GEOADD drivers 106.8301 -6.1754 driver:77
# Nearest 10 within 2 km, closest first, with the distance. Needs Redis 6.2 or later.
GEOSEARCH drivers FROMLONLAT 106.8456 -6.2088 BYRADIUS 2 km ASC COUNT 10 WITHDIST
# GEOADD stores a sorted set whose score is a 52-bit geohash, so ordinary sorted-set
# commands work on it. Redis has no per-member TTL, so keep a last-seen set to expire drivers:
ZADD drivers:seen 1791619200 driver:42
ZRANGEBYSCORE drivers:seen -inf 1791619170 # not seen in 30 s: candidates to remove
ZREM drivers driver:42Ketahui apa yang ada di baliknya. Score-nya adalah geohash 52 bit, jadi masalah boundary ada secara internal, itulah sebabnya kompleksitas yang didokumentasikan sebanding dengan item di bounding box selaras grid di sekitar bentuk, bukan hanya yang ada di dalamnya. Area sangat besar dengan COUNT kecil tetap bisa lambat. Tidak ada expiry per member, sehingga driver yang offline tetap di set sampai Anda menghapusnya, dan sorted set pendamping berisi waktu last-seen adalah cara paling sederhana.
Index tempat itu lebih banyak dibaca; index driver didominasi tulis, dan itu membalik keputusan. Ambil 100.000 driver online yang ping tiap 4 detik. Itu 25.000 write posisi per detik, lebih dari dua miliar per hari, dan masing-masing menjadi versi baris baru di Postgres sekaligus menulis ulang entri GiST, karena dokumentasi PostgreSQL menyatakan heap-only update hanya mungkin jika tidak ada kolom ter-index yang berubah.
Assumed inputs (a design exercise, not a measurement):
online drivers = 100,000
position ping interval = 4 seconds
driver speed = 10 m/s (36 km/h)
Position updates
100,000 / 4 = 25,000 updates per second
25,000 x 86,400 = 2,160,000,000 updates per day
Postgres: every UPDATE writes a new row version, and because the indexed location
column changes it cannot be a heap-only (HOT) update, so the GiST entry is rewritten too.
= 25,000 row versions and 25,000 index updates per second, for ever
How often does a driver actually change geohash cell (precision 6, straight-line bound)?
north-south: 611 m / 10 m/s = 61 s per cell
east-west: 1,216 m / 10 m/s = 122 s per cell
100,000 x (1/61 + 1/122) = 2,459 cell changes per second, at most
vs 25,000 position updates = about 10x fewer index-relevant writes
Snapshot instead of every ping (live position in Redis, history in Postgres every 30 s)
100,000 / 30 = 3,333 Postgres writes per secondAda dua tuas. Pertama, yang dipedulikan index adalah selnya, bukan posisinya: pada 10 m/s driver melintasi sel precision 6 paling cepat tiap 61 detik arah utara-selatan, sehingga perpindahan sel maksimal sekitar 2.459 per detik, sekitar sepuluh kali lebih sedikit dari ping. Kedua, pisahkan penyimpanan: simpan posisi live di Redis dan tulis snapshot ke Postgres tiap 30 detik, yaitu 3.333 write per detik, bukan 25.000.
Saring juga berdasarkan kesegaran. Posisi yang lebih tua dari 30 detik berarti driver masuk terowongan atau menutup aplikasi, dan menampilkannya lebih buruk daripada tidak menampilkan siapa pun. Apa pun penyimpanannya, query harus membawa kondisi updated_at, atau job pembersih harus membuang member yang basi.
S2 dan H3 adalah kerabat dewasa geohash. S2 merepresentasikan data pada bola tiga dimensi sehingga menghindari sambungan proyeksi peta datar, dan H3, dikembangkan di Uber, membagi dunia menjadi sel heksagonal. Heksagon penting karena setiap tetangga berjarak sama, yang menghilangkan kasus sudut pada persegi, tetapi keduanya adalah library yang Anda tambahkan ke service, bukan fitur yang sudah ada di database. Perbandingan di bawah adalah cara saya memilih.
| Pendekatan | Letak index | Titik bergerak | Pilih saat |
|---|---|---|---|
| Geohash | Kolom teks dengan btree, atau kunci itu sendiri | Murah, titik hanya berganti kunci saat melintasi sel | Butuh kunci portabel, cache key, atau sharding per area |
| Quadtree | Tree di memori dalam satu proses | Delete dan insert, plus penyeimbangan ulang | Satu worker memegang posisi live dan kepadatan sangat tidak merata |
| S2 atau H3 | Kolom cell id yang dihitung library | Sama seperti geohash, cell id berubah saat melintas | Butuh tetangga seragam atau analitik lintas banyak kota |
| PostGIS dengan GiST | GiST index di disk, diquery dengan ST_DWithin | Setiap gerakan menulis ulang versi baris dan entri index | Default untuk tempat dan armada yang tidak terlalu besar |
| Redis GEOSEARCH | Sorted set di RAM dengan score geohash 52 bit | Overwrite cepat dengan GEOADD, tetapi member basi harus dibuang | Posisi live yang ditulis ulang tiap beberapa detik |
Jalankan checklist ini sebelum memilih, berurutan, dan berhenti di jawaban ya pertama:
Kecenderungan saya mulai dengan PostGIS, menambah Redis hanya ketika write rate terukur menjadi masalah, dan tidak menulis quadtree sendiri sebelum keduanya gagal. Hitungan di atas adalah ujinya: jika 25.000 write per detik bukan angka Anda, Anda tidak butuh penyimpanan kedua.
Pencarian terdekat adalah soal desain kunci. Ubah kedekatan dua dimensi menjadi sesuatu yang bisa di-seek index, ingat bahwa sel adalah filter kasar, bukan jawaban, cari tetangga selain sel tengah, dan biarkan write rate titik bergerak, bukan keanggunan struktur data, yang menentukan di mana posisi live disimpan.
Sumber dan bacaan lanjutan