--- title: 'Uzamsal Dizinler' source: 'https://academia.sh/tr/kurslar/bellek-ici-depolar/uzamsal-dizinler' course: 'Bellek İçi Depolar ve Önbellek Sistemleri' language: tr updated: '2026-08-17T18:08:58+00:00' license: 'CC BY-SA 4.0' --- # Uzamsal Dizinler Yakınlık sorgusunun bellek içi bir yapıyla kurulması: aynı sorgunun düz tarama, hücre kovası ve uzamsal anahtarlı sıralı kümeyle çözülmesi, üç yapının tuttuğu ek baytın ve sorgu başına taradığı aday sayısının ölçülmesi, tanenin sorgu anında seçilebilmesinin neye mal olduğunun sayılması. Akışın kimliği sıralanabilir olduğu için "şu andan sonrası" sorusu bir arama değil, bir konum belirlemesiydi. Kütüphanenin bir sorusu daha var ve o sorunun doğal bir sıralaması yok: okur, durduğu noktanın bir kilometre çevresindeki ödünç ve iade noktalarını istiyor. İki boyutlu bir konumu tek bir eksende sıralamanın her yolu bazı komşuları birbirinden uzağa düşürür; ne sıralı küme ne de akış bu soruya doğrudan yanıt verir. Çözüm düzlemi hücrelere bölmek ve her noktaya bir **uzamsal anahtar** yazmaktır. Hücre boyunun nasıl seçileceği bu dersin konusu değildir; o karar Vaka Çalışmaları kursunun Veri Yoğun Sistemler konusunda, Konum Tabanlı Servis vakasında ölçülmüş ve verilmiştir. Burada tane bir **girdi**dir ve sorulan şey başkadır: aynı yakınlık sorgusu bellek içi bir depoda hangi yapıyla kurulur, o yapı kaç bayt fazladan tutar ve karşılığında kaç adayı elemekten kurtarır. ## Uzamsal Anahtar Anahtar iki koordinatın bitlerinin sırayla dizilmesiyle üretilir: her eksen on altı bite niceleniyor, bitler dönüşümlü olarak yerleştiriliyor ve ortaya otuz iki bitlik tek bir sayı çıkıyor. Bu düzenin tek işe yarar özelliği şudur: bir hücrenin bütün noktaları anahtarın **baştaki bitlerini** paylaşır, dolayısıyla hücre sıralı bir dizide **bitişik bir aralıktır**. Kaç bitin paylaşıldığı taneyi belirler — ilk on iki bit 1 km'lik hücreyi, ilk on altı bit 0,25 km'lik hücreyi verir. | Kod | Varsayım | Değer | Gerekçe | |---|---|---|---| | BY18 | ödünç ve iade noktası | 120.000 | şube, iade kutusu, okul ve istasyon noktaları | | BY19 | bölge | 64 × 64 km | tek büyükşehir; düzlem yaklaşımı bir model basitleştirmesidir | | BY20 | temel kayıt | 20 bayt | konum çifti 16 bayt, nokta kimliği 4 bayt | | BY21 | sorgu yarıçapı | 1 km ve 0,25 km | yürüme mesafesi ve bina çevresi | BY21 bu dersin karar verdiren varsayımıdır: tek bir yarıçap olsaydı üç yapıdan ikisi ayırt edilemezdi. ## Üç Yapı Düzenek aynı 120.000 noktayı üç ayrı yapıya koyar ve aynı 300 sorguyu hepsine sorar. Bayt sayıları tamponların kendi boyundan, karma tabloların maliyeti ise kodda görünen bir formülden okunur. ```js // uzamsal.mjs — ayni yakinlik sorgusu uc bellek ici yapiyla: duz tarama, hucre kovasi ve // uzamsal anahtarli sirali kume. Bayt sayilari tamponlardan ve acik bir formulden okunur. // Bolge 64x64 km'lik bir duzlem olarak modellenir; noktalar kumelenmis, tohum gorunur. const N = 120_000, KENAR = 64, SORGU = 300, TOHUM = 20260731, KUME = 24; let d = TOHUM; const rast = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; }; const merkez = Array.from({ length: KUME }, () => [rast() * KENAR, rast() * KENAR]); const nokta = () => { // %35 duzgun, %65 kume cevresinde if (rast() < 0.35) return [rast() * KENAR, rast() * KENAR]; const [mx, my] = merkez[Math.floor(rast() * KUME)]; const a = rast() * 2 * Math.PI, r = -Math.log(1 - rast()) * 2.5; return [Math.min(KENAR - 1e-9, Math.max(0, mx + r * Math.cos(a))), Math.min(KENAR - 1e-9, Math.max(0, my + r * Math.sin(a)))]; }; const nx = new Float64Array(N), ny = new Float64Array(N), nid = new Int32Array(N); for (let i = 0; i < N; i += 1) { const [x, y] = nokta(); nx[i] = x; ny[i] = y; nid[i] = 100000 + i; } const TEMEL = nx.byteLength + ny.byteLength + nid.byteLength; const yay = (v) => { v = (v | (v << 8)) & 0x00ff00ff; v = (v | (v << 4)) & 0x0f0f0f0f; v = (v | (v << 2)) & 0x33333333; v = (v | (v << 1)) & 0x55555555; return v >>> 0; }; const nicele = (u) => Math.min(65535, Math.floor((u / KENAR) * 65536)); const anahtar = (x, y) => ((yay(nicele(y)) << 1) | yay(nicele(x))) >>> 0; // 32 bit uzamsal anahtar const p2 = (n) => { let k = 1; while (k < n) k *= 2; return k; }; const ua = new Uint32Array(N), us = new Int32Array(N); // sirali kume: anahtar + uye kimligi for (let i = 0; i < N; i += 1) { ua[i] = anahtar(nx[i], ny[i]); us[i] = i; } us.sort((a, b) => ua[a] - ua[b]); const sa = new Uint32Array(N); for (let i = 0; i < N; i += 1) sa[i] = ua[us[i]]; const SK_TABLO = p2(2 * N) * 8; // uye -> puan karma tablosu, yuva 8 bayt const SK = sa.byteLength + us.byteLength + SK_TABLO; const BIT = 6, KAYMA = 2 * (16 - BIT); // 2^6 = 64 hucre/eksen, hucre 1 km const kovalar = new Map(); for (let i = 0; i < N; i += 1) { const h = Math.floor(ua[i] / 2 ** KAYMA); if (kovalar.has(h)) kovalar.get(h).push(i); else kovalar.set(h, [i]); } const dolu = kovalar.size; const KOVA = p2(2 * dolu) * 12 + dolu * 8 + N * 4; // yuva 12 + dizi ustverisi 8 + uye 4 const sorgular = Array.from({ length: SORGU }, nokta); const tr = (x) => x.toLocaleString("tr-TR", { maximumFractionDigits: 2 }); const yakin = (q, i, R) => (nx[i] - q[0]) ** 2 + (ny[i] - q[1]) ** 2 <= R * R; const altSinir = (v) => { let l = 0, r = N; while (l < r) { const m = (l + r) >> 1; if (sa[m] < v) l = m + 1; else r = m; } return l; }; function calis(R, bit) { // sorgu kutusunu kaplayan hucreler const c = KENAR / 2 ** bit, k = Math.ceil(R / c), kayma = 2 * (16 - bit); let duzAday = 0, duzEs = 0, kovaAday = 0, kovaEs = 0, skAday = 0, skEs = 0, aralik = 0; for (const q of sorgular) { for (let i = 0; i < N; i += 1) { duzAday += 1; if (yakin(q, i, R)) duzEs += 1; } const cx = Math.floor(q[0] / c), cy = Math.floor(q[1] / c); for (let dy = -k; dy <= k; dy += 1) for (let dx = -k; dx <= k; dx += 1) { const x = cx + dx, y = cy + dy; if (x < 0 || y < 0 || x >= 2 ** bit || y >= 2 ** bit) continue; const h = ((yay(y) << 1) | yay(x)) >>> 0; if (bit === BIT) { // hucre kovasi yalniz kendi tanesini bilir for (const i of kovalar.get(h) ?? []) { kovaAday += 1; if (yakin(q, i, R)) kovaEs += 1; } } const alt = h * 2 ** kayma, ust = alt + 2 ** kayma; // sirali kumede bitisik aralik aralik += 1; for (let j = altSinir(alt); j < N && sa[j] < ust; j += 1) { skAday += 1; if (yakin(q, us[j], R)) skEs += 1; } } } return { duzAday: duzAday / SORGU, duzEs: duzEs / SORGU, kovaAday: kovaAday / SORGU, kovaEs: kovaEs / SORGU, skAday: skAday / SORGU, skEs: skEs / SORGU, aralik: aralik / SORGU, c }; } console.log(`model: ${tr(N)} nokta, ${KENAR}x${KENAR} km, ${KUME} kume, ${SORGU} sorgu, tohum ${TOHUM}`); console.log(`yogunluk ${tr(N / KENAR ** 2)} nokta/km2, dolu hucre ${tr(dolu)} (1 km tanesinde)\n`); console.log("yapi".padEnd(30) + "temel bayt".padStart(12) + "dizin eki".padStart(12) + "uye basina ek".padStart(15) + "toplam".padStart(12)); for (const [ad, ek] of [["duz tarama (dizi)", 0], ["hucre kovasi, 1 km tane", KOVA], ["uzamsal anahtarli sirali kume", SK]]) console.log(ad.padEnd(30) + tr(TEMEL).padStart(12) + tr(ek).padStart(12) + (ek / N).toFixed(2).padStart(15) + tr(TEMEL + ek).padStart(12)); console.log("\nsorgu basina taranan aday (ayni 300 sorgu, ayni yaricap)"); console.log("yaricap".padEnd(10) + "tane".padStart(9) + "hucre".padStart(7) + "duz".padStart(10) + "kova".padStart(9) + "s.kume".padStart(9) + "eslesme (duz/kova/s.kume)".padStart(27)); for (const [R, bit] of [[1, BIT], [0.25, BIT], [0.25, 8]]) { const s = calis(R, bit), k = bit === BIT; console.log(`${R} km`.padEnd(10) + `${KENAR / 2 ** bit} km`.padStart(9) + s.aralik.toFixed(0).padStart(7) + tr(s.duzAday).padStart(10) + (k ? tr(s.kovaAday) : "-").padStart(9) + tr(s.skAday).padStart(9) + `${s.duzEs.toFixed(2)} / ${k ? s.kovaEs.toFixed(2) : "-"} / ${s.skEs.toFixed(2)}`.padStart(27)); } ``` ``` model: 120.000 nokta, 64x64 km, 24 kume, 300 sorgu, tohum 20260731 yogunluk 29,3 nokta/km2, dolu hucre 4.096 (1 km tanesinde) yapi temel bayt dizin eki uye basina ek toplam duz tarama (dizi) 2.400.000 0 0.00 2.400.000 hucre kovasi, 1 km tane 2.400.000 611.072 5.09 3.011.072 uzamsal anahtarli sirali kume 2.400.000 3.057.152 25.48 5.457.152 sorgu basina taranan aday (ayni 300 sorgu, ayni yaricap) yaricap tane hucre duz kova s.kume eslesme (duz/kova/s.kume) 1 km 1 km 9 120.000 821,22 821,22 372.25 / 372.25 / 372.25 0.25 km 1 km 9 120.000 821,22 821,22 40.90 / 40.90 / 40.90 0.25 km 0.25 km 9 120.000 - 97,39 40.90 / - / 40.90 ``` Bu sayılar **ölçüm** sınıfındadır; aday ve eşleşme sayıları tohuma ve kümelenme parametrelerine bağlı, bayt sayıları bağlı değil — onlar tampon boylarıdır. Son sütun her satırda üç yapının aynı eşleşmeyi bulduğunu söylüyor: 1 km'de 372,25, 0,25 km'de 40,90. Dizin bir yaklaşıklık değil, bir **ön eleme**dir; kesin uzaklık her adayda ayrıca hesaplanır ve hiçbir yapı bir sonucu kaçırmaz. ## Ek Baytın Karşılığı Üç yapı da aynı 2.400.000 baytlık temel kaydı taşıyor; fark **dizin eki** sütunundadır. Hücre kovası üye başına 5,09 bayt ekliyor ve sorgu başına taranan adayı 120.000'den 821,22'ye indiriyor — yüz kırk altı kat. Bu, dersteki en ucuz kazanç: 611.072 bayt karşılığında sorgu maliyetinin yüzde 99,3'ü gidiyor. Sıralı küme aynı sorguda hiçbir şey kazandırmıyor. Üye başına 25,48 bayt, yani hücre kovasının beş katı yer tutuyor ve 1 km sorgusunda tastamam aynı 821,22 adayı tarıyor. Bu satır tek başına okunursa sıralı küme kötü bir seçimdir. Ek baytın nereye gittiği de sayılabilir: 3.057.152 baytın 2.097.152'si, yani yüzde 68,6'sı, üye kimliğinden anahtara giden karma tablodur. Bu tablo sorgu için değil **güncelleme** için tutulur. Gezici kütüphane durağı yer değiştirdiğinde üyenin sıralı dizideki eski yerini bulmak gerekir; tablo olmadan bu, dizinin taranması demektir. Noktalar hiç kımıldamasaydı sıralı kümenin eki üye başına 25,48 bayttan 8 bayta inerdi — o durumda hücre kovasından yalnız üç bayt pahalı olurdu. ## Tane Sorgu Anında Seçilirse Farkı ikinci ve üçüncü satır gösteriyor. Okur bina çevresini, yani 0,25 km'yi sorduğunda hücre kovası hâlâ 821,22 aday tarıyor: kovalar ekleme anında 1 km'lik taneye göre kurulmuştur ve daha ince bir soru sorulduğunda kova yine dokuz kilometrekarelik alanı döndürür. Daha ince bir tane istemek, bütün kovaların yeniden kurulması demektir. Sıralı kümede anahtar otuz iki bitin tamamını taşıdığı için **her önek uzunluğu geçerli bir aralıktır**. Aynı 0,25 km sorgusu ilk on altı biti kullanarak sorulduğunda taranan aday 97,39'a iniyor: sekiz kat az iş ve aynı 40,90 eşleşme. Sıralı kümenin satın aldığı şey adaydan tasarruf değil, **taneyi ekleme anında değil sorgu anında seçebilme** yeteneğidir. Bu, üç yapıyı bir karar tablosuna oturtur. Düz tarama sıfır ek bayt tutar ve her sorguda yüz yirmi bin kayda dokunur; nokta sayısı birkaç bini geçmiyorsa doğru seçimdir. Hücre kovası sorgu yarıçapı sabitse en ucuz dizindir ve 5,09 baytla adayın yüzde 99,3'ünü eler. Uzamsal anahtarlı sıralı küme, yarıçap sorgudan sorguya değiştiğinde ya da noktalar yer değiştirdiğinde 25,48 baytı hak eder; sabit yarıçaplı ve durağan bir kümede o bayt boşa gider. ## Özet - Uzamsal anahtar iki koordinatın bitlerini dönüşümlü dizerek tek bir sıralanabilir sayı üretir; bir hücre böylece sıralı dizide bitişik bir aralık olur ve önek uzunluğu taneyi belirler. - Üç yapı da aynı sonucu döndürür: 1 km'de 372,25, 0,25 km'de 40,90 eşleşme. Dizin bir yaklaşıklık değil ön elemedir ve kesin uzaklık her adayda ayrıca hesaplanır. - Hücre kovası dersin en ucuz kazancıdır: üye başına 5,09 bayt karşılığında taranan aday 120.000'den 821,22'ye iner, yani sorgu maliyetinin yüzde 99,3'ü gider. - Sıralı küme üye başına 25,48 bayt ister ve kendi tanesindeki sorguda hiçbir aday kazandırmaz; bu baytın yüzde 68,6'sı sorgu için değil, üyenin yerini güncelleyebilmek için tutulan karma tablodur. - Fazladan baytın karşılığı yarıçap değiştiğinde görünür: 0,25 km sorgusunda hücre kovası 821,22, sıralı küme 97,39 aday tarar, çünkü tane ekleme anında değil sorgu anında seçilir. ## Sonraki Adım Yakınlık sorgusu bir liste döndürüyor ve iş orada bitmiyor. Okur listeden bir noktayı seçtiğinde kütüphane şunları yapmak zorunda: o noktadaki kopya sayısını okumak, okurun açık ödünç sınırını denetlemek, kopya sayısını bir azaltmak, ödünç kümesine kaydı eklemek ve etkinlik akışına giriş yazmak. Buraya kadarki her yapı bu adımlardan **birini** atomik yapabiliyor; beşini birden yapabilen bir şey görülmedi. Adımlar tek tek gönderildiğinde araya başka bir okurun aynı kopyayı alması sığar. Sonraki ders bu çok adımlı işi iki biçimde kurar ve aradaki farkı gidiş sayısı, yarış penceresi ve engellenen süre olarak sayar.